## Fft interpolation based on fft samples a detective story with a surprise ending – rick lyons q gases componen el aire

###########

The notion of FFT interpolation is straightforward to describe. That is, for example, given an N = 16 sample x( n) time-domain sequence shown in Figure 1(a), performing an N = 16 point FFT on x( n) produces the | X( m)| magnitude of samples shown by the red dots in Figure 1(b). electricity cost by state The blue dashed curve in Figure 1(b) is the magnitude of the discrete-time Fourier transform (DTFT) of x( n), what I like to call the "true spectrum" of x( n).

Knowing that my home-grown MATLAB code is about as reliable as the paper towel dispenser in the Men’s Room, I sked our DSP colleague Neil Robertson to implement Eq. (1) using my above x(n) sequence and a value of k = 4.4688. Neil graciously agreed and his MATLAB code produced the same incorrect XRef.[1](4.4688) = ‑1.1023 ‑j1.1053 that I obtained.

Equation (3) is a correct way to compute an interpolated X( k) value, but look at it carefully. Before continuing, do you see a way to reduce the number of arithmetic operations needed to compute a single X( k) value? Did you notice that neither the numerator nor the 1/ N factor inside the summation in Eq. (3) are functions of m? That fact allows us to move them both outside the summation giving us:

Equation (4) has a significantly reduced computational workload relative to that of Eq. (3) as we shall see. Don’t feel bad if you didn’t foresee those beneficial simplifications leading to Eq. (4). Neither did I—while writing this blog I found those slick algebraic moves in [3]. gas definition wikipedia So now, Eq. (4) is my preferred method for computing a single interpolated X( k) spectral value based on N FFT samples. Now that we have a workable Eq. (4), let’s briefly revisit the suspicious Eq. (1).

I presented an X( k) FFT interpolation equation published in the literature, Eq. (1), for computing a single X( k) spectral value based on N FFT samples, where frequency k is not an integer. Equation (1) is not valid and I showed why that is so. (I remain troubled by this and perhaps someone can prove me wrong.) Next I presented four different expressions, Eq. (2) through Eq. (5), for computing an X( m) sample and compared their computational costs. Finally I realized the most efficient method for computing a single X( m) sample is to simply perform an N‑point DFT using Eq. (6). I apologize for this blog being so lengthy. e gaskell I didn’t have the time to make it shorter.

Let’s say we applied a real-valued pure sinusoidal input sequence, padded with lots of zero-valued samples, whose frequency is very near Fs/4 Hz to the DFT. The spectral magnitude results show a positive-freq |sin(x)/x|-like envelope and a negative-freq |sin(x)/x|-like envelope. Those |sin(x)/x| envelopes are very symmetrical in that their lower and upper sidelobes are roughly mirror images of each other.

Next we apply a real-valued pure sinusoidal input sequence, padded with lots of zero-valued samples, whose frequency is very near zero (or Fs/2) Hz to the DFT. The spectral magnitude results show a positive-freq distorted |sin(x)/x|-like envelope and a negative-freq distorted |sin(x)/x|-like envelope. Those |sin(x)/x| envelopes are "distorted" in that they are not symmetrical. Their lower and upper sidelobes are no longer mirror images of each other. 2015 electricity increase I interpret that behavior to be caused by spectral leakage from the negative-freq spectral energy crossing the zero-Hz (or Fs/2-Hz) boundary and contaminating the positive-freq spectral components. Likewise I believe spectral

You already know this Scott, but what I’m sayin’ is: The true shape of the positive-frequency spectral magnitude envelope of a real-valued sinusoidal sequence depends on the frequency of that sinusoid. When the sinusoid’s frequency is near zero or Fs/2 Hz, the positive-freq magnitude envelope will NOT be a |sin(x)/x| curve. However, the larger the size of the DFT the more similar the spectral magnitude envelopes will be to a |sin(x)/x| curve.

Now, we know that the basic assumption in the DFT is that the signals f(n) and F(m) in both domains are periodic with period N (the length of the transform), that is THEY ARE NOT FINITE in extent and any attempt to process them MUST recognize that fact. Then applying Eq. (a) to a time domain signal that is derived from an IDFT must include all of the periodic extensions of the output. gas out game commercial A careful look at Eq. (a) will show that the contribution to the sum by the extensions decays slowly, and therefore we have to take many periodic extensions into account to come up with a reasonable approximation.

I won’t do it here, but using the properties of the DFT (or the FT) can lead to Eq. (1) as a spectral interpolator similar in form to my Eq. (a), and the same condition applies: any attempt to evaluate an interpolated spectral value must include all (or at least a large number) of periodic extensions of F(m) in the sum. A single period will just not hack it 🙂

To demonstrate this I wrote my own MATLAB code that took the same 16 length data that Rick used, took the FFT, and then concatenated many of the output buffers. I then used the summation over all buffers to estimate the same component (in the center of the record) corresponding to Rick’s example, and sure enough, the more buffers I included the closer my estimate came to the true value. Convergence was slow however, and it took about 80 concatenated buffers to come within 0.001 of the true value in the real and imaginary parts.