Viterbi譯碼器的并行優(yōu)化設(shè)計

摘 要：本文提出了一種（2，1，9）卷積編碼及其Viterbi譯碼的軟件實現(xiàn)方案。該方案應(yīng)用軟件技術(shù)實現(xiàn)了卷積碼維特比譯碼器功能，在程序?qū)崿F(xiàn)中充分運用了蝶形運算、周期性回溯等卷積碼的固有特性，獲得了Viterbi譯碼輸出。重點對蝶形運算和維特比算法進行了SSE并行優(yōu)化。仿真實驗表明，此方案可大幅提高譯碼效率，縮短處理時間。

關(guān)鍵詞：卷積編碼；Viterbi譯碼；SSE并行優(yōu)化；蝶形運算

中圖分類號：TN911.2

隨著通信技術(shù)的發(fā)展，特別是3G時代的普及，人們對通信的準確性提出了很高的要求，為此，在數(shù)據(jù)傳輸過程中都采用信道編碼技術(shù)。由于卷積碼編碼簡單，性能優(yōu)良被廣泛采用。Viterbi算法是一種最大似然譯碼，在譯碼過程中要遍歷所有可能的狀態(tài)，所以其計算復(fù)雜度很高?，F(xiàn)有的實現(xiàn)方法都是單指令數(shù)據(jù)流，處理效率極低，不能滿足現(xiàn)狀移動實時通信的需求。對此Intel推出單指令多數(shù)據(jù)流擴展SSE，SSE是一套專門為單指令多數(shù)據(jù)架構(gòu)設(shè)計的指令集，它可以實現(xiàn)數(shù)據(jù)的并行處理，效率極高利用SSE對算法進行并行優(yōu)化，能提高信號處理的速度，減少時延，滿足現(xiàn)代的高速率、大容量通信。

1 卷積碼的Viterbi譯碼器的基本結(jié)構(gòu)

卷積碼譯碼采用經(jīng)典的維特比譯碼算法。算法分為兩大步驟：前向遞推，簡單概括為“加、比、選”操作；回溯找出最佳路徑。圖1為維特比譯碼器的基本結(jié)構(gòu)。

2 卷積碼的Viterbi譯碼器的結(jié)構(gòu)設(shè)計

2.1 維特比譯碼器的三個重要的參數(shù)

維特比譯碼器存在三重要的參數(shù)，分別是徑存貯容量、合并距離、回溯路徑譯碼位。徑存貯容量定義路徑存貯的大小，規(guī)定我們周期性的回溯生成譯碼數(shù)據(jù)。合并距離的設(shè)置使得回溯時可以從任意一個當前狀態(tài)開始，不需要從最小的度量距離節(jié)點開始。回溯路徑譯碼位可以避免因為盡可能多的得到譯碼輸出而增加譯碼延遲，設(shè)置每次的回溯時譯碼的位數(shù)。

2.2 加比選單元的蝶形運算

維特比譯碼采用向前遞推算法，向前遞推過程是一個狀態(tài)轉(zhuǎn)移的過程。TD-SCDMA無線電接收器采用（2，1，9）卷積碼的編碼方式，卷積碼狀態(tài)寄存器為8，編碼器有28=256個狀態(tài)數(shù)。觀察卷積碼的狀態(tài)轉(zhuǎn)移過程，可發(fā)現(xiàn)其規(guī)律性很強，可由多個蝶形圖構(gòu)成，蝶形運算如下圖2，整個狀態(tài)轉(zhuǎn)移圖由128個這樣的蝶形組成。

加比選的蝶形運算中每個蝶形包括當前狀態(tài)為i和i+states（states為狀態(tài)數(shù)的一半，這里為128）兩個節(jié)點的加，比較，和選擇運算，他們的0分支和1分支在籬笆圖的下一個節(jié)點合并。

2.3 分支度量的計算

在計算分支度量時，通常有軟判決和硬判決兩種輸入。對于硬判決采用漢明距離定義，主要是以1或者0來定義。對于軟判決可做相似定義，根據(jù)軟判決的輸入位數(shù)據(jù)頂最大歐氏距離的取值。

2.4 路徑存貯記錄

從當前狀態(tài)經(jīng)過加_比較_選的蝶形運算后，到達下一個狀態(tài)，通過對每一個分支度量的積累計算留下與接收序列距離最近的幸存路徑。

2.5 回溯

