信道编码新进展简介-2014

信道编码新进展简介背景移动通信、卫星通信、无线互联网的快速发展无线城域网（WMAN，WirelessMetropolitanAreaNetwork） 无线局域网（WLAN，WirelessLocalArea） 无线个域网（WPAN，WirelessPersonalAreaNetwork） 无线传感器网络（WSN，WirelessSensorNetwork） 物联网（IoT，InternetofThings） 无线自组织网络（WAN，WirelessAdHocNetwork）新概念的提出及推广使用，使信息论的研究工作逐渐转向网络信息理论领域，以解决复杂电磁环境中宽带和多媒体通信所面临的理论问题。信息理论与编码基础背景本章仅对Turbo码、空时编码（STC，SpaceTimeCoding）、低密度奇偶校验码（LDPC，LowDensityParityCheck）码以及网络编码与协作进行简要讨论。信息理论与编码基础本章内容提要10.1Turbo码10.1.1Turbo码的编码及其性能10.1.2Turbo码的译码简介10.2空时分组码10.2.1正交空时分组码10.2.2正交空时分组码的译码10.2.3准正交空时分组码10.2.4准正交空时分组码的译码10.3低密度奇偶校验码10.3.1低密度奇偶校验码的定义10.3.2低密度奇偶校验码的译码10.4网络编码与协作10.4.1网络编码10.4.2网络编码协作Turbo码10.1Turbo码在传统的编码方式中，通常通过构造大量代数结构的码来选择出一个好码。但是，这种结构设计方法的缺点是，为了尽量接近香农信道容量的理论极限，要求增加线性分组码码字的长度或增加卷积码的约束长度，从而导致最大似然估计译码器的计算复杂度随码字长度增加按指数增加，这又使得在实际应用中译码器难以实现。10.1Turbo码各种构造具有较大“等效”分组长度的编码方法运用而生。这些方法的基本思想是尽管“编码长度”较大但在译码过程中能够将它们分解为许多较容易实现的步骤来完成。在这一研究领域，Turbo码是一个成功的例子，它以一种崭新的方式构造好码并且以较为合理的复杂度进行译码。10.1Turbo码10.1.1Turbo码的编码及其性能Turbo码的基本形式如图10.1所示。它看起来像一个典型的系统分组码，其编码输出分成消息比特和校验比特两大部分，而校验比特又分为z1、z2两部分，其不同之处在于其中一个含有交织器而另一个则没有。图10.1Turbo码编码器框图10.1Turbo码通常情况下，图10.1中的两个编码器都采用相同的结构，但是也可以采有不同的编码器组合。Turbo码推荐使用的编码器是短限长的递归系统卷积码（RSC，RecursiveSystematicConvolutional）。采用卷积码递归，也即将一个或多个抽头的输出反馈到移位寄存器的输入端，其原因是使移位寄存器的内部状态与它过去的输出有关，以此对错误图样的状态施加影响，因为系统码的单个误码会引起多个校验误码，而基于这种方法就可以获得更好的整体编码效益以提高性能。10.1Turbo码图10.28状态递归系统卷积码编码器图10.2给出了一个8状态递归系统卷积码编码器。10.1Turbo码交织器主要可分为周期交织器和伪随机交织器两种。Turbo码使用的是伪随机交织器，对系统比特进行交织，实质上相当于对另一组信息比特m’送给编码器，因此等效的码长扩大了1倍。虽然Turbo码中的两个编码器都使用卷积码，但整体上它是分组码，其分组长度取决于交织的长度。由于图10.1的两个RSC卷积码编码器都是线性的，因此可认为Turbo码是线性分组码。10.1Turbo码Turbo码采用并行编码方案，输入的消息比特一方面直接进入编码器1，另一方面经过交织器重新排序后输入到编码器2。信息比特和由两个编码器生成的两组校验比特组成了Turbo编码器的输出。10.1Turbo码由于并行编码方案使用了递归的系统卷积码，并在两个编码器之间引入了伪随机交织器。因此，Turbo码对信道误码实质上表现出随机的特性，同时，其结构又使得译码方案切实可行。根据编码理论可知，如果分组足够大，随机选取的码可以接近香农的信道容量，这是Turbo码具有优越性能的真正原因。10.1Turbo码图10.3给出了一个码率为1/2且具有较大分组长度的Turbo码经AWGN信道传输时的误码性能。为了便于比较，图中还给出了在相同AWGN信道条件下的另外两条曲线，即未编码的数据传输（码率=1）曲线和码率为1/2时的香农理论极限。图10.3Turbo码的误码性能及相关比较10.1Turbo码对图10.3进行分析可以看出，虽然在Eb/N0较低时，Turbo码进行传输时的误比特率明显高于未编码的数据传输，但是当Eb/N0达到某一临界值时，Turbo码的误比特率会迅速下降。尤其值得注意的是，当误比特率达到10-5时，Turbo码要求的Eb/N0仅比香农理论极限值大0.5dB。然而必须指出，如此高的性能改善，其代价是交织器的大小或Turbo码的分组长度必须足够大。此外，改善性能所需的大量迭代也会增加译码器的等待时间，其原因主要是信息的数字处理没有对反馈提供帮助。10.1Turbo码10.1.2Turbo码的译码简介Turbo码的译码原理如图10.4所示。它通过对系统噪声模型和两个译码器中两组校验比特的运算，产生原始信息比特的估计值。在讨论具体译码过程之前，先介绍内部信息和外部信息的概念。图10.4Turbo码的译码原理10.1Turbo码外部信息实际上是通过挖掘信息比特和译码器产生的原始输入数据比特之间的相关性而得到的增量信息。外部信息可以用对数似然比值来表示，并用如图10.5所示的两个对数似然比的差计算。由消息比特译码段产生的外部信息，定义为在该译码段的输出端计算得到的对数似然比与内部信息的差值，此内部信息由反馈到这个译码段输入端的对数似然比表示。实际应用的Turbo码译码算法颇为复杂，这里仅仅给出一些基本概念，具体内容就不再讨论了。图10.5外部信息10.2空时分组码空时编码将编码和信号处理技术相结合，使用多个发射和接收天线进行信息的发送和接收，在多个发射天线和各个时间周期的发射信号之间能够产生空域和时域的相关性，这种空时相关性可以使接收机克服多输入多输出（MIMO，Multi-inputMulti-output）信道衰落和减少接收误码，从而有效改善无线通信系统的信息容量、信息率和误码率性能，可以在不牺牲带宽的情况下获得更高的编码增益。多输入多输出系统图

