一種改進(jìn)的Turbo 碼全并行譯碼算法迭代停止準(zhǔn)則*

趙瑞祥，潘克剛，王欣婷

（陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210001）

0 引言

Turbo 碼是一種性能優(yōu)異的信道編碼方式，編碼復(fù)雜度低，糾錯(cuò)性能好，通用性較強(qiáng)，技術(shù)成熟，在各個(gè)領(lǐng)域中得到了廣泛應(yīng)用[1]。但是，Turbo 碼通用譯碼算法采用串行迭代的譯碼方式，在更高業(yè)務(wù)速率、更低傳輸時(shí)延的應(yīng)用場(chǎng)景中面臨巨大的挑戰(zhàn)。

長(zhǎng)期演進(jìn)技術(shù)（Long Term Evolution，LTE）系統(tǒng)中Turbo 碼采用分塊并行譯碼思想，通過二次項(xiàng)置換多項(xiàng)式（Quadratic Permutation Polynomials，QPP）交織器[2]實(shí)現(xiàn)了整個(gè)碼塊的部分并行譯碼，但是譯碼算法固有的串行性使吞吐量受到了極大限制。

直到Turbo 碼全并行譯碼算法[3]的提出，將整個(gè)碼塊的每個(gè)子塊大小分割成了1 bit，獲得了最大的并行度。對(duì)于全并行譯碼算法，后續(xù)又進(jìn)行了深入研究和完善，包括改進(jìn)的EXIT 圖[4]、Turbo 均衡算法的研究以及在GPU、VLSI 等各種硬件上的實(shí)現(xiàn)[5]。通過對(duì)全并行譯碼算法硬件架構(gòu)的改進(jìn)，證實(shí)其可以實(shí)現(xiàn)超過15 Gb/s 的高吞吐量和最低0.42 μs的時(shí)延[6]。但是，全并行譯碼算法要達(dá)到傳統(tǒng)譯碼算法的性能，需要增加約6 倍的譯碼迭代次數(shù)。

針對(duì)全并行譯碼算法迭代次數(shù)過多的問題，對(duì)比分析多種譯碼迭代停止準(zhǔn)則，對(duì)基于外信息絕對(duì)值信噪比（SNR Based on the Absolute Value of Extrinsic Information，SBAE）準(zhǔn)則[7]進(jìn)行了優(yōu)化，并區(qū)分不同信噪比結(jié)合符號(hào)不同率（Sign Difference Ratio，SDR）準(zhǔn)則[8]，提出了一種改進(jìn)的迭代停止準(zhǔn)則，在保證譯碼性能的前提下，有效降低了迭代次數(shù)。第1 節(jié)簡(jiǎn)要介紹Turbo 碼的全并行譯碼算法和常用的迭代停止準(zhǔn)則；第2 節(jié)詳細(xì)描述改進(jìn)的迭代停止準(zhǔn)則的原理和方法；第3 節(jié)在LTE 系統(tǒng)條件下進(jìn)行性能仿真和對(duì)比分析；最后總結(jié)全文。

1 Turbo 碼的全并行譯碼及迭代停止準(zhǔn)則

1.1 Turbo 碼的全并行譯碼算法

全并行譯碼算法實(shí)際是Turbo 碼分塊并行譯碼算法的一種極端情況，即把每個(gè)碼塊的大小減小到1，然后分別對(duì)應(yīng)一個(gè)譯碼計(jì)算單元進(jìn)行譯碼，并將這些單元分為上下兩路。編碼交織器采用QPP 交織器。QPP 交織器作為一種確定型交織器，采用兩個(gè)二次多項(xiàng)式進(jìn)行交織和解交織運(yùn)算。交織地址的計(jì)算可以采用遞歸的方式，無需乘法或者取模運(yùn)算，并且數(shù)據(jù)經(jīng)過QPP 交織器后的位置信息仍具有相同的奇偶性。全并行基本譯碼結(jié)構(gòu)如圖1 所示。

圖1 全并行譯碼算法

圖1 中，計(jì)算單元方塊中的UP 和DOWM 分別表示上、下兩路計(jì)算單元；N即為第N個(gè)計(jì)算單元；分別表示上路接收到的第k個(gè)校驗(yàn)位和信息位的對(duì)數(shù)似然比（Log Likelihood Ratio，LLR）；表示上路向下路傳遞的外信息；表示上路接收到的外信息用做的先驗(yàn)信息；s和x分別對(duì)應(yīng)上、下兩路；下路的計(jì)算單元同理。

