快速码字搜索算法在G.722.2中的应用

刘兴旺,张雪英,李凤莲

(太原理工大学信息工程学院,太原030024)

在2000年12月,3GPP选择自适应多速率宽带语音编码 AMR-WB[1](Adaptive Multi-Rate Wideband Speech Codec)算法作为第三代移动通信系统使用的语音编解码算法。2002年1月,ITU-T又将其命名为宽带语音编码标准G.722.2,其音频带宽在50～7 000 Hz,采样率为16 kHz,支持9种速率模式,分别为：模式0(6.60kbit/s)、模式1(8.85 kbit/s)、模式 2(12.65 kbit/s)、模式3(14.25 kbit/s)、模式 4(15.85 kbit/s)、模式5(18.25 kbit/s)、模式 6(19.85 kbit/s)、模式 7(23.05 kbit/s)、模式8(23.85 kbit/s)。在G.722.2中导抗谱对(Immittance Spectral Pair,ISP)系数矢量量化[2]采用的是穷尽搜索算法(Full search,FS),假设码书,

式中：N为码书尺寸;k为矢量维数,每次失真计算需要k次乘法、k-1次加法和k次减法,则矢量x进行穷尽搜索需要 Nk次乘法、N(k-1)次加法、Nk次减法和N-1次比较。可以看出,计算复杂度是由码书尺寸和矢量维数决定的,对于大尺寸码书和高维矢量,计算复杂度将很大,限制了算法的实用性,所以有必要寻求快速有效的算法以减少计算复杂度。G.722.2作为宽带语音编码算法,其量化参数为16维ISP系数,如果直接对16维ISP参数进行量化,计算复杂度将会很高,因此在G.722.2标准中,在第一级量化时将16维ISP分裂为9维和7维的2个子矢量,但计算复杂度仍然很高。笔者对ISP分裂后的9维和7维的2个子矢量分别采用下述快速码书搜索算法来降低G.722.2标准的复杂度。

1 快速码字搜索算法

1.1 部分失真搜索算法

部分失真搜索[3,4](Partial Distortion Search,PDS)算法是一种最基本的快速码字搜索算法。算法在计算某个码字与输入矢量之间失真测度的同时判断累加的部分失真是否已经超过目前的最小失真,一旦超过则终止该码字与输入矢量之间的失真计算。

假定目前最小失真为

式中,yi表示第i个码字。部分失真算法的具体步骤如下：

b.若i＞N-1,终止算法,y p为矢量x的最近码字,p为码字索引。

c.d i=d i+(x l-y il)2,若 d i＞d min,则 i=i+1,

转步骤b.否则进行下一步。

d.若 l＜k-1,则 l=l+1,转 c;否则 d min=d i,p=i,i=i+1,转b.

部分失真码书搜索算法以增加s次比较换得减少k-s次相乘、k-s次相加及k-s次相减,在一定程度上减少了码字搜索时间,但是所减少的效率是有限的。一种快速有效的码字搜索算法应该满足三个条件：

a.有良好的初始匹配码字;

b.可以快速排除码字;

c.在设定搜索范围之后还可以再次合理地限定搜索范围。

可见PDS算法并没有考虑因素a.和c,只是对因素b设定了一个提前退出失真计算的判断准则。所以PDS常常用于许多快速搜索算法的最后一步,以排除其他方法已经无法排除的码字。

1.2 超立方体码书搜索算法

超立方体码书搜索算法[4,5](Hypercube Approach Search,HAS)首先选定一个特殊的初始匹配码字作为失真最小的码字,再利用这个初始码字来删除其它的候选码字,如果不能删除则更新初始码字。

设目前最小失真为d min=d(x,y p),0≤p≤N-1,输入矢量x和码字yi之间的下标为l的绝对误差分量为：

输入矢量 x和码字yi之间的最大绝对误差分量定义为：

1)对输入矢量 x和码书C,计算绝对误差eij,i=0,1,…,N-1,j=0,1,…,k-1;求出每个码字的最大绝对误差分量ei,max;并找出初始匹配码字y p,其索引为;计算当前最小失真d min=d(x,yp)。

由于超立方体码书搜索算法的初始匹配码字为具有最小的最大绝对误差分量的码字,选取初始匹配码字时需要Nk次绝对误差运算和(Nk-1)次比较运算,码字搜索的过程中每更新一次d min,需要一次开方运算,与部分失真码书搜索算法比较减少了Nk次乘法、N(2k-1)次加法和 N-1次比较,从而大大减少计算量和编码时间。码字搜索开始于ei,max,i=0,1,…,N-1,有利于选择一个良好的初始匹配码字,并对随后的候选码字比较容易检验和排除,所以参加失真计算的码字数目将减少。但超立方体码书搜索算法与全搜索算法相比,编码质量会有所降低,如果超立方体码书搜索算法与部分失真搜索算法结合使用,则可以进一步减少计算量并且结合后的编码质量优于部分失真码书搜索算法。

