一種多維網格編碼譯碼器的高效FPGA設計*

蘭　天，那寶玉，甘　明，張　劍

(1.中國電子科技集團公司第十研究所，四川 成都 610036；2.全軍后勤信息中心，北京 100036)

?

一種多維網格編碼譯碼器的高效FPGA設計*

蘭天1，那寶玉2，甘明1，張劍1

(1.中國電子科技集團公司第十研究所，四川 成都 610036；2.全軍后勤信息中心，北京 100036)

修回日期：2015-06-08Received date:2015-03-20；Revised date：2015-06-08

摘要：為在實時通信系統中有效利用多維網格編碼調制(MDTCM)的短碼特性，設計了一種適合FPGA實現的高效多維網格編碼譯碼器。在該設計中，提出了一種易于硬件實現的改進歸一化譯碼算法，采用四級流水線和乒乓環結構，并充分利用譯碼算法中的固有特性，有效降低了資源消耗和譯碼延遲。測試表明，該設計簡單可靠，性能穩定，易于移植擴展，非常適合實時通信場合的應用，目前該譯碼器已成功應用于某實時通信系統中。

關鍵詞：狀態約束；網格編碼調制；乒乓環；流水； FPGA

0引言

無線實時通信系統往往需要具備較強的誤碼糾錯能力，同時又有很小的通信延遲要求。常用的一些信道碼，如Turbo、LDPC等雖然可以很好滿足糾誤碼性能的要求，但卻由于編碼模塊較長，會導致高的譯碼延遲。多維網格編碼可以滿足這些要求。但由于多維網格編碼在譯碼時采用了迭代BCJR算法，其中涉及大量的矩陣運算，乘加運算，因而設計實現時極可能導致高譯碼延遲，從而不能體現其短碼結構在譯碼延時上帶來的好處。

針對上述問題，本文提出了一種易于硬件實現的修正歸一化算法，采用四級流水線，及乒乓環結構，利用算法特性，有效降低了資源消耗和譯碼延遲。

1多維網格編碼簡介

傳統的網格編碼調制[1](TCM)將信道編碼與調制聯合考慮，通過擴展調制信號集可以在不擴展帶寬的情況下獲得編碼增益，但一般應用于帶限系統, 在很多擴頻系統中，編碼與調制仍是單獨考慮的。

多維網格編碼[2-6]可以看作是TCM在功率受限系統中的擴展。它將擴頻與編碼調制有機的結合起來，可以很方便的同跳時，跳頻，直擴系統配合使用。它不再著眼于帶寬的不擴展，而是通過多維的星座點映射，以在網格圖上獲得更好的自由歐氏距離。

從網格圖路徑形式上講，多維網格編碼采用循環編碼，可得到一種具有短碼結構的網格編碼，它滿足狀態約束，即對于輸入的編碼序列，保證在網格圖上產生的狀態轉移序列具有循環碼特性，且起始狀態等于結束狀態。這種狀態轉移的循環特性克服了傳統TCM必須使用尾比特將網格狀態歸零，從而降低編碼效率的缺點。由于不需要一個固定的起始或結束狀態，這對于編譯碼將帶來一個明顯的好處，即對于一個固定的輸入序列，通過在網格圖上得到的閉合路徑是唯一的，這為最終譯碼的良好性能提供了保證。

圖1　幾種擴頻方式比較

如圖1為多維網格編碼與傳統擴頻方式之間的比較。從上到下，依次為非編碼擴頻方式，編碼擴頻方式，TCM級聯擴頻方式，多維網格編碼方式。可以清晰的看到，將編碼，調制與擴頻整合到了一個步驟中考慮，這為多維網格編碼帶來更大的編碼增益。

2多維網格編碼的編譯碼算法

為方便后續討論,作如下參數說明,定義(n,D)，n為每個狀態的輸出分支數，即輸入信號集的大小；D為網格深度，即從起始狀態，到達所有可達狀態的最小步數。由此可見對于(n,D)，其網格圖上一共有nD個狀態。L為碼長，N為信號維數。

