摘? 要： 大約束度卷積碼作為信道糾錯(cuò)編碼在通信中得到了廣泛的應(yīng)用,而其相應(yīng)的Viterbi譯碼器" title="譯碼器">譯碼器硬件復(fù)雜度大,限制了譯碼速度。分析了Viterbi譯碼器的結(jié)構(gòu),優(yōu)化了各模塊,合理地組織了存儲(chǔ)器結(jié)構(gòu),簡(jiǎn)化了接口電路" title="接口電路">接口電路。用FPGA實(shí)現(xiàn)Viterbi譯碼器,提高了譯碼器速度。

　　關(guān)鍵詞： 卷積碼? Viterbi譯碼? ACS 路徑度量存儲(chǔ)?? FPGA實(shí)現(xiàn)

?

　　Viterbi算法是一種基于最大后驗(yàn)概率的卷積譯碼算法,應(yīng)用廣泛。CDMA的IS-95標(biāo)準(zhǔn)和WCDMA 3 GPP標(biāo)準(zhǔn)將卷積碼作為高速實(shí)時(shí)數(shù)據(jù)傳輸?shù)男诺兰m錯(cuò)編碼,使Viterbi譯碼器成為移動(dòng)通信系統(tǒng)的重要組成部分。

　　為保證糾錯(cuò)性能,卷積碼約束度一般選擇比較大的,在3 GPP中規(guī)定約束度K=9。出于實(shí)時(shí)性的考慮,移動(dòng)通信系統(tǒng)中對(duì)譯碼時(shí)延的要求比較高,需要高速譯碼器的支持。可是Viterbi譯碼算法的復(fù)雜度、所需存儲(chǔ)器容量與約束長(zhǎng)度成指數(shù)增長(zhǎng)關(guān)系,成為限制譯碼器速度的瓶頸。Viterbi譯碼器每解碼一位信息位就需對(duì)2K-1個(gè)寄存器的狀態(tài)進(jìn)行路徑度量,并對(duì)相應(yīng)的存儲(chǔ)單元" title="存儲(chǔ)單元">存儲(chǔ)單元進(jìn)行讀寫。這種情況下,可以采用狀態(tài)路徑存儲(chǔ)單元分塊的方法,以提高其譯碼性能,缺點(diǎn)是ACS單元與存儲(chǔ)器之間的接口電路十分復(fù)雜,不易實(shí)現(xiàn)。

　　本文分析和優(yōu)化了Viterbi譯碼器的結(jié)構(gòu),提出了一種FPGA實(shí)現(xiàn)方案,簡(jiǎn)化了接口電路,提高了速度。用這種結(jié)構(gòu)實(shí)現(xiàn)的單片集成譯碼器譯碼速率達(dá)350kbps、時(shí)鐘頻率30MHz。以下先分析譯碼器總體結(jié)構(gòu),然后對(duì)各模塊設(shè)計(jì)和實(shí)現(xiàn)做詳細(xì)說明。

1 算法簡(jiǎn)述及譯碼器結(jié)構(gòu)

　　本文采用3 GPP標(biāo)準(zhǔn)規(guī)定的K=9,碼率r=1/2的(7538,5618)卷積碼,卷積編碼器送出的碼序列C,經(jīng)過信道傳輸后送入譯碼器的序列為R。譯碼器根據(jù)接受序列R,按最大似然準(zhǔn)則力圖找出正確的原始碼序列。

　　Viterbi譯碼過程可用狀態(tài)圖表示,圖1表示2個(gè)狀態(tài)的狀態(tài)轉(zhuǎn)移圖。S_j,t和S_j+N/2,t表示t時(shí)刻的兩個(gè)狀態(tài)。在t+1時(shí)刻,這兩個(gè)狀態(tài)值" title="狀態(tài)值">狀態(tài)值根據(jù)路徑為0或者1,轉(zhuǎn)移到狀態(tài)S_2j,t+1和S_2j+1,t+1。每一種可能的狀態(tài)轉(zhuǎn)移都根據(jù)接收到的有噪聲的序列R計(jì)算路徑度量,然后選擇出各個(gè)狀態(tài)的最小度量路徑(幸存路徑)。Viterbi算法就是通過在狀態(tài)圖中尋找最小度量路徑向前回溯L步,最后得到的即為譯碼輸出。

?

