，，，

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

0 引言

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

1 編譯碼原理

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

1.1 編碼原理

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

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

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

Sk+1=GSk+Pk

(1)

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

(2)

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

(3)

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

(4)

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

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

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

1.2 譯碼原理

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

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

(5)

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

(6)

最后根據(jù)后驗(yàn)似然比進(jìn)行判決。由于編碼器采用了自截尾，所以αk(s)和βk(s)的初始狀態(tài)都為循環(huán)狀態(tài)，但對(duì)于接收端的譯碼器循環(huán)狀態(tài)是未知的，故需要先進(jìn)行預(yù)譯碼估計(jì)循環(huán)狀態(tài)再進(jìn)行譯碼[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)在每個(gè)狀態(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)通過(guò)前向遞推得到的αN(s)正是終止?fàn)顟B(tài)的概率分布，經(jīng)過(guò)多次迭代，取最后一次迭代所得的αN(s)，得到：

(11)

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

(12)

(13)

1.2.2正式譯碼

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

α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ù)譯碼后確定了兩個(gè)遞歸矩陣的初始狀態(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)的譯碼算法是最大后驗(yàn)概率算法(MAP)，Turbo碼譯碼器采用了最大后驗(yàn)概率算法，但正式譯碼的第一次譯碼迭代將信源符號(hào)假設(shè)為等概率出現(xiàn)，下文將介紹一種利用預(yù)譯碼為正式譯碼提供先驗(yàn)信息的方法，以及一種減小FPGA運(yùn)算量的方法。

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

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

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

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

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)

正式譯碼時(shí)將P(μk|Y)作為每個(gè)符號(hào)的先驗(yàn)概率。

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

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

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

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

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

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

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

(18)

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn):

[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]郝天鐸,王可人,金虎,等.不同錯(cuò)誤圖樣分布對(duì)級(jí)聯(lián)碼譯碼性能的影響[J].探測(cè)與控制學(xué)報(bào),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] 朱益.雙二進(jìn)制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.