2.1編碼算法

編碼步驟[1][2]主要為：根據n，D構造狀態轉移表，初態計算，狀態轉移計算，多維映射四步。

(1)首先根據S=nD構建構造一個狀態轉移表，由此表可以根據輸入與當前狀態得到下一狀態。

(2)輸入長度為k≥D+1的序列i1,i2,i3,…,ik，計算得到初狀態β。

(3)根據1構造的狀態轉移表與2得到的初始狀態β，由輸入信號得到一個閉合網格狀態轉移序列。當編碼模塊長度L≥D+1時，編碼序列所產生的閉合網格環路是唯一的。

(4)利用多維信號對狀態轉移進行符號映射。

一般的，映射信號的維數越高，所得的路徑在網格圖上的自由歐氏距離越大，性能也就越好，不過所需的帶寬的也越寬，因此往往需要在帶寬與性能之間折中。

2.2譯碼算法

譯碼時采用迭代循環移位BCJR算法[3]。

由于狀態轉移序列是一個閉合環路，可以證明將輸入序列作k位移位后所對應的狀態轉移序列是移位前輸入序列對應狀態轉移序列的k位移位。這個性質可以有效的保證多維網格編碼以最大正確概率譯碼。

(2)初始化狀態轉移矩陣γi。

(3)前向狀態度量α0初始化。

(4)更新α1,α2,…,αL，其中：

αt=αt-1γt-1

(1)

(2)

(5)后向狀態度量βL初始化。

(6)更新β0,β1,…,βL-1，其中：

βt-1=γt-1βt

(3)

(4)

(7)迭代終止判決，滿足判決條件則停止迭代，更新γi，得到硬判決結果，否則令：

α0=αL,βL=β0

(5)

然后回到3，繼續迭代更新α，β。

(8)將得到的結果反向循環移位k，即得最終譯碼結果。

圖2給出了N=12時，(4,2)碼與(4,3)碼編碼長度為32比特的性能曲線。從圖中可以看出，(4,3)碼較(4,2)碼有大致1db的增益，這是通過狀態數的增加來獲得的，即(4,3)碼有64狀態，而(4,2)碼只有16狀態。當然狀態數越多編譯碼的復雜度也就越高。

圖2碼長32的多維網格編碼性能比較

3多維網格編碼高速譯碼器設計

一般來講，信道碼的譯碼算法復雜度遠遠高于其編碼算法復雜度，其譯碼延遲的大小往往決定了譯碼器能否用于實時通信系統中[7-9]。為充分發揮多維網格編碼短碼的優勢，本節設計了一種高效多維網格編碼譯碼器實現方案。

3.1歸一化算法改進

在譯碼算法的第4，6兩步，對αt，βt歸一化時涉及到除法運算，這對于硬件實現比較困難。為此，作如下修正：

αt=αt/(max(αt)/Δ)

(6)

βt=βt/(max(βt)/Δ)

(7)

其中p為量化位寬，Δ=2p-1。

進一步的將歸一化算法改寫為：

(8)

(9)

仿真結果表明，經該算法改進后，采用9比特量化時，誤碼曲線與浮點時基本重合。

事實上，改進的歸一化過程也是一個按比例縮放的過程，與原始的歸一化算法一樣，同樣控制了歸一化后的α，β元素值在0與1之間。因此不會對最終的譯碼判決有影響。

改進后，整個歸一化過程可以通過簡單的左移或右移來實現，避免了求和與除法運算，這將極大的消減硬件資源開銷。

3.2狀態轉移矩陣γi簡化

從前一節對譯碼算法的介紹可以看到，在迭代譯碼中所涉及的矩陣乘加運算與γi有關。反復的矩陣運算，除了乘加運算時間，還將帶來大量的讀寫延遲。一個S×S的矩陣一次完整的讀寫周期為2S2，隨S成平方增長。

