论文部分内容阅读
利用数论概念的变换已发展成快而无误的计算有限数字褶积的方法,变换是定义在有限域和整数环上实现以一整数为模的算术。它表明在一定条件下给出的结果和常规的数字褶积是一样的,因为有这些特征由于在定义中考虑到振幅和时间的数字化,这种变换是比较理想的适合数字计算的。当模数选择为费玛数的时候变换结果只要求NlogN个加法和字的移位但无乘法的数量级运算。除了效率高外没有舍入误差也不需要存放基函数。由于字长对于序列长度给予的限制以及溢出问题在文章中给出了克服的方法。给出了在IBM370/155上实现的结果并和快速傅立叶变换进行了比较,这一变换在效果和精度方面都表明是有实质性改进的,也给出基本数论变换的变形。
Transformation using the concept of number theory has evolved into a fast and error-free method of computing finite number convolution. Transformation is the definition of an integer modulo arithmetic over finite fields and integer rings. It shows that the results given under certain conditions are the same as the conventional digital convolution because these features are ideal for digital computation due to the digitization of amplitude and time in the definition. When the modulus is chosen to be a Fermat number, the result of the transformation requires only NlogN additions and word shifts without orders of magnitude in multiplication. In addition to high efficiency, there is no rounding error and no need to store basis functions. The method of overcoming is given in the article due to the limitation of word length on sequence length and overflow. The results achieved on the IBM 370/155 are presented and compared with the Fast Fourier Transform, which shows substantial improvements both in effect and in accuracy, as well as the variations of the basic number theory transformation.