A new hardware efficient design for the one dimensional discrete Fourier transform

This paper presents a new hardware efficient design for the one-dimensional (1-D) discrete Fourier transform (DFT). By combining the advantages of Distributed Arithmetic (DA) computation and features of the cyclic convolution, we can efficiently realize the 1-D N-point DFT using small ROM modules and accumulators. To increase the ROM utilization, we first make all the N ROM modules identical and only share a ROM module in computing all the DFT outputs. Besides, we apply the ROM partition to further reduce the ROM cost with the overhead of slowing down the speeds. This hardware efficient feature is very useful in realizing the long length DFT with critical hardware requirement. Comparison results with the traditional DA-based designs show that the proposed design can reduce the ROM cost exponentially.