3.5.1 MF-TDMA系统常用高效编译码[26]

3.5.1.1 Turbo码

Turbo 码是Claude.Berrou等在1993年ICC上提出的。Turbo码又称并行级联卷积码（Parallel Concatenation Convolutional Code，PCCC），其编码器由两个并行的递归系统卷积码通过随机交织器连接而成，因此称为“PCCC”；译码采用基于最大后验概率的软输入软输出迭代译码方法。Turbo码编、译码方案中很好地应用了Shannon信道编码定理中的随机编、译码条件，从而获得了几乎接近香农理论极限的译码性能。计算机仿真表明，Turbo码不但在高斯信道下性能优越，而且具有很强的抗衰落、抗干扰能力，其纠错性能接近香农极限。Turbo码一经提出便成为信道编码领域中的研究热点，并普遍认为Turbo码在深空通信、卫星通信和移动通信等数字通信系统中均有迷人的应用前景。

1.Turbo码编码

典型的Turbo码编码器结构如图3.29所示。它通常由两个结构相同的递归系统卷积码（RSC）（通常称为子码）构成，RSC1直接对输入的信息序列d_k进行编码，得到校验位y_1k；同时，信息序列d_k通过交织器交织后的序列d_n输入到RSC2进行编码，得到校验位y_2k，Turbo码的码字就是由信息序列和两路校验序列复接构成。子编码器所产生的校验位（ y_1k， y_2k）再经删截矩阵删取后可得到所需码率的Turbo码。

2.Turbo码译码

Turbo码的迭代译码结构如图3.30所示，它主要由两个软输入软输出模块（Turbo码的子译码器）组成，子译码器用来对选定的Turbo码中的RSC子码进行译码。子译码器1将子译码器2获得的信息比特d_k的外信息作为d_k先验信息来对 RSC1 进行译码，获得关于d_k改进的外信息L_1e（d_k），经交织后得到作为子译码器2对RSC2译码的先验信息。子译码器2用与子译码器1同样的方法再次产生信息比特改进的外信息L_2e（d_j），经去交织后得到作为下一次迭代中子译码器1的先验软值。这样在多次迭代后，对子译码器2产生的输出L₂（d_j）去交织后进行硬判决，得到每个信息比特d_k的估值。

迭代译码的关键是一个软输入/软输出的译码器，它可获得每个译码输出比特d_k的对数似然比值，如图3.31所示。

它的三个输入分别是：

① L（d_k）是信息比特d_k的先验信息软值（先验概率的对数似然比）；

② x_k和y_k是编码比特经信道传输受噪声干扰后接收到的采样值（充分统计量），由于采用的是系统编码， x_k对应于未编码的信息比特， y_k对应于编码的校验比特。

它的两个输出分别是：

①是信息比特d_k的软输出（后验概率的对数似然比），它定义为：

是通过BCJR（或称MAP，APP）译码算法得到的；

②是信息比特d_k的外信息（extrinsic information），它是从所有输入的L（d_k）、x_k和y_k中获得的关于信息比特d_k的软值，将作为下级译码中信息比特d_k的先验信息。

对于系统编码，信息比特d_k的软输出可表示成三项的和：

式中，L_c是与信道的增益和噪声方差有关的参数，具体参见后面的详细推导。

通常，我们假定信息发送是等概的，因此在首次迭代的第一级译码时，没有先验信息可用，即L（d_k）=0。第一级译码器通过x_k和y_1k两个输入获得信息比特d_k的软输出，则关于信息比特d_k的外信息定义为：

在第二级译码时，我们将第一级输出的外信息作为信息输入的先验软值，译码器通过三个输入x_k、y_2k和获得信息比特d_k的软输出，同样可获得信息比特d_k的外信息为：

外信息作为下一次迭代中第一级译码的新的先验值。在首次迭代中，第一级译码和第二级译码输出的外信息是相互统计独立的，所以从第一次迭代到第二次迭代所获得的增益较大，但由于译码时采用相同的信息，在后面迭代中输出的外信息相关性越来越大，因而通过迭代改善的性能越来越小，最后一次迭代后，将软输出用来进行硬判决：