10.2空时分组码X为T

个时隙从N个发射天线发射的信号发射矩阵（T×N）10.2空时分组码R为接收矩阵（T×M），包含

T

个时隙中的所有接收信号信道矩阵H，为（N×M）维路径增益10.2空时分组码噪声矩阵n，（T×M）维得到信道输入输出关系的矩阵表示形式：R=X·H+n10.2空时分组码10.2空时分组码空时编码主要分为空时网格码和空时分组码。当其他分集方式可能受限或者不存在时，空时分组码是实现发射分集的一种简单而有效的方法，常见的有正交空时分组码和准正交空时分组码。正交空时分组码首先由Alamouti提出，是一种发射天线数为2的满码率满分集双路分集传输结构，接收端采用最大似然译码。研究表明，当发射天线数大于2时，不可能存在各元素为复数的满码率正交空时分组码，Jafarkhani提出了发射天线数为4的满码率准正交空时分组码。本节简要介绍这两种码。考虑发端有N

个发射天线、收端有M

个接收天线的系统。空时编码设计的目标就是获得最大分集增益

NM

、最大编码增益和可能的最大吞吐量。空时分组码可视为一种能提供满分集增益和具有非常低的编码和译码复杂度的多个发射天线的系统。10.2空时分组码Alamouti码发射机方案图10.2空时分组码假定一个具有2发射天线和单接收天线的系统采用的是Alamouti码，将每bbits映射为一个具有2b个符号的星座图中的一个符号来发射b

