摘要：基于長期演進(LTE)的Tail-biting卷積碼，介紹了維特比譯碼算法，它是一種最優的卷積碼譯碼算法。由于Tail-biting卷積碼的循環特性，采用固定延遲譯碼的方法，降低了譯碼復雜度。通過使用全并行的結構及簡單的回溯存儲方法，設計了一個具有高速和低復雜度的固定延遲譯碼器。在FPGA上實現并驗證，驗證結果表明譯碼器的性能滿足了LTE系統的要求。
關鍵詞：LTE；Tail-biting卷積碼；維特比譯碼算法；固定延遲譯碼；FPGA

0 引言
    LTE(Long Term Evolution)是“準4G”的技術，以OFDM／FDMA和MIMO為其核心技術。它對實時業務、高可靠性業務和廣播級多播業務都能提供較好的支持。LTE在20 MHz頻譜帶寬下能夠提供下行100 Mb／s和上行50 Mb／s的峰值速率，高速率對信道編碼和譯碼技術提出了更高的要求。
    對于LTE低時延、高速率和高可靠性的要求，降低譯碼的實現復雜度和時延以及提高其可靠性對LTE系統性能就顯得極其重要，也是一個巨大的挑戰。

1 LTE中Tail-biting卷積碼
    卷積碼通常用(n，k，N)表示。其中k表示輸入編碼器的數據位數；n表示編碼器輸出的數據位數；N為編碼約束長度，R=k／n是卷積碼的碼率。
    LTE中使用的Tail-biting卷積碼編碼器結構如圖1所示。其約束長度N=7，碼率R=1／3。

    編碼器移位寄存器的初始狀態值被設置為相應的輸入數據流的最后6個信息比特，以至于移位寄存器的初始狀態和結束狀態相同。
    圖1中，D6D5D4D3D2D1表示編碼器的狀態索引(State Index)；ck表示輸入數據比特；表示輸出數據比特。
    卷積碼網格圖中的蝶形結構，如圖2所示。

    隨著編碼比特的輸入，編碼器狀態的轉移過程，由圖2可以看出，時刻t-1的兩個相關狀態Si和Sj轉移到時刻t的兩個狀態Sm和Sn。圖中，PM和BM分別表示路徑度量和分支度量，其中BM的下標為輸出比特的組合。

2 Tail-biting卷積碼的譯碼算法
    維特比算法的實質是最大似然譯碼，它是在卷積碼的網格圖中尋找一條與編碼路徑最接近的最大似然路徑作為其最終譯碼輸出。在譯碼的每個時間單元，把網格圖上各個分支的度量加到前面狀態的路徑度量上，比較進入每個狀態的所有分支的度量，選擇具有最大度量的分支，即幸存路徑，迭代上述步驟，最終輸出最大似然路徑作為其譯碼輸出。
    維特比算法主要由三部分組成：分支度量(Branch Metric，BM)模塊、加比選(Add Compare Select，ACS)模塊和回溯(Trace Back，TB)模塊。
    直接運用維特比算法對Tail-biting卷積碼進行譯碼，其譯碼復雜度大，不利于硬件實現。為了能降低譯碼復雜度，用固定延時譯碼(Fixed Delay Decoding)算法，它是利用Tail-biting卷積碼的循環特性，也就是編碼輸入的開始部分能用來估計譯碼網格圖的最后狀態，執行譯碼操作用的固定延時。
    如有一段長為L的軟判決數據，選擇原數據的后LH個軟判決比特，將其放置在數據頭部，選擇原數據的前LT個軟判決比特，將其放置在數據尾部，最后形成長為LH+N+LT的待譯碼軟判決數據。將它用Viterbi算法譯碼，在譯碼數據中丟棄前LH個比特和后LT個比特，即為所需譯碼數據。其中LH和LT分別稱為頭譯碼長度(Head Decoding Length)和尾譯碼長度(Tail Decoding Length)，為此算法中需要決定這兩個重要參數。

