Turbo乘積碼譯碼器的并行實現(xiàn)方法*

陸連偉,馮占斌

(廣州海格通信集團股份有限公司,廣東廣州510663)

Turbo乘積碼譯碼器的并行實現(xiàn)方法*

陸連偉,馮占斌

(廣州海格通信集團股份有限公司,廣東廣州510663)

本文介紹了Turbo乘積碼(TPC)的串行和并行譯碼器結(jié)構(gòu),提供了一種TPC譯碼器的并行實現(xiàn)方法,該方法對譯碼器乘積碼的P(P≥8)行或列進行并行譯碼,在性能不下降的情況下,顯著提高了譯碼器的吞吐量。與此同時,文中對傳統(tǒng)的分量譯碼器算法——CHASE算法進行了改進,改進后的譯碼器縮短了譯碼周期,從而進一步提高了吞吐量。本文設(shè)計的譯碼器結(jié)構(gòu)適用于多子碼的TPC譯碼器,可實現(xiàn)不同碼字的兼容。

Turbo乘積碼 迭代譯碼 并行譯碼 CHASE算法

0 引 言

Turbo碼具有接近香農(nóng)極限的優(yōu)越性能[1],它的出現(xiàn)是信道編碼研究中的一項重大突破,被稱為二十一世紀(jì)的糾錯編碼。Turbo乘積碼(TPC)作為Turbo碼在譯碼算法上的延伸,且譯碼復(fù)雜度較低,也受到了世界范圍內(nèi)信息和編碼理論界的關(guān)注,并成為該領(lǐng)域近幾年來研究的熱點。

TPC為塊狀碼,一般由兩個或兩個以上的分組碼經(jīng)編碼后成為二維、三維或多維的編碼塊。這里的分組碼在乘積碼中常稱為子碼,這些子碼可以相同也可以不同,可以是BCH碼、奇偶校驗碼、擴展?jié)h明碼等,并可對乘積碼的編碼塊進行截短,從而構(gòu)成滿足通信系統(tǒng)要求的碼率。目前無線通信系統(tǒng)中,以擴展?jié)h明碼作為子碼的居多[2]。

TPC譯碼算法通常采用軟判決迭代譯碼算法[3-4],該算法對碼字的行和列進行重復(fù)迭代譯碼以此獲得很高的糾錯能力。由于按照串行的方式實現(xiàn)對行和列的譯碼嚴(yán)重影響了譯碼器的吞吐量,因此并行譯碼器的研究成為重點。

文中,我們提供了一種更高效的并行譯碼方法,并對子碼為擴展?jié)h明碼的TPC分量譯碼器進行了改進,經(jīng)過改進后的譯碼器可以成倍提高吞吐量,而同時又不提高存儲需求。

本文結(jié)構(gòu)如下,第1節(jié)介紹TPC串行譯碼結(jié)構(gòu)及本文使用的并行譯碼結(jié)構(gòu),并對并行譯碼結(jié)構(gòu)中存儲單元這一關(guān)鍵模塊做了說明,第2節(jié)介紹改進的分量譯碼器算法[5],最后對本文所做工作進行總結(jié)。

1 TPC譯碼器結(jié)構(gòu)

TPC譯碼通常采用迭代譯碼的方式,其譯碼過程為:計算接收符號的可信度,將可信度排列成矩陣,進行行譯碼和列譯碼,將譯碼得到的信息在行譯碼和列譯碼之間傳遞。

圖1為TPC譯碼器串行迭代一次的框圖[6],圖中行譯碼器需要進行M次譯碼然后再進行列譯碼,列譯碼器需要進行N次譯碼然后再進行下一次迭代的行譯碼,其中M和N分別為TPC乘積碼排列成矩陣之后的行數(shù)和列數(shù)。

圖1 常規(guī)串行TPC譯碼器(1次迭代)Fig.1 Serial TPC decoder(one iteration)

