第5章 差错控制

数据通信原理计通学院通信工程系2014年9月——for计算机12级第5章差错控制与信道编码目的要求理解差错控制的基本方法和检错、纠错码构成的基本原理。掌握信道编码的基本原理；了解常用检错码的特性；掌握线性分组码的一般特性；掌握汉明码以及循环码的编译码及其实现原理；了解卷积码的基本概念。本章是本课程的重点。授课内容5.1差错控制的基本概念及原理5.2检错和纠错的基本概念5.3基于信道编码的差错控制方式5.4常用的简单信道编码5.5汉明码及线性分组码5.6循环码5.7卷积码返回目录一、差错控制

所谓差错控制是通过某种方法，发现并纠正传输中出现的错误。它是数据通信系统中提高传输可靠性，降低系统传输误码率的有效措施。5.1差错控制的基本概念及原理返回目录二、信道编码的基本概念

1、基本思路

在发送端被传送的信息码序列的基础上，按照一定的规则加入若干“监督码元”后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则在接收端可以发现传输中的错误，乃至纠正错误。

信息码+监督码=码组，称差错控制编码或纠错编码或信道编码

（加的监督码越多，差错控制能力越强）2、编码效率 将信息序列按照k位码元的长度分成若干个信息码组M，再将信息码组输入到信道编码器，信道编码器按照一定的算法，产生一个新的n位码字A输出，n>k； 所谓编码效率是指信道编码后码字中信息码元的数目与码字总码元数目之比，记为k/n。3、许用码字和禁用码字

信息码组M由k个二进制码元（即比特）组成，所以就有2k个M；A长度为n，n位长度的码字共有2n个，信道编码实质是通过一定的规则，从2n个长度为n的码字中选择了其中的2k个，每个被选中的码字称为许用码字；未被选中的2n-2k个n长的码字称为禁用码字，反映冗余大小。4、信道编码的分类按码组的功能分为检错码和纠错码按监督码与信息码元之间的关系分为线性码和非线性码（1）线性码：是指监督码元与信息码元之间的关系是线性关系，即可用一组线性代数方程联系起来（2）非线性码：指的是二者是非线性关系按照对信息码元处理方法的不同分为分组码和卷积码（1）分组码：是将信息划分为k个码元一组。然后由这k个码元按照一定的规则产生r，从而组成长度n的码组＝k个信息码元＋r个监督码元。分组码一般用符号(n,k)表示，；（2）在卷积码中，每组的监督码元不但与本码组的信息码元有关，而且还与前面若干组信息码元有关。即不是分组监督，而是每个监督码元对它的前后码元都实行监督，前后相连，因此有时也称为连环码。按照信息码元在编码后是否保持原形式不变来分为系统码和非系统码（1）系统码：编码后的信息码元保持原样不变（2）非系统码：编码后的信息码元改变了原来的信号形式三、差错分析的基本概念

危害数据传输的噪声有两类：一类是随机噪声：包括热噪声、散弹噪声以及传输媒介引起的噪声等，引起随机差错；另一类是脉冲噪声：是指突然发生的噪声，包括雷电、开关引起的瞬态变化以及机电交换机的拨号脉冲等，引起突发差错。

根据这两类噪声差错可以分为两种类型：

随机差错，又称独立差错，是指那些独立地、稀疏地和互不相关地发生的差错。（存在这种差错的信道称为随机信道或无记忆信道）

产生的原因：随机噪声

突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。（存在这种突发错误的信道称为突发信道或有记忆信道）

产生的原因：脉冲噪声错误图样：假设发送端发送的序列为A，经信道传输后，接收端接收的序列为B，信道的错误图样为E。E=A+B，实际上是A异或B。因此，在错误图样E中，0表示在传输中未发生错误，1表示在传输中发生了错误，表示错误的码元。如果已知错误图样，就可确定差错类型。一般来说，错误比较集中（1的密度大）的叫做突发差错；错误比较分散的叫做随机差错。为了便于划分突发差错与随机差错的界限，可以通过错误密度或者突发长度来划分。突发长度指第一个错误码元与最后一个错误码元之间的码元数目。错误密度是指第一个错误码元至最后一个错误码元之间的错误码元数与他们之间的总码元数之比。例如：A：1111111111B：1001001111E：0110110000则突发长度为5，错误密度为4/5返回5.2检错和纠错的基本概念一、基本概念1、码长：码字的码元数目，例如(n，k)分组码的码长为n2、码重：指码字中“1”的数目，记作W(A)。 例如：W(110110)=43、码距：又称汉明距，两个等长码对应位不同的数目，记作d(A，B)，例如：A=110110，B=101011，则d(A，B)=44、码距与码重的关系：d(A，B)=W(A+B)返回目录5、最小码距 又称最小汉明距，

