通信原理-第五版-第9章-差错控制编码要点word版本

通信原理-第五版-第9章-差错控制编码要点1.随机性差错：差错是随机的且相互之间是独立出现。通常由高斯白噪声引起；1～2位错误。2.突发性差错：由脉冲性干扰引起,在短暂的时间内出现连续的差错，而这些短暂时间之后却又存在较长的无误码区间。一、差错类型§9.1纠错编码的基本概念混合性差错：既存在随机差错又有突发性差错。以上两种错误性质不同，可采取不同措施处理！可以用来检测一位错误可纠正一位错误或检测两位错误AB

许用码组禁用码组

0001

1110

采用2位二进制码许用码组禁用码组000001010100111101110

011采用3位二进制码采用1位二进制码01二、差错控制的基本方法

在信息序列之后附加一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联，接收端按照既定的规则检验出关联关系，如这种规则受到破坏，将会发现错误，乃至纠正错误。例：三、检错与纠错能力与最小码距d0的关系结论：最小码距决定检错和纠错能力(c)为了同时检测e个错误，纠正t个错误d0e＋t＋1(b)为了纠正t个错误d02t＋1(a)为了检测e个错误，d0e＋1码距：两个码组对应位上不同的数目。码重：码组中“1”的数目。AB0123d0e(a)AB012345d0tt(b)ABd0ett1(c)四、差错控制编码的效用

假设在随机信道中发“0”和发“1”的概率相同，在码长为n的码组中恰好发生r个错误的概率为：(p为误码率)当码长n＝7，误码率时，则有：结论：采用差错控制编码，即使仅能纠正（或检测）1～2个错误，就能使误码率下降几个数量级。五、纠错码的分类1.分组码与卷积码：分组码：将信息码分组，为每组信息码后面附加若干位监督码元，且监督码元仅监督本码组中的信息位。

K个信息位r个监督位码长n＝k＋r卷积码：卷积码也是先将信息序列分组，后面附加监督位，但是监督位不但与本码组的信息位有关，还与前面码组的信息位有关，或者说监督位不仅监督本码组的信息位还监督其它码组的信息位。2.系统码与非系统码系统码：

就是信息位在前，监督位在后的码字。非系统码:信息位与监督位之间无特定的位置关系。§9.2差错控制方式2.前向纠错（FEC）

可以纠正错误

发

收3.混和纠错（HEC）

可以发现和纠正错误

发

收

应答信号

比较：译码复杂性、实时性和占用传输链路(单向还是双向)1.检错重发（ARQ）

（包括停发等候重发、返回重发和选择重发）

能够发现错误

发收

应答信号ARQ：自动重复请求发送1233123ACKNAKACK等待时间发送端接收端123456234567891011123456234567891011从码组2开始重发NAKACK发现错误停发等候重发返回重发1234562789101121234562789101112重发码组2NAKACK发现错误选择重发比较反返回重发和选择重发：

看起来只重传特定的帧比同时将未损坏的帧一起传显得更有效，但是由于接收方进行的排序和存储所需的复杂度，以及发送方选择重传所需的额外逻辑，选择重发ARQ的开销更大，所以并不常用。（1）帧损坏：接收方发现错误，就返回一个否认帧给发送方，发送方重发最后一帧。发送方接收方数据帧0ACK1数据帧1ACK0数据帧0NAK时间时间等待时间等待时间等待时间停等ARQ，损坏帧数据帧0ACK1。。。正确有错误停等ARQ：（2）帧丢失（a）丢失数据帧：发送设备等待ACK或NAK帧直到定时器超时；（b）确认帧丢失:接收方检查到达的新数据帧编号。如果丢失的是NAK帧，接收方将接收新的数据帧拷贝并返回一个ACK帧；如果丢失的是ACK帧，，则接收方将新的数据帧拷贝视为重复帧，对它的接收进行确认并等待下一帧的到来发送方接收方数据帧0ACK1数据帧0ACK1时间时间超时等待时间停等ARQ，确认帧丢失。。。丢失9.3常用的简单纠错码1.奇偶校验设信息位每组长度为n-1位，增加一位监督位，n位编码构成以下约束关系接收端计算校正子奇偶校验可以用来检测单个或奇数个错误2.纵向奇偶校验（LRC）－用于检测突发错误1110011111011101001110011010100111100111110111010011100110101001纵向排列原是数据1110011111011101001110011010100110101010突发错误接收方检验是否满足LRCLRC

10101010监督码元交织编码：针对突发性错误

信息

码

元

0101101100010101001000110000111100011100001111111100010011111110110000监督码元00111000010监督码元10010113.水平垂直奇偶校验它能发现某一行或某一列上所有奇数个错误以及长度不大于行数（或列数）的突发错误5.群计数码111001100信息位监督位发现所有奇数个错误，以及一些偶数个错误，除“0”变“1”，和“1”变“0”成对出现。4.等重码（恒比码）数字电码数字电码

0011015001111010116101012110017111003101108011104110109100115中取3，或7中取4作业：9-3，9-59.4线性分组码定义：信息位和监督位之间的关系是由线性方程组约束的编码称作线性分组码，即监督码元是由信息码元的线性组合而产生。奇偶校验码就是一种效率很高的线性分组码。这里S称为校正子，若S＝0，表示无错，S＝1表示有错误，由于只用了一位监督位a

0，因此只能表示有错与无错。若监督位增加到2位，就可增加一个监督方程式，接收时就可计算2个校正子S1和S2，共有四种可能，除了00表示无错以外，其余3种就可以表示一位错码的的具体位置了。对于二进制编码，知道了错误的位置，就可以实现纠错了一般说来对于，对r个监督位，可以计算r个校正子，它可以指出种错误图样，即个错误位置，因此对于（n，k）码。要想指出一位错码的所有可能位置，则要求：2－1r2－1r

