摘要：介紹了咬尾卷積碼的最優(yōu)和次最優(yōu)譯碼算法的實(shí)現(xiàn)細(xì)節(jié)。給出了采用新的蝶形圖計(jì)算方法和環(huán)形內(nèi)存來(lái)節(jié)省硬件資源的實(shí)現(xiàn)方法，最后給出了次最優(yōu)算法在FPGA上的實(shí)現(xiàn)結(jié)果。
關(guān)鍵詞：咬尾卷積碼；次最優(yōu)譯碼算法；蝶形圖；FPGA

0 引言
    自1955年Elias發(fā)明卷積碼以來(lái)，卷積碼作為一種高效的信道編碼已被用在許多現(xiàn)代通信系統(tǒng)中。卷積碼分為零比特卷積碼(Zero Tail CC，簡(jiǎn)稱(chēng)ZTCC)和咬尾卷積碼(Tail Biting CC，簡(jiǎn)稱(chēng)TBCC)兩種。ZTCC是指在編碼的時(shí)候，碼字后面要另外加上K(K為約束長(zhǎng)度)個(gè)0將編碼寄存器的最后狀態(tài)打出，而TBCC則是直接用碼字的最后K個(gè)比特將編碼寄存器初始化，從而提高編碼率?，F(xiàn)在的3G和4G通信標(biāo)準(zhǔn)中(比如WiMAX或LTE)都采用了TBCC信道編碼。關(guān)于TBCC的譯碼算法很多，其中比較經(jīng)典的譯碼算法有循環(huán)維特比算法(CVA)和BCJR算法。但上述算法由于解碼時(shí)延不固定和復(fù)雜度的原因，均不便于硬件實(shí)現(xiàn)。為此，本文提出了一種便于硬件實(shí)現(xiàn)的次優(yōu)解碼算法。

1 TBCC譯碼算法
1．1 最優(yōu)譯碼算法
    TBCC的理論最優(yōu)譯碼算法是，對(duì)于每一個(gè)可能的初始狀態(tài)(3k)用維特比譯碼算法對(duì)所有可能的狀態(tài)進(jìn)行搜索，最后再根據(jù)最好的狀態(tài)進(jìn)行解碼。但是，這種算法的復(fù)雜度太高，不利于硬件實(shí)現(xiàn)。
1．2 次最優(yōu)譯碼算法
    次最優(yōu)譯碼算法的經(jīng)典代表是CVA算法，此外還有其改進(jìn)的算法比如環(huán)繞維特比算法(WAVA)和雙向維特比算法(BVA)。它們的主要思路是利用圓形buffer將碼字?jǐn)U展成多個(gè)相同碼塊首尾相接的長(zhǎng)碼塊進(jìn)行譯碼。當(dāng)檢測(cè)到首尾狀態(tài)相等或者滿足自適應(yīng)迭代的停止條件時(shí)，即完成譯碼；否則繼續(xù)進(jìn)行迭代。但該算法或其改進(jìn)的WAVA和BVA算法都存在這樣一個(gè)問(wèn)題。那就是解碼的延遲不是固定的，而這非常不便于硬件實(shí)現(xiàn)。
    所以，本文中提出固定延遲的譯碼算法，其基本思路是在碼塊的前Lt個(gè)符號(hào)補(bǔ)在符號(hào)的后面，將碼塊的后Lh個(gè)符號(hào)補(bǔ)在碼字的前面，這樣就構(gòu)成一個(gè)長(zhǎng)度為L(zhǎng)t+N+Lh的新碼塊(假設(shè)原碼字長(zhǎng)度為N)，圖1所示是重構(gòu)的碼塊示意圖。該新碼塊可以按照Z(yǔ)TCC解碼一樣去解碼，然后從具有最小路徑度量(path metric)的狀態(tài)進(jìn)行回溯。

    圖2所示是其譯碼算法流程圖。其中Lt和Lh參數(shù)的選擇應(yīng)根據(jù)仿真來(lái)確定。這里采用典型值：Lt=72，Lh=96。

2 TBCC譯碼算法的實(shí)現(xiàn)
2．1 分支度量(branch metric)的計(jì)算
    維特比譯碼算法采用ML準(zhǔn)則，其分支度量可通過(guò)下式計(jì)算：
   
