Modular pipeline fast Fourier transform algorithm

A modular pipeline architecture for computing discrete Fourier transforms (DFT) is demonstrated. For an N point DFT, two conventional pipeline √ N point fast Fourier transform (FFT) modules are joined by a specialized center element. The center element contains memories, multipliers and control logic. Compared with a standard N point pipeline FFT, the modular pipeline FFT reduces the number of delay lines required. Further, the coefficient memory is concentrated within the center element, reducing the storage requirements in each of the conventional FFT modules. The centralized memory and address generator provide the data storv age and reordering. The data throughput of a conventional pipeline architecture is maintained with a slightly higher end-to-end latency. The architecture and control logic for both a radix-2 and radix-4 modular pipeline FFT is explained and compared to the traditional pipeline FFT. Further, this methodology facilitates the hardware computation of long FFTs when compared to previous techniques. The new logic developed to control the FFT unit is similar in complexity to current systems and does not rely on any exotic components or hardware features. In fact, the control logic can be reduced to a single counter and a handful of combinational logic. Specifically, using the modular FFT algorithm reduces the overall complexity of the hardware pipeline, permits the use of reusable modules, and does not impact the throughput. The reduction in delay lines lowers the dynamic power consumption. The hardware architecture is particularly suited to reprogrammable and custom devices. Simulations are conducted to analyze the architecture. Experimental results for both radix-2 and radix-4 FFTs are presented and compared with the conventional pipeline FFT. A numerical analysis of the modular pipeline FFT is performed and compared to that of a conventional pipeline FFT.