第四章 差错控制编码

第四章差错控制编码4.1引言4.1常用的检错码4.3常用的简单编码4.4线性分组码4.5循环码4.6卷积码4.7网格编码调制●——主要内容4.1概述4.1.1信道编码4.1.2差错控制方式4.1.3纠错编码的基本原理4.1引言信源编码:是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。4.1.1信道编码信道编码:是为了降低误码率，提高数字通信的可靠性而采取的编码。差错控制编码属信道编码，要求在满足有效性前提下，尽可能提高数字通信的可靠性。目的差错控制的目的是用信道编码的方法检测和纠正误码，降低误比特率。前向纠错法（FEC）自动请求重发法（ARQ）混合纠错(HEC)反馈检验法4.1.2差错控制方式

1.检错重发法（ARQ）(又叫自动请求重传)

由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。优点:是译码设备简单，对突发错误和信道干扰较严重时有效，可达到良好的性能缺点:需要双向信道，实时性差Automaticrepeatrequest

2.前向纠错方式FEC(ForwordErrorCorrection)发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。优点:单向传输，实时性好缺点:译码设备较复杂。

3.混合纠错方式发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力，但能检测出来，则经过反馈信道请求发端重发。HEC(Hybrid

ErrorCorrection)具有自动纠错和检错重发的优点，可达到较低的误码率检错重发系统根据工作方式又可分为三种，即停发等候重发系统、返回重发系统和选择重发系统随机信道:差错的出现是随机的，而且错误之间是统计独立的。按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道具有脉冲干扰的信道是典型的突发信道突发信道:错误是成串成群出现的，即在短时间内出现大量错误。混合信道:随机错误和成串错误都占有相当比例短波信道和对流层散射信道是混合信道4.1.3纠错编码的基本原理

例：2位二进制数字构成的码组，共有4种不同的组合。若将其全部利用来表示天气，则可以表示4种不同的天气。00(晴)，01(多云)，10(阴)，11(雨)，在信息码序列中加监督码就称为差错控制编码，也叫纠错编码。不同的编码方法，有不同的检错和纠错能力，监督码元越多，检（纠）错能力越强。

注意纠错码的分类(1)根据纠错码各码组信息码元和监督码元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息码元有关；卷积码中的码元不仅与本组的信息码元有关，而且还与前面若干组的信息码元有关。

根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；纠错码以纠错为目的，一定能检错。

按监督码与信息码的位置关系分系统码与非系统码

(或说根据编码后信码是否保持原来的形式)

1.分组码(n,k)krnk是每组二进制信息码元的数目，n是编码码组的码元总位数又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。码重(weight)一个码组中“1”的数目码距(distance)两个等长码组之间对应位置上不同的位数，又叫汉明(Hamming)距。最小码距(码的最小距离)d０dmin码组集中任意两个码字之间距离的最小值2.检错和纠错能力

码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内:(1)检测e个随机错误，则要求码的最小距离d0≥e+1

ABe1若一种编码的最小码距为d0,则能检出d0-1个错码。(2)纠正t个随机错误，则要求码的最小距离d0≥2t+1;AB1tt(3)纠正t个同时检测e(>t)个随机错误，则要求码的最小距离d0≥t+e+1。

t1eAB3.编码效率编码效率R来衡量有效性:R=k/n其中,k是信息元的个数，n为码长4.2常用的几种简单分组码4.2.1奇偶监督码

1.中心思想:在原信息码后面附加一个监督码元，使得码组中“1”的个数是奇数或偶数。假设一个码组长度n（an-1an-2an-3------a0），其中前n-1位是信息码，最后一位a0为校验位，那么，对于偶校验码2.检验关系式:监督码元a0的取值（0或1）可由下式决定：

对于奇校验码必须保证

监督码元a0的取值（0或1）可由下式决定：

3.特点:

2.检错能力:只能检测出奇数个错码不能进行纠错。1.d0=22.奇偶监督码的编码效率R为

