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

韓 明，任 凱，寧高利

（北京宇航系統工程研究所，北京，100076）

0 引 言

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

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

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

1 TPC 編譯碼算法

1.1 TPC 編碼方式

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

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

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

1.2 經典SISO譯碼算法

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

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

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

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

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

圖2 經典SISO譯碼基本單元 Fig.2 Basic Unit of Classic SISO Decoding

在經典SISO譯碼算法中，一般使用4次迭代，對應α和β的 經 典 取 值 為α= [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來說，考慮到復雜度和性能，p一般取4。

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

1.3 混合譯碼算法

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

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

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

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

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

2 改進的混合譯碼算法

2.1 SISO 算法優化

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

式中γ為可靠性參數，外信息簡化的關鍵在于γ的推導過程。

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

式中σ為高斯白噪聲標準差。

相應的碼字Dh的可靠性可表示為

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

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

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

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

故

由于：

故外信息為

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

2.2 HIHO 算法改進

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

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

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

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

圖5 錯誤圖樣 Fig.5 Error Patterns

2.3 SISO到HIHO的自動切換

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

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

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

3 仿真分析

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

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

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

圖9 算術運算復雜度對比 Fig.9 Comparison of Arithmetic Operation Complexity

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

4 結束語

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