设分组码中（n，k）中k＝4，为了纠正一位错误，则，取r＝3，则n＝7，用

表示，用表示由3个监督方程式计算得到的校正子，并假设这3个校正子与误码对应的关系如下表所示：对于纠正t个错误一、线性分组码的构成：纠正1个错误校正子表S1S2S3误码位置

S1S2S3

误码位置

001

101

010

110

100

111

011

000

无错因此接收端计算下面3个校验关系，可确定误码的位置发送端构成偶校验关系由此监督位可以由信息位的线性组合得到：许用码组信息位

监督位

信息位监督位

0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111二、线性分组码的生成和监督矩阵1.监督矩阵即其中：2.生成矩阵对于所有的编码与信息位的关系：P为

阶矩阵，为

阶单位阵，具有形式称为典型形式的监督矩阵；线性代数理论告诉我们，典型形式的监督矩阵各行一定是线性无关的，非典型形式的监督矩阵可以通过矩阵的初等变换化为典型形式。其中则全部码字由信息位与生成矩阵G相乘得到Q为K

×

r阶矩阵。I

k为k阶单位阵具有典型化形式

的生成矩阵称为典型生成矩阵

它与典型化形式的关系为：

结论：1).由典型化的生成矩阵产生的是系统码组；k

2).典型化的生成矩阵的各行也必定是线性无关的，每一行都是一个许用码组，k行许用码组进过运算可以生成2个不同的码组，非典型形式的生成矩阵经过运算也一定可化为典型形式。

例：若线性分组码的生成矩阵为：典型阵为：监督矩阵三、线性分组码的特性：1)

任意两个许用码组之和仍为许用码组－封闭性2)码的最小距离等于非零码的最小重量。四、线性分组码的伴随式译码设发送的码组为A，接收的码组为R，设E为传输错误图样，则：R－A＝E计算校正子或者对于前面（7，4）码的例子，一位错误图样为：(1000000),(0100000)，(0010000)，(0001000)，(0000100)，(0000001),(0000001)……….例：若接收的码组为1001101计算伴随式：最后一位有错，译码得：1001100校正子S只与E有关，若接收码字R中第I位有错，那么导出的伴随式

恰好是矩阵H的第i列相同的位置。利用伴随式不仅可以判决接收码字中是否有错，而且可以指出差错的位置。作业：9-79.5循环码一、特点：循环码是一种具有循环移位特性的线性分组码，这类码除了具有线性分组码的一般性质外，还具有循环性质带来的其它性能和特征，并可以用不太长的码长来实现，循环码本身的特性使编译设备比较容易实现。1.码多项式：若是一个码字则C的每次循环移位都是一个码字序号信息码(7.3)循环码移位次数码多项式000000000000010011101001101110101311111101002110110100131011010011401001001115710010011106例：(7，3)循环码按模运算规则：模n运算下，一整数m等于其被n除得到的余数．模２运算中，１＋１＝２＝０２＊３＝６＝０

一般的讲，若一整数m可表示为：则：（模n）对于多项式:2.

按模运算

结论：可以证明在循环码中,若是一个码长为n的许用码组多项式，则在模运算下亦是许用码组，即若有：则也是一个许用码组。前面的（7，3）1110100码多项式为左移一位的多项式1110100左移一位的码组1101001对应的多项式显然多项式除法：

二、循环码的生成多项式

对于线性分组码来说只要找到它的生成矩阵就可确定所有的编码码字，而它的生成矩阵的每一行都是一个许用码组，循环码的某一个码字循环移位可得到它的码字。只要找到这个码字就可以得到生成矩阵。这个码字称为生成多项式（码字）。生成矩阵可写为：对于线性分组码，其生成矩阵由K行线性无关的码字组成2.

(n，k)循环码的生成多项式g

(x)是的因式；定理：1.在一个(n，k)循环码中，存在一个唯一的最低次码多项式，其次数为

r=n-k，且常数项必须为１，即生成多项式：

3.若是一个(n－k)次多项式，且是的因式，则一定能生成一个(n，k)循环码。4.

所有码多项式必定能被整除，即

就是说阶数小于(n-1)能被整除的每个多项式都是循环码的许用码组，或必是的倍式(7.k)循环码(n.k)

d

g(x)h(x)(7.6)2(7.4)3(7.3)4(7.1)6结论：(1)一个(n，k)循环码的每一个码多项式也必然是按模运算后某个余式，即一个(n，k)循环码的所有码字都可以通过k个许用码多项式循环移位得到。(2)

循环码完全由其码组长度n及生成多项式g

(x)决定.

例：一个(7，4)循环码，则由生成多项式构成的生成矩阵为：典型阵为：监督矩阵三、循环码的系统码的编码实现系统码组中的最左边的k位是信息码元，随后是n－k位的监督码元，即码多项式为：因此：

有：m

(x)

x

除法求余得到r

(

x)n

-

k例：已知(7，4)循环码的生成多项式为若信息码为1001，求编码码字因此：解：即编码码组为：1001011

S0

S1＋输入m。

S2＋。。。。。K1K2输出ef输入移

存

器反馈输出

mS0S1S2

e

f

000000110111011110011010111011001100000101000001000000反馈

e=S2－1+m0作业：9-1，9-6，9-7，9-8，9-13，9-14(n,k)循环码编码器Sn-k-1输出。。。。。。K1K2f输入S0S0四、循环码的译码校正子计算电路错误图样识别

n级缓存器输入纠错后输出12…………….(n-k)监督矩阵对于最高位错误，校正子为:

a

b

c

七级缓存器纠错后输出门节拍输入

abc与