基于数论变换的小波快速算法及应用
摘 要：小波分析具有时域和频域局部化特性而成为一种有效的分析工具，以小波分析为工具对信号处理和图像处理是小波应用的热点之一。Mallat算法，它是基于多分辨率分析的金字塔算法是小波变换的快速算法。研究基于数论变换的小波快速算法以及应用。
关键词：快速数论变换 Mallat算法 信号处理
中图分类号：O241 文献标识码：A 文章编号：1007-3973（2012）012-091-02
1一维数论变换
由于在中，需要右移r-l位才成000n0n1……nl-1，即倒序得：m=n0n1……nl-10000（l=1，2，……r）。在式（5）中前面r个等式，每个等式都对应一组数据计算，每组数据都需要有 对结点，由于每对结点都需要1次乘和2次加法次数。所以每组数据都需要次乘法和N次加法，当N=2r时，完成组数据共需要次乘法运算和次加法运算。
2.2算法步骤
Step1 输入变换长度N，变换序列x（i），变换参数P，a，INV（正逆变换方向）；
Step2 判断参数是否满足an=1（modP）；
Step3 作递推循环L=1，2，……，PP；
Step4 若INV=0，则返回，得到正变换；
如果INV≠0，那么可求出NINV=N-（modP），最后对序列长度中的每个元素都乘NINV，从而可以得到逆变换。
2.3在小波Mallt中含有噪声的特性
在工程的应用中，有用信号通常表现为低频部分或是一些比较平稳的信号，而含有噪声信号通常表现为高频部分的信号，可通过以下几个步骤来实现一维信号的去噪：
（1）一维信号的小波分解。选择一个小波并确定一个小波分解的层次N次，然后对信号S进行N层分解；
（2）小波分解高频系数的阈值量化。从第1层依次到第N层的高频部分进行阈值处理；
（3）一维小波的重构。根据小波分解的第N层的低频系数和经过量化处理后的第1层到第N层的高频系数，进行一维信号的小波重构。
3改进的去噪算法
（1）对含有噪声信号进行数论变换，得到信号分解后的频谱；
（2）在实际信号中遇到的是一些非整型实数，所以需要先扩大变成整数，对信号进行快速数论变换，得到的结果在进行缩小；
（3）根据分解得到的频谱，对高频系数的阈值量化，对我们所需要的低频成分进行保留，对不需要的频谱进行阈值处理，消除噪声；
（4）对信号的频谱进行逆变换，得到降噪后的信号。
4实验与结论
4.1 Mallat算法及其滤波器实现
Mallat算法是建立在多分辨率滤波器组理论基础上的一种快速算法，我们得先确定滤波器。
输入一个含有噪声的信号 ，用数论变换进行改进，实验如图1、2所示。
4.2实验结果
可以看出图1为含有噪声的原信号，图2是利用NTT原信号重构与去噪后的信号的差，信号误差10-15数量级，可见基于NTT算法在此类信号分解与重构中有很好的效果。
参考文献：
[1] 孙琦，唐远炎，马洪，等.快速小波变换，循环卷积和数论变换[J].四川大学学报，1999（06）.
[2] 蒋增荣.数论变换[M].上海：上海科学技术出版社，1980.
[3] 孙琦，郑德勋，沈仲琦.快速数论变换[M].北京：科学出版社，1980.