Author Topic: FFT window function calculation detail  (Read 5337 times)

0 Members and 1 Guest are viewing this topic.

Offline electr_peterTopic starter

  • Supporter
  • ****
  • Posts: 1443
  • Country: lt
FFT window function calculation detail
« on: November 22, 2022, 12:28:01 am »
I have a question w.r.t. FFT and window function usage. Calculation details of triangle window function values is not 100% clear.
Let's say we want to use triangle window on sampled data - which weighting option is correct? See simple examples with only 5 and 6 data points.

With sample size of 5 weights could be:
  • a) start at zero, end with non-zero (0, 0.5, 1, 1, 0.5)
  • b) start at zero, end with zero (0, 0.5, 1, 0.5, 0)
  • c) start at non-zero, end with non-zero (0.33, 0.67, 1, 0.67, 0.33)
With sample size of 6 weights could be:
  • a) start at zero, end with non zero (0, 0.33, 0.67, 1, 0.67, 0.33)
  • b) start at zero, end with zero (0, 0.5, 1, 1, 0.5, 0)
  • c) start at non-zero, end with non-zero (0.33, 0.67, 1, 1, 0.67, 0.33)


Should flat top peak (in some cases) reach 1 or be below 1? EDIT: irrelevant, scaling takes care of this afterwards. Area under filter is normalized to 1 with scaling.

Which definition is correct? Same question go for other window functions. IMO option a)"zero - non-zero" makes the most sense as it is "periodic" (full period with no repeating points).

One negative thing is that zeros at the start/end make you lose information about 1 or 2 raw samples when using inverse FFT on windowed data.
« Last Edit: December 11, 2022, 11:08:37 pm by electr_peter »
 

Online radar_macgyver

  • Frequent Contributor
  • **
  • Posts: 748
  • Country: us
Re: FFT window function calculation detail
« Reply #1 on: November 22, 2022, 04:48:06 am »
A window function, by definition, must be symmetric and must have the end values equal to zero. According to that definition, the only one that matches is the 'zero-zero' definition. If followed strictly, this means that the popular Hamming window is not a true window function, since it will allow the samples at either end of the input to the DFT to be unequal, resulting in discontinuities in the circular convolution process inherent to the DFT. It's a good enough compromise that everyone uses it anyway.
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 15799
  • Country: fr
Re: FFT window function calculation detail
« Reply #2 on: November 22, 2022, 04:57:10 am »
Yes it should be symmetric.

Now of course since the window is discrete, the least samples you have and the more 1 sample matters. Obvious. So depending on the actual resolution of your FFT anyway and the number of samples, either of your 6 versions may get you pretty similar results. For just a few samples, not so much.
 

Offline electr_peterTopic starter

  • Supporter
  • ****
  • Posts: 1443
  • Country: lt
Re: FFT window function calculation detail
« Reply #3 on: November 22, 2022, 08:04:31 am »
Thanks for input. I am asking because I saw different implementations of window functions in various math packages. With higher sample size it makes little difference, but I would like to have it implemented properly.

General window filter implementation could be:
  • pick a window function, which is symmetric and has 0 at both ends
  • define discrete weights such that 1st and last sample have zero weights.
  • intermediate samples have weights of windows function above them (see graph below)
In case of triangle window and even number of sample points, middle sample weights have flat top and do not reach exactly 1.


With sample size of 5 weights are (0.0, 0.5, 1.0, 0.5, 0.0)
With sample size of 6 weights are (0.0, 0.4, 0.8, 0.8, 0.4, 0.0)

EDIT: I came to conclusion that logic above is not entirely correct. Zero - non-zero fashion is best option, see msg4537295
« Last Edit: November 22, 2022, 09:49:17 pm by electr_peter »
 

Offline electr_peterTopic starter

  • Supporter
  • ****
  • Posts: 1443
  • Country: lt
Re: FFT window function calculation detail
« Reply #4 on: November 22, 2022, 11:12:00 am »
Window function gateway Matlab allows both window versions for most filter with opt parameter. "Symmetric" has zero on both ends, "periodic" has zero on one end.
https://www.tutorialspoint.com/execute_matlab_online.php
Code: [Select]
hanning(6, "symmetric")
hanning(6, "periodic")