該結(jié)構(gòu)譯碼器的吞吐量受困于TPC碼字的行數(shù)M和列數(shù)N,當(dāng)采用較大的M和N時,譯碼器吞吐量很低,下面介紹一種并行結(jié)構(gòu)的譯碼器。

圖2為本文使用的并行譯碼結(jié)構(gòu)框圖[7],該結(jié)構(gòu)在分量譯碼器中同時進行P行或Q列的譯碼,因此在一次迭代過程中,只需要進行N/P次行譯碼和M/Q次列譯碼,大大降低了一次迭代需要的時鐘,因此可以大幅度提高吞吐量。實際應(yīng)用中,TPC的行碼和列碼一般選用同種類型的碼字,這樣做可以共用分量譯碼器,降低資源需求,此時可以選擇P=Q,且取P為M和N的最大公約數(shù)。

圖2 并行TPC譯碼器(1次迭代)Fig.2 Parallel TPC decoder(one iteration)

本文選用4種擴展?jié)h明碼作為二維TPC的子碼,擴展?jié)h明碼參數(shù)分別為:(8,4)、(16,11)、(32, 26)、(64,57),因此支持16種不同的TPC碼。此時分量譯碼器并行數(shù)可選P=8。

這種并行結(jié)構(gòu)譯碼器較傳統(tǒng)結(jié)構(gòu)譯碼器需要更多資源,并且為了實現(xiàn)并行處理,需要將TPC碼字存儲在不同的存儲器中,以實現(xiàn)并行讀寫。

文獻[7](對應(yīng)文獻《PARALLEL DECODING of TURBO PRODUCT CODES for HIGH DATA RATE COMMUNICATION》)中給出了一種存儲器存儲數(shù)據(jù)的結(jié)構(gòu),但該結(jié)構(gòu)中行存儲器與處理器之間的對應(yīng)關(guān)系與列存儲器與處理器之間的對應(yīng)關(guān)系不同,在譯碼器設(shè)計時需使用額外的電路來選擇對應(yīng)關(guān)系。本文設(shè)計的存儲器存儲數(shù)據(jù)的方法如圖3所示,其中方格中的數(shù)字表示存儲器的編號,pi(i=0,…,7)表示并行處理器,分別對應(yīng)所處理的行子碼或列子碼的位置,由圖可以看出,存儲器與處理器一一對應(yīng)。存儲器中每個方格存儲TPC碼字對應(yīng)位置的一部分數(shù)據(jù),該部分數(shù)據(jù)為(M/P,N/P)的矩陣,所有在這個方格中的信息都存儲到對應(yīng)的存儲器中。在接收數(shù)據(jù)階段,P個存儲器按圖中所示以列的方式存儲接收到的信道信息。下面簡單介紹一下分量譯碼器工作過程中對存儲器的讀取控制。

圖3 信息存儲器結(jié)構(gòu)Fig.3 Messagememory construction

在分量譯碼器并行工作過程中,首先從按順序從左到右排列的P個存儲器中讀取P個待處理數(shù)據(jù),然后根據(jù)上圖中的對應(yīng)關(guān)系,將讀取的P個數(shù)據(jù)進行循環(huán)移位送入相應(yīng)的處理器中。以列碼為(8,4)擴展?jié)h明碼的TPC碼的列譯碼為例,每個存儲單元存儲列碼碼字的一個數(shù)據(jù)。讀取時,第1個時鐘讀取第0行數(shù)據(jù)送入編號相同的處理器中;第2個時鐘讀取第1行數(shù)據(jù),然后向左循環(huán)移動1個數(shù)送給處理器;第3個時鐘讀取第2行數(shù)據(jù),然后向左循環(huán)移動2個數(shù)送給處理器;以此類推,第8個時鐘讀取第7行數(shù)據(jù),然后向左循環(huán)移動7個數(shù)送給處理器,從而完成所有數(shù)據(jù)的讀取工作。

