第10章现代编码技术

第10章分组码10.1BCH码10.2RS码10.3卷积码10.4网格码10.5TURBO码10.6LDPC码10.6空时编码

10.1BCH码

10.1.1BCH码的定义

BCH码是一类纠正多个随机错误的循环码，是以3个发现者——博斯(Bose)、查德胡里(Chaudhuri）和霍昆格姆(Hocquenghem)姓氏的字头命名的。这是迄今为止发现的最好的线性分组码之一。

BCH码的重要性在于它解决了生成多项式与最小码距之间的关系问题。

该码的纠错能力很强，且构造简便。

10.1BCH码

10.1.1BCH码的定义

本原多项式的概念。

10.1BCH码

10.1.2BCH码及最小汉明距离

定义1设m是一正整数，m0是任意整数，GF(q)表示有q个元素的有限域，其中q是一个素数或素数的幂，GF(qm)是GF(q)的扩域，a∈GF(qm)，如果一个循环码由GF(q)上的多项式g(x)生成，并且g(x)的根包含下面d-1个根：

a，a

2，a

3，…，a

d－1

那么，称这个由g(x)生成的循环码为设计距离为d的q元BCH码。

如果定义中g(x)有一个根是GF(qm)中的本原元，那么g(x)生成的BCH码码长必定为n=qm－1，称这种BCH码为本原BCH码，否则称为非本原BCH码。非本原BCH码是存在的，其码长是qm－1的因子。

BCH码的优势之一在于，如果确定了BCH码的生成多项式g(x)的连续根，则由g(x)生成的BCH码的实际最小汉明距离不小于设计距离。

定理10.1.1BCH码的最小汉明距离至少为d。10.1.3BCH码的编码方法

二元BCH码

二元信号在工程上最容易实现，因而二元BCH码在工程上应用最广泛。对给定的正整数m和d(d=2t+1，t<2m－1)，二元BCH码的码长、校验位数和最小汉明距离是什么呢？

定理2给定正整数m和t，存在一个(n，k)二元BCH码，其生成多项式以a，a

3，a

5，…，a

2t－1为根，其码长n=2m－1或n|2m－1，能纠正t个错误，并且n－k≤mt。

10.1.3BCH码的译码方法

1.一般译码方法

1）确定BCH码的伴随式；

2）寻找错误位置多项式；

3）纠正错误；

2迭代译码算法10.2RS码

Reed-Solomon码是一类有很强纠错能力的多进制BCH码，也是一类典型的代数几何码。它首先由里德（Reed）和索洛蒙（Solomon）应用MS多项式于1960年构造出来的。

它是一类纠多个随机错误的循环码，具有严格的代数结构，构造方便，便于从理论上对应用进行研究。除了译码算法有些复杂之外，它的纠错能力和译码速度均是其它码类无法比拟的，特别在短和中等码长下其性能接近于理论值。10.2.1RS码的定义

定义:对于一个长度为符号的RS码，每个符号都可以看成是有限域GF（）中的一个元素。最小码距为d0符号的RS码的生成多项式具有如下形式：

这里，是GF（）中的一个元素。

10.2.1RS码的定义

在（n,k）RS码中，输入信号分成kmbit一组，每个码元由mbit组成，因此一个码组共包括k个码元。一个能纠正t个码元错误的RS码的主要参数：

10.2.2RS码的编码

时域编码：时域编译码算法出现较早，由于比较成熟而被广泛采用；

频域编码：频域编译码算法出现的较晚，但由于利用了快速傅立叶正反变换(FFT/IFFT)而提高了编译码速度，具有较大的发展潜力。

这两种算法都比较简单，时域编码只需要运算一次多项式除法，而频域编码只需要计算一次IFFT。

10.2.2RS码的编码

它们的区别在于：经时域算法得到的码字是系统码，可用于截短编码；而频域算法得到的码字是非系统码，不能用于截短编码。

时域编码：

将待编码信息多项式升位后除生成多项式,将所得的余式置于升位的信息多项式之后，就形成RS码。

RS码的编码方法与CRC一样，也是除以，所以同样可以采用移位寄存器来实现。

10.2.2RS码的编码

时域编码：

n-k级线性移位寄存器编码电路10.2.2RS码的编码

它们的区别在于：经时域算法得到的码字是系统码，可用于截短编码；而频域算法得到的码字是非系统码，不能用于截短编码。

时域编码：

将待编码信息多项式升位后除生成多项式,将所得的余式置于升位的信息多项式之后，就形成RS码。

RS码的编码方法与CRC一样，也是除以，所以同样可以采用移位寄存器来实现。

10.2.3RS码的译码方法

RS码的译码算法比其它码类的译码算法复杂得多，这是因为RS码是一种非二元循环码，它不再具备特征为2的域的运算等性质。

分类：

RS码的频域译码算法：RS码的时域译码算法：也是从计算接收码字的伴随式入手的，并且在译码过程中不仅要找出错误位置，而且还要找出对应错误位置的错误大小，这样就增加了它的译码难度。10.2.3RS码的译码方法

RS码的译码算法步骤：

(1)根据接收码字求出伴随式Sj；

(2)由伴随式求出错误位置多项式；

(3)由错误位置多项式求出错误位置值；

(4)由错误位置值求出对应的错误值；

(5)求出错误图样，纠错成功。

10.3卷积码的表示方法

10.3.1卷积码的概念

卷积码是由伊利亚斯提出，其信息码个数和码长通常较小，故时延小，特别适合于以串行形式传输的场合。

另外，卷积码在任何一个码组中的监督码元都不仅与本码组的信息码元有关，而且还与前面若干个码组的信息码元有关，其纠错能力随着前面若干个码组数的增加而增加。故在实际应用中，卷积码的性能优于分组码，而且设备简单。

10.3卷积码的表示方法

10.3.1卷积码的概念

一个(n，k，m)卷积码编码器由输入单元、编码单元和输出单元三部分组成，如图所示。图10.1(n，k，m)卷积码编码器 10.2卷积码的表示方法

10.3.1卷积码的概念

输入单元的功能是把1路串行输入信元变换成k路并行输出，并作为编码单元的k路信元输入；

输出单元的功能是把编码单元的n路并行输出变成1路串行输出，并作为卷积码的码字；

编码单元的功能是把k路并行输入信元变成n路并行输出。是卷积码中最关键的部分。 10.2卷积码的表示方法

10.3.1卷积码的概念

（2,1,2）卷积码编码器

10.2卷积码的表示方法

10.3.1卷积码的概念

（2,1,2）卷积码编码器

10.2卷积码的表示方法

10.3.1卷积码的概念

当有k位数据输入时，输出码字序列共有卷积码的编码效率为10.3.2卷积码的表示法

1.卷积码的多项式

用符号D表示延时算子，输入信息x中的相对于来说晚1个时刻(即一个码元时间长度)出现，相对于晚2个时刻出现，其余以此类推。用Dk表示延时k个时刻，这样，我们可以把输入信息x用一个多项式表示，即

2.卷积码的生成矩阵

10.3.3卷积码的图形表示法

1.树状图

树状图描述的是在任何数据序列输入时，码字所有可能的输出。

卷积码的树状图由节点和树枝组成，从一个初始节点(称为树根)开始，根据输入信息码元是０还是１进行分枝，通常信息码元为０时向上分枝，信息码元为１时向下分枝，并将输出的码字标于树枝上。卷积码的树状图见图。图(2，1，2)卷积码的树状图

2.状态图

状态图主要用来反映卷积码编码器的可能状态，以及由一个状态可能向哪些状态转移。

3.网格图

树状图能清晰地反映编码路径，标出了各个时刻的编码状态，但不能反映状态间的转移；状态图能紧凑地反映状态间的转移情况，但不能显示编码路径及各个时刻的编码状态。网格图有机地结合了两者的优点，如图所示。

图(2，1，2)卷积码的网格图 4.2卷积码的译码方法

卷积码的译码方法主要有代数译码法和概率译码法。代数译码法有与分组码相似的伴随式、错误图样等概念，利用伴随式进行检错、纠错。概率译码法则利用信道统计特性，对接收序列进行最大似然判决，目前，概率译码法普遍通过维特比(Viterbi)译码算法和费诺(Fano)译码算法来实现。1.维特比算法

维特比译码是一种最大似然译码算法。最大似然译码算法的基本思路是，把接收码字与所有可能的码字比较，选择一种码距最小的码字作为译码输出。

当k较大时，由于存储量太大，应用受到限制。由于接收序列通常很长，所以维特比译码是最大似然译码算法的简化。简化的方法是：它把接收码字分段处理，每接收一段码字，计算、比较—次，保留码距最小的路径，直至译完整个序列。

2序列译码

当m很大时，可以采用序列译码法，该译码方法可避免漫长的搜索过程。译码先从树状图的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较，沿着差异最小的分支走向第二个节点；

3门限译码

除上述的维特比译码法、序列译码法外，卷积码的另一种译码方法为门限译码法。门限译码又称大数逻辑译码。门限译码的设备简单，译码速度快，约束长度可较大，适用于有突发错误的信道。

10.4网格编码调制（TCM）

TCM的基本原理是基于Ungcrbeck子集划分理论，将编码器对信息比特的编码转化为对信号点的编码，使得在信道中传输的信号序列遵循一定的规则，即符合网格图中某条特定的路径。这类信号具有如下两个基本持征：(1)在信号空间中，信号点数目比无编码调制情况下对应的信号点数目要多一倍．这些增加的信号点为纠错编码提供了冗余度，但不牺牲带宽；(2)采用卷积码编码规则，在时间上相邻的信号点之间建立依赖关系，因此仅有某些信号点图样或序列才是许用信号序列，这些许用信号序列可用网格结构表示，因此又称为网格编码调制。10.4网格编码调制（TCM）

TCM的基本原理是基于Ungcrbeck子集划分理论，将编码器对信息比特的编码转化为对信号点的编码，使得在信道中传输的信号序列遵循一定的规则，即符合网格图中某条特定的路径。这类信号具有如下两个基本持征：(1)在信号空间中，信号点数目比无编码调制情况下对应的信号点数目要多一倍．这些增加的信号点为纠错编码提供了冗余度，但不牺牲带宽；(2)采用卷积码编码规则，在时间上相邻的信号点之间建立依赖关系，因此仅有某些信号点图样或序列才是许用信号序列，这些许用信号序列可用网格结构表示，因此又称为网格编码调制。10.4网格编码调制（TCM）

8PSK信号空间的集合划分10.4网格编码调制（TCM）

TCM编码器的一般结构10.4网格编码调制（TCM）

网格编码调制的解调与译码采用维持比译码算法，它是软判决最大似然译码，即在所有可能路径中寻找与接收信号序列最接近的路径。不过，这里使用可能发送序列与接收信号之间的欧氏距离作为度量。这部分的处理往往是决定TCM实现复杂度的关键环节。10.5TURBO码

1993年Berrou等人提出的Turbo码实际上是前人工作的巧妙综合和发展，它的核心就是构造长序列的伪随机性的编、译码。最初报告的成果表明其译码性能可以接近香农理论值，Turbo码很快成为国际信息论和编码理论界研究的热点，并试图应用于各种通信系统10.5TURBO码

1Turbo码的编码

ClaudeBerrou教授等人最初提出的Turbo码采用的是并行级联卷积码的结构。下图给出了由两个分量编码器组成的Turbo码的编码框图。10.5TURBO码

1Turbo码的编码

Turbo码编码器主要由分量编码、交织器以及删余矩阵和复接器组成。分量码一般选择为递归系统卷积(RSC)码,当然也可以是分组码、非递归卷积码以及非系统卷积码。分量码的最佳选择是递归系统卷积码。通常两个分量码采用相同的生成矩阵，当然，分量码也可以是不同的。删余矩阵：为提高码率和系统频谱效率，可以将两个校验序列经过删余矩阵删余后（得到）。删余矩阵的元素取自集合{0，1}。矩阵中每一行分别与两个分量编码器相对应，其中“0”表示相应位置上的校验比特被删除，而“1”则表示保留相应位置的校验比特。10.5TURBO码

1Turbo码的编码交织器的作用：是将信息序列中的比特顺序重置。当信息序列经过第一个分量编码器编码后输出的码字重量较低时，交织器可使交织后的信息序列经过第二个分量编码器编码后以很大的概率输出高重码字，从而提高码字的汉明重量；同时好的交织器还可以有效的降低校验序列间的相关性。通过交织，编码序列在长为2N或3N（不经过删余）比特的范围内具有无记忆性，从而由简单短码构造了近似随机长码。交织器实际是一个一一映射函数，作用是将输入信息序列中的比特位置进行重置，以减小分量编码器输出校验序列的相关性和提高码重。因此，交织器设计的好坏在很大程度上影响着Turbo码的性能。

10.5TURBO码

2Turbo码的译码Turbo码的译码通常是运用最大似然译码准则，采用迭代译码的方法实现的。

10.5TURBO码

2Turbo码的译码在TURBO码的译码中采用的软输入、软输出迭代译码算法有多种。常见的标准有MAP算法（MAP-Maximum，即最大后验概率算法）、对数MAP算法（log-MAP算法）、max-log-MAP算法、软输出维特比译码（SOVA—SoftOutputViterbiAlgorithms）等。10.6LDPC码

1Ldpc码的提出低密度奇偶校验码（Low-DensityParity-CheckCodcs，LDPC)码是由Gallager于1962年提出的一种基于稀疏矩阵的线性码。经过Tanner从图论的角度研究LDPC码后，MacKay和Neal重新发现并证明了迭代译码的LDPC码具有渐近香农限的性能。Sac-YoungChung又证明了不规则的LDPC码性能甚至可以距离香农限0.0045dB。这是目前已知的距离Shannon限最近的纠错码。

