Free Books
   Free Books    Mathematics of the DFT  

Fixed-Point FFTs and NFFTs

Recall (e.g., from Eq.$ \,$(6.1)) that the inverse DFT requires a division by $ N$ that the forward DFT does not. In fixed-point arithmetic (Appendix G), and when $ N$ is a power of 2, dividing by $ N$ may be carried out by right-shifting $ \log_2(N)$ places in the binary word. Fixed-point implementations of the inverse Fast Fourier Transforms (FFT) (Appendix A) typically right-shift one place after each Butterfly stage. However, superior overall numerical performance may be obtained by right-shifting after every other butterfly stage [8], which corresponds to dividing both the forward and inverse FFT by $ \sqrt{N}$ (i.e., $ \sqrt{N}$ is implemented by half as many right shifts as dividing by $ N$). Thus, in fixed-point, numerical performance can be improved, no extra work is required, and the normalization work (right-shifting) is spread equally between the forward and reverse transform, instead of concentrating all $ N$ right-shifts in the inverse transform. The NDFT is therefore quite attractive for fixed-point implementations.

Because signal amplitude can grow by a factor of 2 from one butterfly stage to the next, an extra guard bit is needed for each pair of subsequent NDFT butterfly stages. Also note that if the DFT length $ N=2^K$ is not a power of $ 4$, the number of right-shifts in the forward and reverse transform must differ by one (because $ K=\log_2(N)$ is odd instead of even).

Next Section:
The Discrete Cosine Transform (DCT)
Previous Section:
Radix 2 FFT