### Fixed-Point FFTs and NFFTs

Recall (*e.g.*, from Eq.(6.1)) that the inverse DFT requires a
division by that the forward DFT does not. In fixed-point
arithmetic (Appendix G), and when is a power of 2,
dividing by may be carried out by right-shifting
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 (*i.e.*, is implemented
by *half* as many right shifts as dividing by ). 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 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 is not a power of , the number of right-shifts in the forward and reverse transform must differ by one (because is odd instead of even).

**Next Section:**

The Discrete Cosine Transform (DCT)

**Previous Section:**

Radix 2 FFT