Algorithms and Parallel Computing

19.5 PIPELINE RADIX-2 DECIMATION-IN-FREQUENCY FFT PROCESSOR

Wold and Despain [121] proposed a pipeline FFT processor that is based on the decimation-in-frequency FFT DG of Fig. 19.11. Their design is usually referred to as an R2SDF processor. The structure assumes that input data x(n) are available in word-serial format in natural order. This is why the processor at stage 2 delays the input sample by the four-word shift register buffer. For the first N/2 = 4 data words, the processor in stage 2 simply accepts the data words and moves them into the shift register buffer. After N/2 = 4 data samples have been shifted, the processor starts performing the butterfly operations on the input data and the data coming from the shift register buffer. The processor in stage 1 repeats the same actions for a period of N/4 = 2 delay and so on. A pipeline design for the radix-4 decimation-in-frequency FFT processor has been proposed by Despain [125]. The design is usually called an R4SDF processor and is shown in Fig. 19.7 for a 64-point FFT.

Figure 19.11 Cascade pipeline architecture for an eight-point decimation-in-frequency FFT algorithm using an R2SDF processor.