基于預(yù)譯碼技術(shù)的Turbo碼譯碼方法

，，，

(南京理工大學(xué)電子工程與光電技術(shù)學(xué)院， 江蘇 南京 210094)

0 引言

早在1948年，現(xiàn)代數(shù)字通信的奠基人香農(nóng)從理論上證明了只要信息傳輸速率小于信道容量，總存在一種編碼方式使得錯誤概率任意小。自定理[1]提出以來，學(xué)者們提出了眾多的編碼方式，不斷朝著香農(nóng)限逼近，但是距離香農(nóng)極限還存在不小差距。直到1993年，C.Berrou,A.Glavieux和P.Thitimasjshima在國際通信會議上提出了Turbo碼[2]，其優(yōu)異的性能引起了廣大學(xué)者的研究熱潮。目前,Turbo碼被看作是網(wǎng)格編碼調(diào)制技術(shù)問世以來,信道編碼理論研究上所取得的最偉大的技術(shù)成就,具有里程碑的意義。雙二進制Turbo碼在編碼效率、譯碼時延、糾錯性能等方面優(yōu)于傳統(tǒng)的Turbo碼。但現(xiàn)有雙二進制Turbo碼譯碼器對預(yù)譯碼所得信息利用率較低。本文針對此問題，提出了基于預(yù)譯碼技術(shù)的Turbo碼譯碼方法，以及減小FPGA實現(xiàn)復(fù)雜度的方法。

1 編譯碼原理

編碼器決定了一種碼的性能，譯碼器最大限度地挖掘這種碼的優(yōu)勢，Turbo碼的優(yōu)異性能來自于巧妙的編碼結(jié)構(gòu)和循環(huán)迭代譯碼思想。

1.1 編碼原理

圖1所示為雙二進制Turbo碼編碼器結(jié)構(gòu)，交織器消除兩個子碼之間的相關(guān)性，突發(fā)錯誤下交織器有利于級聯(lián)碼的糾錯[3]，刪余器通過對校驗位進行刪余提高碼率。與傳統(tǒng)Turbo碼不同的是輸入序列是由兩個比特信息位組成的符號，因此得名雙二進制Turbo碼。信息位輸入分為兩個支路，每個支路由A,B兩路組成，開關(guān)打到上支路，A,B兩路送入編碼器，輸出三路校驗位V,Y,W，開關(guān)打到下支路，A,B兩路通過交織器再送入編碼器，輸出三路校驗位V′，Y′，W′。最后通過刪余器可以形成多種速率的編碼輸出。

分量碼編碼器采用自截尾[4-5]的循環(huán)遞歸系統(tǒng)卷積碼。傳統(tǒng)的編碼器采用添加全零尾比特使得編碼器的初始狀態(tài)和終止?fàn)顟B(tài)全為零，但是雙二進制Turbo碼由于交織器的存在不能保證兩個分量碼編碼器終止?fàn)顟B(tài)同時為零。自截尾機制原理是在確定生成矩陣的情況下，通過數(shù)學(xué)推導(dǎo)可以推導(dǎo)出只與信息位長度和預(yù)編碼末狀態(tài)有關(guān)的查找表,查找表所得即為循環(huán)狀態(tài)Sc,預(yù)編碼即編碼器初始狀態(tài)為零的一次編碼。

在數(shù)學(xué)推導(dǎo)前，我們定義編碼器的生成矩陣為G，k時刻編碼器狀態(tài)為Sk，k時刻輸入序列為Pk，則可用下式表示該卷積編碼器：

Sk+1=GSk+Pk

(1)

由上式進行遞推可得到編碼器初始狀態(tài)與終止?fàn)顟B(tài)的關(guān)系表達(dá)式：

(2)

為了實現(xiàn)自截尾機制，要求S0=SN=Sc，即：

(3)

由上式可知循環(huán)狀態(tài)Sc存在的條件是I+GN可逆，觀察式(2)和式(3)可得如下關(guān)系式：

(4)

對于圖1所示編碼器，根據(jù)式(4)可列出如下查找表[6]。

表1 循環(huán)狀態(tài)查找表Tab.1 Look-up table of Circular state

表1為圖1的查找表，雙二進制Turbo碼編碼分為兩步，首先，編碼器初始狀態(tài)為零進行編碼，編碼終止?fàn)顟B(tài)作為列索引，信息長度模7作為行索引進行查表，查表所得即為正式編碼的循環(huán)狀態(tài)Sc。最后，將預(yù)編碼所得循環(huán)狀態(tài)作為編碼器的初始狀態(tài)進行編碼，編碼所得序列即為最終編碼。