(n，k)分组码总共有2k个码字，记作Ai（i=0,1,…,2k-1）,则这些码字两两之间都有一个码距，定义该(n，k)分组码的最小码距为：

例如：有一码组集合

10111 11001 00010 11010则该码组的最小码距为2。333422二、检错和纠错的基本概念

检错：验证收到的码字是否是需用码字即可发现错误 纠错：能判断出错误发生的位置，将其纠正三、（n,k）分组码的纠检错能力

一个(n，k)分组码的纠检错能力由其最小码距决定：

1、要在一个码组中检出e个误码，要求

d0e＋1

即任一码组产生小于等于e个误码时，都不会变成另一准用码组。2、要在一个码组中能纠正t个误码，要求

d0

2t＋1

将以t为半径的“球”内所有的禁用码组均判为球心中的准用码组，可纠正t个以内的错误。

3、要在一个码组中能纠正t个误码，同时检出e(et)个误码

d0e＋t＋1

当误码数小于等于t时，可纠正误码；当误码数大于t小于等于e时，不会落入另一码组的纠错范围内。返回5.3基于信道编码的差错控制方式在数据通信系统中，差错控制方式可以分为四种：反馈纠错（ARQ）、前向纠错（FEC）、混合纠错（HEC）和信息反馈（IRQ）四种。返回目录一、检错重发或反馈纠错（ARQ）1、思路 这种差错控制方式在发送端对数据序列进行分组编码，加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。2、重发方式在具体实现检错重发系统时，通常有3种形式：停止等候重发返回重发选择重发（1）停止等候重发

发送端每发送一个码组，就停下来等候，发送端在Tw时间内发送一个码组，然后等候，等候时间为Td，再发送下一个码组，Td>Tw+反馈时间；收端判断下是否有错，会发送一个应答信号给发送端，发送端收到信号（可以是承认信号也可以是否认信号）后，让发送端在下一个发送时间内发送码组，如果发送无错，则发送应答信号为ACK，让发送端接着发送下一个码组；如果发送出错，则发送应答信号为NAK，要求重发这个出错的码组。示例动画演示（2）返回重发

发送端连续发送一个码组，一边发送，一边等候接收端的应答信号。接收端检验，如果发现无错，则发送应答信号ACK，则继续发送码组；如果发现有错，则发送应答信号NAK，如果这个码组出错，那么发送端要求这个错误码组以后已经发送的码组都要重发。比如接收端第2个码组出错，那么接收端返回NAK应答信号时，发送端正在发送第6个码组，等第6个码组发送完，发送端要从这个有错的码组，即第2个码组开始，把已经发送出去的第2、3、4、5、6个码组都要重发。示例动画演示（3）选择重发 发送端连续发送一个码组，一边发送，一边等候接收端的应答信号。接收端检验，如果发现无错，则发送应答信号ACK，则继续发送码组；如果发现有错，则发送应答信号NAK，如果这个码组出错，发送端只需要重发这个出错的码组。

示例动画演示3、特点编码效率比较高，对信道的适应能力强重发导致信道的有效利用率较低，通信的实时性较差译码设备较简单4、应用数据通信系统二、前向纠错（FEC）1、思路前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。2、特点无需重发，实时性好编码效率较低，译码设备比较复杂若错误超出纠错码纠错能力,只好将其抛弃3、应用移动通信系统

三、混合纠错检错（HEC）

1、思路混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。2、特点集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性3、应用移动通信系统，数据传输系统四、信息反馈（IRQ）1、思路接收端把收到的数据序列全部由反向信道送回发端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。2、特点不需要纠错、检错的编译码器，设备简单。

需要和前向信道相同的反向信道，实时性差。

发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。返回5.4常用的简单信道编码5.4.1奇偶监督码5.4.2行列监督码5.4.3恒比码5.4.4重复码5.4.5正反码返回目录码重为奇数或偶数的(n,n-1)系统分组码

