基于改进的快速Fermat数变换的卷积算法及其FPGA实现

A Convolution Algorithm Based on Modified Fast Fermat Number Transform and Its Implementation on FPGA

与离散傅里叶变换(DFT)相比,费尔马数论变换(FNT)用移位代替乘法,因此其运算速度更快,但是快速费尔马数变换算法(FFNT)的变换长度有限且与位宽成比例,而基于Good-Thomas映射的多维分解技术在增加变换长度的同时会使模运算中出现坏因子,伪费尔马变换虽能剔除坏因子却不便用FPGA实现FNT模运算。将艾森斯坦余数系统(ERNS)与多维映射结合,提出改进的FFNT算法(MFFNT),并在Virtex6 FPGA平台上实现了长复数序列的卷积。仿真结果表明,与基于FFT的卷积算法相比,基于MFFNT的卷积算法运算时间较短,乘法器资源消耗较少。

Substituting shift for multiplication,the Fermat Number Transform（FNT） is faster than the Discrete Fourier Transform（DFT）,but the length of Fast Fermat Number Transform（FFNT） is confined to bit width.Although the length of FFNT increases after applying the multi-dimensional decomposition based on Good-Thomas mapping,the bad factor exists in modular arithmetic.The Pseudo Fermat Number Transform（PFNT） can exclude the bad factor,but its implementation is complicated.A Modified Fast Fermat Number Transform（MFFNT） algorithm is proposed in this paper for the efficient circular convolution,which combines the Eisenstein Residue Number System and multi-dimensional mapping.In the end,ninety-six point complex number convolution based on MFFNT is realized on Virtex6 platform.The simulations demonstrate that the proposed algorithm can save much multiplier resource and needs less calculation time.