由上面分析可知,每個存儲器存儲的數(shù)據(jù)個數(shù)相同,并且在行譯碼或列譯碼過程中,每次讀取的P個數(shù)據(jù)都是來自不同的存儲器,因此可以實現(xiàn)并行處理。

2 改進的分量譯碼器算法

此處分量譯碼器采用軟輸出譯碼算法——CHASE譯碼算法[8],其性能接近于最大似然譯碼。該算法的基本原理是利用硬判決譯碼器,根據(jù)不同的試探序列產(chǎn)生幾個候選碼字,然后把他們與接收序列進行比較,挑選一個與接收序列有最小軟距離的候選碼字作為譯碼器的輸出碼字。

對于(n+1,k)擴展?jié)h明碼來說(其中n為擴展?jié)h明碼的碼長,k為信息位長度),傳統(tǒng)的CHASE

算法的譯碼過程如下:

2)構(gòu)造2p個試探錯誤圖樣,這些圖樣取遍了p個最不可靠位置上的所有排列。每個圖樣的長度都為n。注意:只有這p個最不可靠位置可以取值{0, 1},其它位置都取0。

3)確定2p個碼字試探序列,j=1,2,…,2p。

b)將伴隨子轉(zhuǎn)化為錯誤位置pj。如果,那么錯誤位置pj=l,否則pj=-1表示沒有錯誤。這里是H的第l列。

c)糾錯得到有效碼字。如果pj≥0,則⊕1。

5)計算有效碼字集的模擬權(quán)重ωj=-,j=1,2,…,2p。

這里使用的是有效碼字與接收碼字的最大相關(guān)值(或者相關(guān)值相反數(shù)的最小值)作為衡量標(biāo)準(zhǔn),在下面的改進算法中我們將使用最小錯誤權(quán)重作為衡量標(biāo)準(zhǔn),即:所有錯誤位置上置信度之和,可以證明兩種度量是等價的。

6)在有效碼字集里尋找最似然碼字d。,這里。

7)對接收的信號計算額外信息

這里ωc,ωd分別是似然碼字d和c的模擬權(quán)重。c是碼字d的競爭碼字,且ci≠di。如果似然碼字d有不止一個競爭碼字,ωc等于具有最小模擬權(quán)重的碼字。如果不存在競爭碼字,可靠值修正因子β用來計算額外信息。注意,β隨著迭代次數(shù)的變化而變化。

從上面的過程我們可以看出,在傳統(tǒng)CHASE算法過程中,第2)、3)、4)、5)、7)步實際上需要進行循環(huán)計算,這在FPGA實現(xiàn)中會占用很多時間資源,對于實現(xiàn)高速的譯碼器來說是不可忍受的。為此,對傳統(tǒng)的CHASE算法做了改進,定義相鄰的兩個試探錯誤圖樣只有一個不同的比特,則改進后的算法如下:

2)初始化試探錯誤圖樣、模擬權(quán)重、伴隨子、擴展比特以及當(dāng)前最似然碼字的每個比特是否存在競爭碼字、競爭碼字的權(quán)重大小等。

=0(除擴展校驗位以外的試探序列的錯誤圖樣權(quán)重),

ω0=0(當(dāng)前候選碼字的錯誤圖樣權(quán)重),

=max,這里max為實現(xiàn)時采用的一個最大值,保證計算出來的所有權(quán)重都比它小(當(dāng)前最似然碼字的錯誤圖樣權(quán)重),

ωmax=0(錯誤圖樣權(quán)重的最大值),

s=(y1,y2,…,yn)HT(伴隨子),

be=()mod2(擴展比特),

flag(i)=0,i=1,…,n+1(第i個比特的競爭碼字是否存在的標(biāo)志),

ccw(i)=max,i=1,…,n+1(第i個比特的競爭碼字存在時,競爭碼字的權(quán)重),