ITU-T建议——同步数据传输使用偶监督——异步数据传输使用奇监督监督关系：假设将（n，n-1）的奇偶监督码的码字记作：an-1,an-2,…,a1,a0，其中a0为监督码元，其余为信息码元，则各码元满足：5.4.1奇偶监督码返回对水平方向(共L行)和垂直方向(共M列),同时进行奇偶监督的码，记作（LM+L+M+1,LM）。(66，50)行列监督码的一个码字(偶监督)该码具有很强的纠检错能力，常用于短波散射信道等信道干扰比较严重的通信中。5.4.2行列监督码返回该码的特点是码字中1，0数目恒定，亦即1，0数目之比恒定。电传通信中普遍采用3：2码，又称5中取3码，如下所示

国际上通用的ARQ电报通信系统中，采用7中取3码。

5.4.3恒比码恒比码的优点：（1）简单（2）能检测出单个和奇数个错误，还能部分检测出偶数个错误（3）适于传输电传机或其他键盘设备所产生的数字、字母和符号；但不适用于信源来的二进制随机数字序列返回(3，1)重复码两个码字为000和111，其最小码距为3；(n，1)重复码也只有全0码和全1码两个码字，其最小码距为n，却有2n-2个禁用码组，随着码长的增大，其冗余也变得很大；该码随码长增加，具有很强的纠检错能力，但其编码效率的急剧下降；重复码并不是一种优秀的编码方案，仅用于速率很低的数据通信系统中。重复码只有一位信息码元，监督码元是信息码元的重复，所以仅有两个码字；5.4.4重复码返回该码型多用于10单位码的前向纠错设备中，可以纠正一位错误，发现全部两个以下的错误，以及大部分两个以上的错误，其本质就是五单位码的重复；编码规则：信息码组中1的数目为奇数时，监督码是信息码的重复即正码；信息码组中1的数目为偶数时，监督码是信息码的反码。例如：M=11001，则对应得码字为1100111001M=11101，则对应得码字为11101000105.4.5正反码

译码规则： 首先将收到的码字重的信息位和监督位按对应位作模2运算，得到一个5位码组，若该码字中有奇数个1，则将其作为校验码组，若有偶数个1，则取其反码作为校验码组。然后，按照下表进行纠检错译码。 例如：0110101101，则合出码组为00000，信息元中有3个1，奇数，所以检验码组即合成码组00000，对应表，则传输正确。 如0101010111，则合成码组为11101，因为信息元有2个1，偶数，所以校验码为合成码组的反码，00010，则对照表，监督元有1位出错，在校验码组中1对应的位置，即监督元10111中斜体1出错。 如0111010110，则合成码组为11000，信息元中有3个1，则校验码组等于合成码组，11000，则错误情况判断：传输出错，且错误位数大于1。

正反码错误判决表校验码组的形式错误情况判断1全“0”传输正确24个“1”，1个“0”信息元有1位出错，在校验码组中“0”对应的位置34个“0”，1个“1”监督元有1位出错，在校验码组中“1”对应的位置4其它形式传输出错，且错误位数大于1返回5.5汉明码及线性分组码5.5.1线性分组码5.5.2汉明码返回目录5.5.1线性分组码一、线性分组码的定义线性码是指信息位和监督位满足一组线性方程的码；分组码是监督码仅对本码组起监督作用，既是线性码又是分组码称为线性分组码。（n,k）线性分组码，其码字通常记作：

A=[an-1an-2…a0]1×n二、线性分组码的性质（1）封闭性：指码中任意两许用码组之和仍为一许用码组。（2）线性分组码中必有一个全0码组（3）码的最小距离等于非零码的最小重量例：已知一个线性分组码的码组集合为：

000000，001110，010101，011011，100011，101101，110110，111000求该码组集合的汉明距离。解：根据线性分组码的性质可以求出此码组集合的汉明距离为3。三、线性分组码编码1、生成矩阵 对于一个（n,k）线性分组码，其生成矩阵G是k行n列的矩阵，只要有k个线性无关的n元行矢量，都可以构成生成矩阵G，生成矩阵不同，则得到的分组码也不同。2、编码原理

已知(n,k)线性分组码A=[an-1an-2…a0]1×n，其信息码组M=[mk-1mk-2…m1m0]1×k

，则编码过程为：例：假设一个(6，3)分组码生成矩阵为：

编码过程为：