全并行譯碼算法關(guān)鍵在于迭代計(jì)算時(shí)充分利用了QPP 交織器的特性：數(shù)據(jù)經(jīng)過QPP 交織器后的位置信息仍具有相同的奇偶性。于是，將整個(gè)數(shù)據(jù)分為兩組：上路奇數(shù)位置和下路偶數(shù)位置的數(shù)據(jù)為一組，如圖1 中白色譯碼塊所示；上路偶數(shù)位置和下路奇數(shù)位置的數(shù)據(jù)為另一組，如圖1 中陰影譯碼塊所示。一次迭代過程分為兩個(gè)半次迭代過程。在上半次迭代過程中，第一組白色譯碼塊進(jìn)行計(jì)算并交換外信息和傳遞狀態(tài)度量值；下半次迭代過程中，第二組陰影譯碼塊進(jìn)行計(jì)算，并交換外信息和傳遞狀態(tài)度量值，每次操作上下兩路都有一半的碼字進(jìn)行譯碼。綜合來看，每半次迭代就可以交換一半外部信息，而且上下兩路互相交換的是固定對(duì)應(yīng)位置的外部信息。相比于傳統(tǒng)的Log-MAP 算法，全并行譯碼算法的譯碼并行度為N，大大減少了譯碼時(shí)延。

全并行譯碼算法每個(gè)算法塊置信度不是依靠前向和后向遞歸計(jì)算傳播，而是依靠足夠數(shù)量的譯碼迭代來完成。迭代次數(shù)較少會(huì)造成狀態(tài)度量值α和β的不可靠，在相同迭代次數(shù)下性能會(huì)下降。一般達(dá)到相同性能需要調(diào)用的迭代次數(shù)是Log-MAP 算法的6 倍左右。

1.2 Turbo 碼譯碼迭代停止準(zhǔn)則

Turbo 碼譯碼時(shí)一般預(yù)設(shè)一個(gè)最大迭代次數(shù)，達(dá)到規(guī)定的迭代次數(shù)后譯碼停止，而不能根據(jù)信道條件的變化及時(shí)調(diào)整。采用合適的譯碼迭代停止準(zhǔn)則可有效降低迭代次數(shù)，減小譯碼時(shí)延。

Turbo 碼譯碼常用的迭代停止準(zhǔn)則主要是基于交叉熵（Cross Entropy，CE）的迭代停止準(zhǔn)則[9]。通過交叉熵度量來確定軟輸出似然比的接近程度，并利用交叉熵最小化原理近似確定譯碼迭代次數(shù)，但是計(jì)算復(fù)雜度較高。Shao R Y 在CE 準(zhǔn)則的基礎(chǔ)上進(jìn)行了簡(jiǎn)化，提出了符號(hào)變化率（Sign Change Ratio，SCR）和硬判決輔助（Hard Decision Aided，HDA）迭代停止準(zhǔn)則[10]，但SCR 準(zhǔn)則和HDA 準(zhǔn)則均需儲(chǔ)存前次迭代譯碼的信息，消耗了一定的內(nèi)存。其中，SCR 準(zhǔn)則通過判斷前后兩次迭代輸出外信息符號(hào)變化個(gè)數(shù)來判決，HDA 準(zhǔn)則通過檢查兩次迭代譯碼器輸出軟信息的硬判決值是否發(fā)生變化來判決。利用先驗(yàn)信息與外信息的特性，通過比較同一次迭代SISO 譯碼器的先驗(yàn)信息和外信息符號(hào)不同的比特?cái)?shù)，Wu Y F 提出了SDR 準(zhǔn)則[8]。Shibutani A提出了循環(huán)冗余校驗(yàn)（Cyclic Redundancy Check，CRC）判決準(zhǔn)則[11]，先對(duì)一幀信息進(jìn)行CRC 編碼，譯碼時(shí)通過進(jìn)行CRC 校驗(yàn)來停止迭代，但是增加了一定的冗余，降低了帶寬效率。王曉明等人對(duì)外信息準(zhǔn)則[12]進(jìn)行了改進(jìn)，提出了基于外信息絕對(duì)值信噪比的迭代停止準(zhǔn)則（SBAE）。另外，Turbo碼的EXIT 圖也可以用來判斷迭代是否可以停止[13]。