pj∈[1,n](j=1,…,2p-1)是與不同的比特所在的位置(注意:這里使用到了相鄰的兩個測試序列只有一個位置不同的性質(zhì))。

3)執(zhí)行2p次迭代,得到每個比特是否存在競爭碼字,及競爭碼字的權(quán)重大小。

對于第j次迭代(j=1,…,2p),

a)對當(dāng)前的試探序列,根據(jù)伴隨子s計算糾錯以后的錯誤圖樣(候選碼字對應(yīng)的錯誤圖樣),并計算對應(yīng)的權(quán)重。

如果s=0,表明漢明碼沒有錯誤(或無法檢測到錯誤),則tj(i)=(i)(對i∈[1,n]),tj(n+1)=be;ωj=+be*rabs(n+1)。

否則,漢明碼有錯誤,進行糾正。設(shè)s≠0時對應(yīng)的錯誤位置為ls,則tj(i)=(i)(對i∈[1,n],且i≠ls),tj(ls)=(ls)⊕1,tj(n+1)=be⊕1;ωj=+

b)計算當(dāng)前的最似然碼字的試探錯誤圖樣,試探錯誤圖樣的最大值,并判斷每個比特是否存在競爭碼字,及競爭碼字的權(quán)重大小。

如果ωmax＜ωj,則ωmax=ωj。

如果j＞1,則判斷每個比特是否存在競爭碼字,并存儲競爭碼字對應(yīng)的權(quán)重。如果≥ωj,flag(i)=1,ccw(i)=,其中i∈[1,n+1]且(i)≠tj(i);否則,flag(i)=1,ccw(i)=ωj,其中i∈[1,n+ 1],(i)≠tj(i)且ccw(i)＞ωj。

c)產(chǎn)生下一次迭代的試探錯誤圖樣,并更新伴隨子,擴展比特和權(quán)重。

s=s⊕Hpi,Hpi是校驗矩陣H的第pj列對應(yīng)的值;

be=be⊕1

4)計算最似然碼字:d=y⊕。

5)計算外信息。

對于i∈[1,n+1],如果flag(i)=1,則g(i)= (2*d(i)-1)*(ccw(i)-)-ri,

否則,g(i)=(2*d(i)-1)*(wmax-)/p。

從上面的步驟可以看出,改進后的CHASE算法較傳統(tǒng)的CHASE算法主要有如下幾個優(yōu)點:

1)充分利用相鄰兩個試探錯誤圖樣具有很強相關(guān)性的特性,大大簡化了伴隨子及錯誤圖樣權(quán)重的計算,在FPGA實現(xiàn)時,使用的時鐘個數(shù)由M個(列譯碼時)或N個(行譯碼器時)減少為一個時鐘就可以完成,減少分量譯碼器時間,從而提高整個譯碼器數(shù)據(jù)吞吐量;

2)不需要存儲每次計算出來的候選碼字的錯誤圖樣和權(quán)重,輸出外信息時,也不需要對每個比特在所有的候選碼字中進行搜索尋找與最似然碼字比特不同的碼字的最小權(quán)重,只需要根據(jù)得到的是否有競爭碼字的標(biāo)志及對應(yīng)的競爭碼字權(quán)重計算即可,因此節(jié)省了搜索的時間,使用FPGA實現(xiàn)時可以極大地提高吞吐量;

3)不再使用β對沒有競爭碼字的比特進行修正,因此對每次迭代,計算外信息的方法不會因為迭代次數(shù)的變化而變化,便于實現(xiàn)。

3 結(jié) 語

本文對傳統(tǒng)的分量譯碼器算法進行改進,充分利用了錯誤圖案之間的相關(guān)性,降低了伴隨子和錯誤圖樣權(quán)重的計算復(fù)雜度以及計算時間,從而在相同譯碼器結(jié)構(gòu)的條件下,提高了譯碼的吞吐量;處理過程無需存儲譯碼的中間結(jié)果,且每次迭代無需調(diào)整外信息的修正量,因而減少了存儲器的使用,降低了實現(xiàn)復(fù)雜度。