2LDPC码的特点

逼近香农限，易于理论分析和研究，译码算法为迭代算法且复杂度低，可实行完全并行操作，适合硬件实现，具有高速的译码潜力；由于码长较长时，相距甚远的信息比特可能参与同一校验约束，使得连续的突发错误对译码影响不大，因此LDPC码本身具有很好的抗突发错误的能力。另外，译码方法的选择很灵活，甚至是对同一种译码算法，也可通过对不同信道特征选择适合自己的迭代次数等优点。10.6LDPC码

3LDPC码的定义

LDPC码是一类线性分组码，用稀疏奇偶校验矩阵的零空间定义；所谓“稀疏性”指矩阵中包含0的个数远大于1的个数；“低密度”指矩阵中包含1的密度很低。设码长为n，信息位为k，则校验位为r，校验矩阵是一个r=n-k阶的矩阵。校验矩阵的每一行表示一个校验约束，其中所有非零元素对应的码元变量构成一个校验集，由一个校验方程表示。校验矩阵的每一列表示码元符号参与的校验约束。

10.6LDPC码

3LDPC码的定义

二元LDPC码的校验矩阵矩阵的特点归纳如下：每列包含有j个1，即列重量为j；每行包含有k个1，即行重量为k；任何两列之间同为1的行数（称为重叠数）不超过1，即矩阵和Tanner图中无4线循环；j和k均远小于码长度n和矩阵行数r，当时，10.6LDPC码