使用全并行譯碼算法，在AWGN 信道、BPSK調(diào)制下對(duì)常用的迭代停止準(zhǔn)則進(jìn)行Matlab 仿真。本文采用的均為L(zhǎng)TE 標(biāo)準(zhǔn)下的1/3 碼率的Turbo 碼（15/13）8，碼長(zhǎng)為480。迭代停止準(zhǔn)則設(shè)定最大譯碼迭代次數(shù)均為15 次，圖2 仿真了應(yīng)用SCR、HDA、CRC 和SBAE 這4 種準(zhǔn)則的全并行譯碼算法誤碼率性能，并與固定15 次迭代譯碼時(shí)的誤碼率性能進(jìn)行了對(duì)比，BER 表示誤碼率，Eb/N0為信噪比。其中，HDA 和SDR 準(zhǔn)則的門限系數(shù)設(shè)為0.001，SBAE 準(zhǔn)則的判決門限值為0.8。圖2 中，使用迭代停止準(zhǔn)則后，通過設(shè)置合適的參數(shù)，譯碼誤碼性能基本相差不大。

利用圖2 相同的參數(shù)條件，圖3 仿真了4 種迭代停止準(zhǔn)則譯碼所需的平均迭代次數(shù)。使用Turbo碼全并行譯碼算法，SDR 準(zhǔn)則和SBAE 準(zhǔn)則所需的迭代次數(shù)較少。在信噪比大于1 dB 時(shí)，SBAE準(zhǔn)則相對(duì)其他準(zhǔn)則平均要少2 次迭代，但是在BER≥10-2時(shí)，對(duì)應(yīng)的信噪比小于1 dB，較低的信噪比使得外信息交互不存在明顯的正反饋，導(dǎo)致4種迭代停止準(zhǔn)則判決結(jié)果取值不穩(wěn)定，所需迭代次數(shù)變化沒有明顯規(guī)律性。其中，SBAE 準(zhǔn)則所需迭代次數(shù)反而最多，而在已經(jīng)提前收斂的情況下增加迭代次數(shù)對(duì)性能提升是無用的。

圖2 4 種準(zhǔn)則譯碼性能對(duì)比

圖3 4 種準(zhǔn)則平均迭代次數(shù)對(duì)比

2 改進(jìn)的譯碼迭代停止準(zhǔn)則

2.1 SBAE 準(zhǔn)則的優(yōu)化

SBAE 準(zhǔn)則是對(duì)傳統(tǒng)外信息迭代停止準(zhǔn)則的改進(jìn)。圖1 中對(duì)于全并行譯碼算法上下兩路接收到的3 路先驗(yàn)對(duì)數(shù)似然比LLR 值分別為：

式中，a和e分別用來對(duì)應(yīng)先驗(yàn)信息和外信息，LLR 值定義[3]為：

以全并行算法上路第k個(gè)碼塊為例，其輸入數(shù)據(jù)有5 路，分別為校驗(yàn)比特和信息比特的LLR 值下路碼塊外信息經(jīng)解交織后傳遞的先驗(yàn)LLR 值以及相鄰碼塊傳遞的前向和后向狀態(tài)度量值αk-1和βk。計(jì)算單元執(zhí)行譯碼操作后輸出前向和后向狀態(tài)度量值αk、βk-1和外信息。

Wiberg N 對(duì)外部信息特性進(jìn)行了分析，提出用高斯密度函數(shù)來描述外部信息的統(tǒng)計(jì)特性[14]。隨著譯碼迭代次數(shù)的增加，外部信息的絕對(duì)值均值逐漸趨于一個(gè)固定值，因此可將外部信息作為迭代停止準(zhǔn)則的判決依據(jù)。以上路碼塊為例，定義外部信息的絕對(duì)值均值為：

其中i為迭代次數(shù)，即以連續(xù)兩次迭代產(chǎn)生的外信息絕對(duì)值均值之比作為判決函數(shù)，設(shè)定門限Tj，小于該門限時(shí)停止迭代。圖4 和圖5 分別仿真了傳統(tǒng)Log-MAP 算法和全并行譯碼算法在不同信噪比時(shí)外信息絕對(duì)值均值隨迭代次數(shù)變化的曲線。傳統(tǒng)Log-MAP 算法在數(shù)次迭代后，外部信息的絕對(duì)值均值很快達(dá)到一個(gè)固定值，而全并行譯碼算法在迭代次數(shù)增加后，外部信息的絕對(duì)值均值變?yōu)楣潭ㄖ档内厔?shì)不明顯，因此以外信息均值作為判決條件效果不佳，使用SBAE 準(zhǔn)則更加適合。