實際系統(tǒng)中,TPC譯碼器通常會使用多種子碼的TPC碼,本文將不同的TPC碼參數(shù)提前進行存儲,再根據(jù)碼字的不同選取相應(yīng)的參數(shù),實現(xiàn)多種碼字共用一個譯碼器,提高了譯碼器的通用性。采用本文介紹的并行譯碼器結(jié)構(gòu),以及改進后的分量譯碼器算法,我們實現(xiàn)了兼容16種碼字的TPC碼譯碼器,在譯碼器輸入時鐘為96 MHz時,實現(xiàn)了50 Mbps吞吐量。

[1] 王寧,陳名松,杜曉萍.Turbo碼的研究及仿真[J].通信技術(shù),2012,45(03):22-27.

WANG Ning,CHEN Ming-song,DU Xiao-ping.Study and Simulation of Turbo Code.Communications Technology:2012,45(03):22-27.

[2] HE Yejun,ZHUGuangxi,LIU Yingzhuang.Turbo Product Codes and Their Application in the 4th Generation Mobile Communication System[J].Proceedings of SPIE, 2003(5284):221-228.

[3] PYNDIANRameshMahendra.Near-Optimum Decoding of Products Codes:Block Turbo Codes[J].IEEE Trans, 1998,46(08):lO03-1010.

[4] WEIXue-fei,Akansu N A.On Parallel Iterative Decoding of ProductCode[J].Proceedings of IEEE VTC,2001 (04):2483-2486.

[5] HIRSTSimon A.,HONARY Bahram,MARKARIAN Garik.Fast Chase A lgorithm withan Application in Turbo Decoding[J].IEEE Transaction on Communications, 2001,49(10):1693-1699.

[6] ARGON Cenk,MCLAUGHLIN Steven W..A Parallel Decoder for Low Latency Decoding of Turbo Product Codes [J].IEEECommunications letters,2002,6(02):70-72.

[7] ZHANG Xiu-jun,ZHAOMing,ZHOU Shi-dong,etc.Parallel Decoding of Turbo Product Codes for High Data Rate Communication[J].The 57th IEEE Semiannual:Vehicular Technology Conference,2003(04):2372-2375.

[8] CHASED.A Class of Algorithms for Decoding Block Codes with Channel Measurement Information[J].IEEE Trans.Inform.Theory,1972(IT-1 8):170-182.

陸連偉(1983—),男,碩士,工程師,主要研究方向為衛(wèi)星無線通信;

LU Lian-wei(1983-),male,M.Sci.,engineer,majoring in satcom wireless communication.

馮占斌(1980—),男,碩士,工程師,主要研究方向為衛(wèi)星無線通信。

FENG Zhan-bin(1980-),male,M.Sci., engineer,majoring in satcom wireless communication.

A Parallel Im p lem entation of TPC Decoder

LU Lian-wei,FENG Zhan-bin
(Guangzhou HAIGE Communications Group Incorporated Company,Guangzhou Guangdong 510063,China)

This paper describes the serial and parallel structures of turbo product codes(TPC),proposes a parallel implementation of TPC to realize simultaneous decoding of P(P≥8)row-wise or column-wise code vectors of a product code,thus the decoding throughput is obviously raised without any performance degradation.Furthermore,the traditional decoder algorithm——CHASE algorithm,is modified,and this modified algorithm could reduce the decoding cycle and thus further increse the throughput.The proposed decoder architecture is applied to TPC decoder ofmulti-subcode and could achieve compatibility of among different codons.

Turbo product code;iterative decoding;parallel decoding;CHASE algorithm

TN914.31

A

1002-0802(2014)12-1371-04

10.3969/j.issn.1002-0802.2014.12.005

2014-08-26;

2014-10-15 Received date：2014-08-26;Revised date：2014-10-15