信息码组M[m2

m1

m0]码字A[a5

a4

a3

a2

a1

a0]信息码组M[m2

m1

m0]码字A[a5

a4

a3

a2

a1

a0]000001010011000000001101010011011110100101110111110101111000100110101011根据编码原理，输入信息码组M，得到相应的码字A。该(6，3)码是非系统码，信息元m2、m0、m1分别出现在码字A的第1、3、5位，而2、4、6位是编码器产生的监督码元其码表为：要想得到系统码，即码组A中，信息位不变，监督位附加于其后，则需要将生成矩阵G进行典型化。生成矩阵典型化编码过程(6，3)系统分组码表

监督元与信息元之间的一般关系

信息码组M[m2

m1

m0]码字A[a5

a4

a3

a2

a1

a0]信息码组M[m2

m1

m0]码字A[a5

a4

a3

a2

a1

a0]000001010011000000001101010011011110100101110111100110101011110101111000注意到系统码中前k位即信息元，将其写成线性方程组的形式监督关系

监督矩阵

监督关系一般表达或生成矩阵典型阵一般形式(n，k)分组码码字可表示为：(n，k)码的一般编码过程A=[an-1

an-2…an-k

ar-1

…a1

a0]=[mk-1

mk-2…m0

ar-1

…a1

a0]对上式两边同时进行矩阵转置得：

即此时的系数矩阵，即监督矩阵为

生成矩阵和监督距阵的关系(n，k)码的一般编码过程或即

根据需要选定一监督关系确定H阵；求由H距阵和Ｇ阵的关系确定G阵；由A=M·G生成所有码字。生成矩阵和监督矩阵是正交3、伴随式与检错原理

所谓错误图样E，是由发送码字A和接收码字B进行异或运算得到，若E＝0，说明传输无错，即码字A与B相同，但是错误图样只能够反映的是信道噪声的情况，接收端是不能依据其来检错。实际上，判断传输是否出错，可以将接收到的码字B跟分组码的码字进行比较，如果B是分组码(n,k)的码字，说明传输无错。因此，这里定义了个伴随式S伴随式S和错误图样E的关系(6，3)分组码的监督矩阵为：

伴随式

(6，3)分组码伴随式计算电路

4、举例（1）已知某线形码监督矩阵为

试列出所有的许用码组（2）设（7，4）线形码的生成矩阵：

当信息位为0001时，试求其后的监督位。（3）求上题的监督矩阵。

返回5.5.2汉明码一、概念

汉明距是最早发现的具有纠错能力的码，是一种编码效率较高的分组码，也是一种线性码。对于任何的整数，必存在一个(n，k)汉明码，码长n和监督元数目r=n-k满足n=2r-1二、特点

1、可以纠正一位传输错误，且d0=3 2、码长和监督元的关系：n=2r-1

记为：（n，k）＝（2r-1，2r-1-r） 汉明码的编码效率：将监督矩阵记成列矢量的形式，H=[h0h1…hn-2hn-1]，则单个错误（所有的ei只有一位为1）时的伴随式恰好与H的一个列矢量对应，只要H的各个列矢量不为0矢量，且各不相同，则可以纠正单个错误。三、伴随式和错误图样的关系四、实例分析——(7，4)汉明码

首先其监督矩阵，此时监督矩阵为H3×7，3位二进制码元的组合有8种：

000、001、010、011、100、101、110、111其中不全为零的7个正好可用作监督矩阵的列,可得到监督矩阵：

任意调换监督矩阵各列位置并不影响码的纠错能力，将其转化成典型阵的形式，并由其可以得到生成矩阵G由A=MG得到其所有的码字，如下表所示：

假设发送端的码字是A15=1111111，传输过程中第4位a3出现了错误，即接收的码字是B=1110111此时对应的伴随式为：

信息码组Mm3

m2

m1

m0码字Aa6

a5

a4

a3

a2

a1

a0信息码组Mm3

m2

m1

m0码字Aa6

a5

a4

a3

a2

a1

a000000001001000110100010101100111000000000010110010101001111001001100101101011001101110001000100110101011110011011110111110001111001100101001010110011100001110101011101001111111下表给出了该（7，4）汉明码单个错误的错误图样与其对应的伴随式，可以发现伴随式正是监督矩阵的每一列，且该列的位置恰好是码元出错的位置。

由于S不是全零，可判断传输出错，而ST=[011]T，是监督矩阵H的第4列,这正是错误码元发生的位置,因此可以得到错误图样为E=0001000，进而按B+E即可纠错。错误位置错误图样E[e6

e5

e4

e3

e2

e1

e0]伴随式S[s2

s1

s0]无错0000000000b00000001001b10000010010b20000100100b30001000011b40010000101b50100000110b61000000111返回5.6循环码一、概念