3LDPC码的定义

根据上述特点，Gallager给出了一个实例10.6LDPC码

3LDPC码的定义

根据上述特点，Gallager给出了一个实例10.6LDPC码

（15，3，4）LDPC码的Tanner图表示

3LDPC码的定义

一般情况下校验矩阵是随机构造的，因而是非系统形式的。编码时对校验矩阵进行高斯消去可得：

其中,I是单位矩阵，P是n×(n-m)阶矩阵。得生成矩阵由于LDPC码是一种线性分组码，它的编码可采用线性分组码的编码方法来完成。则LDPC码的码字为：10.6LDPC码

4LDPC码的译码

硬判决译码算法：复杂度较低，但是性能较差，在LDPC码的研究前期比较受关注；混合译码算法：复杂度较高且效果并不明显，实用价值不如其余两种译码算法。软判决译码算法：性能更加优异，虽然译码复杂度相比硬判决译码算法更高，但是在目前的硬件水平下已经能够很容易实现，因此LDPC码的软判决译码算法一直是人们研究的重点。目前常用的软判决译码方法主要是置信传播（BeliefPropagation，BP）译码算法。10.6LDPC码

1喷泉码的提出

经典的RS码或LDPC码面临的主要问题是：RS码的编译码复杂度较大。(n,k)RS码的标准编译码方法需要次运算。较大的编译码复杂度限制了RS码的码长，通常n<255。无论RS码还是LDPC码，其应用都基于一定的信道假设，即必须预先假设删除信道的删除概率（即丢包率），据此才能选取(n,k)参数，之后才能设计具体的编译码方法。但是实际应用中，由于信道的时变性，会出现信道优于假设和信道劣于假设的情况。10.7喷泉码

