林 丹，李小文

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

0 引言

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

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

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

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

1 咬尾卷積碼

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

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

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

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

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

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

●不影響卷積碼的錯誤校驗屬性。

這項技術(shù)也有以下缺點：

●譯碼延遲增加了，因為必須確定正確的起始狀態(tài)和回溯的初始狀態(tài)；

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

2 實現(xiàn)

2.1 傳統(tǒng)viterbi譯碼

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

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

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

圖2 Viterbi譯碼算法處理流程

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

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

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

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

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

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

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

圖3 Viterbi譯碼實現(xiàn)過程

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

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

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

圖4 咬尾卷積譯碼

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

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

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

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

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

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

3 仿真結(jié)果

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

圖6 時序仿真圖

4 性能分析

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

圖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è)計及FPGA驗證[J]．復(fù)旦大學(xué)學(xué)報，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] 張宗橙．糾錯編碼原理和應(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è)計教程[M].2版.北京：北京航空航天大學(xué)出版社,2008.

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