hanning(5, "symmetric")
hanning(5, "periodic")

Still not sure which is better after looking through DFT definitions. Difference is only +/- 1 sample, but that is not insignificant.
Considering that windowed function is viewed as repeating function from DFT perspective, case can be made for both zero - nonzero & zero - zero type windows.
If window is [0, 0.5, 1, 0.5], then repetition is [0, 0.5, 1, 0.5, 0, 0.5, 1, 0.5, 0, 0.5, 1, 0.5, ...]
If window is [0, 0.5, 1, 0.5, 0], then repetition is [0, 0.5, 1, 0.5, 0, 0, 0.5, 1, 0.5, 0, 0, 0.5, 1, 0.5, ...]
Both are period, but case with zero-zero leaves additional 0 in the sequence (a flat spot).

Is there a good calculator online for window weights/FFT that I can cross reference windowed FFT results?
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 15799
  • Country: fr
Re: FFT window function calculation detail
« Reply #5 on: November 22, 2022, 07:46:32 pm »
Well you sure can't get a perfect triangle with an even number of samples, so it gets you a trapezoid. It's unfortunate that the FFT requires a 2^n number of samples, thus, an even number. Welcome to the world of numerical computation. I would favor the trapezoid version with 0 at both ends.
 

Online Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7194
  • Country: fi
    • My home page and email address
Re: FFT window function calculation detail
« Reply #6 on: November 22, 2022, 07:54:24 pm »
It's unfortunate that the FFT requires a 2^n number of samples, thus, an even number.
What? No.  O(N log N) time complexity FFTs are known for all integer N, including prime N.  There is no need to limit to N = 2n, except possibly if you are relying on a particularly dumb way to calculate the FFT.

For example, FFTW supports all integer sizes.  To ensure you get the fastest way of computing an FFT of a particular size, gather wisdom, i.e. let the library do some extra work on the first invocation to check which ways work fastest, and it will use that for FFTs of that size later on.  That knowledge, wisdom, is saved in a per-user configuration file.
 
The following users thanked this post: newbrain

Offline electr_peterTopic starter

  • Supporter
  • ****
  • Posts: 1443
  • Country: lt
Re: FFT window function calculation detail
« Reply #7 on: November 22, 2022, 09:44:04 pm »
After reading definitions in different sources I came to conclusion that window for N samples is constructed in zero - non-zero fashion. That is, window weight 0 is zero, 1 to N-1 are non zero. Weight N would be zero again, but that is N+1 sample (counting from 0) and is not used. Final zero is implied from next window period, as shown in graph.
 

Offline newbrain

  • Super Contributor
  • ***
  • Posts: 1801
  • Country: se
Re: FFT window function calculation detail
« Reply #8 on: November 23, 2022, 03:19:00 pm »
A window function, by definition, must be symmetric and must have the end values equal to zero.
Citation needed. Off the top of my head: rectangular and Hamming windows.
Nandemo wa shiranai wa yo, shitteru koto dake.
 

Online Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7194
  • Country: fi
    • My home page and email address
Re: FFT window function calculation detail
« Reply #9 on: November 23, 2022, 09:35:58 pm »
Window width is defined as the width of the nonzero samples in the window.  Adding zeros outside the window does not make it wider.

In other words, window coefficients 0.333, 0.667, 1, 0.667, 0.333 and 0, 0.333, 0.667, 1, 0.667, 0.333, 0 are the exact same window function, and both have width 5.

The definition of a triangular window for discrete Fourier transform is \$w_n = 1 - \left\lvert \frac{2 n - N}{L} \right\rvert\$.
With \$L=N\$, \$n = 1 \dots N-1\$, and you get a window of width \$N-1\$.  It has a single peak iff \$N\$ is even, double if \$N\$ is odd.
With \$L=N+1\$, \$n = 0 \dots N-1\$, and you get a window of width \$N\$.  It has a single peak iff \$N\$ is odd, double if \$N\$ is even.
With \$L=N+2\$, \$n = 0 \dots N\$, and you get a window of width \$N+1\$.  It has a single peak iff \$N\$ is even, double if \$N\$ is odd.
For very large \$N\$, their Fourier transforms and their effect on any signal converge.  You only see differences with small enough \$N\$.