事實上，由于γi表示的是狀態轉移概率矩陣。由BCJR算法可知大部分狀態跳轉是不允許的，即：

p(St=m|St-1=m′)=0

(10)

因此γi里的元素大部分是0，即γi是一個稀疏矩陣。由于可跳轉狀態是根據狀態轉移表所固定的，因此非零元素在γi中的位置也是固定的。所以只需要根據狀態轉移表，更新γi中的非零位置，這樣可以大大減少迭代過程中的運算與讀寫時延。這樣可使與γi有關的計算量減少至約為原來的(n·n)/(nD·nD)。

3.3四級流水結構

從以上譯碼算法介紹可知，一次完整的譯碼步驟較多，如果簡單的按照算法順序，逐步計算，即使考慮了γi的計算的簡化，也勢必造成高譯碼延遲，因此考慮使用流水結構。

根據譯碼算法特性，本文將譯碼過程分解為四個功能上相對獨立的步驟：

(1)初始狀態計算與序列移位。

(2)狀態轉移矩陣初始化。

(3)前向后向狀態度量迭代更新。

(4)迭代中止，譯碼。

根據此四步，考慮采用四級流水結構，這樣可以提高譯碼器的吞吐率，加快譯碼速度。同時，由于流水線的插入，關鍵路徑得到了分割，電路可以工作在更高的時鐘頻率。四級流水結構如圖3所示。

圖3　四級流水結構

3.4乒乓環結構

在四級流水結構中，當第一級的計算結果送入第二級時，第一級已經處于空閑狀態。但是由于第二級計算時需要用到第一級在存儲器中的計算結果，因此這時第一級雖然空閑，但卻只能空等，只有等到第二級計算結束將結果存放至第二級存儲器時，第一級才能接收新的數據。對于后面三級同理。

因此，雖然插入了流水結構，但依然存在模塊的空閑等待，這種等待將導致譯碼延遲的大大增加。

按照前述的流水結構劃分，采用乒乓環的結構，可有效降低各級資源的空閑等待時間，如圖4所示。

圖4　四級乒乓環流水結構

從圖4可以看出，各級之間使用了兩個一樣的存儲器。第一級首先將計算結果存入1a存儲器中。此時第二級開始從1a存儲器中取數計算，同時第一級接收新的數據計算，將計算結果存入1b存儲器中。

第二級在計算完1a中數據后，又馬上開始從1b中取數計算。而第一級又開始接收新的數據，將計算結果存入1a中。如此交替循環，避免了各級的空閑等待，可大大減少了譯碼延遲。

4仿真及資源消耗

本節以編碼長度為32，N=12的(4,2)碼為例，給出了譯碼器設計結果。選用芯片為XILINX的V5SX50T芯片。

圖5　原始算法仿真結果

圖5為按照原始譯碼算法，一次順序譯碼，只考慮歸一化算法修正的仿真結果。譯碼延遲為38 603個操作時鐘，最高時鐘為114 M。

圖6采用四級流水并簡化算法后的仿真結果

圖6是考慮歸一化修正，采用四級流水乒乓環結構，同時優化γi的仿真結果。由于關鍵路徑的縮短，最高時鐘達到了224 M。譯碼延遲為7 858個操作時鐘。

圖7是采用XST綜合得到的RTL級原理圖。該圖可以很清晰的反應出四級流水模塊的互連結構。

圖7　RTL級綜合結果

表1是布局布線后的一些關鍵參數列表。可以看到該設計資源占有量很少，不到所選器件資源的10%。因此可以采用多路并行處理，進一步提高譯碼器的吞吐率，減小譯碼延遲。

表1　FPGA實現后關鍵參數列表

5結束語

作為TCM與擴頻系統的一種結合，多維網格編碼可以同時獲得編碼與擴頻增益，在實時通信中有良好的應用前景。基于多維網格編碼譯碼算法的特點，本文提出了一種易于硬件實現的多維網格編碼譯碼器。該譯碼器，在結構、存儲空間和時序上得以較大的優化，極大降低了資源消耗與譯碼延遲。目前該該譯碼器已成功應用于某高速系統中，性能穩定，可靠。本設計具有較強的靈活性，能通過較小的修改而適應不同的多維網格編碼，后續將用廣闊的應用前景。

