差错控制编码

差错控制编码和线性分组码

§11.1

基本概念§11.2分组码

§11.3循环码

一、什么是差错控制编码及为什么引入差错控制编码？§11.1基本概念

在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。为了在已知信噪比情况下达到一定的误比特率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域、频域均衡，使误比特率尽可能降低。但若误比特率仍不能满足要求，则必须采用信道编码（即差错控制编码），将误比特率进一步降低，以满足系统指标要求。

差错控制编码的基本思路：

在发送端将被传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联（约束）。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。研究各种编码和译码方法是差错控制编码所要解决的问题。

二、差错控制方式1.检错重发法（ARQ）在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道要求发送端重新发送，直到接收端检查无误为止。ARQ系统具有各种不同的重发机制：停发等候重发、返回重发和选择重发等。ARQ系统需要反馈信道，效率较低，但是能达到很好的性能。

2、前向纠错（FEC）发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误。不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。

3、混合方式（HEC）结合前向纠错和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。它是一种折中的方案。1、随机差错：差错的出现是随机的，一般而言差错出现的位置是随机分布的。这种情况一般是由信道的加性随机噪声引起的。一般将这种信道称为随机信道。2、突发差错：差错的出现是一连串出现的。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。这样的信道我们称之为突发信道。3、混合差错：既有突发错误又有随机差错的情况。这种信道称之为混合信道。三、信道发生差错的几种模式四、差错控制编码分类按功能分检错码纠错码纠删码（发现不可纠正的错误时，可发出指示或删除）按信息码元和监督码元之间的校验关系分线性码非线性码按信息码元和监督码元之间的约束方式分分组码卷积码分组码：将k个信息比特编成n个比特的码字，共有个码字。所有传输时前后码字之间毫无关系。==平均每个码字所携带的信息比特率。编码速率=卷积码：也是将k个信息比特编成n个比特，但是前后的N个码字之间是相互关联。个码字组成一个分组码。按信息码元在编码后是否保持原来的形式不变系统码非系统码按纠正错误的类型分纠正随机错误的码纠正突发错误的码按构造差错控制编码的数学方法分代数码几何码算术码按每个码元取值不同分二进制码多进制码纠错码建立在香农理论基础上香农信道编码定理存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入到编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降到任一的值，即五、有扰离散信道编码定理称为误差指数。

结论1、如码长及发送信息速率一定，可以通过增大信道容量，使P减小。2、如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率指数下降。E（R）CC1C2R六、检错和纠错的基本原理如用三位二进制编码来代表八个字母

000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位发生错误，都会使传输字母错误如用三位字母传四个字母

000 A 011 B 101 C 110 D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。差错控制编码如用三位字母传二个字母

000 A 111 B 检两个以下错误，纠正一个错误。结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数 －>引入多余度。码重、码距码重(weight)一个码组中“1”的数目码距(distance)两个码组之间对应位置上1、0不同的位数，又叫汉明(Hamming)距。

10110码重：3 011002距离：3检错、纠错能力为检查出

个错误，要求最小码距为为纠正个错误，要求最小码距为为纠正个错误，同时检查出个错误，要求最小码距为

分组码表示：(n,k) n:帧长 k/n:编码效率特点监督码只用来监督本帧中的信息位分类线性码－信息码与监督码之间为线性关系非线性码－不存在线性关系

奇偶监督码偶监督奇监督如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。 最小码距为dmin=2这种码检错能力不高，采用什么方法提高呢？七、几种简单检错码水平奇偶监督码和水平垂直监督码又叫二维奇偶监督码水平奇偶监督码将码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶校验。在不增加冗余度时，不仅能发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误。水平垂直奇偶监督码不仅对行进行奇偶校验，而且也对列进行奇偶校验。恒比码在码长一定时，“1”码和“0”码的比例恒定。已用于电报传输中。恒比码的译码可以采用查表方法，检错时检查1的个数是否为3。

每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示。由于阿拉伯数字只有10个，因此从32中可能的码字中挑出C53=10个1的个数为3个的码字作为阿拉伯数字的编码方式，见下表阿拉伯数字编码阿拉伯数字编码101011610101211001711100310110801110411010910011500111001101