循环码是一类重要的线性分组码，若(an-1an-2…a0)是循环码的一个码组，则循环移位后的码组：

(an-2an-3…a0an-1) (an-3an-4…an-1an-2) …… (a0an-1…a2a1)仍然是该编码中的码组。

返回目录一个(7，3)系统循环码码表如下所示：信息码组Mm2m1m0码字Aa6a5a4a3a2a1a0信息码组Mm2m1m0码字Aa6a5a4a3a2a1a000000101001100000000010111010111001110011001011101111001011101110011001011110010表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。

二、循环码特点（1）封闭性：指码中任意两许用码组之和仍为一许用码组（2）线性分组码中必有一个全0码组（3）码的最小距离等于非零码的最小重量（4）循环性：循环码中任一许用码字经循环移位后，得到的新码字仍为它的一个许用码字。

三、循环码的数学表示法1、码多项式

(n，k)循环码中，为了便于描述与计算，经常使用n-1次码多项式来表示码字，码字A=[an-1an-2…a1

a0]，它对应的码多项式为：

上式中x的值没有任何意义，仅用它的幂代表码元的位置例如A4=0111001，对应的码多项式为：A4向左循环移1位得A7=1110010，这相当于将A4(x)乘以x，即

A7向左循环移1位得A6=1100101，但若将A7(x)乘以x得到多项式为对于(7，3)循环码的码多项式，其最高次数不能超过6，解决该问题的办法是对上式作模x7+1运算得余作为码多项式2、整数的按模运算在整数运算中，有模n运算。例如，在模2运算中，有

1+1=20(模2),1+2=31(模2),23=60(模2)。一般说来，若一个整数m可以表示为式中，Q为整数，则在模n运算下，有

mp(模n)

所以，在模n运算下，一个整数m等于它被n除得的余数。3、码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则在按模N(x)运算下，有这时，码多项式系数仍按模2运算。例1：x3被(x3+1)除，得到余项1，即例2：

因为 x x3+1x4+x2+1 x4+x x2+x+1

4、循环码的数学表示法 在循环码中，设A(x)是一个长度为n的码组，即 若则A(x)也是该编码中的一个码组。例：一循环码为1100101，即

若给定i=3，则有

上式对应的码组为0101110，它正是A(x)向左移3位的结果。 结论：一个长为n的循环码必定为按模(xn+1)运算的一个余式。

其计算过程如下：例如：四、生成多项式和生成矩阵1、生成多项式

如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如(7,3)循环码中，其它码多项式都是g(x)的倍式，即

在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。 因此，g(x)必须是一个常数项不为“0”的(n－k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(n－k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n－k)，即连续“0”的个数多于(k－1)。显然，这是与前面的结论矛盾的。 我们称这唯一的(n－k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。

因此，一个多项式为(n,k)循环码的生成多项式g(x)必须符合以下三个条件： （1）g(x)是xn-1的一个因式； （2）g(x)是一个n-k次多项式； （3）g(x)多项式中必有一个常数项1。

g(x)、xg(x)、x2g(x)、…、xk-1g(x)是(n，k)循环码的k个线性无关的码字，所以可得其生成距阵G，用码多项式表示G的各行：

2、生成矩阵若信息码组M=[mk-1mk-2…m0]，则：例如：

上表中的编码为(7,3)循环码，n=7,k=3,n–k=4，其中唯一的一个(n–k)=4次码多项式代表的码组是第二码组0010111，与它对应的码多项式即生成多项式为：

g(x)=x4+x2+x+1。

码组编号信息位监督位码组编号信息位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a01000000051001011200101116101110030101110711001014011100181110010将此g(x)代入上矩阵，得到上式不符合G=[IkQ]形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。将该矩阵典型化之后，再按照A=MG编码才能得到(7，3)系统循环码；实际应用中，系统循环码的编译码通常是由g(x)经过简单的代数运算来实现。

3、举例说明 已知循环码的生成多项为，当信息位为1000时，写出它的监督位和整个码组。解：由生成多项式可知n-k=3，而k=4，所以n＝7

第1行+第3行+第4行第1行

第2行+第4行第2行

非典型典型当信息位为1000时，整个码组为监督位为101系统(n，k)循环码码字：

编码原理用码多项式来表示为：五、循环码的编码A=[an-1

an-2…an-k

ar-1

…a1

a0]=[mk-1

mk-2