　　本設(shè)計(jì)采用Xilinx Virtex600E FPGA芯片,在ALDEC公司的Active-HDL仿真環(huán)境下,用Verilog語言完成,并用Xilinx的ISE4綜合實(shí)現(xiàn)。Viterbi譯碼器系統(tǒng)框圖如圖2所示,主要由BMG(路徑計(jì)算模塊)、ACS(加比選模塊)、TB(路徑回溯模塊)、MMU(路徑存儲(chǔ)模塊)等部分組成。采用并行流水線結(jié)構(gòu),各個(gè)模塊在控制信號(hào)統(tǒng)一監(jiān)控下工作,減少了讀取數(shù)據(jù)所需時(shí)間,充分發(fā)揮了FPGA高速計(jì)算的特性,提高了整個(gè)系統(tǒng)的效率。

?

2 子模塊的優(yōu)化和實(shí)現(xiàn)

2.1 ACS模塊

　　由于采用的卷積碼約束度K=9,在譯碼過程中,每一時(shí)刻有2^K-1=256個(gè)狀態(tài),512個(gè)度量路徑值,為了獲得高速率,需采用盡可能多的ACS單元。但由于實(shí)際應(yīng)用中要求電路面積小、功耗低,決定了ACS單元的數(shù)目不能太多。經(jīng)過實(shí)驗(yàn)證明,采用4個(gè)ACS單元并行處理,完全可以達(dá)到應(yīng)用要求。

　　ACS單元用來計(jì)算選擇狀態(tài)的路徑度量。它需要不斷地讀出路徑度量作為操作數(shù),然后將更新的度量寫回各個(gè)狀態(tài)。由于采用4個(gè)ACS單元并行處理,為不造成流水線堵塞,如何對(duì)RAM中的度量數(shù)據(jù)進(jìn)行讀寫是關(guān)鍵。如前述,本文采用狀態(tài)路徑存儲(chǔ)單元分塊的方法。將所有狀態(tài)分成4組,分別對(duì)應(yīng)于4個(gè)ACS。每次運(yùn)算時(shí),4個(gè)ACS同時(shí)從各組狀態(tài)值中讀取數(shù)據(jù)進(jìn)行操作。

???由圖1可知,狀態(tài)S_j和S_j+2/N在狀態(tài)轉(zhuǎn)移中同時(shí)得到兩個(gè)新狀態(tài)S_2j和S_2j+1。因此為了ACS能夠同時(shí)取出這兩個(gè)狀態(tài)值,S_j和S_j+2/N必須存儲(chǔ)在不同的RAM組中。同樣,兩個(gè)計(jì)算出來的新狀態(tài)S_2j和S_2j+1也應(yīng)如此。遵循這種準(zhǔn)則,同時(shí)為簡(jiǎn)化接口電路,采用如下的分組算法:假設(shè)待分配狀態(tài)=S_j=S_K-2S_K-1…S₁S₀,所對(duì)應(yīng)的RAM組為R_m,由于RAM共分成4組,則m=(S_K-2S₁)S₀(兩位二進(jìn)制數(shù)表示)。狀態(tài)分組圖如圖3所示,從中可以看出,從狀態(tài)S₁₂₈開始的后續(xù)狀態(tài)都有規(guī)律地交錯(cuò)位置存儲(chǔ)。由此,ACS單元和狀態(tài)路徑存儲(chǔ)單元的接口電路只需采用兩個(gè)2×2交換器" title="交換器">交換器,如圖4所示。每一個(gè)交換器上連著兩個(gè)ACS單元和兩個(gè)RAM組。這兩個(gè)交換器由輸入狀態(tài)Sj的最高位S_K-2控制。當(dāng)S_K-2=1時(shí),交換器交叉互聯(lián),如果S_K-2為0時(shí),各ACS和RAM直接相連。這種接口設(shè)計(jì)十分容易實(shí)現(xiàn)。

?

?

　　在Viterbi譯碼算法中,譯碼狀態(tài)的轉(zhuǎn)移導(dǎo)致度量的讀出和寫入地址的不同,這樣用FPGA實(shí)現(xiàn)時(shí)就需要兩塊RAM采用乒乓模式實(shí)現(xiàn)。本文更新路徑存儲(chǔ)采用原位運(yùn)算方法,也就是找出狀態(tài)轉(zhuǎn)移的規(guī)律性,建立轉(zhuǎn)移后的新狀態(tài)和轉(zhuǎn)移前的老狀態(tài)地址映射關(guān)系,使度量的更新在原位上進(jìn)行,使存儲(chǔ)空間減小一半。