bits/周期的信号。星座图可以是实的或者复的星座图，如PAM、PSK、QAM等。10.2空时分组码首先发射机通过一个包含2bbits的分组从星座图中选出两个符号，若x2和x1是由包含2b

bits的分组所选定的两个符号，发射机在第一个时隙从第一个天线发射x1，从第二个天线发射x2

。接着在第二个时隙从第一个天线发射，从第二个天线发射。因此发射码字为

10.2空时分组码分别用和来表示天线1和天线2上的发射序列。Alamouti方案的主要特征是两根发射天线的发射序列是正交的10.2空时分组码最大似然译码过程以2个发射天线，1个接收天线的Alamouti码为例，接收信号的矩阵表达式为：以Alamouti码为发射码10.2空时分组码10.2空时分组码10.2空时分组码得到判决统计为：Alamouti码具有两个重要性质：译码简单：通过线性处理，每个符号被分别译码。最大分集：满足秩准则，因此能够提供最大分集。10.2空时分组码实正交设计

广义实正交设计

复正交设计

广义复正交设计10.2空时分组码当天线数更大时，能否设计出类似的空时码？

当发射天线数大于2时，不可能存在各元素为复数的满码率正交空时分组码，Jafarkhani提出了发射天线数为4的满码率准正交空时分组码。10.2空时分组码准正交空时分组码-编码过程Alamouti码的生成矩阵：为了设计一个满速率的码，放宽简单独立译码条件。设计一族码，即准正交空时分组码（QOSTBC），可以进行符号对的独立译码。10.2空时分组码式中矩阵是矩阵的复共轭，例如10.2空时分组码将的第i列表示为。对于任意的待定变量 ，有组与组正交，组内不正交，满足准正交关系。码字的分集阶数为2。10.2空时分组码最大似然译码过程以4个发射天线，1个接收天线举例接收信号的矩阵表达式为：10.2空时分组码10.2空时分组码式中10.2空时分组码取其中10.2空时分组码10.2空时分组码得到判决统计为10.2空时分组码式中10.2空时分组码成对译码准正交空时分组码的最大似然译码就等价于求如下最小问题：通过代数处理求得上述最大似然译码等价于最小化和式为10.2空时分组码式中10.2空时分组码以及10.2空时分组码因为独立于，并且独立于，所以符号对和可以独立的译码。10.2空时分组码旋转准正交空时分组码当有个接收天线时，码率为1时获得的最大分集阶数为。若所有的符号都选自同一星座，那么在这种情况下，速率为1的复正交码不可能达到的 分集阶数。为了达到满分集，对不同的发射符号选用不同的星座。10.2空时分组码例如，可以在发射之前将符号和旋转，将旋转后的版本分别表示为和。用代替时，准正交空时分组码就有可能达到满分集。生成矩阵为10.2空时分组码旋转角度，变为，则上式变为10.2空时分组码将的第i列表示为。对于任意的待定变量 ，有组与组正交，组内不正交，满足准正交关系。10.2空时分组码10.3低密度奇偶校验码LDPC码和大部分可译的接近香农极限的纠错码都可以理解成图形编码。图形不但能描述编码，更重要的是能构造出用于迭代译码的和积译码算法。这种编码方案在保持了合理的译码复杂度的同时，可使信息传输速率接近信道容量。本节首先介绍LDPC码的定义，然后对其编、译码进行简要讨论10.3低密度奇偶校验码10.3.1低密度奇偶校验码的定义LDPC码是一种线性分组码，该码不是通过生成矩阵来定义，而是通过奇偶校验矩阵来定义的。该种码最主要的问题是如何译码而不是编码，因此LDPC码最主要的问题是寻找一种便于译码的算法。其校验矩阵非常大，然而矩阵中非零元素却很少，更准确地说，非零元素在所有元素中所占比例很低，这就是称为“低密度”码的原因。Gallager对LDPC给出了如下定义：一个（N，p，q）LDPC码，长度为N，奇偶校验矩阵H中每列“1”的个数为p，每行“1”的个数为q；每一行中非零元素的个数称为行重，每一列中非零元素的个数称为列重，因此，行重为q，列重为p；如果所有行都是线性无关的，则码字的码率为(q-p)/q。10.3低密度奇偶校验码奇偶校验矩阵H的构造原则是：任意两列只有一个“1”相同；任意两行最多只有一个“1”相同。矩阵的密度r定义为“1”的个数与所有元素个数的比。例如构造一个（12，2，4）码字，其奇偶校验矩阵为（10.20）很显然这种结构满足上面的规则：即每列有p个“1”，每行有q个“1”，即列重p=2，行重q=4，密度r=1/3。很显然这种结构是很随机的。为了描述的方便，LDPC码（N，p，q）等价地表示为（N，k）形式，其中，k=NpN/q为信息位。 N×码率10.3低密度奇偶校验码假设码字为，其中是信息位，而是校验位，上面校验矩阵可以用校验方程表示为（10.21）10.3低密度奇偶校验码也可以用图来表示，通常称为Tanner图。本例校验矩阵对应的Tanner图如图10.6所示。图10.6校验矩阵的Tanner图表示10.3低密度奇偶校验码图中上一行由N个变量节点（用圆圈表示）组成，表示码字的信息位，用表示，对应奇偶校验矩阵的列；下一行由k个校验节点（用方块表示）组成，表示码字的校验位，用表示，对应奇偶校验矩阵的行。节点之间通过边连接，同类节点之间没有边连接，只有两类节点之间有边存在。与变量节点连接的边的条数称为的度，与校验节点连接的边的条数称为的度。对一个正则LDPC码，所有信息位的度都相同，所有检验位的度也相同，这样一个Tanner图就称为正则的。如果校验矩阵的第i行第j列元素为“1”，则Tanner图中的第j个变量节点与第i个校验节点有一条边相连。10.3低密度奇偶校验码10.3.2低密度奇偶校验码的译码正如上面所提，奇偶校验矩阵的稀疏结构是译码的关键，因为它决定译码的复杂度。采用最大似然译码是一个N-p困难问题（也就是说，必须检查所有可能的码字，并与接收信号进行比较）。因此通常采用迭代算法进行译码，该种算法称为置信算法。通过Tanner图进行译码称为置信算法或者消息传递。每个节点收集传入的信息，按照局部规则进行计算，得出每个变量节点值为0的概率。然后每个节点再把计算结果传给其他节点，这种传递是双向的。10.3低密度奇偶校验码一方面，变量节点的计算结果会传递给校验节点，该计算结果定义为