Turbo码的迭代译码方法是Berrou等的一个创举，虽然他们未能给出这种方法的收敛特性和它的理论解释，但实际仿真结果表明它工作得很好，接近了全局的最大似然译码。

下面我们给出软输入/软输出算法——MAP 算法的简洁但不失其严格性的数学推导[27]，在文献[27]中，软输入/软输出模块有各种不同的叫法，如BCJR算法、MAP算法、APP算法。下面的推导基于卷积码的网格图描述。由译码结构可知，该译码模块的功能可概括为：在卷积编码的约束下提供信息比特的最佳后验信息。假定RSC码的编码约束长度为v，则在时刻k（设a_k是RSC编码寄存器的状态），编码器状态s_k可表示成v-1重寄存器状态，也即：s_k=（a_k， a_k-1，…a_k-v+2）。我们同时假定信息比特序列{d_k}是由 K 个相互独立的、等概取值于{+1，-1}二元集的比特d_k组成的，且编码器的初始状态s₀和终止状态s_N都为，也即：s₀=s_N=（0，0，…0）=。我们用来表示RSC编码器的输出码字序列：，用来表示其经过离散无记忆高斯信道后的输出序列：。以典型的未删截码率为 1/3 的Turbo码为例，则有c_k=（X_k，Y_k），r_k=（x_k，y_k）。对于离散无记忆高斯信道，在时刻k，接收到的充分统计量（ x_k， y_k）满足以下关系式：

式中， i_k和q_k是均值为0、方差为σ2的两个独立的高斯噪声。

MAP算法的目的是有效地求出式（3-44），严格来说，是提供信息比特d_k的后验概率对数似然比：

式中，表示在网格时刻k时的状态转移对，下标d_k=+1表示由输入信息比特+1引起的状态转移对。这样，MAP 算法的关键可以归结为概率的有效计算问题。

由卷积码网格状态的Markov特性可以得到：

其中，α_k-1（m′），γ_k（m′， m）及β_k（m）由式（3-51）中相应划线部分所定义。由此不难验证前后向递归算法成立，即有：

式（3-54）中两子项的显式计算如下：

其中， L_c=2/σ2，两式中的A_k和B_k对所有的状态转移对都是一样的，因而可略去不计。最终，不难证明式（3-50）可写成式（3-45）的形式，且外信息为：

式中：

以上算法还可转到Log域（Log-MAP算法[28]），从而可以用加法和查表来代替原MAP算法中的大量乘法运算，目前在实际FPGA实现中普遍采用基于Log域的算法。图3.32给出了典型参数Turbo码的误码率特性曲线，供参考。

3.5.1.2TPC（Turbo乘积码）

1994年P.Ryndiah发现由分组码串行级联构造的Turbo码同样能获得较好的性能，将Turbo码的子码拓展到分组码，称为分组Turbo码（Block Turbo Code，BTC）。后来，他又基于 Chase 算法提出了一种用于线性分组码的软输入软输出迭代算法，并将其应用于乘积码的译码，译码方法类似Turbo码，称之为Turbo乘积码。

Turbo乘积码在译码性能上接近Turbo卷积码，具有较高的编码效率（频谱利用率），同时算法复杂度较低，适合并行处理，采用流水线机制在超大规模现场可编程门阵列（FPGA）上可以实现高速编译码，对于高速数据传输系统来说是一种不错的解决方案。一般认为，Turbo 乘积码较 Turbo 卷积码有着更为广泛的应用前景。

1.TPC编码

Turbo 乘积码从结构上可以由两个或者多组分组码子码排列在一个两维或多维的阵列中构成码字。乘积码按照其构成子码的种类不同可以分为BCH乘积码、奇偶校验乘积码、扩展汉明乘积码。

假设有两个线性分组码：C1（n₁，k₁，δ₁）和C2（n₂，k₂，δ₂），其中n_i、k_i、δ_i分别代表分组子码长度、信息位长度及最小汉明举例。可以通过下列步骤构造乘积码P=C1⊗C2。

①将待编码比特列入k₁× k₂的信息比特矩阵当中；

②对信息比特矩阵中所有的k₁行比特信息，均统一采用子码C1的编码规则编码，随后得出一组k₁× n₂的信息矩阵；

