Moments based fast fourier transform without multiplications
Zhenbing Liu, Guoyou Wang, Jianguo Liu · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2007
Discrete Fourier transform (DFT) is an important tool in digital signal processing. We have proposed an approach to performing DFT via linear sums of discrete moments. In this paper, based on the previous work, we present a new method of performing fast Fourier transform without multiplications by performing appropriate bit operations and shift operations in binary system, which can be implemented by integer additions of fixed points. The systolic implementation is a demonstration of the locality of dataflow in the algorithms and hence it implies an easy and potential hardware/VLSI realization. The approach is also applicable to DFT inverses.