一种改进的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码，快速、合理地选择切换门限，实现性能和复杂度的平衡，是后续研究的方向。