实现快速数字褶积的数论变换

南京大学数学系

利用数论概念的变换已发展成快而无误的计算有限数字褶积的方法,变换是定义在有限域和整数环上实现以一整数为模的算术。它表明在一定条件下给出的结果和常规的数字褶积是一样的,因为有这些特征由于在定义中考虑到振幅和时间的数字化,这种变换是比较理想的适合数字计算的。当模数选择为费玛数的时候变换结果只要求NlogN个加法和字的移位但无乘法的数量级运算。除了效率高外没有舍入误差也不需要存放基函数。由于字长对于序列长度给予的限制以及溢出问题在文章中给出了克服的方法。给出了在IBM370/155上实现的结果并和快速傅立叶变换进行了比较,这一变换在效果和精度方面都表明是有实质性改进的,也给出基本数论变换的变形。