③对上一步得到的矩阵中所有的n₂均统一采用用C2的编码方式进行编码，可得到大小为n₁× n₂的已编码码字矩阵。

构造成一个n₁×n₂的乘积码码字。乘积码P的参数为：码长n=n₁×n₂，信息位长度k=k₁×k₂，最小汉明距离δ=δ₁×δ₂，编码效率R=R₁×R₂。二维TPC码的矩阵结构如图3.33所示。

2.TPC译码

1972年Chase提出了一种使码字错误概率最小的软判决译码算法（见图 3.34），其性能接近于最大似然译码，该算法的基本原理是分别计算接收序列中的每个码元信任值，根据信任值找到可能出错的位置，并产生几个试探序列，从中挑选一个与接收序列有最小软距离的候选码字，作为译码器的输出码字。

Chase译码算法如下：

①从接收序列中，得到一个可信序列α和硬判决序列R_n；

②从中选择一个试探序列T，将试探序列T 与硬判决序列R_n相加，得到一个新的序列；

③把新序列送入硬判决译码器，得到错误图样；

④重复步骤②、③，直到试探序列全部试探完毕，得到一组候选错误图样集合{E_t}；

⑤挑选出一个有最小欧氏距离的错误图样E_min，作为最后确定的错误图样，作为已译码字输出。

Chase算法可分为三种：

（1）Chase-I 算法：译码器产生所有重量为（ d_n/2）的试探序列，总共有个，这种算法译码性能最好，但是译码器设计特别复杂，所以Chase-I算法只适合d_n较小的码和短码。

（2）Chase-II算法：译码时只考虑（ d_n/2）个最低可信度码元位置错误的情况。Chase-II复杂度比 Chase-I算法低，但其译码性能比 Chase-I算法稍差。

（3）Chase-III 算法：译码时产生（ d_n/2+1）个试探序列，Chase-III 与Chase-I、Chase-II相比试探序列最少，计算量和复杂度也最小。Chase-III算法在码的最小距离d_n很大时优点更为突出。但是 Chase-III 算法译码性能与前两种算法相比差很多。

3.5.1.3低密度校验码（LDPC）

低密度奇偶校验码（Low-Density Parity-Check Codes，LDPC）是一种稀疏线性分组码，具有良好的应用前景。LDPC 码最早是由麻省理工学院的R.G.Gallager 于 1963 年发明的[29]。在其博士论文中，Gallager 提出了规则LDPC 码的构造方法、编译码算法以及最小汉明距离分析和译码算法的性能分析等。由于当时的条件限制，编译码器无法用硬件实现；同时，因为计算机的计算能力的限制，精确细致的仿真也不能实施。正是由于这些原因，尽管LDPC码有很好的纠错性能，它仍然被人们忽略将近40年。Turbo码的发明让人们重新认识到了LDPC码，20世纪90年代后期，Mackay、Neal等重新发现了LDPC码。Mackay等通过大量的仿真表明，LDPC码和Turbo码一样，也具有接近香农限的性能。

LDPC码和所有的线性分组码一样，也可以用校验矩阵H和生成矩阵G描述。LDPC 码是一种特殊的分组码，其特殊性就在于它的奇偶校验矩阵中“1”的数目远远小于“0”的数目，称为稀疏性，“低密度”也来源于此。如图3.35所示为随机构造的（20，3，4）规则LDPC码的校验矩阵，码长为20，列重为3，行重为4，码率为1/4。正是基于这种稀疏性，我们才可能实现低复杂度的译码。

图3.35中的校验矩阵的列数表示对应的LDPC码的码长，行数表示对应的LDPC码的校验位的个数，因此码率为（列数—行数）/列数。校验矩阵的列用一个顶点集合来表示，集合中的一个顶点对应编码码字中对应位置的一个比特，称之为信息节点（或者变量节点）；校验矩阵的行用另一个顶点集合来表示，集合中的一个顶点表示编码码字参与的一个校验约束，称之为校验节点。如果校验矩阵中某位置为“1”，那么表示与此行相对应的校验节点和与此列相对应的信息节点是相关的（或者说是相邻的），反之则不相关（或者说是不相邻的）。如果校验矩阵的所有行中的“1”相等并且所有列中的“1”也相等，则称为规则码，反之为非规则码。根据校验矩阵的构造方法不同，LDPC码可分为随机码和代数结构码。

