AlexOlson.com
Design & Implementation of a 512-point FFT using fixed-point arithmetic

In Spring 2006, I took a VLSI Communication Systems course at The University of Texas at Austin. For an individual project, I decided to design and implement (in synthesizable Verilog) a Fast Fourier Transform module using fixed-point arithmetic. I was expecially interested in observing how the quantization effects introduced by the use of fixed-point arithmetic affected the accuracy of the result, especially in the context of ADSL transceivers.

The 512-point FFT module was implemented using a radix-8 FFT. This choice of radix somewhat simplified the implementation as a radix-8 implementation only required 3 stages versus 9 stages for a radix-2 implementation. The choice of using radix-8 over radix-2 also reduced the number of cascaded multiplications, presumably leading to a more accurate result at the expense of additional computation. The implementation made use of the folding technique. The hardware contained only a single complex multiply-accumulate unit and required 12288 cycles to compute an entire FFT. Such an implementation seems suitable for ADSL systems, since ADSL transceivers need only perform on the order of 8000 FFTs/second. (The transmitter and receiver each require at least one FFT, perhaps more depending on implementation). Thus, this module could be used in an ADSL system if clocked to at least 50mhz or 100mhz.

Interestingly, the noise introduced from the use of fixed-point arithmetic was found to nearly match established theoretical predictions:

It was experimentally observed that each additional bit of precision (for calculations) yielded a 6dB increase in the QSNR (signal to quantization noise ratio). Furthermore, the use of rounding (as opposed to truncation) for the arithmetic also yielded a 6dB advantage in QSNR.