一種多維網(wǎng)格編碼譯碼器的高效FPGA設(shè)計*

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

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

?

一種多維網(wǎng)格編碼譯碼器的高效FPGA設(shè)計*

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

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

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

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

關(guān)鍵詞：狀態(tài)約束；網(wǎng)格編碼調(diào)制；乒乓環(huán)；流水； FPGA

0引言

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

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

1多維網(wǎng)格編碼簡介

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

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

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

圖1　幾種擴(kuò)頻方式比較

如圖1為多維網(wǎng)格編碼與傳統(tǒng)擴(kuò)頻方式之間的比較。從上到下，依次為非編碼擴(kuò)頻方式，編碼擴(kuò)頻方式，TCM級聯(lián)擴(kuò)頻方式，多維網(wǎng)格編碼方式?？梢郧逦目吹?，將編碼，調(diào)制與擴(kuò)頻整合到了一個步驟中考慮，這為多維網(wǎng)格編碼帶來更大的編碼增益。

2多維網(wǎng)格編碼的編譯碼算法

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

2.1編碼算法

編碼步驟[1][2]主要為：根據(jù)n，D構(gòu)造狀態(tài)轉(zhuǎn)移表，初態(tài)計算，狀態(tài)轉(zhuǎn)移計算，多維映射四步。

(1)首先根據(jù)S=nD構(gòu)建構(gòu)造一個狀態(tài)轉(zhuǎn)移表，由此表可以根據(jù)輸入與當(dāng)前狀態(tài)得到下一狀態(tài)。

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

(3)根據(jù)1構(gòu)造的狀態(tài)轉(zhuǎn)移表與2得到的初始狀態(tài)β，由輸入信號得到一個閉合網(wǎng)格狀態(tài)轉(zhuǎn)移序列。當(dāng)編碼模塊長度L≥D+1時，編碼序列所產(chǎn)生的閉合網(wǎng)格環(huán)路是唯一的。

(4)利用多維信號對狀態(tài)轉(zhuǎn)移進(jìn)行符號映射。

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

2.2譯碼算法

譯碼時采用迭代循環(huán)移位BCJR算法[3]。

由于狀態(tài)轉(zhuǎn)移序列是一個閉合環(huán)路，可以證明將輸入序列作k位移位后所對應(yīng)的狀態(tài)轉(zhuǎn)移序列是移位前輸入序列對應(yīng)狀態(tài)轉(zhuǎn)移序列的k位移位。這個性質(zhì)可以有效的保證多維網(wǎng)格編碼以最大正確概率譯碼。

(2)初始化狀態(tài)轉(zhuǎn)移矩陣γi。

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

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

αt=αt-1γt-1

(1)

(2)

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

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

βt-1=γt-1βt

(3)

(4)

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

α0=αL,βL=β0

(5)

然后回到3，繼續(xù)迭代更新α，β。

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

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

圖2碼長32的多維網(wǎng)格編碼性能比較

3多維網(wǎng)格編碼高速譯碼器設(shè)計

一般來講，信道碼的譯碼算法復(fù)雜度遠(yuǎn)遠(yuǎn)高于其編碼算法復(fù)雜度，其譯碼延遲的大小往往決定了譯碼器能否用于實時通信系統(tǒng)中[7-9]。為充分發(fā)揮多維網(wǎng)格編碼短碼的優(yōu)勢，本節(jié)設(shè)計了一種高效多維網(wǎng)格編碼譯碼器實現(xiàn)方案。

3.1歸一化算法改進(jìn)

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

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

(6)

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

(7)

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

進(jìn)一步的將歸一化算法改寫為：

(8)

(9)

仿真結(jié)果表明，經(jīng)該算法改進(jìn)后，采用9比特量化時，誤碼曲線與浮點時基本重合。

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

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

3.2狀態(tài)轉(zhuǎn)移矩陣γi簡化

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

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

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

(10)

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