3 譯碼器的設計與實現
    在譯碼器的設計中，采用固定延遲算法。首先對進入譯碼器之前的軟判決數據進行處理，如圖3所示。

    將其處理成圖中所示的待譯碼數據格式，其中DL是實際輸入的所需譯碼數據長度，PL為所需在數據中加的數據前綴長度，也即上述固定延遲算法中的頭譯碼長度，DD為所要達到的譯碼深度(Decoding Depth)，DD-DL為所要加的后綴長度，即固定延遲算法中的尾譯碼長度。在設計中選擇PL為96，由于在LTE系統中DL是變化的，最大為76，不能夠選擇固定的尾譯碼長度，但在本文設計中選擇固定的DD為192。
    譯碼器的整體設計框圖，如圖4所示。圖中譯碼器主要由譯碼器系統控制模塊，分支度量(BM)模塊，加比選(ACS)模塊，回溯(TB)模塊和輸出緩存組成。

    數據處理由譯碼器系統控制模塊控制完成，它控制從輸入緩存中讀入數據進行譯碼。
    下面對譯碼器BM模塊、ACS模塊和TB模塊這三個核心模塊的具體設計與實現進行詳細介紹。
3．1 BM模塊
    在整個系統中分支度量采用的是軟判決數據。軟判決根據接收的的軟判決比特和編碼器網格圖的參考分支，計算其歐氏距離。一般的歐氏距離采用如下公式計算：
   
    式中：ri為接收的軟判決比特；ci為編碼器網格圖的參考分支。上述公式經簡化后結合系統所用軟判決數據特點，可以得到如下計算方法：
   
    式中：Ri為接收的軟判決比特的絕對值；Ci∈{0，1)為參考分支比特。
3．2 BM模塊
    在每一個時鐘中，用得到的分支度量(BM)和路徑度量(PM)相加，得到下一時刻狀態的多個路徑度量，通過比較，選擇一個幸存分支。將每個狀態的幸存分支，存儲到回溯存儲器中，更新路徑度量。在設計中，存儲從數據段(即圖4中的Initial State)開始，在這之前的幸存分支不需存儲。同時，計算出64個狀態中，具有最小路徑度量的狀態。
    如果直接將前一狀態的路徑度量與分支度量相加，得到下一狀態的路徑度量，來選擇幸存分支，如圖2中，比較PMi+BMp和PMj+BMq選擇幸存分支。每個狀態2個加法器，64個狀態就需要128個加法器。
    由于網格圖的蝶形結構，可以比較PMi-PMj和BMq-BMp(即如果PMi+BMp>PMj+BMq，可以將其寫為PMi-PMj>BMq-BMp)，這樣對于每一對相關狀態可以重復使用這兩項，在這個過程中需要用到32個加法器。通過這種方法，可以明顯減少ACS模塊中的加法器數量。
    更新路徑度量的操作設計如下，編碼器的狀態轉移過程如圖2中蝶形結構所示，蝶形結構中兩個相關狀態轉移到兩個新狀態。
    兩個相關狀態對應的用狀態索引分別為i=OD5D4D3D2D1和j=1D5D4D3D2D1，兩個新狀態可以分別表示為m=D5D4D3D2D10和n=D5D4D3D2D11。即，狀態i=0D5D4D3D2D1，如果輸入比特0，轉移到狀態m=D5D4D3D2D10，如果輸入是比特1，轉移到狀態n=D5D4D3D2D11；狀態j=1D5D4D3D2 D1，如果輸入比特0，轉移到狀態m=D5D4D3D2D10，如果輸入比特1，轉移到狀態n=D5D4D3D2D11。根據上面的轉移狀態關系，更新狀態的路徑度量。
    對于幸存分支的存儲表示，本文采取如下方法，狀態m=D5D4D3D2D10，如果由狀態i=0D5D4D3D2D1轉移而來，那么此幸存分支取狀態的最高有效比特0；如果由狀態j=1D5D4D3D2D1轉移而來，此幸存分支取狀態的最高有效比特1。同樣，狀態n=D5D4D3D2D11，如果由狀態i=0D5D4D3 D2D1轉移而來，此幸存分支用0表示；如果是由狀態j=1D5D4D3D2D1轉移而來，此幸存分支用1表示。每個時刻，經過ACS選出64個狀態所對應的幸存分支，存入回溯存儲器。