在国际图书的发行中，经常用编码的方式来防止书号在通信过程中发生错误。如《通信原理》的书号是ISBN7-118-01429-X

其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X”表示校验位（它是罗马数字10的表示）。这里所采用的校验方式如下所示：71180429X=1078917172123324271524415879102134176176(模11)=0。编码的应用：ISBN国际统一图书编号§11.1基本概念§11.2分组码

§11.3循环码

差错控制编码和线性分组码（n，k）中许用码字（组）为2k个。定义线性分组码的加法为模2加，乘法为二进制乘法。即1+1=0、1+0=1、0+1=1、0+0=01x1=1,1x0=0,0x0=0,0x1=0且码字与码字的运算是各个相应比特位上符合上述二进制加法运算规则。一、线性分组码的基本概念1、线性分组码的性质（n，k）线性分组码的性质：封闭性。任意两个码组的和还是许用的码组。码的最小距离等于非零码的最小码重。所谓的线性分组码就是信息位和校验位之间的监督关系是线性的。所谓线性就是监督位能表示成信息的线性和形式。

2、码的校验矩阵和生成矩阵码的校验矩阵（监督矩阵）偶校验码的构成：

对于偶校验码的监督关系：如果S=1，则认为传输时出错；S=0，则认为无误传输。上式称为监督关系，S称为校验子。问题：为了能纠一位错，k位信息至少需要多少位的监督信息，如何设计？如果校验子有两位，则可以有四种组合，可以表示4种不同的信息，如果用其中的一种表示无错，则其它3种可以表示错误的种类（或位置），为了能纠一个错，至少要求监督位数应满足：如果取k=4，则可以确定n>=7。因此，可以用3个校验子来确定传输的7个位置是否出错。假设传输时的码字为，如果与错码的位置对应如下：错码位置错码位置001101010110100111011000

无错可得

在发送端编码时，信息位的取值取决于输入的信息比特，因此它们是随机变化的。监督位应根据信息位的取值按监督关系来确定，即监督位应该使上三式的取值为0。因此，给出信息位后，根据上式可以算出监督位，从而得到（7，4）的所有码组。0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111

分组码（1）汉明码：能纠一位错误(7,4)

分组码（2）在接收端，按如下规律运算分组码（3）分组码的监督方程矩阵形式分组码（4）监督矩阵H矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。只要监督矩阵确定，则编码时信息位与监督位的关系就确定了。因此，线性分组码的设计实际上是如何设计监督矩阵的问题。分组码（5）生成矩阵

，通过生成矩阵可以得到生成码组。如果输入码组为0011分组码（6）由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。因此，如果知道生成矩阵同样可以确定编码的码组。这对所有的线性码都是一样的。假设信息位为，如果编码后的码组为如下形式：，其中

是监督位，则称这种码为系统码。

即系统码经过编码后的码组中前k个就是信息位，后n-k是监督位。只有系统码才有关系系统码和非系统码都有性质：

校验子S

假设我们发送的码组为A，接收到的码组为B，则B=A+E如果我们能在接收端确定E，那么我们就能够通过接收到的B来译码得到A，即A=B+E。如何得到E呢？因此，如果我们将接收到的B按照设计的监督关系进行运算，我们可以得到，S称为错误图样。如果设计使S的不同组合与错误E一一对应，则我们可以利用错误图样得到E，从而进行纠错译码。在（7，4）码的设计中，我们就是运用了这样的基本原理。汉明码

汉明码监督位为位，因此它可以组成个可能情况，其中一个为无错。因此可以监督码位共 要纠正一个错误，必须满足 最小码距如果r位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）扩展汉明码如果在汉明码基础上，再加上一位对所有码字进行校验的监督位监督码字由r

位增加到

r+1位信息位不变码长 码结构纠1位错，检测2位错如（8，4），（16，11）

扩展汉明码矩阵

如(7,4)－>(8,4)缩短汉明码(n,k)－>(n-s,k-s)如(15,11)－>(12,8)

监督矩阵Hs是将原H的前3列去掉缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。缩短汉明码能纠t个错误的(n,k)应满足

取等号时为完备码不同结构的线性码其纠错能力不同，能力和dmin有关，dmin越大越好。第十一章差错控制编码

