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).