1.2 信道编码技术的发展及其在移动通信中的应用

1.2.1 信道编码技术的发展

1948年，C. E. Shannon在贝尔技术杂志上发表了奠基性文献“通信的数学理论”[16]，标志着信息与编码理论这一学科的创立。Shannon在文中提出了著名的有噪信道编码定理，即对任何通信信道都存在一个称为信道容量的参数C，只要实际传输速率R小于C，就存在一种编码方法，当码长充分大时，可使系统的错误概率达到任意小；反之，如果R大于C，则不可能有一种编码能使错误概率趋于0。

在Shannon之前，人们普遍认为在有噪信道里进行通信获得任意小的错误概率的唯一途径就是减小传输速率到零。有噪信道编码定理从理论上证明了通过信道编码技术可使得信息传输速率接近信道容量。编码定理及其证明虽然没有给出编码的具体设计方法，却指出了达到信道容量的编译码方法的指导性路线，即构造随机长码和采用接近最大似然译码（信道编码定理最初是Shannon基于典型序列方法证明的，后来Gallager基于最大似然译码给出了强编码定理）。此后，构造可逼近信道容量（Shannon限）的信道编码具体方法及其可实用的（线性复杂度）有效译码算法一直是信道编码理论与技术研究的中心任务，也就是如何构造出能接近或达到Shannon限的码（称为Shannon码或渐近好码）是编码学者长期追求的目标。

过去的几十年中，有两类纠错编码得到深入研究并在通信/存储系统得到广泛应用，即分组码与卷积码。1950年，数学家Hamming提出了第一个实用的差错控制编码方案，即汉明码[17]。方法是将输入数据每4比特分成一组，然后通过对信息比特进行线性组合得到3个校验比特，组成7比特的码字。利用校验比特不仅可以检测传输错误，还可以纠正单个随机错误。这个编码方法就是分组码的基本思想。分组码很快引起代数学家的兴趣，并迅速发展成系统的代数编码理论，成为纠错码中理论体系最完整、最成熟的一类码字。1954年，Reed和Muller提出了一种新的分组码：Reed-Muller码，简记为RM码[18]。RM码是一类参数选择很广的分组码，在码字长度和纠错能力方面具有较强的适应性。1957年，Prange提出了一类重要的分组码即循环码[19]，它在线性码中占有重要地位，是分组码中研究最深入、应用最广泛的子集。循环码的码字具有循环移位特性，由此大大简化了编译码结构，使得实用成为可能。循环码中一个重要成员就是由Bose、Ray-Chaudhuri和Hocquenghem于1959―1960年分别提出的可纠正多个随机错误的BCH码[20][21]。BCH码纠错能力强，编码简单，具有严格的代数结构。1960年，Reed和Solomon构造了一类很强纠错能力的多进制BCH码，即著名的Reed-Solomon码[22]（简称RS码）。RS码最突出的优点是非常适合纠正突发错误，在CD播放器、DVD播放器及DVB和数字用户线（DSL）标准中有广泛的应用。分组码虽然基于数据分组的编码方式，译码时必须等待整个码字完整接收下来，才能实现译码，故在码长较大时会引入一定的时延。

卷积码[23]是与分组码同时发展起来的另一种纠错编码方式。卷积码编码时本组的校验元不仅与本组的信息元有关，还与以前时刻输入到编码器的若干信息组有关。正是由于利用了各组之间的相关性，且每组的长度及其包含的信息的长度均较小，因此在与分组码同样的码率和设备复杂度条件下，无论从理论上还是从实际上均已证明卷积码的性能不比分组码差。但是由于缺少有效的分析工具，分析上得到的成果要少于分组码，并且好码往往要借助计算机搜索。在相同的码长下，卷积码的译码比分组码相对容易一些，最常用的是维特比（Viterbi）算法[24][25]，它是基于卷积码网格图的一种最大似然译码算法，卷积码译码以流的方式连续进行，译码时延相对较小。

