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

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University