快速碼字搜索算法在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.