矩形变换和数论变换

时间:2008-12-23

  卷积的快速实现和离散傅立叶变换(discrete Fourier traNSform,DFT)的计算都是信号和图像处理中经常遇到的问题。在实践中,这些操作通常都是用快速傅立叶变换(fast Fourier transform,FFT)算法实现的。NTT在某些场合要优于基于FFT的系统。此外也有可能采用矩形变换,像Walsh/Hadamard或算法傅立叶变换,来得到DFT或卷积的近似。

  1971年,Pollard[144]在有限群上定义了NTT。由于存在变换对:

  其中N×N-1≡1,α∈ZM(ZM={0,1,2,…M-1},ZM=Z/MZ)是序列N的一个元素,也就是在有限群(ZM,×)中,对于所有k∈(1,2,…,N-1)有aN≡1和αk≠1。

  对于给定的多元组(α,M,N),能够确保这样的变换对存在是非常重要的。很明显,α必须是N阶的模M。为了保证逆NTT(INTT)的存在,其他的条件是:

  (1)乘法的逆N-1模M必须存在,也就是说,方程x×N≡1modM必须有一个解x∈ZM

  (2)变换矩阵|A|=|[αkn]|的行列式必须是非零矩阵,这样矩阵才是可逆的,也就是说A-1存在。

  (3)如果α和M没有公共因子,或简写成gcd(α,M)=0,只能够得出乘法的逆存在。

  (4)对于第二种情况,要用到代数学中的事实:NTT矩阵是Vandermonde矩阵的一个特例(a[k]=akN),它满足下面的行列式:

  如果det(V)≠0,则需要a[K]≠a[l]≠l。实际上,由于需要计算的模M,就又产生了第二个约束条件。特别是在约束条件(也就是god(Πak-al,M)=1中,不能够有0因数。

  由此得出结论,要检验NTT的存在,必须要确认:

  对于Zp,当p为质数时,上面给出的所有条件均自动满足。在Zp中可以找到p-1阶的元素。但是变换长度p-1一般还要受到实际应用的限制,因为就“—般”乘法和模运算化简而言还是需要的,而且在二进制或QRNS算法中更适合采用“标准”FFT[1145,35]

  在环M=2b中没有有价值的变换。但使用邻近的2b±1还是可能的。如果使用的是质数,则条件1和3均自动满足。接下来要讨论什么样的质数2b±1是已知的。

  默希尼和费尔马(Mersenne和Fermat)数 法国数学家马丁·默希尼(Martin Mersenne1588-1648)首先研究了2b-1形式的质数,用几何级数表示为:

  可以看出,Mersenne质数的指数3也必须是质数,这是必要条件,但并不是充分条件,例如:211-1=23×89就不是质数。初的Mersenne质数2b-1的指数为:

  2b+1类型的质数来自Fermat初的理论。Fermat推测所有的2(2t)+1数都是质数,但是正像Mersenne质数一样,这是必要条件,但不是充分条件。因为如果b是奇数,也就是b=q2t,则有

  不是质数,就像(24+1)|(212+1),也就是17|4097。到目前为止己经知道了5个Format质数,分别是:

  但是欧拉(1707-1783)指出F5=232+1可以被641除尽。到F21为止还没有再出现Fermat质数,这就将NTT的可能质数中的Format质数减少到前5个。

  欢迎转载,信息来源维库电子市场网(www.dzsc.com


  
上一篇:3D忆阻器混合芯片面世 实现人工神经网络
下一篇:Flash驱动

免责声明: 凡注明来源本网的所有作品,均为本网合法拥有版权或有权使用的作品,欢迎转载,注明出处。非本网作品均来自互联网,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。

相关技术资料