基于預譯碼技術的Turbo碼譯碼方法

，，，

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

0 引言

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

1 編譯碼原理

編碼器決定了一種碼的性能，譯碼器最大限度地挖掘這種碼的優勢，Turbo碼的優異性能來自于巧妙的編碼結構和循環迭代譯碼思想。

1.1 編碼原理

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

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

在數學推導前，我們定義編碼器的生成矩陣為G，k時刻編碼器狀態為Sk，k時刻輸入序列為Pk，則可用下式表示該卷積編碼器：

Sk+1=GSk+Pk

(1)

由上式進行遞推可得到編碼器初始狀態與終止狀態的關系表達式：

(2)

為了實現自截尾機制，要求S0=SN=Sc，即：

(3)

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

(4)

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

表1 循環狀態查找表Tab.1 Look-up table of Circular state

表1為圖1的查找表，雙二進制Turbo碼編碼分為兩步，首先，編碼器初始狀態為零進行編碼，編碼終止狀態作為列索引，信息長度模7作為行索引進行查表，查表所得即為正式編碼的循環狀態Sc。最后，將預編碼所得循環狀態作為編碼器的初始狀態進行編碼，編碼所得序列即為最終編碼。

1.2 譯碼原理

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

圖2所示的框圖是下文介紹的譯碼算法的整體框圖。該算法分成預譯碼和正式譯碼，預譯碼估計編碼的循環狀態Sc。預譯碼和正式譯碼的內部結構相同，在FPGA實現時，預譯碼和正式譯碼可以共用一個模塊，節省FPGA資源，降低實現復雜度。

(5)

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

(6)

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

1.2.1預譯碼

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

(7)

(8)

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

α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)正是終止狀態的概率分布，經過多次迭代，取最后一次迭代所得的αN(s)，得到：

(11)

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

(12)

(13)

1.2.2正式譯碼

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

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

(14)

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

(15)

其中，Sc為預譯碼所得的循環狀態。

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

2 基于預譯碼的譯碼方法

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

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

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

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

根據式(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所示的分量編碼器狀態機為3位，有8個狀態，在某個狀態下，根據輸入的2位信息位可向下一個狀態轉移，故在某狀態下可向4個不同的狀態轉移，所以分支度量矩陣在某時刻有32個分支，并且每個分支有確定的信息位和校驗位。

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

行索引為該分支對應的信息位或者校驗位，列索引為輸入的軟信息，查表所得為該分支可信度的一個度量。以四分之一碼率編碼器為例，譯碼器中的一個子譯碼器每個時刻有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)

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

3 仿真與FPGA實現

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

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

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

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

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

4 結論

本文提出了基于預譯碼技術的Turbo碼譯碼方法，該方法將預譯碼所得的后驗似然比轉換為后驗概率并作為正式譯碼的先驗概率，仿真結果表明該方法可以提升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]郝天鐸,王可人,金虎,等.不同錯誤圖樣分布對級聯碼譯碼性能的影響[J].探測與控制學報,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].杭州：浙江大學,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.