3.3四級流水結(jié)構(gòu)

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

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

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

(2)狀態(tài)轉(zhuǎn)移矩陣初始化。

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

(4)迭代中止，譯碼。

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

圖3　四級流水結(jié)構(gòu)

3.4乒乓環(huán)結(jié)構(gòu)

在四級流水結(jié)構(gòu)中，當(dāng)?shù)谝患壍挠嬎憬Y(jié)果送入第二級時，第一級已經(jīng)處于空閑狀態(tài)。但是由于第二級計算時需要用到第一級在存儲器中的計算結(jié)果，因此這時第一級雖然空閑，但卻只能空等，只有等到第二級計算結(jié)束將結(jié)果存放至第二級存儲器時，第一級才能接收新的數(shù)據(jù)。對于后面三級同理。

因此，雖然插入了流水結(jié)構(gòu)，但依然存在模塊的空閑等待，這種等待將導(dǎo)致譯碼延遲的大大增加。

按照前述的流水結(jié)構(gòu)劃分，采用乒乓環(huán)的結(jié)構(gòu)，可有效降低各級資源的空閑等待時間，如圖4所示。

圖4　四級乒乓環(huán)流水結(jié)構(gòu)

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

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

4仿真及資源消耗

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

圖5　原始算法仿真結(jié)果

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

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

圖6是考慮歸一化修正，采用四級流水乒乓環(huán)結(jié)構(gòu)，同時優(yōu)化γi的仿真結(jié)果。由于關(guān)鍵路徑的縮短，最高時鐘達(dá)到了224 M。譯碼延遲為7 858個操作時鐘。

圖7是采用XST綜合得到的RTL級原理圖。該圖可以很清晰的反應(yīng)出四級流水模塊的互連結(jié)構(gòu)。

圖7　RTL級綜合結(jié)果

表1是布局布線后的一些關(guān)鍵參數(shù)列表?？梢钥吹皆撛O(shè)計資源占有量很少，不到所選器件資源的10%。因此可以采用多路并行處理，進(jìn)一步提高譯碼器的吞吐率，減小譯碼延遲。

表1　FPGA實現(xiàn)后關(guān)鍵參數(shù)列表

5結(jié)束語

作為TCM與擴(kuò)頻系統(tǒng)的一種結(jié)合，多維網(wǎng)格編碼可以同時獲得編碼與擴(kuò)頻增益，在實時通信中有良好的應(yīng)用前景?；诙嗑S網(wǎng)格編碼譯碼算法的特點，本文提出了一種易于硬件實現(xiàn)的多維網(wǎng)格編碼譯碼器。該譯碼器，在結(jié)構(gòu)、存儲空間和時序上得以較大的優(yōu)化，極大降低了資源消耗與譯碼延遲。目前該該譯碼器已成功應(yīng)用于某高速系統(tǒng)中，性能穩(wěn)定，可靠。本設(shè)計具有較強(qiáng)的靈活性，能通過較小的修改而適應(yīng)不同的多維網(wǎng)格編碼，后續(xù)將用廣闊的應(yīng)用前景。

參考文獻(xiàn)：

[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系統(tǒng)設(shè)計與仿真[J]. 通信技術(shù)，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編碼調(diào)制技術(shù)研究[D].西安 西安電子科技大學(xué)，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]雷赟. 網(wǎng)格編碼調(diào)制技術(shù)的研究及其在VHF跳頻通信系統(tǒng)中的應(yīng)用[D].西安 西安電子科技大學(xué)，2012.

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

[8]唐星.帶寬有效編碼調(diào)制技術(shù)研究[D].武漢 華中科技大學(xué)，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—)，男，碩士，工程師，主要研究方向為編譯碼、高速數(shù)據(jù)鏈、抗干擾通信；

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

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

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

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

文獻(xiàn)標(biāo)志碼：A

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

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

doi:10.3969/j.issn.1002-0802.2015.07.022