基于FPGA 的Turbo 碼快速實現算法*

朱勝利

（中國電子科技集團公司第十研究所，四川 成都 610036）

0 引言

信道編碼是通信系統的一個重要組成部分，是提高通信系統可靠性的重要手段。它的性能好壞直接影響通信質量。香農于1948 年發表了他的開創性論文《通信的數學理論》，并提出了著名的有噪信道編碼定理[1]。信道編碼定理指出：任何一個通信信道都有確定的信道容量C，如果通信系統所要求的傳輸速率R＜C，則存在一種編碼方法，當碼長充分大并應用最大似然譯碼（Maximum Likelihood Decoding，MLD）時，信息的錯誤概率可以任意小。信道編碼定理奠定了糾錯編碼理論的基石。

香農用信道編碼定理說明了逼近信道容量“好碼”的存在性，美中不足的是其并沒有給出構造“好碼”的實用方法。實際中，當要求通信的差錯概率很低時，將迫使通信系統采用碼長很長的編碼，從而使得譯碼算法變得異常復雜而難以實現。因此，在香農編碼定理出現后的的相當一段時間內，隨機編碼理論僅僅作為分析、證明編碼理論的工具，而如何構造這種性能逼近香農限的“好碼”從而讓其應用于實踐，并未引起人們足夠的重視。

經過大量研究，BERROU 等人于1993 年提出了一種新的信道編碼方案——Turbo 碼[2]。為了實現隨機編碼的思想，他們將卷積編碼和隨機交織器巧妙地結合在一起，并采用軟輸出迭代譯碼來逼近最大似然譯碼，從而獲得幾乎接近香農理論極限的譯碼性能。這一理論成果的公布立即在編碼界引起轟動，也為香農隨機編碼理論的應用奠定了基礎。

Turbo 碼是級聯碼的一種，常用的是并行級聯卷積碼（Parallel Concatenated Convolutional Code，PCCC）。該碼是由兩個獨立遞歸系統卷積碼（Recursive Systematic Convolutional，RSC）構成的并行級聯碼[3]。除此之外，有學者提出了串行級聯卷積碼（Serial Concatenated Convolutional Code，SCCC）[4]。本文研究對象為PCCC。交織器的存在讓Turbo 碼中加入了近似隨機成分，使其能夠達到非常接近香農限的性能。事實上，Turbo 碼的性能與香農限僅僅相差0.7 dB。Turbo 碼的級聯結構還有一個好處是其可以將短碼變為長碼，從而大大擴展其應用范圍。Turbo 碼的出現標志著信道編碼理論與技術研究進入了一個嶄新的階段，結束了長期以來人們將信道截止速率作為實際容量的歷史，同時改變了人們構造“好碼”的傳統觀念。

一般而言，信道編碼通過舍棄一部分信道容量來獲得糾錯能力的提升。舍棄部分信道容量主要表現為在編碼器的輸出中加入部分與輸入比特相關的校驗比特，以提高糾錯能力，但由于校驗比特的加入使得編碼效率下降。通常情況下，要在編碼效率和誤比特率之間取得一定平衡。刪余作為提高碼率的一種主要方法，本質上是按照某種規律固定地刪除編碼器輸出信息中的部分比特，刪除比特的多少最終決定Turbo 碼的碼率。為了讓接收端能夠更準確的譯碼，刪余器需要準確指出被刪除校驗比特的位置，一般情況下采用刪余矩陣來表示。刪余操作的存在使得Turbo 碼能夠靈活輸出各種不同碼率的碼字，從而適應不同的應用場景。

目前，國外許多大學和研究機構都在進行Turbo 碼的研究，且已有幾家公司能夠提供與Turbo碼有關的產品；國內也有很多高校在研究Turbo 碼在相關領域的應用。Turbo 碼具有接近香農限的性能，特別適用于對功率要求嚴格的場合，如能源極端受限的深空及衛星通信中，以及為了降低被發現的概率而要求發射信號功率盡可能低的軍事通信中。另外，Turbo 碼近似隨機碼，有很好的距離特性，因而有很強的抗衰落和抗干擾能力。目前，Turbo碼已經成為第三代移動通信系統的標準之一[5]，也已經開始有關其關鍵技術的標準化，如3GPP LTE及Wimax 等無線標準組織紛紛將其作為其信道編碼方式。此外，Turbo 碼在文本傳輸和數據存儲等方面也有應用。

