首页 理论教育数论变换:简单高效的数学处理方法

数论变换:简单高效的数学处理方法

【摘要】:与余弦变换基相比,数论变换没有舍入误差,不需要存储三角函数,在相同变换长度下,速度优于余弦变换。而且数论变换本身就是整型变换,无需进行提升就可得到可逆的变换。对比式和式可以看出,反数论变换基中的元素β=α-1,又α-1=αN-1,所以反数论变换基如下:实现构造数论变换MATLAB代码如下:实现构造数论变换MATLAB代码如下:4阶数论变换基函数图形如图4-5所示。图4-54 阶数论变换基函数图形图4-54 阶数论变换基函数图形

20世纪70年代初,Rader和Agarwal及Burrus等人提出了构造模M剩余类环ZM上的离散变换,即数论变换(Number Theoretic Transform),并把数论变换引入数字信号处理中。与余弦变换基相比,数论变换没有舍入误差,不需要存储三角函数,在相同变换长度下,速度优于余弦变换。而且数论变换本身就是整型变换,无需进行提升就可得到可逆的变换。

数论变换是在以正整数M为模的整数环ZM上定义的线形正交变换,所用运算法则是数论中同余运算,它在ZM上具有循环卷积特性,基本函数由整数的方幂构成。设xiZMi=0,1,…,N-1,如果作用在序列x0x1xN-1上的一种变换为

978-7-111-48233-8-Chapter04-43.jpg

有如下形式的逆变换:

978-7-111-48233-8-Chapter04-44.jpg

且具有循环卷积性质,则称式(4-35)为在ZM上长为N的数论变换,可表示成:

X≡T·x(mod M) (4-37)

式中,T是数论变换基,形式如下:

978-7-111-48233-8-Chapter04-45.jpg

式(4-37)中,x=[x0x1,…,xN-1]TxnZMn=0,1,…,N-1)且αZM。以上两式各元素选取的条件有:①M是质数;②N必须是M-1的因子;③α是模MN阶单位根,即αN=1(mod M),且αk≠1(mod M)(k=1,2,…,N-1)。

对比式(4-35)和式(4-36)可以看出,反数论变换基中的元素β=α-1,又α-1(mod M)=αN-1(mod M),所以反数论变换基如下:

978-7-111-48233-8-Chapter04-46.jpg

实现构造数论变换MATLAB代码如下:

978-7-111-48233-8-Chapter04-47.jpg

4阶数论变换(M=5,α=2)基函数图形如图4-5所示。

978-7-111-48233-8-Chapter04-48.jpg

图4-54 阶数论变换基函数图形