；另一方面，校验节点的计算结果会传递给变量节点，该计算结果定义为

；最后，总的计算结果由所有节点的

、

和外部信息得出。如图10.7所示，接收信号矢量为

。图10.7消息传递因子图10.3低密度奇偶校验码对AWGN信道，有如下的译码步骤：（1）首先，知道接收信号矢量

的值，就可以决定数据比特的值。知道了噪声

的统计值之后，就可以计算变量节点为“1”或“0”的概率，然后把信息传递给校验节点。反之，校验节点暂时不能把有用信息传递给变量节点，因此，有

（10.22）

（10.23）10.3低密度奇偶校验码（2）其次，校验节点给每个变量节点传递一个不同的信息。假设与第i个变量节点相连的所有校验节点的集合为Ai，则每个校验节点包含两种重要的信息： ①它知道与该校验节点相连的所有数据比特的值（或概率大小）； ②进入校验节点的所有数据位之和为0mod2，这是奇偶校验矩阵的关键点，根据这些信息，可以计算第j个数据位发生的概率。10.3低密度奇偶校验码因为是AWGN信道，会产生连续输出，由于不是二进制信道，因此需要用对数似然来代替简单的概率，信息变为（10.24）式中：A(i)-j指“A(i)中除去第j个校验节点的集合”，即去除第j个校验节点之后，与第i个变量节点相连的所有校验节点的集合；上标(l-1)是指第

(l-1)次迭代。10.3低密度奇偶校验码（3）然后，利用校验节点传递的信息来更新对数据比特所做的判决。规则为 (10.4)式中：