2.2 幸存路徑管理模塊

　　幸存路徑的存儲(chǔ)和回溯是Viterbi算法關(guān)鍵的一步,最終的譯碼輸出從對(duì)幸存路徑的回溯中得到。由于采用基2的狀態(tài)轉(zhuǎn)移算法,當(dāng)前時(shí)刻對(duì)應(yīng)的前序時(shí)刻狀態(tài)只有2個(gè),所以在路徑回溯中采用1bit指針?biāo)惴āＲ簿褪钦f,在每個(gè)狀態(tài)路徑更新時(shí),只需寫1bit路徑狀態(tài)轉(zhuǎn)移信息。幸存路徑存儲(chǔ)單元可看作一個(gè)存儲(chǔ)器陣列,每列對(duì)應(yīng)一個(gè)狀態(tài),一列中的每個(gè)單元都有一個(gè)1位的指針。在實(shí)際設(shè)計(jì)中,考慮到數(shù)據(jù)總線的帶寬有限,對(duì)于8位的幸存路徑數(shù)據(jù)總線,在幸存路徑存儲(chǔ)器中將256個(gè)狀態(tài)分成32塊。對(duì)應(yīng)幸存路徑時(shí),先通過當(dāng)前狀態(tài)地址尋址的方式來選擇所對(duì)應(yīng)的幸存路徑塊。

　　在實(shí)際應(yīng)用中,為了保證譯碼的準(zhǔn)確度,幸存路徑的回溯長(zhǎng)度通常取4～5倍約束長(zhǎng)度,本文回溯長(zhǎng)度定為64。如圖5所示,當(dāng)一個(gè)解碼初始信號(hào)進(jìn)來后,系統(tǒng)把當(dāng)前所有狀態(tài)中的最小狀態(tài),也就是最小狀態(tài)值作為當(dāng)前狀態(tài)值,路徑回溯模塊把地址值送入MMU中,從32個(gè)分組塊中選取相應(yīng)的幸存路徑存儲(chǔ)單元得到幸存狀態(tài)值(8位),然后根據(jù)當(dāng)前狀態(tài)的指針從這8位數(shù)據(jù)中得到1位幸存路徑比特,而下一個(gè)狀態(tài)值由當(dāng)前狀態(tài)的低7位和這個(gè)幸存路徑比特決定。當(dāng)回溯了64步后,控制信號(hào)給出一個(gè)輸出指示時(shí),當(dāng)前狀態(tài)值的最高位即是解碼輸出值。

?

?

　　本文重點(diǎn)從ACS的并行處理、度量路徑的存儲(chǔ)管理和路徑回溯上對(duì)Viterbi譯碼方法進(jìn)行了討論。從實(shí)際應(yīng)用出發(fā),考慮到硬件功耗的降低和面積的減小,采用了4個(gè)ACS并行,路徑的存儲(chǔ)和管理都采取了分組的模式,簡(jiǎn)化了接口電路,譯碼達(dá)到了較高的速度,完全可以滿足3 GPP標(biāo)準(zhǔn)的要求。用Xilinx 的Virtex600E FPGA芯片實(shí)現(xiàn)了K=9、碼率為1/2、編碼速率為350kbps、時(shí)鐘頻率40MHz的Viterbi譯碼器。表1列出了Xilinx ISE對(duì)本設(shè)計(jì)綜合布線報(bào)告中提供的參數(shù)。

?

?

參考文獻(xiàn)

1 王新梅,肖國鎮(zhèn). 糾錯(cuò)碼原理與方法. 西安:西安電子科技大學(xué)出版社,1991

2 S.Y. Kim， H. Kim I.C. Park. Path metric memory management for minimizing interconnections in Viterbi decoders.ELECTRONICS LETTERS 2001;37(7):14

3 Yun-Nan Chang， Hiroshi Suzuki and Keshab K.Parhi. A 2-Mb/s 256-State 10-Mw Rate-1/3 Viterbi decoder.

IEEE J Solid-State Circuit， 2000； 35(6)

4 Shieh Ming-Der， Sheu Ming-Hwa， Wu Chieh-Ming and?Ju Wann-Shyang. Efficient management of in-place path

? metric update and its implementation for Viterbi decoders.?IEEE Int. Symp.Circuits and Systems， 1998；4

5 Biver，M.，Kaeslin，H.， and Tommasini，C. In-place updating?of path metrics in Viterbi decoders. IEEE J. Solid-State?Circuits， 1989； 24 (8)