§11.1基本概念§11.2分组码

§11.3循环码

§11.3循环码(Cycliccode)

1957年发现特点线性分组码循环性——任一许用码字经过循环移位后，得到的码组仍为一个许用码组如是循环码的一许用码组

则也是一许用码组

设（7，4）汉明码C的生成矩阵和校验矩阵为：得到16个码组是：（1000101）（0001011）（0010110）（0101100）（1011000）（0110001）（1100010）（0100111）（1001110）（0011101）（0111010）（1110100）（1101001）（1010011）（1111111）（0000000）由以上这些码组可以看到：如果是C的码组，则它的左右移位都是C的码组，具有这种特性的线性分组码称为循环码。

循环码的性质：1、封闭性：任何许用码组的线性和还是许用码组。由此性质可以得到：线性码都包含全零码。最小码重就是最小码距。

2、循环性：任何许用的码组循环移位后的码组还是许用码组。循环码的多项式表示定义：码的码多项式如下：例1：（1011000）的码多项式为码多项式表示码组 码多项式码组码多项式左移一位左移位

为许用码组，则也是许用码组

码组左移3位如左移3位后，得是许用码组循环码生成多项式g(D)循环码完全由其码长n和生成多项式构成。其中g（D）是一个能除尽的n-k阶多项式。阶数低于n并能被g（D）除尽的一组码多项式就构成一个（n，k）循环码。也就是说，阶数小于n-1且能被g（D）除尽的每个多项式都是循环码的许用码组。循环码生成多项式g(D)g(D)是D的(n-k)次即r次多项式信息多项式为M(D),k位，(k-1)次多项式g(D)定理.一个(n,k)的二进制循环码可以看成是唯一由它的生成多项式产生，即如(7,3)循环码，n=7,k=3,r=4如果信息位为010，M(D)=D

生成码为0111010例如，（7，4）循环码的生成多项式则阶数低于n-1能被g（D）除尽的多项式为如下：，则对应的循环码多项式为

因此，对应的循环码组为（1111111）。假设循环码生成多项式的构造1、循环码多项式表示及循环性质循环码中任何码组的循环移位还是许用码组。定理一：码组，经过移位位，得到码组

则可以证明：即例2：（7，4）循环码（1000101）的码多项式为移位1位后变成

将它被除，得到

因此，循环左移一位的余式为其相对应的码组为（0001011），正好是（1000101）循环左移一位的结果。

2、循环码多项式的构造定理二：（n，k）循环码的生成多项式一定是的因式，即

反之，如果是一个n-k次多项式，且除尽则此一定生成一个（n，k）循环码。因式分解可以通过计算机分解的方式分解，也可以通过查表（别人已经作好的因式分解表）例，因此，（7，4）循环码的生成多项式可以选择或而（7，3）循环码的生成多项式可以选择或

（7，6）循环码的生成多项式为D+1，实际上就是简单的偶校验码。（7，1）循环码的生成多项式为实际上是7重重复码。生成矩阵G(D)由于k位信息位共有个码组，如果现有信息码生成k个码字，且这k个码组都线性无关，用这k个码组作为一个矩阵G的k行构成生成矩阵G(D)称为循环码的生成矩阵多项式1、非系统码的生成矩阵输入信息码元为时，相应的循环码组多项式为：

由上式得到的码组不是系统码。例：已知（7，4）循环码的生成多项式为求生成矩阵。所以解：(7,3)循环码生成矩阵2、系统码的生成矩阵

系统码定义：（n，k）系统码的码组中前k个比特是信息比特，后n-k个比特是循环监督位。问题：已知生成多项式g（D），如何构造系统码的生成矩阵？系统码的生成矩阵典型形式非系统码系统码(7,3)循环码生成矩阵监督矩阵在系统码中，码组应该具备如下的形式：

其中，的次数小于等于n-k-1。实际上上式表示了如何生成系统码，即将信息码多项式升n-k次，然后以g（D）为模，求出余式r（D）。非系统码系统码系统码的码多项式为例如，(7,4)码，1011

非系统码系统码(7,3)码例：已知（7，4）系统循环码的生成多项式为求生成矩阵。解：系统码的生成矩阵形式肯定是因此我们选择信息多项式为