林 丹，李小文

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

0 引言

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

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

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

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

1 咬尾卷積碼

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

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

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

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

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

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

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

這項技術也有以下缺點：

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

●接收器復雜度略微增加。

2 實現

2.1 傳統(tǒng)viterbi譯碼

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

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

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

圖2 Viterbi譯碼算法處理流程

在某些應用中，Viterbi譯碼是根據接收到的符號逐數據塊進行譯碼，與鄰數據塊之間是相互獨立的，即在每個數據塊內進行譯碼，各數據塊之間相互獨立[6]。

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

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

（2）將每次編碼輸出的兩個比特量化為相應的數值，通過每一組數值計算出該組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（該數值根據實際的情況來定，如回溯深度和分支度量值等，以便計算），狀態(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），即回溯過程，就是根據回溯深度以及ACS過程中所保存的PM值和幸存路徑信息進行相應的算法回溯出譯碼結果。

圖3 Viterbi譯碼實現過程

2.2 咬尾卷積碼的viterbi譯碼實現

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

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

圖4 咬尾卷積譯碼

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

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

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

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

圖5 單個數據塊

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

3 仿真結果

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

圖6 時序仿真圖

4 性能分析

圖7顯示了一個32個符號的數據塊，約束長度為3。圖中咬尾編碼的數據塊通過譯碼器3次的曲線，與一個標準連續(xù)流（非咬尾）譯碼器幾乎相同。數據塊通過譯碼器兩次的曲線顯示相當壞的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譯碼器的設計及FPGA驗證[J]．復旦大學學報，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] 張宗橙．糾錯編碼原理和應用[M].西安：西安電子科技大學出版社,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數字系統(tǒng)設計教程[M].2版.北京：北京航空航天大學出版社,2008.

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