1.LDPC码校验矩阵构造

LDPC码的校验矩阵决定了LDPC码的性能和实现复杂度，校验矩阵结构可分为伪随机结构和准循环结构。Gallager 给出的结构通常称为伪随机结构。伪随机结构的LDPC码性能较好，但由于生成矩阵和校验矩阵规律性较差，因此编译码实现复杂度高，一般只用于仿真，在工程中难以应用。工程上常用具有代数结构特性的准循环结构的LDPC码，其性能非常接近随机结构的LDPC码，但实现复杂度和资源消耗远小于随机结构的LDPC码。循环码是指码字C向左（或右）循环移位一位后仍是码集中的一个码字。如果把码字分为等长的l段， C=（c₁，c₂，…，c_l），而每一段都是循环码，那么该码字是准循环码。如果l=1，那么准循环码就是循环码。

准循环（Quaci-Cyclic，QC）LDPC 码可以用母矩阵或校验矩阵表示。一个码长为N=nL（ L为子矩阵的大小，n为母矩阵的列数，m为母矩阵的行数）的准循环LDPC码的校验矩阵可表示为[30]：

式中， A_{i， j}是L× L单位阵循环移位后的矩阵。如果A_{i， j}是5×5的单位矩阵循环右移位1位得到的（即循环移位值为1），那么A_{i， j}可表示为：

由于循环移位矩阵A_{i， j}完全决定于偏移量，因此总可以用P=[ p_{i， j}]_m×n来表征校验矩阵H_qc，如下式所示：

p_{i， j}为与其对应的循环移位矩阵A_{i， j}的偏移量。如果p_{i， j}＞0，则表示H_qc矩阵中对应的A_{i， j}是右偏移量为p_{i， j}的置换矩阵；若p_{i， j}=0，则表示A_{i， j}为单位阵；若p_{i， j}＜0（一般用-1来表示），则表示A_{i， j}为全零矩阵。P称为H_qc矩阵的母矩阵，H_qc矩阵则可看作P矩阵的扩展矩阵。假如P矩阵为式（3-62）所示的矩阵，且子矩阵大小L=10，则由于m=3，n=6，那么该母矩阵表示的LDPC码的码长为6×10=60，码率为（6-3）/6=1/2。

2.LDPC编码

LDPC码是一种特殊的线性分组码，它可以按照分组码常用的编码方法进行编码。由GHT=0可以从校验矩阵H （列数为N，行数为M）推导出生成矩阵G （列数为 N，行数为 N-M），因为只考虑二元域的情况，因此所有的运算都是与和异或的运算。

定义校验矩阵H=[C₁C₂]，其中矩阵C₂是一个稀疏的M× M 的可逆方阵，矩阵C₁是一个稀疏的N×（ N-M）的矩阵，N是H矩阵的行数，M是H矩阵的列数。对矩阵H进行高斯消去的过程中可以得到矩阵。LDPC码的生成矩阵可以表示为：

式中，I_k是K×K的单位矩阵，K=N-M。得到生成矩阵后，可根据下式可以得到编码后的码字：

式中， S是信息码字，C为编码后的码字。

一般而言，这样得到的生成矩阵G不是稀疏矩阵，编码时仅存储生成矩阵G就需要消耗相当大的资源。因此这种算法目前没有太大的现实意义，一般用于性能仿真中。工程上通常利用准循环码生成矩阵的一些特殊特性进行编码，可使实现复杂度得到显著的降低。

若G_qc为准循环码的生成矩阵，则编码过程可以描述为：

假设校验矩阵H_qc满秩（即r=mL），则可以通过以为单位的列交换，在H_qc中找到一个mL× mL的矩阵D₁，其秩也为mL，且可逆。

H_qc以循环移位阵为单位进行列交换后（为简便仍用H_qc表示）转换为：

在该条件下，可假设生成矩阵满足以下形式：

