Algorithms and Parallel Computing

19.3 PIPELINE RADIX-2 DECIMATION-IN-TIME FFT PROCESSOR

Wold and Despain [121] proposed a pipeline FFT processor that is based on decimation-in-time FFT DG of Fig. 19.6. Their design is usually referred to as a radix-2 single-path delay feedback (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 (SR) 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-time FFT processor has been proposed by Despain [125]. The design is usually called a radix-4 single-path delay feedback (R4SDF) processor and is shown in Fig. 19.7 for a 64-point FFT. Other efficient designs are possible such as the ones given in References [126–128].

Figure 19.6 Cascade pipeline architecture for an eight-point decimation-in-time FFT algorithm using a R2SDF processor.

Figure 19.7 Cascade pipeline architecture for a 64-point FFT algorithm using an R4SDF processor. ...