摘要：基于長(zhǎng)期演進(jìn)(LTE)的Tail-biting卷積碼，介紹了維特比譯碼算法，它是一種最優(yōu)的卷積碼譯碼算法。由于Tail-biting卷積碼的循環(huán)特性，采用固定延遲譯碼的方法，降低了譯碼復(fù)雜度。通過使用全并行的結(jié)構(gòu)及簡(jiǎn)單的回溯存儲(chǔ)方法，設(shè)計(jì)了一個(gè)具有高速和低復(fù)雜度的固定延遲譯碼器。在FPGA上實(shí)現(xiàn)并驗(yàn)證，驗(yàn)證結(jié)果表明譯碼器的性能滿足了LTE系統(tǒng)的要求。
關(guān)鍵詞：LTE；Tail-biting卷積碼；維特比譯碼算法；固定延遲譯碼；FPGA

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

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

    編碼器移位寄存器的初始狀態(tài)值被設(shè)置為相應(yīng)的輸入數(shù)據(jù)流的最后6個(gè)信息比特，以至于移位寄存器的初始狀態(tài)和結(jié)束狀態(tài)相同。
    圖1中，D6D5D4D3D2D1表示編碼器的狀態(tài)索引(State Index)；ck表示輸入數(shù)據(jù)比特；表示輸出數(shù)據(jù)比特。
    卷積碼網(wǎng)格圖中的蝶形結(jié)構(gòu)，如圖2所示。

    隨著編碼比特的輸入，編碼器狀態(tài)的轉(zhuǎn)移過程，由圖2可以看出，時(shí)刻t-1的兩個(gè)相關(guān)狀態(tài)Si和Sj轉(zhuǎn)移到時(shí)刻t的兩個(gè)狀態(tài)Sm和Sn。圖中，PM和BM分別表示路徑度量和分支度量，其中BM的下標(biāo)為輸出比特的組合。

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

3 譯碼器的設(shè)計(jì)與實(shí)現(xiàn)
    在譯碼器的設(shè)計(jì)中，采用固定延遲算法。首先對(duì)進(jìn)入譯碼器之前的軟判決數(shù)據(jù)進(jìn)行處理，如圖3所示。

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

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

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

4 FPGA驗(yàn)證
    該設(shè)計(jì)采用Verilog HDL語言編寫代碼，使用Quartus 9．0綜合，并在Altera公司的StratixⅢEP3SL340F151713型號(hào)的FPGA上驗(yàn)證，該設(shè)計(jì)的譯碼器能達(dá)到135．78 MHz的速度，使用FPGA資源為4 992個(gè)ALUTs。

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