I am currently working on a application which requires an inverse Fourier transform (IFFT) and am using a function library provided by Texas Instruments, in the datasheet they give an example on how to use one of their IFFT functions (shown below).

My question is: whilst I understand the need to perform bit reversal either on the input (decimation in time for an FFT) or the output (decimation in frequency for an FFT), I can't understand what's happening in the code given in the example. No bit reversal is performed on the input or the outputs only on the twiddle factors, is there some maths I am missing? Maybe something to do with the why the code accesses individual twiddle factors?

ps. The code is original from page 4-34 of this document: http://www.ti.com/lit/ug/spru657c/spru657c.pdf

void main(void)
 gen_w_r2(w, N); // Generate coefficient table
 bit_rev(w, N>>1); // Bit−reverse coefficient table
 DSPF_sp_cfftr2_dit(x, w, N);
 // radix−2 DIT forward FFT
 // input in normal order, output in
 // order bit−reversed
 // coefficient table in bit−reversed
 // order
 DSPF_sp_icfftr2_dif(x, w, N);
 // Inverse radix 2 FFT
 // input in bit−reversed order,
 // order output in normal
 // coefficient table in bit−reversed
 // order
 divide(x, N); // scale inverse FFT output
 // result is the same as original
 // input

The answer to your question can be found just in reading the comments in the C code that you quoted. The process looks like this:

  1. The input vector x is passed through a function DSPF_sp_cfftr2_dit(), which is described as a radix-2 decimation-in-time forward FFT. It expects its input in normal order and writes its output in bit-reversed order. It expects its twiddle factors to be in bit-reversed order (which they are, as shown in the first two lines of the function).

  2. The forward FFT result is passed through another function DSPF_sp_icfftr2_dif(), which is described as a radix-2 decimation-in-frequency inverse FFT. It expects its input in bit-reversed order (which it is, as the input is the output of the forward FFT above, which was in bit-reversed order). It expects its twiddle factors to be in bit-reversed order (which they are). It writes its output in normal order.

So, what you have is an input vector x that starts in normal order and runs through an FFT/IFFT round trip, resulting in a vector that is also in normal order (and should be approximately identical to the original vector x).

  • $\begingroup$ Hi, thanks for the reply. Ok that's fine. Perhaps I should have put my question in a slightly different way: the forward FFT is expecting its twiddle factors to be bit reversed, is the usual for an FFT algorithm or is it it some quirk of this FFT function provided by TI? $\endgroup$ – bluefocs May 1 '14 at 13:55
  • $\begingroup$ The twiddle factors don't need to be in non-bit-reversed order if the output is in bit-reversed order and the input isn't. $\endgroup$ – hotpaw2 May 1 '14 at 14:19
  • $\begingroup$ It's simply a convention chosen by TI. I have seen it done both ways on other DSP libraries $\endgroup$ – Hilmar May 1 '14 at 15:04
  • 1
    $\begingroup$ @bluefocs: It behooves TI to write their DSP libraries so that they perform the fastest possible on their processors. If they have hardware that can easily handle bit-reversed addressing (which many of their DSPs do), then it's worth it to them to levy the requirement on the software developer to provide the twiddle factors in that ordering if it buys some extra performance. $\endgroup$ – Jason R May 1 '14 at 15:41

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.