是指去除第i个变量节点之后，与第j个校验节点相连的所有变量节点的集合。10.3低密度奇偶校验码（4）根据上面的讨论，可以计算出数据位是“1”或“0”的近似后验概率，为

（10.43）由此可以对译出的码字进行初步判决，如果译出码字与发射码字相同，即校验和为0，则停止译码。10.3低密度奇偶校验码例10.1已知一LDPC码的奇偶校验矩阵为假设发射的码字为信道为AWGN信道，噪声方差为接收端对应的信噪比为接收码字为求译码结果。下面给出一个利用低密度奇偶校验矩阵进行译码的例子。dB10.3低密度奇偶校验码接收似然值的硬门限会导致译出的码字中第2位出现1个错误，即消息传递迭代算法和纠错过程如图10.8所示。a.计算

，进行初步估计，得出校验和不为零，找出错误位置，然后计算μ(1)和L，对译出码字进行判断，计算出校验和不为零，即10.3低密度奇偶校验码10.3低密度奇偶校验码b.继续迭代，计算

、μ(2)和L，对译出码字进行判断，计算出校验和不为零，即10.3低密度奇偶校验码c.继续迭代，计算

、μ(3)和L，对译出码字进行判断，计算出校验和不为零，即10.3低密度奇偶校验码d.继续迭代，计算

、μ(4)和L，对译出码字进行判断，计算出校验和不为零，即10.3低密度奇偶校验码e.继续迭代，计算

、μ(5)和L，对译出码字进行判断，计算出校验和不为零，即10.3低密度奇偶校验码f.继续迭代，计算

、μ(6)和L，对译出码字进行判断，计算出校验和不为零，即10.3低密度奇偶校验码g.继续迭代，计算

、μ(7)和L，对译出码字进行判断，计算出校验和为零，译码停止，译出码字与发射码字相同，即10.3低密度奇偶校验码图10.8低密度奇偶校验消息传递的迭代过程LDPC码还有很多译码算法，感兴趣的读者可以参考相关文献。10.4网络编码与协作10.4.1网络编码网络编码是一种基于网络层的编码技术，允许网络节点在传统数据转发的基础上参与数据处理，是一种提高网络吞吐量、稳健性和安全性的有效方法。其核心思想是在传统存储转发的路由算法基础上，通过允许对接收的多个数据包进行编码信息融合，增加单次传输的信息量，提高网络整体性能。网络编码概念一经提出便引起了国际学术界的关注，其理论和应用已成为通信领域研究的新热点。10.4网络编码与协作1.网络编码的相关概念下面通过一个例子来介绍网络编码的相关概念。图10.9给出了传统路由方法与网络编码进行比较的示意图，可以用图10.9(b)来阐述网络编码的基本原理。图中s是信源，x、y是信宿，各条点对点的传输链路的信道容量都是1，现要将2比特数据a、b同时从s传到x、y。易知s与z、y之间均分别存在两条独立路径，若采用传统路由方法，如图10.9(a)所示，由于两组路径间存在共有链路wz，a、b不能同时在wz上传输，则s到z、y的最大信息传输速率为1.5比特/单位时间。若采用网络编码方法，在节点w上对a、b执行异或操作并转发，则节点x可以通过aba计算解出b，同理y也可以解出a，从而使s到z、y的信息流速率达到2比特/单位时间，带宽利用率提高33％。10.4网络编码与协作

（a）传统路由方法示意图

（b）网络编码示意图图10.9传统路由方法与网络编码的比较10.4网络编码与协作该例表明，只要允许网络中的节点进行网络编码，网络的传输效率就能得到进一步的提升。当然，所用的编码和解码方案是要通过网络协议进行协商的。事实上，网络编码理论突破了传统的路由概念，允许通信网络的中间节点对接收到的信息进行编码处理，可以有效提升通信网络的传输能力。10.4网络编码与协作下面用三元组(S，T，X来)描述组播通信。信源S将一组消息X＝(x1,,xn)

