I am trying to find a way to shift the outputs of the FFT (any algorithm implementation, currently using radix-2) by half a bin with the same bandwidth. To put it another way, say you have a 512pt FFT sampling data for a bandwidth of 100 kHz. The frequency bins are going to fall ~390 Hz apart (bandwidth) For example 195 to 585 is effectively the band pass range for bin 2 which happens to fall at the center frequency of 390 Hz. Bin 3 is from 585 to 975 with Fc being 790 Hz. Say I want Fc to be 585 instead of 790. This represents a shift of all the FFT outputs by half a band.

I do not want to double the size of the FFT to get the result. I do not want to multiply the signal in time domain prior to FFT by an offset frequency as I don’t want to deal with extra products within bandwidth of the overall FFT.

Is there a way through modification of the twiddle factors to get the desired effect?

  • 2
    $\begingroup$ Multiplying by a time varying complex exponential in the time domain, to effect a shift in the frequency domain, is equivalent to modifying the twiddle factors, isn't it? Why the "I do not want to multiply the signal in time domain prior to FFT" restriction? It seems to me performing an FFT with nonstandard twiddle factors throws away a large body of well tested and optimized FFT implementations that you can leverage. $\endgroup$ – Andy Walls May 21 '18 at 13:46
  • 1
    $\begingroup$ Maybe I am doing something wrong because when I multiply I always get two signals, the desired one plus a mixing product. $\endgroup$ – Skybit May 21 '18 at 14:08
  • 2
    $\begingroup$ If you're using a complex exponential, you won't get a mixing product. However, the spectrum shift is cyclic: frequencies shifted past $F_s/2$ will wrap back around to $-F_s/2$. $\endgroup$ – Andy Walls May 21 '18 at 14:15

Well, if you're willing to perform multiplications in the time domain, you can cyclically shift the whole spectrum in the frequency domain using:

$$x'[n] = e^{j\pi \frac{f}{F_s/2}n} x[n]$$

Where $x[n]$ is your original input sequence, $F_s$ is your sample rate, and $f$ is the amount of frequency shift you desire.

The DFT of $x'[n]$ will have a spectrum that is cyclically shifted by $f$ Hertz, compared to the DFT of $x[n]$. And there will be no "extra products within the bandwidth of the overall FFT", if by that you meant mixing products, from say multiplying by a cosine to effect a shift.

I suppose you could merge that complex exponential factor into your twiddle factors of a custom FFT implementation, but I would advise against that. Page 19 of these notes shows how that merge would happen: http://eeweb.poly.edu/iselesni/EL713/zoom/dftprop.pdf if you are dead set on modifying the twiddle factors instead of a separate multiplication.

| improve this answer | |
  • $\begingroup$ That’s exactly what I am trying to communicate. Thanks. I must have been multiplying wrong. $\endgroup$ – Skybit May 21 '18 at 14:55
  • $\begingroup$ You can run into numerical problems with library implementations if you let the exponent of the exponential get too large. When it exceeds $2\pi$, just normalize it back down to be between $[-\pi, \pi]$ or $[0, 2\pi]$. $\endgroup$ – Andy Walls May 21 '18 at 15:50
  • $\begingroup$ @Hilmar suggests that the frequency-shifted FFT may be more efficient to implement. $\endgroup$ – Olli Niemitalo Jan 11 '19 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.