SBAE 準(zhǔn)則采用了外信息絕對(duì)值對(duì)應(yīng)的信噪比的定義，即將譯碼模塊看作一個(gè)外信息信噪比增益器，定義為：

判決函數(shù)為連續(xù)兩次迭代產(chǎn)生的信噪比的比值：

通過設(shè)定判決函數(shù)Q≤a來終止迭代，其中a為判決門限。

圖4 Log-MAP 算法外信息變化

圖5 全并行譯碼算法外信息變化

不同于傳統(tǒng)的Log-MAP 算法，全并行譯碼算法的每個(gè)碼塊交換外信息的同時(shí)還進(jìn)行了前向后向狀態(tài)度量值的傳遞。在全并行算法改進(jìn)的EXIT 圖研究中，將前向、后向狀態(tài)度量值的計(jì)算進(jìn)行結(jié)合[4]。因此，在改進(jìn)的SBAE 準(zhǔn)則中，保留傳統(tǒng)SBAE 準(zhǔn)則判決依據(jù)，并加入了對(duì)前向、后向狀態(tài)度量值α或β的絕對(duì)值均值的判決。圖6 仿真了在不同信噪比時(shí)上路碼塊前向狀態(tài)度量值絕對(duì)值均值隨迭代次數(shù)變化的曲線，發(fā)現(xiàn)前向狀態(tài)度量值α的絕對(duì)值均值隨迭代次數(shù)的增加其增量變緩，因此設(shè)定合適的判決門限可以進(jìn)行終止迭代，使SBAE 準(zhǔn)則在低信噪比時(shí)判決性能更好。

圖6 前向狀態(tài)度量值變化

令上路碼塊前向狀態(tài)度量值判決函數(shù)為：

優(yōu)化后的SBAE 準(zhǔn)則中，式（8）和式（9）根據(jù)不同條件可以分別進(jìn)行判決，增加了SBAE 準(zhǔn)則判決的準(zhǔn)確性，避免了在低信噪比條件下判決的迭代次數(shù)變化過大的問題。

2.2 優(yōu)化的SBAE 準(zhǔn)則+SDR 準(zhǔn)則

在高信噪比的條件下，利用外部信息作為迭代停止準(zhǔn)則可以達(dá)到很好的譯碼效果，但是在低信噪比時(shí)判決函數(shù)取值變化浮動(dòng)較大，判決終止的迭代次數(shù)較多[15]。圖3 中，對(duì)于Turbo 碼全并行譯碼算法，低信噪比時(shí)SDR 準(zhǔn)則擁有較好的性能，因此將優(yōu)化后的SBAE 準(zhǔn)則與SDR 準(zhǔn)則進(jìn)行結(jié)合，實(shí)現(xiàn)迭代停止準(zhǔn)則性能的最優(yōu)化。

符號(hào)不同率（SDR）準(zhǔn)則由Wu Y F 提出，是對(duì)SCR 準(zhǔn)則的延伸。在Turbo 碼譯碼過程中，兩路數(shù)據(jù)的先驗(yàn)信息和外信息互相傳遞，令D(i)表示第i次迭代后上路碼塊外信息和先驗(yàn)信息之間符號(hào)不同的個(gè)數(shù)。隨著迭代次數(shù)的增加，D(i)的值逐漸減少，得到SDR 準(zhǔn)則判決函數(shù)為：

這里q為判決參數(shù)，N為碼長(zhǎng)，滿足該判決函數(shù)將停止迭代。SDR 準(zhǔn)則統(tǒng)計(jì)的實(shí)際為同一次迭代兩個(gè)外部信息的符號(hào)差別數(shù)，計(jì)算量同SCR 準(zhǔn)則相當(dāng)，但是不需要額外儲(chǔ)存前一次的外部信息。與SBAE 準(zhǔn)則相同的是，SDR 準(zhǔn)則同樣也是利用外部信息進(jìn)行判決。