上述各信道编码方案虽然译码复杂度大多在可接受的范围内，然而由于码长较短，其性能距Shannon限有较大距离。为了构造出译码复杂度可接受且差错控制性能优异的长码，Elias在发明卷积码的前一年便提出了乘积码的概念，这是第一个由短码构造长码的方法。乘积码以两个线性分组码作为分量码，其码长为各分量码码长的乘积，译码可通过对各分量码单独译码从而得到次优的结果。1966年，Forney提出了另一种由短分量码构造长码的编码方案：（串行）级联码[26]。在级联编码方案中，将内码和外码进行串行级联，内译码器可以看作一个噪声滤波器，它不仅能改变错误分布，而且能有效增加信号的接收信噪比。为了提高级联码的性能，常采用卷积码为内码，分组码（如RS码）为外码。该方案充分利用了卷积码和RS码的纠错性能互补的特点，在工业界有着广泛的应用。级联编码方案虽然可以提高系统性能，同时也损失了部分编码效率，而且内、外译码器间只是顺序译码并没有信息交换。需要说明的是，几乎同一时期，Gallager提出了LDPC码，这是一种直接构造长码并采用低复杂度的迭代译码来解决译码问题的编码方法，但在随后的几十年中，由于受硬件、软件所限及级联码的影响，低密度校验码并没有引起太多关注。

经典纠错编码尽管设计精巧，但其性能与Shannon限存在2～3 dB的明显差距。现代纠错编码的特征是具有逼近Shannon限的译码性能。到目前为止，学术界与工业界影响力最大的三类先进的现代纠错编码方式分别是Turbo码、LDPC码与Polar码。

1993年，法国的Berrou等提出了并行级联卷积码即Turbo码[27]，他将卷积码和随机交织器结合在一起，实现了随机编码的思想，同时通过多个软输出译码器之间的迭代，系统渐近性能逼近容量限。仿真结果表明，在加性高斯白噪声（Additive White Gaussian Noise, AWGN）信道上，采用长度为65536比特的伪随机交织器在调制方式为BPSK时，码率为R=1/2的Turbo码在误比特率（Bit Error Rate, BER）为10-5时距离Shannon限约0.7dB。这一惊人发现改变了长期以来把信道截止速率作为实际容量的历史，使信道编码理论和实践进入了一个崭新的阶段。Turbo码除了性能优异，还由于是卷积码并行级联得到，因此编码复杂度很低；Turbo码具有很好的灵活性，理论上可以支持任意长度的信息比特进行编码，通过速率匹配操作可以得到任意码率的码字；Turbo码译码算法为软输入软输出（soft-input soft-output）的迭代译码[28][29]，其缺陷在于具有较高的译码复杂度，且译码并行度受限，同时Turbo码虽然中低码率性能优异但在高码率时，受过度打孔影响，性能恶化，且容易出现较高的译码平层。

随着对Turbo码的深入研究，发现Turbo码的实现原理和Gallager提出的LDPC码极其相似，从此LDPC码被重新发现。LDPC码是一类线性分组码，其对应的奇偶校验矩阵是“1”的个数很少的稀疏矩阵。LDPC码最早是由Gallager于20世纪60年代初期在其博士论文中提出的[30][31]，故又称为Gallager码。但在其后的长时间里被忽视了，其中一个重要原因是就当时的技术条件而言，LDPC编译码器的实现过于复杂；再就是RS码的发现，RS码与卷积码构成的级联码被认为是很完美的。直到1996年，MacKay等发现LDPC码同样具有逼近信道容量的译码性能[32][33], LDPC码才又引起了人们的研究兴趣。MacKay的研究表明，尽管规则LDPC码性能优异，但与Turbo码相比还有一定的差距。2001年，Richardson等提出了著名的密度进化算法来优化非规则LDPC码的参数[34-37]，基于此所设计的1/2码率的非规则LDPC码在AWGN信道中，其性能门限距Shannon容量限不超过0.0045dB，仿真也表明在BER=10-6时，长度为107的非规则LDPC码距离信道容量0.04 dB[38]。这一结果超过所知的最好的Turbo码，是继MacKay重新发现LDPC码后，又一具有里程碑意义的成果。LDPC的主要优点在于译码复杂度低且其结构适于部分并行或全并行译码，是实现高吞吐译码的最有力竞争者。LDPC码缺点在于编码复杂度较高，所需的存储量较大，性能优异的LDPC码构造比较困难，同时对任意固定的码长与码率都需要对应一个校验矩阵，如果要支持灵活的信息比特长度与编码码率对LDPC校验矩阵构造、译码器的设计来说都是个严峻的挑战。LDPC码性能取决于校验矩阵的构造，而校验矩阵构造方法主要分为随机构造和代数构造两类。随机构造方法主要是附加一定的约束条件利用计算机搜索的方法得到目标校验矩阵；代数构造方法主要是利用组合构造方法、几何构造方法、图论方法、实验设计方法、置换设计方法等来设计性能优异的校验矩阵。一般来说，代数的方法往往更容易设计出性能优异的LDPC码，但是随机构造方法则约束更少，高深的数学知识也不一定是必需的。无论是随机的还是代数的LDPC码构造方法在学术界与工业界都得到了广泛的研究与应用。