式（3-68）称为“系统—准循环码生成矩阵”，这里 I 一个L× L的单位阵，0 一个L×L的零阵，G_i，j为L×L的循环移位矩阵，其中1≤i≤n-m，1≤ j≤m。生成矩阵由两部分组成，左边部分I_（n-m）L和右边部分P。I_（n-m）L的主对角线是m-n个L× L的单位阵，右边部分P是由（m-n）×m个L× L循环移位矩阵构成的矩阵。准循环 LDPC 码的生成矩阵须满足的充分必要条件是：

式中，[0]是一个mL×（n-m）L的零阵。设g_{i， j}为循环子阵G_{i， j}的“行生成矢量”（即G_{i， j}的第一行），如果求得所有的g_{i， j}，则的所有循环移位子矩阵G_{i， j}也就可以确定了。

假设u=（1，0，…，0），0=（0，0，…，0）这两个向量的长均为 L，则对于1≤i≤n-m，子矩阵G_i的第一行为g_i=（0，…，u，0，…，0，g_i，1，g_i，2，…，g_m）其中u在g_i的第i个部分。因为，所以有：

假设s_i=（g_i，1，g_i，2，…，g_i，m），则根据式（3-70）可以得出：

由于D₁是方阵且满秩，因此可逆。那么由式（3-71）可得：

所有的{s_i}，1≤i≤n-m对这些行生成向量进行循环移位就得到所有的G_{i， j}，那么对应的生成矩阵也就唯一确定了。

当校验矩阵不是满秩时（即r＜mL），那么可以通过以为单位的列交换，在H_qc中找到一个mL× mL的矩阵D₂，其秩也为r。假设D₂矩阵中的第i～j列线性相关，如果令行向量s_i中对应的第i～j比特位为 0，就可以消除D₂的非满秩对求解s_i的影响，于是得到等式：

式中， s_i′是指s_i中去掉第i～j位后的新向量；是去掉D₂中的第i～j列和第i～j行后的矩阵，是M_i去掉第i～j行后的矩阵。在中加 j-i+1个0后得到s_i；所有的{s_i}，1≤i≤n-m循环移位后得到G2：

编码运算其实就是信息向量与生成矩阵G的二元乘积，此运算可以用如图3.36所示的移位寄存器完成。对于随机结构的LDPC码，在完成每一比特的乘法时都需要向B寄存器加载生成矩阵G的行向量，当码长较长时所需的资源会非常多；而对于具有准循环结构的LDPC码而言，信息向量与生成矩阵G的二元乘积，其实就是信息向量与生成矩阵G的子矩阵G_{i， j}二元乘积，很大程度上减少了编码器所需资源。循环移位寄存器B初始化为子矩阵G_{i， j}的生成向量g_{i， j}，每输入一个信息比特，寄存器B就循环移位1次，当第L个信息比特输入后，重新初始化寄存器B，继续循环移位，直到完成所有G_{i， j}与输入信息的二元乘法，即完成编码。

3.LDPC译码

Gallager 在他早期的论文中提出了两种有效的译码算法：硬判决译码算法和概率译码算法，这两种译码算法都是基于树图的译码算法，可以得到很好的性能，但计算较为复杂。从那以后有人陆续发现了其他的相关算法，这些算法都是迭代计算且基于图论中变量的分布，可以说是与Gallager概率译码算法等价的，它们都属于消息传递算法，其中置信传播（Belief Propagation，BP）算法是消息传递算法中一种性能优异且易于实现的算法。LDPC译码器的结构框图如图3.37所示。VNFU对应信息节点处理单元，完成信息节点的相关运算；CNFU对应校验节点处理单元，完成校验节点的相关运算。

当译码开始后，所有校验节点处理单元获取从信息节点处理单元传来的信息，处理完成后将“校验节点信息”反馈给信息节点处理单元；然后所有信息节点处理单元获取校验节点处理单元和信道传来的信息进行计算，然后将“变量节点信息”反馈给校验节点处理单元。

BP译码根据传递信息的不同分为概率域BP译码、对数域BP译码；根据修改的校验节点传递的信息的不同，BP 译码分为最小和译码和归一化的最小和译码。概率域 BP 译码需要大量的乘法运算，对数域 BP 译码需要复杂的查表运算，而归一化最小和译码能获得性能和复杂度较好的折中，最有利于硬件实现。