Turbo 編碼的硬件實現一直都是Turbo 碼研究的重要課題，也是將Turbo 推向商業化應用的基礎和難點。目前，業界對Turbo 碼譯碼算法的研究較多[6-11]，而對其編碼的硬件實現研究相對較少。時述有等人提出了一種基于FPGA 的Turbo 碼編碼算法，交織器采用實時產生的方式，當碼長很長時時序控制變得相當困難[12]。張永超等人分別利用數字信號處理（Digital Signal Process，DSP）和現場可編程邏輯門陣列（Field Programmable Gate Array，FPGA）對Turbo 碼的編碼進行了研究分析，指出了兩種實現方式的優劣，對工程實踐具有一定的參考[13]。沈業兵等人提出了一種突發通信中Turbo碼編譯碼的FPGA 實現方案[14]。藺吉順等人針對CCSDS 標準Turbo 碼提出了一種性能較好的編碼實現方法，但由于編碼過程利用ROM 表實現，不利于算法的實時擴展[15]。

針對現有算法的不足和具體項目的工程需要，基于FPGA 提出了一種可以實現不同碼長、不同碼率的Turbo 碼編碼方法。該方法實現資源消耗較少，硬件結構簡單，可擴展性好，時序穩定，具有較強的工程實踐價值。

1 Turbo 碼簡介

Turbo 碼一般由兩個反饋的RSC 分量編碼器和一個交織器并行連接而成，校驗位經過刪余處理后得到不同碼率的碼字[16]。RSC 編碼器只輸出編碼的校驗序列，然后通過刪余進行碼率調整，與原始信息序列一起輸出得到Turbo 碼的編碼輸出序列。一種常用的Turbo 碼編碼器，如圖1 所示。

圖1 Turbo 編碼器的結構

Turbo 碼編碼時輸入信息X1，第一路直接進入編碼器1 進行編碼，輸出校驗序列O1；原始信息經過交織器進行交織處理，以增加信息的隨機性。交織之后的信息序列X2 送入編碼器2 進行編碼，輸出校驗序列O2。編碼器1 和編碼器2 的輸出送入刪余處理模塊生成特定碼率的Turbo 碼，刪余之后的數據和原始信息序列復用生成最后的碼字。

分量編碼器是Turbo 碼邊編碼中非常重要的一環，其設計的好壞直接決定了Turbo 碼的糾錯性能。Turbo 碼的發明者之一Thitimajshima 在研究Turbo碼的分量碼時發現，信噪比對分量碼的誤比特性能具有重要影響。高信噪比時，非系統卷積碼優于系統卷積碼；低信噪比時，系統卷積碼優于非系統卷積碼。另外，循環編碼器可以改善碼的比特誤碼率性能。實際中，Turbo 碼的優勢主要體現在低信噪比條件下，因此Turbo 碼分量碼一般選擇系統卷積碼。Turbo 碼RSC 編碼器的結構，如圖2 所示。

圖2 Turbo 碼RSC 編碼器的結構

從圖2 可以看出，該分量編碼器的記憶深度為4，對應16 種狀態。該分量編碼器由后向連接多項式g1=1+x3+x4和前向連接多項式g2=1+x+x3+x4共同組成，對應的多項式生成矩陣為：

1.1 交織器