当n很大时，编码效率高3.编译码器简单4.一般用于计算机数据通信4.2.2二维奇偶监督码(又称行列监督码，方阵校验码)1.基本思想：与一维奇偶监督码相似，不同点在于每一个码元都要受到纵横两个方向的监督。例如：有50个待发送的码元，将它们排成5行10列(5×10)方阵，方阵中每一行是一个码组，每行最后加上一个监督码进行行监督，同样在每一列的最后也加上一个监督码进行列监督然后按行或按列发送：2.检错能力：

接收端按同样行列排成方阵，发现不符合行列监督规则的判决有错，其检错能力(1).能检出所有行，列中的奇数个错误。(2).能发现大部分偶数个错误：(3).错码位置处于矩形四个角时检不出错误。

3.特点(1)适合检测突发错码(2)一般用于短波系统4.2.3恒比码(又称等重码或定1码)

1.基本思想：

每个码组含有相同数目的“1”和“0”，即“0”的个数与“1”的个数的比值恒定，故得此名。这种码在检测时，只要计算接收码组中“1”的数目有无变化，就知道有无错码。

2.检错能力：只有当1→0和0→1成对出现时无法检错，其余情况均能检错。

∴检错能力很强

数字数字保护电码123456789001011110011011011010001111010111100011101001101101中国电传通信保护码采用n=5中取w=3的恒比码。每个汉字用4位阿拉伯数字表示，而每个数字用5位二进制符号构成：

中文电报编码首先将每一个单字编码为四位十进制数字，再将每一位十进制数字用二进制的五单位数字保护码表示。通信

663902071010110101101101001101101110010110111100

国际电报通信中广泛采用的是“7中取3码”，许用码字共有35个，可分别表示26个字母和其它的一些符号。

3、特点非线性分组码，但不是系统码检错功能简单，编译码设备简单常用于键盘发送系统4.2.4正反码1.中心思想

r=k.

编码的监督位数目与信息位数目相同，监督码是信息码的重复还是反码，由信息码中1的个数而定。编码信息码中含有奇数个1重复信息码中含有偶数个1取反码译码：由校验码进行译码信息位⊕监督位=合成码若接收码组的信息位中有奇数个1，则合成的码组为检验码若接收码组的信息位中有偶数个1，则合成的码组的反码为检验码由合成码得校验码收端根据校验码组进行检错检验码组全为0，无错码有k-1个1，1个0则信息码组中有一位错码，其位置对应检验码组中0的位置有k-1个0，1个1则监督码中有一位错码，其位置对应检验码组中1的位置其它组合，错码多于一个例：收到码组为10010101102.检错能力正反码具有纠正一位错码的能力，并能检出全部两位以下的错码和部分两位以上的错码3.特点1.效率：50﹪因为k=r2.常用于电报通信中4.2.5群计数码群计数码是将信息码元分组后，计算每组码元中1的个数，然后将这个数目的二进制表示为监督码元，一起送往发送端。例：一组8位的信息码元为10111001，其中1的个数为5个，于是将101作为监督码元。这样传输的码组为10111001101收端只要检测监督码元所标示的1的数目与信息码元的1的数目是否相同来判断传输过程中有无错误。特点：非线性分组系统码,群计数码的检错能力很强，它可以检测除1变0和0变1成对出现的错误以外的其他形式的错误。4.3线性分组码

线性:监督码元与信息码元满足线性关系分组(n,k)（an-1an-2an-3------a0）一、性质1、任意两许用码组之和（逐位模2和）仍为一许用码组，即线性码具有封闭性。2、最小码距等于非零码组中的最小码重回顾奇偶监督码在接收端解码时，实际上就是在计算若S＝0，认为无错若S＝1，认为有错S只有两种取值，只能代表有、无错两种信息，不能指出错码位置。监督关系式校正子在（n,k）码中，为能纠正一位错误要求在（n,k）码中，k=4。为能纠正一位错码，则r至少应为多少？举例说明如何构造监督关系式：上例中，若取r=3，则n=k+r=7。(7,4)线性分组码（a6a5a4a3a2a1a0)校正子与错码位置的对应关系如表规定(也可以另外规定)。S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错由表可见，当一错码位置在a2,a4，a5或a6时校正子S1为1；否则S1为0即构成如下关系由此解出给定信息位后，可直接按上式算出监督位监督方程信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111112、监督矩阵H和生成矩阵G