3．3 BM模塊
    回溯算法，由于已經將每個時鐘下所有狀態的幸存分支存儲在回溯存儲器里，在達到譯碼深度DD后，開始對整個幸存分支進行回溯，如圖3所示。當達到回溯深度(Trace Back Depth)后，幸存路徑就開始合并，就開始輸出譯碼數據。
    回溯指針是卷積碼編碼逆過程的狀態索引?；厮葜羔樀木唧w建立過程如下：回溯開始時，由ACS中計算的最小度量狀態的狀態索引作為初始回溯指針，從回溯存儲器中讀出的所有64個狀態的幸存分支中，選出該回溯指針對應的幸存分支，形成下一個回溯指針，以此在回溯過程中循環向前，在每一時鐘中形成回溯指針。
    由幸存分支的存儲表示可以得出，回溯指針m=D5D4D3D2D10，如果該指針對應的幸存分支為比特0，那么下一個回溯指針為i=0D5D4D3D2 D1，如果對應的幸存分支為比特1，那么下一個回溯指針為j=1D5D4D3D2D1；同理，回溯指針n=D5D4D3D2D11，如果幸存分支為比特0，下一個回溯指針為i=0D5D4D3D2D1，如果幸存分支為比特1，那么下一個回溯指針為j=1D5D4D3DzD1。
    在該設計中，最重要的是譯碼深度(DD)的選擇，譯碼深度能夠決定所用的回溯存儲器得深度。結合數據前綴的固定延遲操作，采用一個單端口RAM(SPRAM)，大小為96×128 b，如圖5所示。

    在一個譯碼周期里，數據前綴譯碼結束，從數據段(即圖3所示start state)開始，每2個時鐘往SPRAM里寫1次這兩個時鐘分別產生的幸存分支，共128 b，如圖5所示，即順序寫入數據R0R1，R2R3，R4R5，……，往SPRAM里寫數據共需192個時鐘。在達到譯碼深度后，開始回溯，讀出SPRAM里幸存分支，每個時鐘讀出兩個連續幸存分支，進行回溯指針的操作，在回溯深度后就會合并為一條幸存路徑，直到回溯完成，共需96個時鐘。在回溯的同時，如有數據輸入譯碼器，開始下一個周期的譯碼，在回溯操作從SPRAM讀數據的96個時鐘里，用來譯碼數據前綴，在數據段開始時往SPRAM里寫數據，同時回溯操作的讀數據也已完畢。
    從SPRAM里讀出的數據R(DL+5)～R6(DL為數據長度)中的幸存路徑，即為譯碼比特，輸出到輸出緩存中。根據系統需要，譯碼比特輸出到輸出緩存完成后，一次將最終的譯碼數據輸出。

4 FPGA驗證
    該設計采用Verilog HDL語言編寫代碼，使用Quartus 9．0綜合，并在Altera公司的StratixⅢEP3SL340F151713型號的FPGA上驗證，該設計的譯碼器能達到135．78 MHz的速度，使用FPGA資源為4 992個ALUTs。

5 結語
    本文設計的譯碼器，利用Tail-biting卷積碼的循環特性，采用固定延遲的算法與維特比算法結合，使其硬件實現更簡單，采用并行結構以及簡單的回溯存儲器方法，顯著提高譯碼器速度。在設計各個子模塊時，優化了硬件結構，減少占用資源和降低功耗，使其整體性能更優。
    本文設計的譯碼器在FPGA上實現和驗證，能達到135．78 MHz時鐘，該譯碼器達到了LTE系統所要求的122．88 MHz時鐘要求，達到了LTE系統所要求的整體性能，并已應用到ASIC芯片設計中。