1.2 譯碼原理

Turbo碼常用的算法有SOVA算法[7]，MAP算法[8]以及改進的MAP算法。SOVA算法復(fù)雜度上低于MAP算法，但是性能較差。目前常用的是MAX-LOG-MAP算法[9]。

圖2所示的框圖是下文介紹的譯碼算法的整體框圖。該算法分成預(yù)譯碼和正式譯碼，預(yù)譯碼估計編碼的循環(huán)狀態(tài)Sc。預(yù)譯碼和正式譯碼的內(nèi)部結(jié)構(gòu)相同，在FPGA實現(xiàn)時，預(yù)譯碼和正式譯碼可以共用一個模塊，節(jié)省FPGA資源，降低實現(xiàn)復(fù)雜度。

(5)

在這里引入三個遞歸矩陣，分別為前向遞歸矩陣αk(s)，分支度量矩陣γk(s′，s)，后向遞歸矩陣βk(s)，其數(shù)值代表編碼器該時刻各個狀態(tài)的概率，公式(5)可以轉(zhuǎn)換為這三個矩陣的表達(dá)式[10]，如下所示：

(6)

最后根據(jù)后驗似然比進行判決。由于編碼器采用了自截尾，所以αk(s)和βk(s)的初始狀態(tài)都為循環(huán)狀態(tài)，但對于接收端的譯碼器循環(huán)狀態(tài)是未知的，故需要先進行預(yù)譯碼估計循環(huán)狀態(tài)再進行譯碼[11-13]。

1.2.1預(yù)譯碼

式(7)和式(8)分別是前向遞歸矩陣αk(s)，后向遞歸矩陣βk(s)的遞歸公式：

(7)

(8)

由公式可知αk(s)和βk(s)分別是由α0(s)和βN(s)根據(jù)分支度量矩陣γk(s′，s)遞推而得的，但是預(yù)譯碼前不知初始狀態(tài)，所以假設(shè)初始狀態(tài)在每個狀態(tài)的可能性是相等的，即：

α0(s)=2-m,s=0,1,2,…,2m-1

(9)

βN(s)=2-m,s=0,1,2,…,2m-1

(10)

α0(s)通過前向遞推得到的αN(s)正是終止?fàn)顟B(tài)的概率分布，經(jīng)過多次迭代，取最后一次迭代所得的αN(s)，得到：

(11)

同理，β0(s)正是初始狀態(tài)的概率分布：

(12)

(13)

1.2.2正式譯碼

正式譯碼與預(yù)譯碼整體框架一致，只是α0(s)和βN(s)的初始狀態(tài)與預(yù)譯碼時有所不同：

α0(s=Sc)=1,α0(s≠Sc)=0

(14)

βN(s=Sc)=1,βN(s≠Sc)=0

(15)

其中，Sc為預(yù)譯碼所得的循環(huán)狀態(tài)。

上文提到的前向遞歸矩陣αk(s)和后向遞歸矩陣βk(s)是根據(jù)分支度量矩陣γk(s′，s)遞推得到的，在預(yù)譯碼后確定了兩個遞歸矩陣的初始狀態(tài)，然后再由式(7)和式(8)遞歸出αk(s)和βk(s)，所以確定γk(s′，s)后就能遞推得到所有的衡量矩陣。

2 基于預(yù)譯碼的譯碼方法

在Turbo出現(xiàn)以前，信道編碼使用的算法是最大似然算法(ML)，它假設(shè)信源輸出0,1是等概率出現(xiàn)的，是一種次優(yōu)的譯碼算法。香農(nóng)信息論指出最優(yōu)的譯碼算法是最大后驗概率算法(MAP)，Turbo碼譯碼器采用了最大后驗概率算法，但正式譯碼的第一次譯碼迭代將信源符號假設(shè)為等概率出現(xiàn)，下文將介紹一種利用預(yù)譯碼為正式譯碼提供先驗信息的方法，以及一種減小FPGA運算量的方法。

2.1 一種利用預(yù)譯碼為正式譯碼提供先驗信息的方法