我們在程序中設(shè)置一個標志位，當路徑存貯記錄長度第一次超過回溯路徑譯碼位長度時，將標志位復(fù)位，繼續(xù)進行運算。當路徑存貯記錄長度達到定義的路徑存貯容量時，選擇從任意一個狀態(tài)開始進行回溯。先回溯定義的合并距離長度，回溯時只是記錄狀態(tài)，不生成輸出譯碼位，然后從剛得到的狀態(tài)繼續(xù)回溯以生成輸出譯碼位。

2.6 程序設(shè)計流程圖（如圖3）

3 維特比算法的SSE并行優(yōu)化

Viterbi算法是一種最大似然譯碼，在譯碼過程中要遍歷所有可能的狀態(tài)，所以其計算復(fù)雜度很高。現(xiàn)有的實現(xiàn)方法大多數(shù)是采用單指令單數(shù)據(jù)流串行處理Viterbi譯碼算法中的加-比-選，遍歷每一種狀態(tài)。這種方法效率低，對通信帶來的時延很大，僅適用于低速、小容量，對實時性要求低的通信系統(tǒng)。隨著通信技術(shù)的發(fā)展，低速、小容量的通信顯然不能滿足人們的需求，人們更希望速率高、實時性好的通信系統(tǒng)。利用SSE對維特比優(yōu)化，可以大大提高譯碼效率，提高信號處理的速度，減少時延，滿足現(xiàn)代的高速率、大容量通信。

3.1 SSE并行優(yōu)化維特比的加比選單元

（1）將蝶形運算將其展開，由于SSE的拓展寄存器是128bit，每個狀態(tài)是32bit。所以展開的次數(shù)為4。

（2）將所有出現(xiàn)的數(shù)組，將軟比特的乘，加，比較，選擇，復(fù)制到下一個狀態(tài)，進行分析。

（3）并對其進行SSE并行指令優(yōu)化，下圖4為維特比優(yōu)化狀態(tài)圖的比較。

3.2 SSE并行優(yōu)化維特比的函數(shù)設(shè)計

（1）將軟比特的數(shù)據(jù)存放在兩個128bit的寄存器內(nèi)存中，用bm[]表示4次蝶形運算的軟比特數(shù)，通過SSE函數(shù)“uint32x4_t vld1q_u32（const uint32x4_t *）”將數(shù)組分別加載到內(nèi)存中。

4 測試實驗及總結(jié)

選?。?，1，9）形式的卷積碼按照上述方法進行譯碼，譯碼個數(shù)分別為100，400，800。用T優(yōu)化前表示使用傳統(tǒng)的Viterbi譯碼方法譯碼的時間，T優(yōu)化后表示使用并行優(yōu)化后的Viterbi譯碼方法譯碼時間，用T優(yōu)化倍數(shù)=T優(yōu)化前/T優(yōu)化后表示優(yōu)化倍數(shù)。在測試試驗中，分別選取了100，400和800個比特進行編碼。為了比較容易看出結(jié)果，每次譯碼時，重復(fù)譯碼10000次，然后算出重復(fù)譯碼10000次的運行前后的時間差，每次試驗對1000個時間差求平均，得到的結(jié)果如表1所示。從表1可以看出，不論編碼個數(shù)是100，400還是800，其優(yōu)化前的時間是優(yōu)化后的將近4s倍。

5 結(jié)語

通過對維特比運算的SSE并行優(yōu)化，每做一次的蝶形運算的時間，并行優(yōu)化后可做四次蝶形運算，實現(xiàn)數(shù)據(jù)的并行處理，大大的提高了程序運行的效率，縮短了運行時間。這樣可以利用SSE對算法進行優(yōu)化效率極高，能提高信號處理的速度，減少時延，滿足現(xiàn)代的高速率、大容量通信。

參考文獻：

[1]徐超穎.三種使用的糾錯編碼技術(shù)及其軟件實現(xiàn)[D].西安交通大學碩士學位論文.

[2]ChiP Fleming A Tutorial on Convolutional Coding with Viterbi Decoding Spectrum Applications，2001.

[3]王新梅，肖國鎮(zhèn).糾錯碼一原理與方法[M].西安：西安電子科技大學出版社，2002.

[4]青松，程岱松，武建華.數(shù)字通信系統(tǒng)的仿真與分析[M].北京：北京航空航天大學出版社，2003.

作者簡介：劉慶文（1987-），男，山東泰安人，研究生，研究方向：電子與通信工程；李欣（1960-），男，黑龍江哈爾濱人，碩士生導(dǎo)師，教授，研究方向：無線通信與通信系統(tǒng)；王心志（1986-），男，研究方向：通信與信息系統(tǒng)。

作者單位：哈爾濱理工大學 通信工程系，哈爾濱 150080