For a triangle window with width 5, I'd use 0.333, 0.667, 1.000, 0.667, 0.333.

(Thing is, with small \$N\$, I would not want to rely on the approximation on what a specific geometric window filter shape has on the Fourier transformed data: I'd want to examine the coefficients effect on the windowed signal directly.)
 

Offline electr_peterTopic starter

  • Supporter
  • ****
  • Posts: 1443
  • Country: lt
Re: FFT window function calculation detail
« Reply #10 on: November 23, 2022, 10:06:16 pm »
Window width is defined as the width of the nonzero samples in the window.  Adding zeros outside the window does not make it wider.
I think it does. I consider that for sampled data of \$N\$ points filter should have \$N\$ points and DFT algorithm calculates from \$N\$ real points to get \$N\$ complex points as a result. All additional zeros (or extra zero padding) increase total number of points to \$>N\$ for DFT input. DFT results are sensitive to every data point, including zeros.

I base this on Spectrum and spectral density estimation by the Discrete Fourier transform (DFT), including a comprehensive list of window functions and some new at-top windows , page 11-13, (17) (18) formulas and figure 5.
\$w_j = \frac{1}{2} [ 1 - cos (\frac{2 \pi * j}{N})], j = 0, \dots, N-1\$ notation is used for \$N\$ points, automatically giving zero as first window value and non-zero for last window value (in example case of Hanning window). \$N\$ is assumed to be even, but for window definition that is irrelevant.
« Last Edit: November 23, 2022, 10:19:19 pm by electr_peter »
 

Offline jasonRF

  • Regular Contributor
  • *
  • Posts: 205
  • Country: us
Re: FFT window function calculation detail
« Reply #11 on: November 24, 2022, 12:20:25 am »
Window width is defined as the width of the nonzero samples in the window.  Adding zeros outside the window does not make it wider.
I think it does. I consider that for sampled data of \$N\$ points filter should have \$N\$ points and DFT algorithm calculates from \$N\$ real points to get \$N\$ complex points as a result. All additional zeros (or extra zero padding) increase total number of points to \$>N\$ for DFT input. DFT results are sensitive to every data point, including zeros.

I base this on Spectrum and spectral density estimation by the Discrete Fourier transform (DFT), including a comprehensive list of window functions and some new at-top windows , page 11-13, (17) (18) formulas and figure 5.
\$w_j = \frac{1}{2} [ 1 - cos (\frac{2 \pi * j}{N})], j = 0, \dots, N-1\$ notation is used for \$N\$ points, automatically giving zero as first window value and non-zero for last window value (in example case of Hanning window). \$N\$ is assumed to be even, but for window definition that is irrelevant.
Yes, starting with a signal of length \$N\$ and zero-padding so that it is now length \$M\$ (with \$M>N\$) leads to a spectrum with \$M\$ frequency bins.  But this is mathematically equivalent to doing the \$N\$-point FFT then interpolating the output onto the larger set of \$M\$ frequencies. 

And by the way, not all windows are zero at the end.  Look up the Hamming window, for example.

jason
 

Online Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7194
  • Country: fi
    • My home page and email address
Re: FFT window function calculation detail
« Reply #12 on: November 24, 2022, 12:42:28 am »
Window width is defined as the width of the nonzero samples in the window.  Adding zeros outside the window does not make it wider.
I think it does.
No, you're conflating "DFT width" and "window width".  The PDF you linked to, uses terms like "a window function to be used with DFT of length N".  That length refers to the DFT size, and not the window function size.

Discrete Fourier transform is defined as
$$Y_k = \sum_{n=0}^{N-1} s_n e^{-i 2 \pi k n / N} \tag{1}\label{1}$$
and windowed discrete Fourier transform is
$$Z_k = \sum_{n=0}^{N-1} w_n s_n e^{-i 2 \pi k n / N} \tag{2}\label{2}$$
By definition, zero \$w_n\$ contribute nothing to the sum.
It is important to realize that above, \$N\$ is the width of the DFT.
(It is possible to implement a DFT that incorporates the window function in its coefficients, at computational cost \$O(M \log N)\$, I believe, where \$M\$ is the number of nonzero values in \$w_n\$.)

(Also note that when generating spectrograms or power spectrums, the magnitude at bin \$k\$ is squared and then divided by the square of the sum of window function weights, \$(\sum w_n)^2\$, and the result multiplied by 2 because for real inputs, the FFT is symmetric, and we only consider the positive frequencies.  The width of the DFT, \$N\$, is not important, as it only determines the precision and range in frequencies.)

Like I wrote, triangle filters can be defined in at least three different ways.  For large \$N\$, they all converge to the same.
Even the linked PDF states on page 8, "This window function starts near or at zero, then increases to a maximum at the center of the time series and decreases again."

Because zero \$w_n\$ coefficients lose information about the original time-domain signal, you normally want the windowing function to be nonzero within the DFT window, and zero elsewhere; this maximizes the amount of information you can obtain from the time-domain signal.  The cases where you do use zeros are when you have a DFT implementation that restricts the DFT length, and want to use a smaller window; or when you want more precision in frequencies.
Also, window overlap is NOT calculated in terms of the DFT length (for example, half the DFT length), but in terms of the window function width.

The reason DFT of the same windowed signal varies as the DFT size varies, is because of two things: spectral leakage, and the center frequencies of the bins vary as a function of the DFT length.

As a practical example, consider window 0.2 0.4 0.6 0.8 1.0 0.8 0.6 0.4 0.2, and signal \$s_n\$ = 0.0872 0.9962 0.2588 -0.9063 -0.5736 0.7071 0.8192 -0.4226 -0.9659, via A=realFFT(0.0174 0.3985 0.1553 -0.7250 -0.5736 0.5657 0.4915 -0.1690 -0.1932), and B=realFFT(0.0174 0.3985 0.1553 -0.7250 -0.5736 0.5657 0.4915 -0.1690 -0.1932 0 0 0 0 0 0 0 0 0).

You'll find out that A[0] = B[0], and A[k] = B[2k].  In other words, by increasing the DFT length \$N\$ (by adding zeroes to the window function), you only increased the frequency resolution.  Using numpy.fft.rfft(),
Code: [Select]
n   Re B[n] Im B[n]  |B[n]|   Re C[n] Im C[n]  |C[n]|   Re A[n] Im A[n]  |A[n]|
0   -0.0036  0.0000  0.0036   -0.0036  0.0000  0.0036   -0.0036  0.0000  0.0036
1    0.0018  0.0165  0.0166    0.0073  0.0149  0.0166    0.0329  0.0826  0.0889
2    0.0329  0.0826  0.0889    0.0783  0.0421  0.0889    0.0196 -0.2755  0.2762
3    0.2152 -0.0192  0.2161    0.0910 -0.1960  0.2161   -0.0342  0.0839  0.0906
4    0.0196 -0.2755  0.2762   -0.2679 -0.0672  0.2762   -0.0078 -0.0069  0.0105
5   -0.2079 -0.0449  0.2127   -0.0081  0.2125  0.2127
6   -0.0342  0.0839  0.0906    0.0898 -0.0123  0.0906
7    0.0092  0.0060  0.0110   -0.0032 -0.0105  0.0110
8   -0.0078 -0.0069  0.0105    0.0050  0.0092  0.0105
9   -0.0192  0.0000  0.0192    0.0192  0.0000  0.0192
If you look at what happens if you shift the samples in B by moving some of the zeros to the front but keeping the FFT the same size –– above, C=DFT(0 0.0174 0.3985 0.1553 -0.7250 -0.5736 0.5657 0.4915 -0.1690 -0.1932 0 0 0 0 0 0 0 0) ––, you'll see that the magnitude of each bin stays the same, |A[0]| = |C[0]|, |A[k]| = |C[2k]|, but the phase in each bin in C is different, as expected.

Small changes in DFT length \$N\$ can be confusing, because spectral leakage affects only signals whose wavelength is not an exact multiple of \$N\$.  The signal that yielded a perfectly crisp peak at DFT length \$N\$ will be spread out in DFT length \$N+1\$ or \$N-1\$.
« Last Edit: November 24, 2022, 12:53:53 am by Nominal Animal »
 

Online radar_macgyver

  • Frequent Contributor
  • **
  • Posts: 748
  • Country: us
Re: FFT window function calculation detail
« Reply #13 on: November 24, 2022, 04:41:50 am »
A window function, by definition, must be symmetric and must have the end values equal to zero.
Citation needed. Off the top of my head: rectangular and Hamming windows.

OK I don't have one - my DSP texts are all at work. From all the references I could find online, the requirement is that window functions are zero-valued *outside* their length, which I realize is not the same thing.

For what it's worth, Matlab and Octave both return zeros for the first and last elements of a Bartlett window.
 

Offline newbrain

  • Super Contributor
  • ***
  • Posts: 1801
  • Country: se
Re: FFT window function calculation detail
« Reply #14 on: November 24, 2022, 08:31:27 am »
I'll give you one:
Quote from: Lyons - Understanding digital signal processing
Another common window function is the Hamming window shown in Figure 3-15(h). It’s much like the Hanning window, but it’s raised on a pedestal.
Nandemo wa shiranai wa yo, shitteru koto dake.
 

Offline gf

  • Super Contributor
  • ***
  • Posts: 1425
  • Country: de
Re: FFT window function calculation detail
« Reply #15 on: November 24, 2022, 08:37:05 am »
Small changes in DFT length \$N\$ can be confusing, because spectral leakage affects only signals whose wavelength is not an exact multiple of \$N\$.

It depends on the window function. Leakage is zero for those frequencies, where the frequency response of the spectrum analysis filter has zeros. And it is the window function, which determins the spectrum analysis filter which is shifted to and applied at each frequency bin. For a rectangular window, the spectrum analysis filter of each bin happens to have zeros at the frequencies of all other bins. A Hann window, for instance, does not have zeros at the two immediate neighbor bins, but otherwise still at all other bins, granted the "periodic" variant of the Hann window is used. And for other window functions, it is yet different.

Quote
The signal that yielded a perfectly crisp peak at DFT length \$N\$ will be spread out in DFT length \$N+1\$ or \$N-1\$.

One point of view is that frequencies spread out to other regions in the spectrum. Another point of view for leakage is that each bin's spectrum analysis filter has a particular frequency response, and all frequencies falling into the passband are accumulated by the bin. At the end the result is the same (i.e. a convolution in the frequency domain), but I find the latter more intuitive to understand, due to the analogy with a SA.
 

Offline electr_peterTopic starter

  • Supporter
  • ****
  • Posts: 1443
  • Country: lt
Re: FFT window function calculation detail
« Reply #16 on: November 24, 2022, 09:29:28 am »
I agree to points above from @Nominal Animal (scaling for power, symmetry, zero padding effect), also to a point in previous post about widening with zeros. I meant adding zeros to a window weights, not outside window. I get same results from your example and effect of zero padding on front or back is clear to me.

My interpretation of your example - for 9 sampled points, take a variant of triangle window weights with no zeros (so that no information is lost in such a small sample) and calculate FFT. For small \$N\$ triangular window weights with no-zeros probably is better (IMO it is a compromise in a desperate situation). For non-triangular window I would use first filter weight as zero.

My choice of triangular (Bartlett) window as the basic example is not the best as there are multiple definitions for discrete weights calculation. Hanning window function can used as a basis for discussion as it has only 1 formula that I am aware of.

In the same source linked above, section C, almost all of the windows have similar definitions for \$w_j, j = 0, \dots, N-1,\$ resulting in \$w_0 = 0\$. Also, weights are symmetric \$w_j = w_{N-j}\$. This is so called DFT-symmetry.

Part II. Harmonic analysis of finite-extent data and the DFT, pages 172-173 from
"On the Use of Windows for Harmonic Analysis With the Discrete Fourier Transform"
, discusses concept of DFT-even in more detail. It implies \$w_0 = 0\$ and \$w_{N-1} <> 0\$ with DFT symmetry \$w_j = w_{N-j}, w_0 = w_N\$

Window function (i.e. continuous) has zero at both ends, definitely (exluding Hamming and some others). Discrete weights for DFT should have zero weight on one end only.
« Last Edit: November 24, 2022, 09:40:08 am by electr_peter »
 

Offline gf

  • Super Contributor
  • ***
  • Posts: 1425
  • Country: de
Re: FFT window function calculation detail
« Reply #17 on: November 24, 2022, 11:54:25 am »
Yes it should be symmetric.

A symmetric FIR filter is linear-phase. Consequently, a symmetric window function results in a linear phase spectrum analysis filter.

Btw, searching the web, there also seem to exist use cases for asymmetric window functions.

Window function gateway Matlab allows both window versions for most filter with opt parameter. "Symmetric" has zero on both ends, "periodic" has zero on one end.
Still not sure which is better after looking through DFT definitions. Difference is only +/- 1 sample, but that is not insignificant.
Considering that windowed function is viewed as repeating function from DFT perspective, case can be made for both zero - nonzero & zero - zero type windows.

The "periodic" variant honors the circular/periodic nature of a DFT, assuming that the (N+1)th point is identical to the first point of the next period. Therefore the (N+1)th point is excluded, because the first point is already included. I.e. hanning(N,"periodic") is the same as hanning(N+1,"symmetric")(1:end-1). The same equality can be used to calculate periodic versions for some other window functions, where Matlab/Octave don't provide a symmetric/periodic option.
« Last Edit: November 24, 2022, 11:59:02 am by gf »
 

Online Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7194
  • Country: fi
    • My home page and email address
Re: FFT window function calculation detail
« Reply #18 on: November 24, 2022, 01:06:24 pm »
There is no Hanning window function!  There is Hann, and there is Hamming.  They are closely related, but different.
 

Online Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7194
  • Country: fi
    • My home page and email address
Re: FFT window function calculation detail
« Reply #19 on: November 24, 2022, 01:08:28 pm »
Small changes in DFT length \$N\$ can be confusing, because spectral leakage affects only signals whose wavelength is not an exact multiple of \$N\$.
It depends on the window function.
Yup, I agree (with your entire response).  I was only considering the window at hand.

Another point of view for leakage is that each bin's spectrum analysis filter has a particular frequency response, and all frequencies falling into the passband are accumulated by the bin.
I prefer this point of view myself.  For one, it leads to useful approaches when one is investigating single-frequency signals, and is looking for the frequency of the spectrum peaks at sub-bin precision.

(That discussion also often leads to variations of the sinc function, opening up another math avenue.)
« Last Edit: November 24, 2022, 01:10:12 pm by Nominal Animal »
 

Offline gf

  • Super Contributor
  • ***
  • Posts: 1425
  • Country: de
Re: FFT window function calculation detail
« Reply #20 on: November 24, 2022, 01:36:32 pm »
There is no Hanning window function!  There is Hann, and there is Hamming.  They are closely related, but different.

The name of the guy was indeed "Julius von Hann". Nevertheless I see "Hann" and "Hanning" being used as synonyms for each other almost everywhere. The matlab function is hanning(), too.
 

Online Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7194
  • Country: fi
    • My home page and email address
Re: FFT window function calculation detail
« Reply #21 on: November 24, 2022, 02:12:16 pm »
There is no Hanning window function!  There is Hann, and there is Hamming.  They are closely related, but different.
The name of the guy was indeed "Julius von Hann". Nevertheless I see "Hann" and "Hanning" being used as synonyms for each other almost everywhere. The matlab function is hanning(), too.
Well, people can call poop chocolate if they want, but it does not make it true.  (Anyway, I do believe Matlab/Octave have hann() and hamming(), too, so maybe hanning() is just an alias to help stupid people?)

I would actually prefer the functions have descriptive names instead of people names, but we humans aren't rational that way.

The reason the two are conflated is that both are examples of \$K=1\$ cosine sum window functions,
$$w_n = \sum_{k=0}^K (-1)^k a_k \cos\left(\frac{2 \pi k n}{N}\right), \quad 0 \le n \le N$$
i.e. both described using the same formula,
$$w_n = a_0 - (1 - a_0) \cos\left(\frac{2 \pi n}{N}\right), \quad 0 \le n \le N \tag{Both}\label{Both}$$
with \$a_0 = 0.5\$ being a Hann window, simplifying (via \$\cos(2 x) = 1 - 2 \sin^2(x)\$) to
$$w_n = \sin^2\left(\frac{\pi n}{N}\right), \quad 0 \le n \le N \tag{Hann}\label{Hann}$$
and \$a_0 = \frac{25}{46} \approx 0.54\$ being a Hamming window, simplifying to
$$w_n = \frac{25}{46} - \frac{21}{46}\cos\left(\frac{2 \pi n}{N}\right), \quad 0 \le n \le N \tag{Hamming}\label{Hamming}$$
« Last Edit: November 24, 2022, 02:31:16 pm by Nominal Animal »
 

Offline rhb

  • Super Contributor
  • ***
  • Posts: 3518
  • Country: us
Re: FFT window function calculation detail
« Reply #22 on: December 10, 2022, 01:51:37 am »
The windows in the left column of the initial post are correct.  As anything multiplied by zero is zero, any other implementation is naive.

An odd length window introduces a half sample phase delay in the output.  So forcing even length windows to be odd avoids that at the cost of not being the specified transfer function.  That may or may not matter.  Normally for a window function it doesn't matter.  I like Bartlett and Gaussian windows because of the frequency domain behavior.

In any case, one should always look at both the frequency and time domain impulse responses to verify you are getting the window you expect.  Doesn't matter if you wrote it or your employer paid >$100k for a seat.  Take a Reagan approach, "Trust, but verify."  Every time!

FWIW The assertion that there is an N log N solution for prime lengths is not correct.  In that case there are no periodicities and thus no escape from N**2.

It took me *years* to grasp the FFT properly because the explanations were so bad.  The concept is simple, add all the samples of the form  i*2*pi for all integer i  *before* multiplying rather than after.  That's all it is.  Or put differently, you can decompose an FFT by *any* factor, not just 2.  The DFT is sampled at (i/N)*2*Pi.  So for all values of i/N which are integers you can exchange the order of operation and rop lots of expensive multiplies.  But as should be clear, for N integer there are no integer values of i/N.

Unfortunately, there are a lot of very bad DSP codes floating around.  And minor differences in jargon and definitions just makes matters worse.

Have Fun!
Reg
 

Online Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7194
  • Country: fi
    • My home page and email address
Re: FFT window function calculation detail
« Reply #23 on: December 10, 2022, 07:41:16 am »
FWIW The assertion that there is an N log N solution for prime lengths is not correct.  In that case there are no periodicities and thus no escape from N**2.
Utter bullshit.  Just because Cooley-Tukey cannot do prime N, does not mean it cannot be done in general.

For examples of O(N log N) for prime N, look at Bluestein and Rader FFT algorithms.

For practical implementation you can trivially verify for yourself, just go take a look at the FFTW library.

It took me *years* to grasp the FFT properly because the explanations were so bad.
Are you sure you actually did?
 

Offline electr_peterTopic starter

  • Supporter
  • ****
  • Posts: 1443
  • Country: lt
Re: FFT window function calculation detail
« Reply #24 on: December 10, 2022, 11:19:37 am »
The windows in the left column of the initial post are correct.  As anything multiplied by zero is zero, any other implementation is naive.
I am going with this implementation (zero - non-zero fashion) described in left column. Filters based on functions, which have single peak in the middle, will have single peak with even \$N\$ and "flat top" with odd \$N\$. And almost all filters will have single zero as first weight (except raised cosine and other special cases), but non-zero as last weight.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf