Architectures for multiplierless fast Fourier transform hardware implementation in VLSI

This paper presents a novel processor for the implementation of multiplierless FFT´s in VLSI. The arithmetic scheme is specially tailored for the simple binary coefficients used for these FFT´s, which make multiplication trivial. (The class of coefficients dealt with are those that have a maximum of 2 nonzero digits; i.e., sum of 2 integers powers of 2 with each power in the range 0-4.) A single chip processing element for a 4-point DFT (for a radix 4 FFT) with an execution time of 400 ns using a 10 MHz clock has been realized. The chip has an estimated maximum gate count of 11 000 and pin count of 85. It has the capability of achieving a 40 MHz throughput rate for a 1024-point FFT using 20 processing IC´s. The use of the 4-point chip to implement higher radix algorithms and various other issues are discussed.