一種改進的TPC混合譯碼算法

韓 明，任 凱，寧高利

（北京宇航系統(tǒng)工程研究所，北京，100076）

0 引 言

Turbo 乘積碼（Turbo Product Code，TPC）是一種性能優(yōu)良的信道編碼，其編碼器設(shè)計簡單，譯碼方式靈活，可根據(jù)糾錯能力和實時處理的不同需求合理選擇軟判決或硬判決譯碼方法[1～3]，被廣泛應(yīng)用于飛行器測控領(lǐng)域[4～6]。

1994年，法國學(xué)者Pyndiah等將Turbo碼軟輸入軟輸出（Soft In Soft Out，SISO）的迭代思想應(yīng)用到TPC碼的譯碼過程中，獲得了接近香農(nóng)極限的編碼增益[7]，被稱為經(jīng)典SISO譯碼算法。但該算法復(fù)雜，在一定程度上限制了其在信息高速傳輸時的應(yīng)用[8～10]。對SISO譯碼算法的簡化與改進，在糾錯性能和算法復(fù)雜度上尋求折中，是國內(nèi)外學(xué)者長期以來關(guān)注的重點，梯度譯碼、并行譯碼、自適應(yīng)譯碼等算法被相繼提 出[11～13]。2009年，融合了軟判決和硬判決譯碼算法思想的混合譯碼算法由Al-Dweik等提出，在幾乎不改變譯碼性能的前提下，降低了譯碼復(fù)雜度[14]。文獻[15]進行簡單優(yōu)化，提出了基于伴隨混合譯碼算法。之后，Lu等優(yōu)化了混合譯碼算法，更新外信息獲取方式[16]。由于混合譯碼可有效降低復(fù)雜度，但對性能影響很小，有利于譯碼硬件實現(xiàn)。

本文以傳統(tǒng)混合譯碼算法為基礎(chǔ)，在軟判決譯碼時簡化外信息計算過程，硬判決譯碼時針對特殊錯誤圖案使用串接算法，同時設(shè)定軟判決到硬判決譯碼時的自動切換門限，形成了改進的混合譯碼算法，有利于航天測控設(shè)備的小型化和國產(chǎn)化。

1 TPC 編譯碼算法

1.1 TPC 編碼方式

TPC是一種二維的串行級聯(lián)碼字，其編碼形式如圖1所示，只需要依次對行和列進行編碼即可。經(jīng)典的硬輸入硬輸出（Hard In Hard Out，HIHO）譯碼就是進行編碼的逆運算[17,18]。

TPC碼的子碼均為線性分組碼，一般為 RS碼、BCH碼或者漢明碼，為簡化編譯碼流程，行和列選用相同的編碼形式。綜合編碼效率和復(fù)雜度，在飛行器測控中使用最多的是子碼為擴展?jié)h明碼的TPC碼，這也是本文重點研究和探討的碼字。

圖1 TPC編碼形式 Fig.1 TPC Encoded Form

1.2 經(jīng)典SISO譯碼算法

經(jīng)典SISO譯碼算法是信道編碼專家Pyndiah基于Chase 2算法發(fā)展而來的。其中一個SISO單元處理過程為：收到軟輸入信息R后首先判斷其中的不可靠位（p個），然后得出含有 2p q= 個測試序列的集合Z，并對Z中的所有序列譯碼處理形成候選碼字集Ω，最后基于歐氏距離確定Ω中的似然碼字D和競爭碼字C，并進一步獲得軟輸出信息，外信息即為輸入輸出軟信息之差。

軟輸出信息rj"計算公式為

式中dj為D中第j個碼元；β為可靠性因子；rj為第j個碼元的軟輸入信息。

經(jīng)典譯碼算法使用多個相同 SISO處理單元串接的迭代處理方法，每個單元均包含了兩個SISO處理過程，如圖2所示，迭代過程中軟輸入信息計算方式為

式中m和W分別為半迭代次數(shù)和外信息；α為重量因子。

圖2 經(jīng)典SISO譯碼基本單元 Fig.2 Basic Unit of Classic SISO Decoding

在經(jīng)典SISO譯碼算法中，一般使用4次迭代，對應(yīng)α和β的 經(jīng) 典 取 值 為α= [0,0.2,0.3,0.5,0.7,0.9,1.0,1.0],β=[0,0.2,0.3,0.5,0.7,0.9,1.0,1.0]。對 TPC(64，57)2來說，考慮到復(fù)雜度和性能，p一般取4。

