词条 | 数论变换 |
释义 | shulun bianhuan 数论变换(卷名:电子学与计算机) number-theoretic transform 在快速傅里叶变换(FFT)中,变换因子 ![]() ![]() ![]() ![]() 把一个给定的正整数M称为模(mod),如果用M去除任意两个整数α和β,所得余数相同,便称作α和β对模M同余,记作 因此,同余式运算规则是以正整数M为模的整数环(域上所定义的一种线性正交变换。 在式(1)中,整数a、N、M三者之间必须满足如下关系: 满足上式的最小正整数N叫做a对模M的指数,a是1的N次根,或简称a是N 阶的。例如,a为2时对模7的指数是3,对模11的指数是10。 在数论变换中要求找到合适的a、N和M值。所选择的N应当是高复合数。但如采用2的乘方,就能构成像FFT算法那样的信号流图,并且希望选取的N值足够大,以满足实际需要。其次,所选取的a应当能用简便的方法实现乘法运算,因为在计算机中乘法运算最花费时间;如果a是2的乘方,可以用移位操作实现a的乘方运算,因而比较方便。又由于是模运算,所以不存在舍入误差。此外,M最好也是位数不太多的二进制数,而且必须是大于2的素数。 麦森数论变换 在数论变换的一般公式 (1)中的模M采用麦森数时,就称为麦森数论变换。麦森数为 它是一奇数。令k=PQ,P为素数,便有 ![]() ① a=2,N=P,aN=2P呏1[mod(2P-1)],但P是素数,N=P也是素数,不是高复合数。 ② a=-2,N=2P,(-2) ![]() 费马数论变换 在数论变换中比较合理的模M是选用费马数,即 前几个Ft的值是F0=3;F1=5;F2=17;F3=257;F4=65537;这五个费马数都是素数,而F5和F6都是复合数: 因为是按模M=Ft费马数进行算术运算,所以长为N=2m的序数的费马数论变换及其反变换表达式可写成 ![]() ![]() 的最小正整数。 费马数论变换和傅里叶变换相类似。当N =2m时,数论变换的快速计算法的信号流图和 FFT的算法信号流图也是一致的,只是把WN换成a。但是,费马数论变换的基本函数是由2的方幂构成,不需要使用乘法,仅为移位操作,其运算速度快于 FFT算法。加上费马数论变换算法是模算术运算,不存在舍入误差,从而能得到高精度的褶积。此外,由于FFT的基本函数是三角函数,需要预先存储这些基本函数,而费马数论变换算法却不需要存储基本函数。费马数论变换的缺点主要是它没有物理意义,在信号处理中不能运用中间过程;运算需要的字长与变换点数之间存在着严格的关系,随着输入序列的增长往往需要很长的字长。 参考书目 何振亚著:《数字信号处理的理论与应用》,人民邮电出版社,北京,1983。 |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。