通過分析譯碼迭代次數(shù)對(duì)Turbo 碼性能的影響，可將BER性能曲線劃分3 個(gè)區(qū)域[16]：在BER≥10-2時(shí)，迭代次數(shù)對(duì)BER的性能影響較小，大量增加譯碼迭代次數(shù)對(duì)提高性能影響不大；在10-5≤BER≤10-2時(shí)，BER性能曲線隨著迭代次BER≤10-5時(shí)，一般在迭代2～3次時(shí)就趨于收斂，數(shù)的增加而迅速下降，在一定次數(shù)后趨于收斂；在再進(jìn)行迭代增益變得非常小。

改進(jìn)后的迭代停止準(zhǔn)則是優(yōu)化的SBAE 準(zhǔn)則與SDR 準(zhǔn)則相結(jié)合，滿足SDR 準(zhǔn)則或優(yōu)化后的SBAE準(zhǔn)則一方條件即可終止迭代，實(shí)現(xiàn)不同信噪比條件下譯碼次數(shù)最小化。在誤碼率BER ≥10-2時(shí)，對(duì)應(yīng)較低的信噪比，式（9）或式（10）一方達(dá)到判決門限時(shí)終止迭代，為降低計(jì)算量不需用式（8）進(jìn)行判決；在誤碼率BER ≤10-2時(shí)，對(duì)應(yīng)較高的信噪比，此時(shí)以式（8）和式（10）作為判決標(biāo)準(zhǔn)，一方達(dá)到判決門限時(shí)終止迭代?？梢?，改進(jìn)后的迭代停止準(zhǔn)則能夠更好地適應(yīng)不同信噪比的條件，實(shí)現(xiàn)譯碼迭代次數(shù)的最小化。

3 仿真對(duì)比

在AWGN 信道、BPSK 調(diào)制下進(jìn)行Matlab 仿真，采用LTE 標(biāo)準(zhǔn)下的1/3 碼率的Turbo 碼（15/13）8，使用全并行譯碼算法，碼長(zhǎng)為480，對(duì)優(yōu)化SBAE+SDR 準(zhǔn)則、SBAE 準(zhǔn)則和SDR 準(zhǔn)則3 種迭代停止準(zhǔn)則的譯碼誤碼性能和譯碼迭代次數(shù)進(jìn)行對(duì)比。其中，SBAE 準(zhǔn)則的門限值a設(shè)為0.8，SDR 準(zhǔn)則的門限參數(shù)q設(shè)為0.001，改進(jìn)的迭代停止準(zhǔn)則設(shè)置fα(i)的門限值Tα為1.13，Q的門限值a為0.8，門限參數(shù)q為0.001。

從圖7 的仿真結(jié)果來看，改進(jìn)的迭代停止準(zhǔn)則與SBAE 準(zhǔn)則和SDR 準(zhǔn)則性能相差不大。圖則8 仿真了不同信噪比情況下的譯碼迭代次數(shù)。在信噪比為0～1 dB 時(shí)，改進(jìn)算法迭代次數(shù)明顯減少，分別比SDR 準(zhǔn)則和SBAE 準(zhǔn)則約少2 次迭代，保證了低信噪比條件下較低的譯碼迭代次數(shù)；在信噪比為1～2.5 dB 時(shí)，改進(jìn)準(zhǔn)則的平均迭代次數(shù)同樣最少，比SDR 準(zhǔn)則平均要少3.5 次迭代，實(shí)現(xiàn)了不同信噪比條件下始終保持較少的譯碼迭代次數(shù)。綜合來說，在達(dá)到相同的性能時(shí)，改進(jìn)的迭代停止準(zhǔn)則有效減少了全并行譯碼算法的迭代次數(shù)。

圖7 譯碼性能對(duì)比

圖8 平均迭代次數(shù)對(duì)比

4 結(jié)語(yǔ)

本文提出的優(yōu)化SBAE+SDR 準(zhǔn)則，結(jié)合了SBAE準(zhǔn)則和SDR 準(zhǔn)則的優(yōu)點(diǎn)，滿足不同信噪比條件下的Turbo 碼全并行譯碼算法的譯碼性能。仿真結(jié)果表明，該準(zhǔn)則有效減少了Turbo 碼全并行譯碼算法的譯碼迭代次數(shù)，提高了譯碼吞吐量，降低了譯碼時(shí)延，能夠更好地應(yīng)用于不同場(chǎng)景。