交織器對Turbo 碼具有重要作用，主要作用是提高低重序列的輸出碼重和減小譯碼輸出之間的相關性。交織器直接影響Turbo 碼的距離譜和性能，可以提高Turbo 碼的抗突發錯誤的能力，還可以改善Turbo 碼的重量分布，最終在接收端使用基于SISO 的迭代譯碼算法可以降低誤碼率（Symbol Error Rate，BER）。一般而言，Turbo 碼的交織器主要有分組交織器和偽隨機交織器兩種類型，而偽隨機交織器可以獲得更好的編碼性能。本文采用CCSDS 推薦的交織器，具體采用二次置換多項式交織器。該交織器對存儲空間的需求較少，操作簡便，復雜度較低，結構靈活，性能優良。

對于指定的信息塊長度k，交織算法如下進行。

令k=k1*k2。對于s=1,2,…,k，π(s)可以表示為：

1.2 刪 余

如圖1 所示，正常情況下如果不存在刪余（打孔），則使用兩個RSC 分量編碼器的Turbo 編碼輸出的碼率為1/3。也就是說，在編碼序列中，每3個比特中僅有1 個信息比特和2 個校驗比特。為了得到不同碼率的Turbo 編碼，有選擇地刪除編碼輸出序列中的一些冗余校驗位是很有必要的，而這一過程由刪余操作來完成。

刪余通常是按周期、有規律進行的。以碼率為1/n的Turbo 碼為例，定義一個刪除周期，假設為T。在每個周期內，共有T個信息輸入到編碼器，經編碼后得到nT編碼比特。與nT個編碼比特相聯系的是一個n×T的刪余矩陣P，具有如下形式：

刪余矩陣P中的元素Pij取值為1 或者0，1 表示對應位置的編碼比特被容許輸出，0 表示對應位置雖然存在編碼比特但是不會輸出。從信息傳輸的角度來看，這些不被輸出的比特被刪除了，也是刪余的含義。對于前面提到的Turbo 碼，可以通過如下刪余舉證得到1/2 碼率的Turbo 碼：

2 算法簡介

首先，兩個分量編碼器的所有寄存器初始化為0，運行一個周期（486+0）bit，從而產生一個長為980 bit 的碼塊。每個周期的前486 bit，輸入開關在低位接收輸入數據，最后4 bit 開關切換到高位，從移位寄存器中接收反饋信號。該反饋和最左邊的加法器反饋抵消，從而對寄存器進行清零操作。寄存器清零期間，編碼器仍將繼續輸出非零編碼序列。系統的未編碼輸出包括486 個原始信息比特和最后移位寄存器中的數據。

假設分量編碼1 的輸出為O1=[O1,1O1,2O1,3…O1,490]，編碼器2 的輸出為O2=[O2,1O2,2O2,3…O2,490]，之后結合信息序列打孔復用后得到整體輸出980 bit的碼字。

根據Turbo 碼的編碼結構，基于FPGA 的Turbo編碼器設計的關鍵在于RSC 編碼器的設計、交織模塊的設計、打孔模塊的設計以及各模塊時序的控制。在實際工程應用時，數據流是按要求組幀的。這就要求Turbo 碼對相同的輸入狀態產生相同的輸出結果，意味著在每一次編碼完畢后需要對分量編碼器的寄存器清零。而兩個分量編碼器的寄存器能否同時歸零對Turbo 碼的性能具有一定的影響。

對于卷積碼而言，要使編碼網格終止比較簡單，只需在輸入信息序列后加入m（編碼約束長度）個0 即可。但是，對于系統遞歸卷積碼編碼器，由于有反饋的存在，編碼器的狀態很難確定，添0 的策略并不能達到網格終止的目的。此外，由于交織器的存在，編碼器1 回到全0 狀態時，編碼器2 不一定回到全0 狀態。業界學者提出了很多比較實用的方法，最簡單的是在輸入端設置開關電路來實現網格的終止。另一種方法是只對RSC 編碼器1 的信息序列后加入m個0 比特，使其狀態回到全0，而對編碼器2 不做處理，可以在任何狀態停止編碼。這樣僅僅喪失了一定的性能。本文中采用數據末尾補1 的做法。

