林 丹，李小文

（1 重慶郵電大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400065；2 重慶郵電大學(xué) 通信學(xué)院 重慶 400065）

0 引言

LTE采用下行正交頻分多址（OFDM），上行單載波頻分多址(SC-FDMA)的方式[1]。OFDM是LTE系統(tǒng)的主要特點(diǎn)，它的基本思想是把高速數(shù)據(jù)流分散到多個(gè)正交的子載波上傳輸，從而使子載波上的符號(hào)速率大大降低，符號(hào)持續(xù)時(shí)間大大加長(zhǎng)，因而對(duì)時(shí)延擴(kuò)展有較強(qiáng)的抵抗力，減小了符號(hào)間干擾的影響[2]。在LTE系統(tǒng)中，為了獲得正確無(wú)誤的數(shù)據(jù)傳輸，要采用差錯(cuò)控制編碼技術(shù)。

很多數(shù)據(jù)通信標(biāo)準(zhǔn)采用卷積碼作為前向糾錯(cuò)的方法[3]。采用這種編碼方式的數(shù)據(jù)通常都使用Viterbi譯碼器進(jìn)行譯碼，Viterbi譯碼器受格形狀態(tài)概率和分支度量的約束。傳輸?shù)臄?shù)據(jù)通常由一串0比特結(jié)尾，以強(qiáng)制編碼器回到0狀態(tài)，這樣譯碼器能從已知的狀態(tài)開(kāi)始譯碼，但是信道必須傳輸額外的符號(hào)[4]。

另一種方法是保證格形起始和終止于某個(gè)相同的狀態(tài)，稱之為咬尾技術(shù)，它具有不要求傳輸任何額外比特的優(yōu)點(diǎn)。咬尾在幾種流行的通信標(biāo)準(zhǔn)里使用，如IEEE802.16，LTE等。

本文介紹了在FPGA中實(shí)現(xiàn)的咬尾卷積碼的Viterbi 譯碼算法。算法在整體延遲一段時(shí)間后，正確輸出譯碼結(jié)果。

1 咬尾卷積碼

咬尾卷積碼的約束長(zhǎng)度為7，編碼率為1/3。卷積碼的編碼器配置如圖1所示。

編碼器的移位寄存器的初始值應(yīng)當(dāng)設(shè)置為輸入流的最后6位信息比特，這樣移位寄存器的初始和最終狀態(tài)保持一致。若用表示編碼器的6個(gè)移位寄存器，則移位寄存器的初始值應(yīng)當(dāng)設(shè)

咬尾試圖解決傳輸多余的終止比特的問(wèn)題。在包傳送之前，包的最后Z個(gè)數(shù)據(jù)比特用來(lái)初始化編碼器移位寄存器，也就是編碼器的起始狀態(tài)和終止?fàn)顟B(tài)由包指定。這也隱含了在傳輸?shù)谝粋€(gè)符號(hào)前整個(gè)數(shù)據(jù)包對(duì)于編碼器來(lái)說(shuō)必須是可用的。

另一種方法是先用開(kāi)始的Z個(gè)數(shù)據(jù)比特初始化編碼器，在這個(gè)時(shí)間內(nèi)不傳輸任何輸出符號(hào)，然后余下的（N-Z）個(gè)數(shù)據(jù)比特進(jìn)行編碼并傳送，開(kāi)始的Z個(gè)比特緊跟在最后進(jìn)行編碼。這種方式同樣使編碼器的初始狀態(tài)和終止?fàn)顟B(tài)相同。這種方法的優(yōu)點(diǎn)是在編碼開(kāi)始前不需要獲得整個(gè)數(shù)據(jù)包，但是接收器接收到的編碼后的序列不是正序。

咬尾技術(shù)具有以下優(yōu)點(diǎn)：

●不影響編碼率，總的傳輸比特為N/R；

●不影響卷積碼的錯(cuò)誤校驗(yàn)屬性。

這項(xiàng)技術(shù)也有以下缺點(diǎn)：

●譯碼延遲增加了，因?yàn)楸仨毚_定正確的起始狀態(tài)和回溯的初始狀態(tài)；

●接收器復(fù)雜度略微增加。

2 實(shí)現(xiàn)

2.1 傳統(tǒng)viterbi譯碼

Viterbi譯碼算法[5]是由Viterbi于1967年提出的降低計(jì)算復(fù)雜度的算法。它是計(jì)算網(wǎng)格圖上在時(shí)刻 到達(dá)各個(gè)狀態(tài)的路徑和接收序列之間的相似度，或者說(shuō)距離，去除不可能成為最大似然選擇對(duì)象的網(wǎng)格上的路徑，即，如果有兩條路徑到達(dá)同一狀態(tài)，則具有最佳度量的路徑被選中，稱為幸存路徑。對(duì)所有狀態(tài)都進(jìn)行這樣的選路操作，譯碼器不斷在網(wǎng)格上深入，通過(guò)去除可能性最小的路徑實(shí)現(xiàn)判決，從而降低譯碼器的復(fù)雜性。

