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

摘要

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