尽管Turbo和LDPC码的性能距离Shannon容量限已经非常小，但是始终没有达到容量限。2008年，Arikan在国际信息论会议（ISIT）上首次提出了信道极化的概念[39]，并于2009年发表的论文中对极化编码（Polar码）给出了详细的阐述[40]。Polar码是首个可严格证明在二进制输入对称离散无记忆信道下可达容量限的编码方案，Polar码的出现引起了学术界与工业界的高度关注。Polar码是线性分组码，其生成矩阵是基于信道极化现象构造得到的类哈达玛矩阵。Arikan发现将极化核矩阵使用Kronecker积进行扩展，并使用扩展矩阵对各子信道进行合并，然后按照顺序对合并后的矢量信道进行分裂，则对于组合前的二进制信道会发生信道极化。该现象使得分裂后信道产生两极分化：一部分会变成容量趋于0的纯噪声信道；另一部分变成容量趋于1的无噪声信道。在这样的极化信道上信道编码是非常简单的：只需要将所要传输的数据加载在容量趋近于1的那些信道上，而容量趋近于0的那些信道不使用，就可以实现数据的可靠传输。在译码算法方面，Arikan给出的原始Polar译码方法是逐次抵消（Succesive Cancellation, SC）算法，该算法译码复杂度为O(N log N)。在码长趋于无穷大时，使用简单的SC译码算法就可以取得优异性能，但是在码长受限时，基于SC算法的Polar码性能损失严重。文献[41]提出了一种基于SC的改进译码算法，称为SCL（SC List）译码算法，在中短长度的码长时可以获得接近最大似然译码的性能。Polar码采用SCL译码时性能非常优异，编码简单，可以很简单地实现任何码率的Polar编码，支持多速率码的速率适配方法也很简单，对实际应用来说非常具有吸引力。然而，年轻的Polar码也存在很多问题，如译码列表较大时，SCL译码的时间复杂度与存储空间都很高，同时SCL译码适于串行译码实现高吞吐译码器比较困难；SCL译码无法输出对数似然比软信息，IR-HARQ方案也不如LDPC与Turbo成熟等。

关于信道编码理论与技术的发展，可进一步阅读相关文献[42][43]，相关应用可参见文献[44]。

1.2.2 信道编码技术在移动通信中的应用

蜂窝移动通信系统在过去几十年中迅猛发展，使得用户彻底摆脱终端设备的束缚，变成社会发展和进步的必不可少的工具。纠错编码作为不可或缺的一环，在移动通信系统中有着广泛的应用。

第一代通信系统是模拟通信系统，业务信道采用模拟信号传输，而控制信道传输数字信令并进行了信道编码与数字调制操作。以英国系统为例，基站与终端信道编码采用不同的BCH码，编码后重复5次发送以提高衰落信道性能。

第二代移动通信系统，如欧洲的GSM系统、北美的IS-95都是数字通信系统。GSM在全速率业务信道与控制信道采用了约束长度为5，码率为1/2卷积编码。更具体地，GSM全速率业务信道20ms业务帧包含260个比特，其中50个最重要的比特、132个重要比特、78个不重要比特。50个重要比特首先进行循环冗余校验（Cyclic Redundancy Check, CRC）编码得到53个比特的码字，然后与后面的132个重要比特与4个全零尾比特一起采用1/2码率的卷积码进行编码得到378个比特，最后的78个比特不予保护得到456个比特的语音编码块。对于半速率业务信道为了改善通话质量采用码率为1/3，约束长度为5卷积编码。GSM控制信道采用外码为Fire码[45]、内码为卷积码的串行级联编码方案，由于Fire码适于检测与纠正突发错误码，与善于纠正随机错误的卷积码结合可以进一步提高控制信令的可靠度。

IS-95窄带CDMA系统的纠错编码是分别按照前向链路与反向链路来设计的，主要包括卷积编码与CRC编码。前向链路中除导频信道之外的同步信道、寻呼信道、业务信道都采用了约束长度为9，码率为1/2，生成多项式为[561,753]8的(2,1,9)卷积码。反向链路（包括业务信道和接入信道）则采用了约束长度为9，码率为1/3，生成多项式为[557,663,711]8的(3,1,9)卷积码。反向链路卷积码的码率更低，具有更强的纠错能力，有利于提高基站采用非相干解调接收时的抗干扰能力。卷积码编码器如图1.5所示。