圖1 1/3編碼率的咬尾卷積編碼器

Viterbi譯碼算法一般的實(shí)現(xiàn)流程如圖2所示。由圖2可以看出Viterbi算法的主要實(shí)現(xiàn)過(guò)程可分為4大部分：分支度量計(jì)算（BMC）；加比選（ACS）；存儲(chǔ)幸存路徑存儲(chǔ)器（SSM）；輸出判決（OD）。

圖2 Viterbi譯碼算法處理流程

在某些應(yīng)用中，Viterbi譯碼是根據(jù)接收到的符號(hào)逐數(shù)據(jù)塊進(jìn)行譯碼，與鄰數(shù)據(jù)塊之間是相互獨(dú)立的，即在每個(gè)數(shù)據(jù)塊內(nèi)進(jìn)行譯碼，各數(shù)據(jù)塊之間相互獨(dú)立[6]。

從圖3我們可以清楚的看到，對(duì)輸入的數(shù)據(jù)通過(guò)編碼器進(jìn)行卷積編碼，到最后的輸出譯碼結(jié)果，總過(guò)經(jīng)歷了以下幾個(gè)過(guò)程：

（1）對(duì)輸入的數(shù)據(jù)進(jìn)行卷積編碼，編碼速率為1/2，即每輸入一個(gè)比特編碼輸出兩個(gè)比特。

（2）將每次編碼輸出的兩個(gè)比特量化為相應(yīng)的數(shù)值，通過(guò)每一組數(shù)值計(jì)算出該組4個(gè)狀態(tài)（s0，s1，s2，s3）的分支度量值，即BM值。

（3）進(jìn)行加比選（ACS）運(yùn)算，同時(shí)保存路徑信息。如圖2，首先在0時(shí)刻給4個(gè)狀態(tài)（s0，s1，s2，s3）賦初始路徑向量值（PM）：假如起始點(diǎn)為狀態(tài)s0，則狀態(tài)s0的初始路徑向量值為PM0=100（該數(shù)值根據(jù)實(shí)際的情況來(lái)定，如回溯深度和分支度量值等，以便計(jì)算），狀態(tài)s1，狀態(tài)s2，狀態(tài)s3的初始路徑向量賦值為PM1=PM2=PM3=0。

（4）ACS過(guò)程。因?yàn)榈竭_(dá)每一個(gè)狀態(tài)的有兩條路徑（見(jiàn)圖3），例如到達(dá)狀態(tài)s0(00)的兩條路徑分別是s0(00)和s1(01)，從中選出到達(dá)s0路徑度量值最大的一條路徑作為幸存路徑。如圖 2， 若 從 0時(shí) 刻 到 1時(shí) 刻 ：BM0=-8，BM1=0，max{PM0+BM0,PM1+BM1}=PM0+BM0=92，所以1時(shí)刻到達(dá)狀態(tài)s0的保留路徑為0時(shí)刻從狀態(tài)s0來(lái)的路徑，從而更新1時(shí)刻s0的PM0=92，同時(shí)由于1時(shí)刻到達(dá)s0的是“0”路徑，所以保存的該時(shí)刻s0的路徑信息是0（若是“1”路徑，則保存的該時(shí)刻s0的路徑信息為1），以此類推可求出該時(shí)刻到達(dá)狀態(tài)s1,s2,s3的幸存路徑，存儲(chǔ)該路徑信息，更新其路徑度量值PM。

（5）輸出判決（OD），即回溯過(guò)程，就是根據(jù)回溯深度以及ACS過(guò)程中所保存的PM值和幸存路徑信息進(jìn)行相應(yīng)的算法回溯出譯碼結(jié)果。

圖3 Viterbi譯碼實(shí)現(xiàn)過(guò)程

2.2 咬尾卷積碼的viterbi譯碼實(shí)現(xiàn)

在多數(shù)的咬尾應(yīng)用里，在傳輸之前使用數(shù)據(jù)包的最后Z個(gè)比特來(lái)對(duì)編碼器狀態(tài)進(jìn)行初始化，這樣在一個(gè)數(shù)據(jù)包內(nèi)編碼器具有相同的起始和終止?fàn)顟B(tài)，對(duì)于最佳譯碼來(lái)說(shuō)，譯碼器的應(yīng)該從這個(gè)狀態(tài)開(kāi)始構(gòu)建格形，否則，由于在包的開(kāi)始階段進(jìn)行錯(cuò)誤校正會(huì)降低似然度，從而導(dǎo)致BER增加。

如果一個(gè)數(shù)據(jù)包內(nèi)有多個(gè)回溯長(zhǎng)度，一種方法是在包的末尾譯碼第一個(gè)TB塊（傳輸塊）。假定數(shù)據(jù)包終止于正確狀態(tài)，TB塊 0的格形構(gòu)建開(kāi)始于正確的起始狀態(tài)，如圖4所示，這個(gè)例子假定一個(gè)數(shù)據(jù)包包含了（N+1）個(gè)回溯長(zhǎng)度。

