Multiplierless discrete Fourier transform based on moments

Abstract

A novel algorithm to perform Discrete Fourier Transform（DFT） multiplierlessly was proposed.First, by modular mapping and truncating Taylor series expansion, the DFT was expressed in the form of the product of the constants and discrete moments.Second, by performing appropriate bit operations and shift operations in binary system, the product could be transformed to some additions of integers.The proposed algorithm only involved integer additions and shifts because the discrete moments could be computed only by integer additions.The systolic VLSI was designed to perform the new algorithm, followed by complexity analysis.Compared with the state-of-the-art systolic structure, the proposed design was multiplierless and easier to implement with less hardware and time.The approach was also applicable to other discrete transforms.

Keywords

• moments
• discrete Fourier transform
• multiplierless
• systolic VLSI