通过中继节点传递给一组信宿T=(t1,,tn),x1,,xn均是某个字母表上的符号。网络编码就是一组满足某些约束条件的边函数的集合。通过为节点

iI的每条出边找到一个映射，使得所有信宿

tiT能同时接收到消息集合X，并保证节点的输出信息完全由其输入信息和生成信息决定，则称网络具有网络编码解。10.4网络编码与协作2.编码方法网络编码的基本特征就是在网络层对传输的信息进行智能化处理，包括采用各种编码策略。对一个给定的组播网络，如何设计网络编码实现最大流传输是一个重要的问题。网络编码按照节点输出和输入的关系可划分为线性网络编码和非线性网络编码，根据编码系数生成的随机性可划分为随机网络编码和确定网络编码。这里仅讨论目前比较成熟的网络编码构造方法－代数法，信息流法，随机网络编码方法10.4网络编码与协作（1）代数法代数型编码方法是由R.Kotter和M.Medard提出，其核心思想是将网络中节点输入信息与输出信息之间的关系利用矩阵的形式表示出来，从中发现一些内在的联系。这样可以帮助人们从网络系统的角度重新认识信息传输的内在规律，包括网络中各个节点的编码设计。Koetter等人给出了网络编码构造的代数框架，将系统转移矩阵M分解为T个子矩阵

，通过构造一组参数使得每个子矩阵的行列式非0，从而得到网络编码解。基于代数法的构造算法的优点在于可借助成熟的矩阵理论分析各类拓扑结构的网络编码问题，其缺点是可扩展性差、计算量大。10.4网络编码与协作（2）信息流法信息流法利用解耦技术，将网络编码问题分解为确定编码子图和给子图分配码字两个子问题分别求解。Jaggi等人给出了一个多项式时间复杂度的网络编码构造算法，分为两个步骤：首先采用流算法为每个信宿找到从信源到信宿的n条边不重叠的路径集合，然后采用贪心策略对已知路径的边按拓扑顺序分配线性码，并保证任意信宿的n条入边上的全局编码向量线性独立，且能扩张成有限域，从而获得网络编码解。信息流法的优点在于解耦合的两个子问题可结合成熟的优化理论采用分布式算法分别求解，难点在于保证所有信宿的人边上的编码向量均线性独立。10.4网络编码与协作（3）随机网络编码方法所谓随机的网络编码方法，就是每个网络节点独立的随机选取一种映射方式将它自己接收到的输入信息映射到相应的输出链路上。通常情况下，该映射方式选取为线性映射，即在给定的一个有限数域上为每个输入信息流选取相应的加权系数。利用这种方法，可以证明在进行组播信号时，每个接收节点可以以很高的概率恢复原始信号。10.4网络编码与协作3.网络编码的应用举例考虑如图10.10所示的网络拓扑结构的信息传输系统，S表示信源节点，D表示目的节点，A、B和C表示中继节点，负责将信源S的信息转发给目的节点D。10.4网络编码与协作图10.10抗一条链路中断的网络编码模式10.4网络编码与协作从图10.10的拓扑结构可知，当每条链路的最大传输容量均为一个信息单位时，则从信源S到目的节点D的最大传输容量为3个信息单位。对这种点到点的网络传输，只采用多路径的传输模式，就可以实现最大传输容量的传输。在本结构中，这3条路径分别为：S→A→D，S→B→D和S→C→D。然而，如果在这些路径中某一条链路发生中断，则目的节点D就无法恢复信源S发送的信息。例如B→D这条路径中断了或出现故障，此时需要通知源节点调整发送方式或修改传输路径。而B→D这条路径中信源发送的信息会全部丢掉。显然，这种单纯的多路由网络传输模式是无法抗网络链路故障的。10.4网络编码与协作与此对应的是，如果采用如图10.10所示的网络编码的模式，在路径S→A→D传输信息a，在路径S→B→D传输信息b，在路径S→C→D传输信息a+b，那么一旦有一条路径出现问题使得信息无法正常传输，目的节点D仍能正确恢复信源S发送的信息。例如B→D这条路径中断了或出现