陸連偉,馮占斌

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

Turbo乘積碼譯碼器的并行實現方法*

陸連偉,馮占斌

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

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

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

0 引 言

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

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

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

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

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

1 TPC譯碼器結構

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

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

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

該結構譯碼器的吞吐量受困于TPC碼字的行數M和列數N,當采用較大的M和N時,譯碼器吞吐量很低,下面介紹一種并行結構的譯碼器。

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

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

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

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

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

圖3 信息存儲器結構Fig.3 Messagememory construction

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

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

2 改進的分量譯碼器算法

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

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

算法的譯碼過程如下:

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

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

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

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

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

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

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

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

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

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

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

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

ω0=0(當前候選碼字的錯誤圖樣權重),

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

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

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

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

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

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

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

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

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

a)對當前的試探序列,根據伴隨子s計算糾錯以后的錯誤圖樣(候選碼字對應的錯誤圖樣),并計算對應的權重。

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

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

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

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

如果j＞1,則判斷每個比特是否存在競爭碼字,并存儲競爭碼字對應的權重。如果≥ω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)產生下一次迭代的試探錯誤圖樣,并更新伴隨子,擴展比特和權重。

s=s⊕Hpi,Hpi是校驗矩陣H的第pj列對應的值;

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)充分利用相鄰兩個試探錯誤圖樣具有很強相關性的特性,大大簡化了伴隨子及錯誤圖樣權重的計算,在FPGA實現時,使用的時鐘個數由M個(列譯碼時)或N個(行譯碼器時)減少為一個時鐘就可以完成,減少分量譯碼器時間,從而提高整個譯碼器數據吞吐量;

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

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

3 結 語

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

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

[1] 王寧,陳名松,杜曉萍.Turbo碼的研究及仿真[J].通信技術,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