1喷泉码的提出

喷泉码不仅具有很小的编译码复杂度，而且可以由k个原始分组生成任意数量的编码分组，有效适应信道的时变性，而其代价仅仅是具有很小的译码开销。喷泉码(FountainCodes)只是一种比喻的说法，指该种编码可以由k个原始数据分组生成任意数量的编码分组，而接收方只要收到其中任意m个编码分组，即可通过译码以高概率成功恢复全部原始数据分组。

10.7喷泉码10.7喷泉码

2喷泉码的优点

喷泉码是第一个无几率删除码，能即时生成无限纠错包，保护任何大小的源数据，并不受丢包率的影响。喷泉码能在任何网络及操作平台上以非系统化及系统化码的形式，在应用层、链路层、或应用层与链路层上同时运行，提高数据传输的可靠性。喷泉码是线性码。一般纠错码解码复杂度是二次方，而喷泉码是线性，因此它能处理一般纠错码不能处理的丢包率。10.7喷泉码

2喷泉码的优点

喷泉码是通用删除码，因为它不受删除率的影响，在任何删除信道都能达到近乎最优化性能，并且在文件越大的情况下它的效率越高。喷泉码大部分处理只是进行小数量的模二加计算。模二加的所得值与逻辑操作奇偶校验相等，是计算机的基本操作，对处理器要求很低。因此喷泉码的编解码都能实用普通的电脑并高速完成。喷泉码的应用对内存要求很低，比一般需要进行交织的纠错码低约8到10倍。10.7喷泉码

3喷泉码的分类

随机线性编码LT码Raptor码

3喷泉码的分类

随机线性编码数字喷泉码(FountainCodes)是一种与码率无关，支持异步接入，具有线性编译码复杂度的新型随机编码方式，具有很小的编译码复杂度，有接近理想的纠删性能，适合于提供针对脉冲噪声的编码保护。喷泉码输入信息单元的长度可以为任意长(从1bit到通常的kbits)。由k个原始分组生成任意数量的编码分组，且每个编码单元的产生相互独立。只要接收端的信息不足以完全译码，就可以继续接收，直到全部信息被成功译出。有效适应信道的时变性，而其代价仅仅是具有很小的译码开销。10.7喷泉码

3喷泉码的分类

随机线性编码喷泉码的设计需要考虑两方面的问题：应该尽量减小译码复杂度，理想情况下，应该使生成每个编码分组需要的运算量是一个与k无关的常数，而成功译码m个编码分组获得