Turbo碼譯碼還存在另一種譯碼方式，即不進行循環(huán)狀態(tài)的預(yù)估計，將預(yù)譯碼作為一次完整的譯碼，對預(yù)譯碼所得的后驗似然比直接進行判決，得到譯碼數(shù)據(jù)。我們在AWGN信道下進行了仿真，如圖3所示。編碼器為圖1所示，碼率為1/3，幀長2 808 bit，BPSK調(diào)制，預(yù)譯碼迭代6次。雖然預(yù)譯碼直接進行判決性能較差，但其后驗似然比是有效的。

受該譯碼方法的啟發(fā)，可將預(yù)譯碼所得的后驗似然比轉(zhuǎn)換為后驗概率作為正式譯碼的先驗概率。圖4所示為改進后的譯碼框圖，其中L(μk)為預(yù)譯碼所得的后驗似然比。

根據(jù)式(5)，我們可以由后驗似然比L(μk)反推出每個符號的后驗概率：

P(μk=0|Y)=(1+eL(μk=1)+
eL(μk=2)+eL(μk=3))-1

(16)

P(μk=i|Y)=eL(μk=i)×
(1+eL(μk=1)+eL(μk=2)+eL(μk=3))-1
i=1,2,3

(17)

正式譯碼時將P(μk|Y)作為每個符號的先驗概率。

2.2 一種分支度量矩陣生成的方法

圖1所示的分量編碼器狀態(tài)機為3位，有8個狀態(tài)，在某個狀態(tài)下，根據(jù)輸入的2位信息位可向下一個狀態(tài)轉(zhuǎn)移，故在某狀態(tài)下可向4個不同的狀態(tài)轉(zhuǎn)移，所以分支度量矩陣在某時刻有32個分支，并且每個分支有確定的信息位和校驗位。

譯碼器的輸入為軟信息，本文所用的軟信息為3比特量化，故可將軟信息轉(zhuǎn)化為8個可信度等級，然后可用下表計算分支度量矩陣每條分支的可信度，由于運算是在對數(shù)域上進行的，所以下表的可信度是負(fù)值的。

行索引為該分支對應(yīng)的信息位或者校驗位，列索引為輸入的軟信息，查表所得為該分支可信度的一個度量。以四分之一碼率編碼器為例，譯碼器中的一個子譯碼器每個時刻有2位信息位和3位校驗位，則該子譯碼器的分支度量矩陣中一條分支的可信度為5個度量之和。

表2 可信度查找表Tab.2 Look-up table of reliability

我們定義k時刻收到的信息位為ak和bk，校驗位為wk、yk、vk，信息位和校驗位都為3比特，k時刻第i條分支理論的信息位為Ak,i和Bk,i，校驗位為Wk,i，Yk,i，Vk,i，則k時刻分支度量矩陣的生成公式為：

γk,i=〈Ak,i|ak〉+〈Bk,i|Bk〉+
〈Wk,i|wk〉+〈Yk,i|yk〉+〈Vk,i|vk〉
i=1,2,3,…,32

(18)

式中，〈|〉符號代表查找表所得的數(shù)值。

3 仿真與FPGA實現(xiàn)

我們使用Matlab對改進后的譯碼方法進行了性能仿真，編碼器為圖1所示，碼率為1/3，幀長2 808 bit，AWGN信道，BPSK調(diào)制，預(yù)譯碼迭代3次，正式譯碼迭代3次。

圖3仿真曲線直接對預(yù)譯碼的后驗似然比進行判決，誤比特率明顯降低，說明預(yù)譯碼的后驗似然比是具有參考價值的。通過式(16)和式(17)將后驗似然比轉(zhuǎn)換為后驗概率并作為正式譯碼的先驗概率加快了譯碼的收斂速度，由仿真圖5可知改進后能提高約0.3 dB的性能。并且該方法沒有對譯碼結(jié)構(gòu)和譯碼迭代次數(shù)進行改變，所以譯碼時延以及資源消耗和改進前保持一致。

關(guān)于γk(s′，s)的生成，我們采用了可信度查找表的方法，還有一種常用的方法是歐氏距離生成法。我們對兩種生成方式在AWGN信道下進行了仿真，如圖6所示。編碼器為圖1所示，碼率為1/3，幀長2 808 bit，BPSK調(diào)制，預(yù)譯碼迭代3次，正式譯碼迭代3次。兩者性能基本沒有差別，但是可信度查找表的方法較歐氏距離生成法計算量小很多。