該算法盡管性能優(yōu)良，但實現(xiàn)難度較大，其運算量主要來自構(gòu)造候選碼字集合時眾多代數(shù)譯碼過程和獲取外信息時繁瑣的算數(shù)運算過程。實際上，由于TPC譯碼算法均由SISO算法演變而來，其復(fù)雜度通用方法是用代數(shù)譯碼數(shù)目及算術(shù)運算數(shù)目進行評估和對比。

1.3 混合譯碼算法

混合譯碼算法是對傳統(tǒng)SISO譯碼算法的改進，其基本思想為融合傳統(tǒng)軟判決譯碼算法和硬判決譯碼算法的優(yōu)點，使用經(jīng)典SISO算法實現(xiàn)接受信息誤碼的快速減少，然后使用傳統(tǒng)HIHO算法糾正數(shù)量有限的殘余錯誤碼字，從而降低軟判決迭代次數(shù)，在幾乎不影響譯碼性能提前下，簡化譯碼過程，壓縮譯碼時延。

混合譯碼算法可表示為Hybrid(m，n)形式，m表示SISO譯碼迭代次數(shù)，n表示HIHO譯碼迭代次數(shù)，基本流程如圖3所示。

圖3 混合譯碼算法 Fig.3 Block of Hybrid Decoding Algorithm

該算法在文獻[14]中有詳細(xì)介紹和算法仿真，本文不再贅述。但需要說明的是，混合譯碼算法為通用方法，該文獻中所有仿真均針對子碼為擴展 BCH碼的TPC碼，文獻中 TPC(64，51)2使用Hybrid(3.5，4)，譯碼性能與4次迭代SISO算法幾乎相同，可作為以相似編碼效率TPC的譯碼參考。

混合譯碼算法缺點明顯：首先僅對SISO迭代次數(shù)做了簡化，獲取外信息仍相對繁瑣；其次，HIHO存在眾多不能糾正的錯誤圖案，對于子碼為擴展?jié)h明碼的TPC碼，若傳遞給HIHO的數(shù)據(jù)包含“#”型錯誤圖案，無論迭代多少次，均無法糾正；從SISO到HIHO的切換按照預(yù)先設(shè)定值進行，不能根據(jù)信道質(zhì)量合理壓縮SISO迭代次數(shù)，無法實現(xiàn)譯碼過程切換的智能化、自適應(yīng)。

2 改進的混合譯碼算法

2.1 SISO 算法優(yōu)化

SISO算法中，如果無法獲取競爭碼字C，則說明代數(shù)譯碼之后的第j個碼元dj具有較高的可靠性，相應(yīng)的外信息就能用dj乘相應(yīng)的可靠性參數(shù)等效[16]，特別適合子碼為擴展?jié)h明碼的TPC碼譯碼過程的簡化。

式中γ為可靠性參數(shù)，外信息簡化的關(guān)鍵在于γ的推導(dǎo)過程。

在AWGN信道中，BPSK傳輸每個比特可靠性信息（Log Likelihood Radio，LLR）為

式中σ為高斯白噪聲標(biāo)準(zhǔn)差。

相應(yīng)的碼字Dh的可靠性可表示為

如果Dw(1),Dw(2),Dw(3),… ,Dw(aw)是從漢明距離角度離Rh第2近的碼字，共有aw個。在σ→0的信道環(huán)境下，可得：

即，高信噪比時，式（5）可簡化為

若Rh中可能有e個錯誤碼元（即漢明距離dH(Rh,Dh)=e），pe為某個碼元錯誤接收可能性，則：

σ→ 0 條件下BPSK誤碼率為其中，Q(x) =e-x2/2/2，Rc為信息傳輸速率，Eb為單比特能量，N0為噪聲功率譜密度。

故

由于：

故外信息為

可見，在滿足公式使用條件時，可避免獲取候選碼字集及外信息的繁瑣計算。注意到該公式推導(dǎo)建立在Dh可信這一基礎(chǔ)上，對于擴展?jié)h明碼構(gòu)造的 TPC碼，考慮到其子碼的糾錯能力，Dh與Rh一致，即可認(rèn)為Dh可信，此時dmin=4，dH(Rh,Dh) =e=0，外信息改進的混合譯碼算法中將在條件滿足時，使用該公式，簡化SISO譯碼流程。

2.2 HIHO 算法改進

對于子碼為擴展?jié)h明碼的 TPC碼，1.3節(jié)提到HIHO存在眾多不能糾正的錯誤圖樣，可在HIHO后串接部分簡單操作，提升譯碼性能。