參考文獻：

[1]Ungerboeck G. Channel Coding with Multilevel/Phase Signals[J]. IEEE TransInf. Theory, 1982, 55-67.

[2]WANG Qi, WEI Lei. Iterative Viterbi Algorithm for Concatenated Multidimensional TCM[J]. IEEE Transactions on Communication，2002(1): 12-15.

[3]Kamalakar Ganti, Jeffrey C Dill. Symbol Assignment for High-Rate Circular Trellis-based Turbo Codes[C]. IEEE WCNC，2008, 1056-1060.

[4]郭晶, 魏東興. SOSTTC-OFDM系統設計與仿真[J]. 通信技術，2010,9(43):76-78.

GUO Jin, WEI Dong-xin. Application of Super-Orthogonal Space-Time Trellis Codes in MIMO-OFDM System[J]. Communications Technology,2010,09(43):76-78.

[5]王玨. 多維TCM及CPM編碼調制技術研究[D].西安 西安電子科技大學，2012.

WANG Jue. Research on Multidimensional Trellis-Coded Modulation and Continuous-Phase Modulation Techniques[D]. Xi an: Xidian University, 2012.

[6]Priya K H, Tamilarasi M. A Trellis-Coded Modulation Scheme with 32-Dimensional Constant Envelope Q2PSK Constellation[C]. ICCSP, 2013(1): 821-825.

[7]雷赟. 網格編碼調制技術的研究及其在VHF跳頻通信系統中的應用[D].西安 西安電子科技大學，2012.

LEI Yun. Research on TCM and Its Application Within VHF Hop Communication System[D]. Xi an: Xidian University, 2012.

[8]唐星.帶寬有效編碼調制技術研究[D].武漢 華中科技大學，2012.

TANG Xing. Research on Bandwith Efficient Code-Modulation Technique[D]. WU Han: The Huazhong University of Science and Technology, 2012.

[9]CHEN Yi-hua, SU Mei-lin, NI Yi-fan. Implementation of Trellis Coded Modulation Encode on SDR Communication System[C]. ICEMI, 2013(2):687-691.

蘭天(1982—)，男，碩士，工程師，主要研究方向為編譯碼、高速數據鏈、抗干擾通信；

那寶玉(1979—)，男，博士，工程師，主要研究方向為軍隊后勤信息化；

甘明(1978—)，男，碩士，高級工程師，主要研究方向為高速數據鏈、高速編譯碼；

張劍(1975—)，男，博士，高級工程師，主要研究方向為新型數據鏈、抗干擾通信。

An Efficient FPGA Design of MDTCM Decoder

LAN Tian1，NA Bao-yu2,GAN Ming1，ZHANG Jian1

(1.No.10 Institute of CETC, Chengdu Sichuan 610036, China;

2.Logistics Information Centre of PLA, Beijing 100036，China)

Abstract：Aiming at the effectively-used the short-code characteristics of MDTCM in real-time communication system, an efficient design of MDTCM decoder is proposed. Based on this, a modified normalization decoding algorithm suitable for hardware implementation is designed. With four-pipeline and ping-pang loop structure, and by taking full advantage of the intrinsic characteristics of decoding algorithm, the resource consumption and decoding delay are effectively reduced. Practical test show that this design, being simple, reliable and stable, and easy to transplant and extend, is suitable for real-time communication system, and now this decoder is successfully applied to certain real-time communication system.

Key words：state constraint;TCM;ping pang loop;pipeline;FPGA

作者簡介：

中圖分類號：TN850.3

文獻標志碼：A

文章編號：1002-0802(2015)07-0860-05

收稿日期：*2015-03-20；

doi:10.3969/j.issn.1002-0802.2015.07.022