對于交織器的實現，業界主要有兩種實現方式：一種是根據交織關系，利用FPGA 實時產生交織器的輸出；另一種使用ROM 表，即利用軟件工具如MATLAB，根據交織關系產生交織輸出，并存儲于ROM 表中。實際上，當交織長度增加時，利用第一種方法實現編碼會帶來很大延遲，不利于Turbo編碼的實現。本文主要使用第二種實現方式，將交織關系存儲于ROM 表，方便調用。在數據交織時，數據通過一個偽雙口RAM，順序寫入，而讀出時則根據ROM 表輸出的數據讀出。因為ROM 表中的數據其實是原始信息下標的交織序列，對應RAM的讀出地址。當面對不同的交織關系時，只需替換增加對應的ROM 表即可。

基于以上設計原則及技術需求，所提基于FPGA 的Turbo 碼編碼算法的流程如圖3 所示。

圖3 算法流程

如圖3 所示，算法實現時，對于每一幀數據，首先在幀尾補m個1 得到新的信息序列，其中m為RSC 移位寄存器的深度。這樣可以使得每一幀編碼完畢后兩個RSC 移位寄存器的狀態均歸零，然后對補“1”之后的信息序列和對應的交織序列分別進行編碼。圖3 左側是編碼器2 的主要編碼路徑，右側是編碼器1 的編碼路徑。因為編碼器2 的輸入數據要先進行交織處理，交織后的輸出序列相對原始信息序列存在一定的延遲。為了對齊兩個編碼器的輸入，需要對送入編碼器1 的信息序列進行延遲處理。數據對齊后，兩個編碼器同時進行編碼。最后，為了得到不同碼率的Turbo 碼，對兩個編碼器輸出校驗比特通過刪余模塊進行刪余處理。由于刪余模塊每次輸出多個比特，為了得到連續輸出，先將刪余之后數據的使能進行隔斷，達到時序控制的目的，之后利用串轉換模塊將使能不連續的并行數據轉化為使能連續的串行數據輸出，從而完成編碼。

整個Turbo 編碼的核心是分量編碼器的實現。為了給出詳細的編碼實施方案，圖4 給出了分量編碼器的具體實現過程。

如圖4 所示，分量編碼器按比特進行編碼。每次輸入1 bit，輸出時按不同的碼率輸出多個比特。編碼從第1 個比特開始，輸入比特信息后需要計算反饋多項式的反饋量Fd。以具有4 個反饋移位寄存器的RSC 為例，假設其值為lfsr(4)、lfsr(3)、lfsr(2)、lfsr(1)，則反饋值Fd 為lfsr(4)與lfsr(3)的異或，然后計算寄存器的更新量ad=Fd xor lfsr(4)，進而得到兩比特輸出。Dout1 是輸入信息比特din，而Dout2 是寄存器更新值ad 與lfsr(4)、lfsr(3)、lfsr(1)異或的結果，即Dout2=ad xor lfsr(1) xor lfsr(3) xor lfsr(4)。完成一次編碼輸出后需要更新移位寄存器，由寄存器更新值ad 替換lfsr(1)的值，原1、2、3 位置的值左移即可，及lfsr（4 to 3）=lfsr（3 to 1），lfsr（1）=ad。寄存器更新后，繼續下一比特的編碼。編碼時，考慮到移位寄存器的清零需求，需要對輸入數據的數量進行判斷。當i ＜Len+1，即還未到對寄存器清零時，輸入下一個比特繼續上邊的編碼過程；若不然，則與上面過程不同的是，寄存器的更新值ad永遠為零。之后對輸入信息數量進行判斷，如果i ＜Len+4，則繼續下一個比特的編碼，否則說明已經完成當前所有比特信息的編碼，且編碼器狀態已經清零，編碼結束，直到下一幀數據到來再繼續以上編碼。

圖4 分量編碼器的實現流程

3 仿真分析

為了驗證算法的有效性，在Xilinx 公司的XC7VX690T 芯片上實現了Turbo（486，980）的編碼。表1 是整個Turbo 編碼器消耗的主要硬件資源，其中包括為了實現編碼器而存在的數據產生、對外接口處理等必要模塊。從表1 可以看出，算法實現占用的硬件資源十分少，說明該編碼器實現復雜度低、硬件資源消耗少等優勢。