在實現(xiàn)方面，本文所用的FPGA為Spartan3系列的xc3s2000，時鐘頻率為38.4 MHz。圖7所示為FPGA實現(xiàn)的總框圖，其中實線表示數(shù)據(jù)流向，虛線表示控制信號或地址。圖1編碼器中兩個分量碼的結(jié)構(gòu)一致，所以譯碼器的兩個分量碼譯碼器可以共用一個模塊以節(jié)省FPGA資源?？刂颇K控制譯碼迭代次數(shù)，信息序列的交織以及后驗似然比的解交織。圖7中分量碼譯碼器與似然比存儲器形成了一個環(huán)路，在控制模塊的控制下，分量碼譯碼器對信息序列進行順序譯碼和交織譯碼，迭代次數(shù)滿足停止準(zhǔn)則后，斷開環(huán)路對最后一次迭代得到的符號似然比進行判決輸出。順序譯碼指信息序列和對應(yīng)校驗序列有序輸入分量碼譯碼器進行譯碼，交織譯碼指信息序列交織后和對應(yīng)校驗序列輸入分量碼譯碼器進行譯碼。交織映射表存儲器在控制模塊控制下，為輸入數(shù)據(jù)緩沖器和似然比存儲器提供交織地址。

由于FPGA資源和譯碼時延的限制，輸入的數(shù)據(jù)為3 bit量化，譯碼迭代次數(shù)為6次，其中3次預(yù)譯碼迭代，3次正式譯碼迭代,在時鐘頻率為38.4 MHz的情況下，一次迭代FPGA耗時5 ms左右。

4 結(jié)論

本文提出了基于預(yù)譯碼技術(shù)的Turbo碼譯碼方法，該方法將預(yù)譯碼所得的后驗似然比轉(zhuǎn)換為后驗概率并作為正式譯碼的先驗概率，仿真結(jié)果表明該方法可以提升0.3 dB的譯碼性能，并且譯碼時延以及資源消耗和改進前保持一致。最后修改了分支度量矩陣生成方式，與歐式距離生成法譯碼性能差不多，時延降低，在時鐘頻率為38.4 MHz的情況下，一次迭代FPGA耗時為5 ms左右。

參考文獻:

[1]Shannon C E. A mathematical theory of communication[J]. Bell System Tech. J.,1948(1):876-878.

[2]Berrou C, Glavieux A, Thitimajshima P. Near shannon limit error-correcting coding and decoding： Turbo codes[C]// in Proc. 1993 Int. Conf. Comm,1993(2):1064-1070.

[3]郝天鐸,王可人,金虎,等.不同錯誤圖樣分布對級聯(lián)碼譯碼性能的影響[J].探測與控制學(xué)報,2015,36(3)：86-90.

[4]Berrou C, Douillard C, Jézéquel M. Multiple parallel concatenation of circular recursive convolutional (CRSC) codes[J]. Annals of Telecommunications, Tome 54, N°3-4, 2000:21-24.

[5]Anderson J B, Hladik S M. Tailbiting MAP decoders[C]// IEEE J. Sel, Areas Commun, 1998,16(2):297-302.

[6] Soleymani MR,Gao Yingzi,Vilaipornsawai.Turbo coding for Satellite and Wireless Communications[M].Massachusetts：Kluwer Academic Publishers,2002.

[7] Hagenauer J, Hoeher P. A Viterbi algorithm with soft-decision out-puts and its applications[C]// in Proc. Global Telecommunications Conf,1989(3):1680-1686.

[8] Bahl l, Cocke J, Jelinek F, et al. Optimal decoding of linear codes for minimizing symbol error rate[C]// IEEE Trans. Inf. Theory, 1974:284-287.

[9] Roberston P, Villebrun E, Hoeher P. A comparison of optimal and sub-optimal MAP decoding algorithms operatiting in the log domain[C]// in Proc. IEEE Int. Conf. Communications, 1995:1009-1013.

[10] 朱益.雙二進制Turbo碼的研究[D].杭州：浙江大學(xué),2008.

[11] Im S B, Kim M G, Choi H J. An Efficient Tail-biting MAP Decoder for Convolutional Turbo Codes in OFDM System[C]// IEEE Region 10 Conference, TENCON 2004 Volume B,2004：589-592.

[12] Giancristofaro D, Bartolazzi A. Novel DVB-RCS standard Turbo Code：details and performances of a decoding algorithm[C]// ESA conference, 2001:467-469.

[13] Douillard C, Jezequel M, Berrou C, The Turbo code Standard for DVB-RCS[C]// 2nd International Symposium on Turbo Codes & Related Topics, Brest, France, 2000:535-538.