第三代移动通信与2G相比要提供更高的传输速率、更多形式的数据业务，所以纠错编码提出更高要求。3G仍然以IS-95中的(2,1,9)和(3,1,9)卷积码作为语音信道和各个控制信道的纠错编码方案。确定Turbo码为数据、多媒体等业务的编码方案。3GPP在WCDMA系统中采用的Turbo码的母码码率为1/3，两个8状态的Turbo分量编码器的生成多项式为g0=13, g1=15，编码器结构如图1.6所示。WCDMA Turbo码内交织器采用分组（block）交织器，交织器的行的数目为5、10或20，支持的信息比特的长度范围为40≤K ≤5114，信息比特按行写入交织器，经过行列置换后，逐列读出[46]。

第四代移动通信（LTE）同样采用了卷积码与Turbo码作为纠错编码方案，而且卷积码用于控制信道，Turbo码用于数据信道。与WCDMA的纠错编码方案相比，LTE对纠错编码方案进行了进一步优化。

LTE卷积编码采用1/3码率的咬尾卷积码（Tail-Biting Convolutional Codes, TBCC），约束长度为7，生成多项式（按八进制）为[133,171,165]8，编码框图如图1.7所示。LTE TBCC有6个移位寄存器，其初始值用信息比特的最后6个比特进行初始化，如此一来，移位寄存器的初始与最后状态是相同的，与尾比特归零操作相比，TBCC降低了尾比特的开销，这对于信息比特长度很短的控制信令来说会明显提高其频谱效率。

LTE Turbo编码结构与WCDMA相近，都是基于两个8状态的生成多项式为g0=13, g1=15的Turbo分量编码器并行级联得到1/3码率的母码，但是分量码间的内部交织器与WCDMA完全不同。LTE Turbo采用二次置换多项式（Quadratic Permutation Polynomials, QPP）交织器，即f(i)=(f1· i+f2· i2)mod K，其中i代表交织后的序号，f(i)代表交织器输入的序号，K是编码器输入比特序列的长度，其范围为40≤K ≤6144。QPP交织器的主要优点是无冲突交织处理，能够支持并行译码，相对于WCDMA Turbo码的串行译码能够显著提高译码速度[47][48]。

LDPC码作为另外一种接近Shannon限的信道编码，虽然由于早期研究不够成熟，错过了3G与4G标准，但其出色的性能，较低的译码复杂度使其被多个重要的国际标准采纳，如Wi-Fi、WiMax、CCSDS等。

Wi-Fi中如802.11n与802.11ac采用的LDPC码支持648、1296、1944三种码长，1/2、2/3、3/4、5/6四种码率[49]。上述LDPC码校验矩阵具有准循环结构，码长为648/1296/1944对应的循环子矩阵大小分别为27/54/81，且校验矩阵具有双对角结构，该结构导致所设计的码具有较小的存储量，便于实现部分并行译码，同时可以直接根据校验矩阵进行编码。在802.11n/802.11ac协议中通过对LDPC码执行缩短与打孔操作实现速率匹配。Wi-Fi中LDPC码能够实现较大的吞吐量，其设计思想影响了后续标准中LDPC码的设计。

WiMax（Worldwide Interoperability for Microwave Access）采用的LDPC码的校验矩阵，通过将多个基矩阵中的每个元素扩展为一个子矩阵，得到多种码率和码长的LDPC码[50]。实际使用的基矩阵有6种，码率分别为1/2、2/3、3/4和5/6，基矩阵的列数都为24，扩展因子取值为Z=[24:4:96]。基于基矩阵改变扩展因子就得到不同大小的校验矩阵，对应不同长度的码，码长N=24×Z，范围为576≤N ≤2304。WiMax采用的校验矩阵与Wi-Fi类似，都具有双对角结构可以实现线性复杂度编码。

针对空间通信应用，CCSDS（Consultative Committee for Space Data Systems）蓝皮书标准化了两类LDPC、码[51]。第一类为基于欧几里得几何构造的(8176,7156)准循环LDPC码，其校验矩阵由2行16列循环子矩阵构成，每个循环子矩阵大小为511×511。该码的码率较高，其BER误码平层低于10-10，译码收敛速度快，仅需要10次迭代译码就接近收敛。第二类LDPC码，具有更低的码率应用于深空通信，分别支持码率为1/2、2/3、4/5，码长为1024、4096、16384，共9个码。该LDPC码同样为准循环矩阵，子矩阵的大小根据码长与码率的不同分别取值为{128,256,512,1024,2048,4096,8192}。第二类码的码长与码率比较灵活，性能非常优异，但是译码收敛速度较慢，其误码平层性能不如第一类码。

各个标准中对纠错编码的研究及其工业化经验为5G纠错编码的设计打下了坚实的基础。