基于矩的无乘法离散傅立叶变换

Multiplierless discrete Fourier transform based on moments

提出了一种无乘法实现离散傅立叶变换(DFT)的新算法:通过模运算和泰勒展开,把DFT的计算转化为离散矩和常系数乘积的形式;然后,通过在二进制系统中进行比特运算和移位运算,把浮点乘积转化为定点的整数加法。离散矩可由全加法实现,因此新算法只涉及整数加法和移位运算。此外,为该算法设计出脉动阵列VLSI结构,并和现有结构进行了对比分析。分析结果表明新结构不涉及乘法运算,节约了硬件资源,加快了运算速度。该方法也可以推广到其他离散变换的计算。

A novel algorithm to perform Discrete Fourier Transform （DFT） multiplierlessly was proposed. First, by modular mapping and tnmcating Taylor series expansion, the DbT 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 multipliedess and easier to implement with less hardware and time. The approach was also applicable to other discrete transforms.