基于ＤＳＰ的最优小波包基算法的实现
摘 要：小波包分析能够为信号提供一种更加精细的分析方法,它将频带进行多层次划分,对多分辨分析没有细分的高频部分进一步分解,并能够根据被分析信号的特征,自适应地选择相应频带,使之与信号频谱相匹配,从而提高时-频分辨率。为了能在DSP嵌入式设备中应用小波包分析方法进行信号处理，首先讨论小波包分解的过程和最优基及代价函数的选择方法，然后提出一种在DSP上实现香农熵代价函数的小波包分解算法的方法，并在浮点型DSP TMS320C6713B上实现了此算法。最后针对具体的数字信号进行小波包分解和最优基选择的实验，实验结果证明了该方法的正确性和高效性。
关键词：小波包；代价函数；最优基；DSP
中图分类号：TP274文献标识码：B
文章编号：1004-373X(2008)22-161-03
Implementation of Optimized Wavelet Packet Basis Algorithm Based on DSP
WANG Jingyan
(Shanghai Institute of Applied Physics,Chinese Academy of Sciences,Shanghai,201800,China)
Abstract：Wavelet packet analysis is a precies analytical method by which the frequency band is further divided into multiple layers and the high frequency is divided in a more deep-going way.On the basis of characters of the signal,it can select the frequency band so that it can match the signal frequency properly and improve the time frequency resolution.In order to apply wavelet packet analysis in signal processing on DSP embedded equipment,the process of wavelet packet decomposition and the method for choosing the best base and cost function are discussed.Wavelet packet decomposition whose cost function is Shannon entropy is then implemented on floating point DSP TMS320C6713B.Experiment of wavelet packet decomposition and best base choosing is made.Effectiveness of this method is verified by results of the experiment.
Keywords：wavelet packet;cost function;best base;DSP
在小波分析是一维及二维信号数据分析与处理的有力工具,其主要优点就是提供了时频局部分析与细化的能力［1］。它可以对信号进行有效的时频分解,但在高频频段其频率分辨率较差,而在低频频段其时间分辨率较差。
小波包分析能够为信号提供一种更加精细的分析方法,它将频带进行多层次划分,对多分辨分析没有细分的高频部分进一步划分,并能够根据被分析信号的特征,选择相应频带,使之与信号频谱相匹配,从而提高了时－频分辨率。
数字信号处理器(Digital Signal Processor，DSP) 以其适合信号处理的独特结构和快速的指令周期，而应用于各种实时信号处理的场合。将小波包分析与DSP 相结合用于实时信号处理
必将产生巨大的实用价值。
1 最优基小波包分解
1.1 小波包理论
小波变换的分辨率在时-频平面中随频率不同而变化,子带的频率越高,其频率分辨变换没有对高频子带进行再分解,不利于对高频子带的数据压缩。由小波变换发展而来的小波包技术弥补了这个缺点,它可根据信号本身的特点在一定范围内任意选择分辨率,有利于数据的高效压缩［1］。
对于给定的正交尺度函数Φ(x)及对应的小波函数Ψ(x)，设μ0(x)=Φ(x)，μ1(x)=Ψ(x)，由下面的递推公式定义正交小波包：
μ2n(x)=2∑khkμn(2x－k)
μ2n+1(x)=2∑kgkμn(2x－k)
图1是三级小波包分解树的示意图,左子节点是父节点的低频逼近子图,右子节点是父节点的高频细节子图,(0,0)节点表示待分解的原始信号。
1.2 最优小波包基的选取
根据上面的定义可知，小波库中有很多小波包基，而不同的小波包基一般具有不同的时频局部化能力，反映不同的信号特性，因此，对于一个给定的信号，希望选择一个较好的小波包基，用来表达信号的特点。为了选择一个较好的小波包基，首先给定一个序列的代价函数，然后在所有的小波包基中寻找使代价函数最小的基。对于一个给定向量，代价最小就是最有效的表示，此基便称为最佳基［2］。
图1 三级小波包分解树示意图
在一个正交小波包基下，可以把信号f(t)展开，使得f(t)与一个小波包系数序列x = {xk}对应。在序列{xk}上定义一个信息代价函数M，它满足如下2个条件：
（1） 可加性条件，即：
M({xk})=∑k∈ZM(xk),M(0)=0
（2） 信息代价函数M的取值应反映系数的集中程度。
对于一个给定的信息代价函数M，L2(R)的小波包基B 称为信号f(t)相对于代价函数M 的最优基，如果在L2(R)的所有小波包基中，f(t)在小波包基B下对应的小波包系数序列具有最小的信息代价函数值。
采用工程上常用的基于Shannon信息熵的代价函数，即定义序列x = {xk}的熵为：
M(x)=－∑jPjlog Pj
式中Pj=|xj|2‖x‖2，且当P=0时，Plog P=0。
由于信息是半可加的，所以引入可加函数：
λ(x)=－∑k|xk|2log|xk|2
则M(x)可以表示为：
M(x)=‖x‖2λ(x)+lg‖x‖2
这样，当λ(x)最小时， M(x)也最小。
有了上面的信息代价函数，就可以求出使信息代价函数最小的小波包序列，从而求出最优基。当基库是一个二叉树时，可以采用自底向顶的快速搜索法选择最优小波包基。
1.3 最优基快速搜索算法
有了信息代价函数之后，采用自底向顶的快速搜索算法来寻找最优基，所谓最优基就是在小波库的所有小波包基中使代价函数最小的基。
下面给出此种快速搜索算法［3］。
第一步：根据上面介绍的代价函数计算出分解图中各个结点的信息代价,并把相应的信息代价的数字写在树的结点里。
第二步：从最低层的所有结点开始标记，将它们的信息代价作为一个初始值。称上层结点为父结点，下层结点为子结点。若父结点的信息代价比子结点低,那么就标记父结点， 否则不标记。如此上推，直到顶层。
第三步： 然后检查所有结点,取最上层所标记的结点。当高层有结点被标记时， 其相应子结点的标记应删除。最后将最优基中的系数抽取出来，以一定的顺序输出。下面就给出最优基树图(见图2)。
图2 最优基树图
2 最优基小波包分解的DSP实现
2.1 浮点型DSP TMS320C6713B
本文选择TI公司的TMS320C6000 系列的TMS320C6713B (以下简称C6713B) 芯片作为算法硬件平台。
TMS320C6000 系列DSP 是美国TI 公司的新一代高性能的数字信号处理芯片，具有很高的工作频率和极强的并行处理能力。片内有A，B两组共8个并行处理单元，每组内分为L，M，D，S 四个单元，每组处理单元结合同侧的寄存器组和数据通道，构成一个完整的数据处理单元。
本文采用以6713B芯片为中心的TDS6713EVM开发板，此开发板是闻亭公司最新研制的高速语音信号（采集）处理平台，可作为专用语音信号编解码处理测试平台，也可用于各种对数据精度有特殊要求的浮点数字信号处理场合［4］。TDS6713EVM系统结构图如图3所示。
图3 TDS6713EVM系统结构图
选择CCS 2 ('C6000)作为DSP软件开发环境。
2.2 小波包分解算法的程序实现
算法实现采用C++语言进行编程，因为C++编译器能有效地对集合代码进行优化。算法程序的重点是信号的小波包分解与最优基选择程序的实现，主程序的流程图如图4所示。
其中最优基选择中计算Shannon 信息熵代价的关键代码如下所示：
temp=data［nlevel］［i］*data［nlevel］［i］;
max-=temp*(float)log(temp);
图4 主程序流程图
最优基快速搜索算法的关键代码如下所示：
//若父结点的信息代价比子结点低,
//那么就标记父结点， 否则不标记。
if(cost［nlevel］［nblock］>=(cost［nlevel+1］［2*nblock］+cost［nlevel+1］［2*nblock+1］)){
sig［nlevel］［nblock］=0;cost［nlevel］［nblock］=cost［nlevel+1］［2*nblock］+cost［nlevel+1］［2*nblock+1］;
}
else{
sig［nlevel］［nblock］=1;
//当高层有结点被标记时，其相应子结点的标记应删除。
int len=2;
int start=nblock<<1;
for(int i_l=nlevel+1;i_l
sig［i_l］［i_b］=0;
len=len<<1;
start=start<<1;
}
}
在CCS 2 (′C6000)编译环境下编程，程序编译优化后，加载到DSP工作平台上。由于本算法使用的存储空间较多，程序中大量使用了堆空间，默认的存储分配方式无法满足要求，所以重新编写cmd文件分配堆栈空间大小如下：
-stack 0xf00
-heap 0x20000
3 实验结果以及分析
输入信号对本文DSP程序进行测试，信号长度为1 024点，波形如图5所示。
使用db5小波对信号进行3层小波包分解， 选择Shannon 信息熵作为代价，得到最优小波包基节点为：(2,2) (3,0) (3,1) (3,2) (3,3) (3,4) (3,7)，由此得到最小代价为-90 002.773 438。最优基小波包分解结果波形如图6所示。
对最优基小波包分解结果进行小波包合成，得到重建信号波形如图7所示。
图5 1 024点原始信号波形图
图6 最优基小波包分解的结果波形图
图7 小波包重建波形图
可以看到重构后的波形无明显失真，这说明本程序的正确性。利用CCS的Profiler提供的程序运行时钟统计功能，得到小波包分解所用的时钟数为8 266 039，最优基选择所用的时钟数为4 716 800。
4 结 语
该文中讨论了小波包分解的过程和最优基及代价函数的选择方法，在浮点型DSP TMS320C6713B上实现了香农熵代价函数的小波包分解算法。小波包在信号分析方面的明显优势与DSP在实时信号处理上的广泛应用使得本文的实现方法有着重要的应用价值。
参考文献
［1］杨永明,路陈红.小波包分析在一维及二维信号去噪中的应用［J］.西安建筑科技大学学报:自然科学版,2004,36(3):364-367,159.
［2］史贤俊,林飒,李瑞亮.基于最优小波包基的信号去噪算法及其应用［J］.海军航空工程学院学报,2006,21(5):506-509.
［3］王淑艳,李昌青.基于小波包最优基的心电图压缩 ［J］.生物医学工程学杂志,2002,19(2):256-258.
［4］闻亭数字系统（北京）有限公司.TDS6713EVM用户手册［Z］.北京:闻亭数字系统（北京）有限公司,2006.
［5］胡广书.现代信号处理教程［M］.北京:清华大学出版社,2005.
［6］Yang Yongming,Xu Chao.A Wavelet Packet-based Block-partitioning Image Coding Algorithm with Rate-distortion Optimization ［J］.Image Processing,2005,3(11):201-204.
［7］Carnero B,Drygajlo A.Perceptual Speech Coding and Enhancement Using Frame-synchronized Fast Wavelet Packet Transform Algorithms ［J］.Signal Processing,1999,47(6):1 622-1 635.
［8］Philippe,P,de Saint-Martin F M,Lever M.Wavelet Packet Filter Banks for Low Time Delay Audio Coding ［J］.Speech and Audio Processing,1999,7(3):310-322.
［9］Cristan A C,Walden A T.Multitaper Power Spectrum Estimation and Thresholding:Wavelet Packets Versus Wavelets ［J］.Signal Processing,2002,50(12):2 976-2 986.
［10］Sun Fang,Liu Yibing,Li Ming,et al..Gear Faults Diagnosis Based on Wavelet Packet and Fuzzy Pattern Recognition ［J］.Control Conference,2000,52(12):1 267-1 270.
［11］Laine A,Fan J.Texture Classification by Wavelet Packet Signatures ［J］.Pattern Analysis and Machine Intelligence,1993,15(11):1 186-1 191.
作者简介 王靖琰 男，1985年出生，硕士研究生。主要从事生物特征识别（Biometrics）、图像及语音信号处理与识别研究。