表1 主要硬件資源消耗

為了進一步驗證算法的有效性，本文使用Xilinx 旗下ISE 軟件自帶的Isim Simulator 對所提算法中的主要功能模塊進行仿真。針對分量編碼器的仿真結果如圖5 所示。

圖5 中din 為輸入串行的信息比特數據，din_valid 為其對應的使能，編碼器的輸出為dout，對應輸出使能為dout_valid。可以看到，輸出dout 為并行4 位的，這是為了支持不同的碼率，而4 位輸出可以支持到1/6 Turbo 編碼。

圖5 Turbo 分量編碼器的仿真結果

刪余處理模塊的仿真結果，如圖6 所示。以1/2 碼率來說，它的編碼矩陣為P=[1 0；0 1]，即Turbo 編碼輸出的4 bit 中，除了信息位，校驗位根據需要取編碼器1 或者2 的輸出。圖6 中，din_valid 表示編碼器的輸出使能。由于在此之前對兩個編碼器的輸入做了數據對齊處理，因此兩個編碼器的輸出共用一個使能。Index 決定輸出哪一個編碼器的校驗位，dout 和dout_valid 分別表示模塊的輸出及使能。

圖6 刪余處理模塊仿真結果

從前面的描述可以看出，目前Turbo 碼的輸出中信息位和校驗位是并行的。為了根據不同的碼率將其轉換為串行數據，考慮到信息位和校驗位的關系，將刪余模塊的輸出使能進行隔斷，具體操作時需要根據碼率來調整輸出使能的狀態，方便后續模塊的處理。另外，為了適應后續處理模塊對時鐘頻率的不同要求，這里通過fifo 對時鐘進行適配處理。數據隔斷模塊的仿真結果如圖7 所示。

圖7 碼率調整，數據隔斷模塊仿真結果

圖7 中：wr_clk 表示寫時鐘；rd_clk 表示讀時鐘；din 表示打孔輸出后的數據，即刪余模塊的輸出；din_valid 是其對應連續使能；rate 表示碼速率，00指1/2；dout 和dou_valid 分別表示輸出信息及輸出使能。可以看出，dout_valid 已不再連續，在1/2 碼率下數據隔一拍輸出一次。

編碼數據使能隔斷后，需要對編碼數據進行并串轉換處理并讓輸出使能連續。這部分工作由并串處理模塊完成。對應Isim 的仿真結果如圖8 所示，其中dout_valid 為最終編碼輸出使能。可以看到，dout_valid 從之前的隔斷狀態更新為連續狀態。

圖8 并串轉換模塊仿真結果

4 結語

針對實際工程的需求，提出了一種基于FPGA的Turbo 碼快速實現算法。該算法首先利用仿真軟件生成交織關系，存儲于ROM 表中用于交織路RSC 的編碼。相比于實時交織關系計算，利用ROM 表實現使得交織序列的延遲較小且固定，利于編碼之前交織序列和原信息序列的對齊，同時更易控制時序。在每一幀數據后添加“1”，使得每一幀數據編碼后兩路RSC 的移位寄存器能夠同時歸零。為了兩路RSC 能夠同時進行編碼，對信息序列進行延遲處理。為了得到特定碼率的Turbo 碼以適應不同的工程需求，對編碼模塊輸出的兩路校驗序列進行刪余處理，同時隔斷使能信號以輸出完整的Turbo 碼字。隔斷使能使得特定碼率Turbo 碼的產生時序易于控制，便于后續并串轉換模塊的處理。此外，利用Isim Simulator 軟件仿真驗證了所提方法正確性，并在Xilinx 的XC7VX690T 芯片上驗證了編碼器的有效性。仿真及實際工程應用說明，該編碼器結構簡單，硬件資源消耗少，且易于擴展，性能良好，具有較強的工程參考及實踐價值。