改写为(模2)简记为

或称为监督矩阵H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度典型阵r行n列转置得K行r列Q=PT，在Q矩阵的左边在加上一个k×k的单位矩阵，就形成了一个新矩阵G：

典型形式生成矩阵K行n列称为生成矩阵生成矩阵G的每一行都是一个码组G为典型生成矩阵，则得到的码为系统码否则得到的码为非系统码例【1】已知线性（6，3）码的生成矩阵为

求（1）信息码组为101对应的编码码组（2）所有许用码组、各码组的码重、最小码距和该码的差错控制能力。

例2已知（7，4）码的生成矩阵为：列出所有许用码组并求监督矩阵例3课后习题9-61、写出监督方程2、由监督方程求出所有许用码组3、求生成矩阵4、最小码距？只用于检错，能检出几位错码？只用于纠错？同时用于检错和纠错？若发送码组为表示该位接收码元无错；表示该位接收码元有错。3、译码接收码组为二者之差为E称为错误图样

接收端译码时计算错误图样与校正子之间有确定的关系无错时，S等于零有错，S不等于零。校正子(伴随式)纠错-----------只纠一位错误时例4

设验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？且有3个接收码组解：1）若无错，则错误图样为0，S为0

B1无错B2错B3错2）∵

S2=H第1列∴E=[100000]第1位错同理S3=H第3列∴E=[001000]第3位错例5、已知一（7，4），监督码元和信息码元之间的关系为：求（1）信息码字I=[0011]时的编码码组

（2）

如果接收的码字B=[1000101]，确定收到的码组是否有错，并纠正。4、汉明码（1）码长满足（2）最小码距d0=3（3）编码效率§4.4

循环码循环码除具有线性码的一般性质外,还具有循环性

即任一码组循环一位以后，仍为该循环码中的一个许用码组。一、循环码的特点线性分组码循环码举例——(7,3)循环码码组信息位监督位码组信息位监督位编号a6a5a4a3a2a1a0编号a6a5a4a3a2a1a00000000041001011100101115101110020101110611001013011100171110010例如A=0011101A(x)=0x6+0x5+1x4+1x3+1x2+0x1+1x0=x4+x3+x2+12、码多项式——码组的多项式表示二、循环码的运算1、码多项式的按模运算若一个整数m,若可以表示为则：m≡

p(模n)多项式F(x)被n次多项式N(x)除，得到商式q(x)和一个次数小于n的余式R(x)，即码多项式系数仍按模2运算，即只取值0和1则写为F(x)≡

R(x)

(模N(x))例如在循环码中，若T(x)是一个长为n的许用码组，则在按模运算下，亦是一个许用码组。则T’（X）也是该编码码组中的一个许用码组假设用g（x）表示一个前k-1位皆为0（第k位不为0）的码组生成多项式2、循环码的生成多项式（1）g(x)是一个常数项为1的次多项式；（2）g(x)是的一个因式；（3）该循环码中其它码多项式都是g(x)的倍式。

任意一码组多项式可表示为：一个k位的信息码组Ｄ＝［dk-1,dk-2,…….d0]信息码多项式:T(x)=d(x)g(x)d(x)代入T(X)得：不大于n-1次的多项式假如输入信息码元mk-1mk-2…m0则例：求（7，4）循环码的生成多项式g(x),当信息码组D=[1010]时，求输出码组若能找到k个线性无关的码组,就能构成矩阵G。

g(x)、xg(x)，x2g(x)，…，xk-1g(x)都是许用码组，而且这k个码组是线性无关的。因此可以用来构成循环码的生成矩阵G。3．循环码的生成矩阵G例表9—6的循环码,唯一的一个(n-k)次码多项式代表的码组是0010111，相对应的码多项式为因此,循环码的生成矩阵G可以写成这个生成矩阵不是系统码的生成矩阵，可以通过行变换，变换成系统码的生成矩阵。

g(x)＝x4+x2+x+1将此g(x)代入上式，得到三.循环码的编