圖4 咬尾卷積譯碼

在數(shù)據(jù)包的開(kāi)始階段，TB塊0用來(lái)確定TB塊1的正確起始狀態(tài)。由于在構(gòu)建格形時(shí)并不知道從哪一個(gè)狀態(tài)開(kāi)始，因此此時(shí)譯碼的TB塊0可能是不正確的，先忽略TB塊0的數(shù)據(jù)輸出?！?/p>

在末尾重新插入塊0，則塊N可以作為訓(xùn)練序列，為塊0提供正確的起始狀態(tài)。這種方法明顯地為塊0增加了額外的譯碼延遲。除了起始和終止的數(shù)據(jù)塊外，其他的數(shù)據(jù)塊都是按正常方式解碼，每個(gè)塊的終止?fàn)顟B(tài)都自動(dòng)地為下一個(gè)塊提供起始狀態(tài)。

另一種方法是先輸入數(shù)據(jù)塊N，忽略輸出數(shù)據(jù)。這種技術(shù)給格形結(jié)構(gòu)的TB塊0提供了正確的起始狀態(tài)。這個(gè)塊之后緊跟著塊0到塊N的數(shù)據(jù)。TB塊0在末尾處再次輸入以給TB塊N的譯碼提供訓(xùn)練序列。這種方法的優(yōu)點(diǎn)在于譯碼器端所有的數(shù)據(jù)都是以正確順序輸出。缺點(diǎn)是必須等待所有的包被接收完才能開(kāi)始譯碼。

若一個(gè)數(shù)據(jù)包只含有一個(gè)回溯長(zhǎng)度的數(shù)據(jù)，那么可以把塊0通過(guò)譯碼器3次，則以上的方法同樣有效。第一次給格形結(jié)構(gòu)確定正確的起始狀態(tài)，第二次構(gòu)建格形，第三次進(jìn)行正確的訓(xùn)練以使回溯開(kāi)始于正確的狀態(tài)（見(jiàn)圖5）。

圖5 單個(gè)數(shù)據(jù)塊

TB塊0必須通過(guò)3次，若只通過(guò)了2次，則會(huì)增加BER，導(dǎo)致幾乎所有的包都錯(cuò)誤解碼。在第6節(jié)的性能分析中的曲線顯示了其性能。

3 仿真結(jié)果

使用verilog語(yǔ)言[7]在ISE[8]中進(jìn)行綜合、實(shí)現(xiàn)，布線后的時(shí)序仿真圖如圖6，圖6為正確的維特比譯碼時(shí)序仿真圖，輸入的比特序列為一串隨機(jī)數(shù)，經(jīng)過(guò)卷積編碼后輸入到Viterbi譯碼器，最后輸出的譯碼序列與輸入序列一致。本譯碼器實(shí)現(xiàn)了正確的譯碼功能。

圖6 時(shí)序仿真圖

4 性能分析

圖7顯示了一個(gè)32個(gè)符號(hào)的數(shù)據(jù)塊，約束長(zhǎng)度為3。圖中咬尾編碼的數(shù)據(jù)塊通過(guò)譯碼器3次的曲線，與一個(gè)標(biāo)準(zhǔn)連續(xù)流（非咬尾）譯碼器幾乎相同。數(shù)據(jù)塊通過(guò)譯碼器兩次的曲線顯示相當(dāng)壞的BER性能。對(duì)于更大的約束長(zhǎng)度，由于選擇正確起始狀態(tài)的似然性的降低會(huì)使性能更差。

圖7 BER性能

[1] 3GPP TS 36.201 v8.1.0: LTE Physical Layer-General Description(Release 8)[S]. 2008-05；7-8.

[2] 3GPP TS 36.211 v8.3.0: Physical Channels and Modulation (Release 8)[S]. 2008-05；71.

[3] 鄭宇馳，周曉方，閔昊．OFDM 系統(tǒng)中Viterbi譯碼器的設(shè)計(jì)及FPGA驗(yàn)證[J]．復(fù)旦大學(xué)學(xué)報(bào)，2005，44(6)：923-927.

[4] Bill Wilkie and Beth Cowie．Viterbi Decoder Block Decoding-Trellis Termination and Tail Biting.XAPP551(1.0) February 14,2005.

[5] 張宗橙．糾錯(cuò)編碼原理和應(yīng)用[M].西安：西安電子科技大學(xué)出版社,2003.

[6] Martin R?der and Raouf Hamzaoui.Fast Tree-Trellis List Viterbi Decoding[J].IEEE Trans Communications,2006,53(3):453-460.

[7] 夏宇聞．verilog數(shù)字系統(tǒng)設(shè)計(jì)教程[M].2版.北京：北京航空航天大學(xué)出版社,2008.

[8] EDA先鋒工作室.Xilinx ISE 9.X FPGA/CPLD設(shè)計(jì)指南[M].北京：人民郵電出版社,2007.