数论变换是一种计算卷积的快速算法。计算卷积的快速算法中最常用的一种是使用快速傅里叶变换,然而快速傅里叶变换具有一些实现上的缺点,举例来说,资料向量必须乘上复数系数的矩阵加以处理,而且每个复数系数的实部和虚部是一个正弦及余弦函数,因此大部分的系数都是浮点数,也就是说,必须做复数而且是浮点数的运算,因此计算量会比较大,而且浮点数运算产生的误差会比较大。
而在数论变换中,资料向量需要乘上的矩阵是一个整数的矩阵,因此不需要作浮点数的乘法运算,更进一步,在模数为的情况下,只有种可能的加法与种可能的乘法,这可以使用内存把这些有限数目的加法和乘法存起来,利用查表法来计算,使得数论变换完全不须任何乘法与加法运算,不过需要较大的内存与消耗较大的存取内存量。
虽然使用数论变换可以降低计算卷积的复杂度,不过由于只进行整数的运算,所以只能用于对整数的信号计算卷积,而利用快速傅里叶变换可以对任何复数的信号计算卷积,这是降低运算复杂度所要付出的代价。
数论变换的变换式为
而数论变换的逆变换式为
注解:
(1) 是一个质数。
(2) 表示除以M的余数
(3) 必须是的因数。(当时和互质)
(4)是对模数之模反元素
(5)为模M的N阶单位根,即而且。若此时,我们称为模M的原根
举一个例子:
一个的点数论变换与逆变换如下,取,注意此时
正变换
逆变换
(1) 正交性质
数论变换矩阵的每个列是互相正交的,即
(2) 对称性
若,则的数论变换也会有的特性。
若,则的数论变换也会有的特性。
(3) 反数论变换可由正数论变换实现
,即的数论变换。
步骤一:把改写成,若,则
步骤二:求的数论变换。
步骤三:乘上。
(4) 线性性质
若,,(表互为数论变换对)则有。
(5) 平移性质
若,则,而且。
(6) 循环卷积性质
若,,则,而且。(代表圆形卷积。)
这个性质是数论变换可以用来作为卷积的快速算法的主要原因。
(7) 帕塞瓦尔定理(Parseval's Theorem)
若,则,而且
梅森质数是指形如的质数记做,其中是一个质数。
在梅森质数数论变换中,取,可以证明可以如下选取:
(1)
(2)
在这两种选取方式下,由于是2的幂次,所以只需移位运算,但不是2的幂次,所以基数-2的蝴蝶结构不适用于此例中,同时为质数或一个质数的两倍,并不是一个可以拆解成很多质因数乘积的数,因此也无法由互质因子算法得到太大的好处。梅森质数数论变换通常用于较短序列的卷积运算