Design of low-cost and high-throughput linear arrays for DFT computations:Algorithms, architectures, and implementations

Recursive algorithms for discrete Fourier transform (DFT) computation are p roposed, where the common entries of the decomposed matrices are factored o ut in order to reduce the number of multipliers during implementation. The derived algorithms are essentially band-matrix-vector multiplications with matrix bandwidth of 3 in the radix-a case and bandwidth of 7 in the radix-4 case, Low-cost architectures are derived using an efficient mapping techni que for the corresponding heterogeneous dependence graphs of the decomposed band matrices. Only log(2) N(3 log(4) N) adders and log(2) N - 1(log(4) N - 1) multipliers are needed to compute the DFT of size N using the proposed radix-2 (radix-4) linear array architectures, a great saving in hardware c ost compared to previous approaches. Due to the simplicity and regularity o f the architectures, it is possible to reduce the power consumption of the DFT processors by temporarily disabling the multiplier units at proper time steps. VLSI implementations of an g-point radix-2 DFT processor and a 64-p oint radix-4 DFT processor are also given.