1.3 超立方体和部分失真相结合的方法

超立方体和部分失真相结合的方法(PDHAS)把超立方体码书搜索算法的步骤2修改为如下过程：若则 yi不是与x最接近的码字,i=i+1,继续判断下一个码字,否则,使用部分失真方法判断是否可以排除。如果可以排除,则i=i+1,继续判断下一个码字。如果部分失真算法也不能排除,则更新 d min=d(x,y i)和 p=i,i=i+1,继续判断下一个码字。算法在i=N-1时停止,最终得到的y p是x的最近码字。

超立方体和部分失真相结合的方法的优点在于用比较运算代替了乘法运算,比单独利用超立方体和部分失真中任何一种方法都有效,PDHAS比PDS在初始匹配码字方面得到加强,比HAS更合理地限定了搜索范围。可见PDHAS算法不仅对强有力的码字删除准则和良好的初始匹配码字有了考虑,并且还在设定搜索范围之后进一步合理地限定了搜索范围,所以PDHAS算法的效果优于单独使用PDS或HAS。

2 计算仿真结果

实验时所用男声和女声均选自 TIMIT数据库,客观评价标准采用 ITU-T P.862.2制定的wideband-Perceptual Evaluation of Speech Quality(w-PESQ)。20句男、女声分别采用FS搜索算法的G.722.2算法、PDS改进的G.722.2算法、HAS改进的G.722.2算法、PDHAS改进的G.722.2算法的编码时间平均值以及与采用FS搜索算法的G.722.2算法相比较9种模式编码时间的减少值,分别用D 1、D2、D 3表示,见表 1。从表1可以看出改进的算法比原算法的编码时间相应减少,这表明算法复杂度有所降低。男声和女声采用FS的编码时间平均值分别是358 ms和336 ms,而分别采用PDS,HAS,PDHAS的编码时间平均值是350,338,335 ms和330,314,311 ms;与FS相比较9种模式编码时间的减少值分别为8,20,23和6,22,25 ms,编码时间平均减少的百分比分别为2.2%,5.7%,6.4%和1.8%,6.5%,7.4%。在男声模式2的情况下,PDHAS比FS的平均编码时间减少值达到29 ms,平均编码时间减少的百分比为8.5%;在女声模式8的情况下,PDHAS比FS的平均编码时间减少值达到35 ms,平均编码时间减少的百分比为10%,这表明编码系统的复杂度有显著降低。

表1 FS,PDS,HAS,PDHAS编码时间比较 ms

20句男、女声平均w-PESQ值以及与FS相比较9种模式平均w-PESQ值的减少值,用D 1、D2、D3表示,见表2。可以看出利用PDHAS码书搜索算法,男声和女声的平均w-PESQ值比FS都只下降0.034,变化很小。对于女声来说模式4的情况下,PDHAS比FS的平均w-PESQ值最大减少0.050,下降的幅度很小;对于男声模式2而言,也只下降了0.052,减少幅度不大。因此PDHAS算法不仅可以实现原有的码字搜索功能,并且解码语音的w-PESQ值变化很小,但编码时间得到很大的降低。

表2 FS,PDS,HAS,PDHAS的w-PESQ值比较

3 结束语

比较编码时间可以直观地看出复杂度的改变情况。从表1可以看出优化算法比原算法的编码时间相应减少,复杂度有所降低。比较w-PESQ值可以直观地看出语音质量的改变情况,从表2可以看出优化算法比原算法减小的幅度很小。男生和女生12.65 kbit/s以上的模式的w-PESQ值超过了4.0,可以提供宽带模式。同时8.85 kbit/s和6.60 kbit/s两种模式w-PESQ值也在3.5以上,达到通信质量标准。可见,矢量量化优化算法不仅可以实现原有的码字搜索的功能,还可以使编码时间得到一定的降低。

[1] ITU-T.Wideband coding of speech at around 16 kbit/s using Adaptive Multi-Rate Wideband(AMR-WB)[S].ITU-T Recommend.G.722.2,2003.

[2] Linde Y,Buzo A,Gray R.An Algorithm for Vector Quantizer De2 sign[J].IEEE Transactions on Communications,1980,28(1)：84295.

[3] BEI C,GRAY R B.An Improvement of the Minimum Distortion Encoding Algorithm for Vector Quantization[J].IEEE Transactions on Communications,1985,COM-33(10)：1132-1133.

[4] 孙圣和,陆哲明.矢量量化技术及应用[M].北京：科学出版社,2002.

[5] Cheng D,Gersho A,Ramamurthi B,et al.Fast Search Algorithms for Vector Quantization and Pattern Matching[C].International Conference on Aeoustics,Speech and Signal Processing,1984.