改進的 HIHO算法分為查找錯誤圖樣和分類糾錯兩個階段，可稱為串接譯碼算法。基本思想是，利用擴展?jié)h明碼在糾1位錯誤的同時可檢測2位錯誤的特點，在傳統(tǒng) HIHO之后，繼續(xù)查找某些特殊的錯誤圖樣，并根據(jù)不同圖樣特點進行分類處理，糾正其中錯誤碼元，算法如圖4所示。

圖4 改進的HIHO算法 Fig.4 The Improved HIHO Algorithm

改進的 HIHO算法可糾正圖5（黑點表示錯誤碼元，相鄰行/列之間正確碼元省略）中3種類型錯誤，提高譯碼性能，復(fù)雜度方面只是近似附加了一次 TPC碼字代數(shù)譯碼。針對這3種類型錯誤圖樣的詳細(xì)方法和仿真結(jié)果，文獻[19]中已有介紹和分析，改進的混合譯碼算法中將使用這種串接譯碼算法，代替原 HIHO算法，糾正特殊錯誤圖樣，提高譯碼性能。

圖5 錯誤圖樣 Fig.5 Error Patterns

2.3 SISO到HIHO的自動切換

混合譯碼算法涉及到2種譯碼算法之間的切換，為簡化譯碼器，在不同的信噪比環(huán)境下，譯碼算法應(yīng)做到自適應(yīng)和智能化。基本思想是在改進的SISO算法之后，判斷可能正確譯碼的行/列數(shù)目，計算其占TPC行/列的比例，若該比例大于預(yù)先設(shè)定的門限值Th_right，則轉(zhuǎn)入改進的 HIHO算法，若小于預(yù)先設(shè)定的門限值Th_right，則繼續(xù)執(zhí)行SISO迭代，直到迭代完成，具體算法流程如圖6所示。

圖6 改進的混合譯碼算法流程 Fig.6 Flow Chart of the Improved Hybrid Decoding Algorithm

混合譯碼的復(fù)雜度主要取決于SISO算法，門限值Th_right的引入，可做到SISO到HIHO的智能切換，當(dāng)信噪比較高時，減少SISO的迭代次數(shù)，提高譯碼效率。Th_right的選定，需根據(jù)TPC碼型，通過仿真確定。

3 仿真分析

選取子碼為擴展?jié)h明碼TPC(64，57)2，使用Matlab進行經(jīng)典SISO算法、原混合譯碼算法、改進的混合譯碼算法的仿真分析，譯碼性能和復(fù)雜度對比見圖7至圖9。BPSK信號經(jīng)高斯白噪聲信道，不可靠比特數(shù)設(shè)為4。經(jīng)典SISO算法迭代4次；原混合譯碼算法SISO和HIHO迭代次數(shù)分別為3.5和4；改進的混合譯碼算法初始SISO設(shè)定為3.5次，HIHO在傳統(tǒng)方式迭代2次后，串接檢錯和糾錯處理過程，Th_right為80%。

圖7 各譯碼算法性能 Fig.7 Performance of Different Decoding Algorithms

圖8 代數(shù)譯碼復(fù)雜度對比 Fig.8 Comparison of Hard-decision Decoding Complexity

圖9 算術(shù)運算復(fù)雜度對比 Fig.9 Comparison of Arithmetic Operation Complexity

可以看出，在誤碼率為 10-5時，改進的混合譯碼算法與經(jīng)典 SISO算法、原混合譯碼算法性能幾乎相同，但對比原混合譯碼算法，代數(shù)譯碼和算術(shù)運算復(fù)雜度均降低了約50%，整體復(fù)雜度約為經(jīng)典SISO算法的 45%以下、原混合譯碼算法的一半，且隨著信噪比提高，復(fù)雜度進一步減小。可見，改進的混合譯碼算法特別適用于飛行器測控、衛(wèi)星通信等鏈路余量大，對實時通信要求高的場合。

4 結(jié)束語

以擴展?jié)h明碼為子碼的TPC碼為重點，在分析經(jīng)典SISO譯碼算法和混合譯碼算法基礎(chǔ)上，對混合譯碼算法進行改進，簡化SISO外信息計算過程，提高HIHO糾錯能力，并利用門限值控制SISO到HIHO的算法切換，實現(xiàn)譯碼的自適應(yīng)和智能化，在性能無損的前提下，復(fù)雜度顯著降低。切換門限的選擇是改進的混合譯碼算法中的難點，需通過大量的仿真和分析確定。針對不同編碼效率的TPC碼，快速、合理地選擇切換門限，實現(xiàn)性能和復(fù)雜度的平衡，是后續(xù)研究的方向。