Iterative FFT

Overview

FFT algorithm is a very regular structure, which facilitates an efficient implementation. The computations of the iterative FFT are divided into stages. The number of stages is shown in Listing 1. Within each stage, data shuffling and the so-called butterfly computation and twiddle factor multiplications are performed. Usually, the butterfly operations are all identical and the twiddle factor multiplications and data shuffling follow some kind of pattern. Figure 1 shows the block diagram of an iterative DIF (Decimation in Frequency) FFT that supports from 4 to 4k FFT points.

Features

• Configurable for FFT sizes from 4 to 4096 FFT points.
• Supports radix-2 and 4
• Parameterized (radix, internal quantization, and FFT size)
• Decimation In Frequency (DIF) implementation
• The one eighth twiddle values are saved for lowest ROM requirements
• Used to compute both FFT and IFFT transforms
• Performs 4K point FFT in under 0.3 msec at 100 MHz

Applications

• 3GPP LTE
• WiMAX (IEEE Std 802.16d)
• Digital Video Broadcasting (DVB)
• xDSL
• Other communication systems

IP Deliverables

• Synthesizable Verilog
• System Model (Matlab)
• Verilog Test Benches
• Documentation

Download