2．2 加-比較-選擇器(ACS)
    圖3所示是ACS的狀態(tài)轉(zhuǎn)移蝶形圖。實(shí)際上，卷積碼的Trellis圖具有如下性質(zhì)(LTE中TBCC編碼約束長(zhǎng)度為7)：

    對(duì)于每一個(gè)狀態(tài)，其前面的狀態(tài)為i<<1和(i<<1)+32；而對(duì)于每一個(gè)狀態(tài)，其后面的狀態(tài)為(i>>1)％64和(i>>1+1)％64。
    上述性質(zhì)在硬件實(shí)現(xiàn)時(shí)非常好用。由上述性質(zhì)可以給出路徑度量的計(jì)算式：
    
    從上面的公式可以看出。計(jì)算一個(gè)蝶形圖需要4次加法和2次比較。圖4所示是ACS路徑度量蝶形圖。此外，操作時(shí)還可采用Andries的簡(jiǎn)化方法來(lái)減小硬件開(kāi)銷(xiāo)，其公式如下： 

    計(jì)算出需要2次加法。對(duì)于LTE中約束長(zhǎng)度為7的TBCC來(lái)說(shuō)，總共有64個(gè)狀態(tài)，可以分別在兩個(gè)蝶形圖里面使用(符號(hào)會(huì)有所變化)，這樣，加法器就減小為32，加上每個(gè)路徑度量更新還需要一個(gè)加法器，這樣共需要的加法器為32+64=96，比之前未簡(jiǎn)化的算法少用了32個(gè)加法器。
2．3 回溯
    回溯的深度(Trace back Depth)必須大于編碼深度(Coding Depth)，這是因?yàn)?，?jīng)過(guò)回溯CD的長(zhǎng)度，所有的幸存路徑均會(huì)收斂。每次回溯時(shí)，所有幸存路徑都需要從內(nèi)存里面讀出TD個(gè)狀態(tài)，同時(shí)將有TD-CD個(gè)判斷之后的比特送入LIFO?；厮葜?，會(huì)有TD-CD的內(nèi)存空間可寫(xiě)，另外在回溯時(shí)，還需要TD-CD個(gè)內(nèi)存空間來(lái)保存進(jìn)來(lái)的數(shù)據(jù)，這樣，內(nèi)存空間就共需TD+(TD-CD)=2TD-CD。在此可取典型值TD=96，CD=72。
2．4 FPGA的實(shí)現(xiàn)
    本設(shè)計(jì)采用的FPGA芯片為Altera的StratixIIIEP3SL340系列器件，其在QuartusII9．0下綜合出來(lái)的RTL視圖如圖5所示。其布線后所占用的資源如表l所列。

3 仿真驗(yàn)證

    本文采用的開(kāi)發(fā)流程是先在matlab下仿真出浮點(diǎn)算法的性能，然后根據(jù)系統(tǒng)要求用C實(shí)現(xiàn)定點(diǎn)模型，在和浮點(diǎn)的版本比較后，再采用Ver-ilog實(shí)現(xiàn)。由于用verilog做性能仿真比較慢，本文采用的仿真和驗(yàn)證方法是在定點(diǎn)C下做性能仿真，然后將C版本的輸入輸出作為黃金參考數(shù)據(jù)，再用modelsim仿出vetilog版本的數(shù)據(jù)和參考數(shù)據(jù)做對(duì)比，如果數(shù)據(jù)完全一樣，則驗(yàn)證通過(guò)，否則調(diào)試verilog語(yǔ)言并追蹤錯(cuò)誤。
    驗(yàn)證選擇的碼長(zhǎng)為1080，將TBCC解碼器放在4×4 MIMO接收機(jī)里，可得到如圖6所示的SNR曲線。

    由圖6可知，在SNR很小的時(shí)候，TBCC解碼器的性能反而較硬判決會(huì)下降，這是由于SNR太小，TBCC已經(jīng)無(wú)法從很少的已知信息中糾正其他的錯(cuò)誤信息。而當(dāng)SNR較大時(shí)，TBCC解碼器就可以從相對(duì)多的已知信息中糾正錯(cuò)誤信息。由圖6可見(jiàn)，在誤碼率為10-3以下時(shí)，TBCC能夠獲得約2l dB的增益。

4 結(jié)束語(yǔ)
    該解碼器已經(jīng)用在MIMO接收機(jī)的FPGA版本中。并且經(jīng)過(guò)實(shí)驗(yàn)室測(cè)試，能夠成功的解碼出咬尾卷積編碼，并具有較好的性能。另外，該解碼器在實(shí)現(xiàn)上用的硬件資源很少，這可為整個(gè)系統(tǒng)的集成奠定基礎(chǔ)。