现代通信理论第八讲纠错编码

第八讲

差错控制编码现代通信理论一、差错类型随机性差错：由高斯噪声引起，差错是随机的且相互之间是独立出现的。突发性差错：由脉冲性干扰引起，在短暂的时间内出现大量的差错，而这些短暂时间之后却又存在较长的无误码区间。混合性差错：即存在随机差错又有突发性差错二、差错控制的基本方法

在信息序列之后附加一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联，接收端按照既定的规则检验出关联关系，如这种规则受到破坏，将会发现错误，乃至纠正错误。第一部分纠错编码的概念提高信息传输的的可靠性和有效性，始终是通信工作所追求的目标，纠错编码是提高信息传输可靠性的一种重要手段差错控制编码属于信道编码信道容量：信息通过信道传输，单位时间内信道上所能传输的最大信息量（即信息速率速率）称为信道容量。对于加性高斯白噪声信道有：通过对信息进行适当的编码，一个含有噪声的信道所引起的差错可以减小到任一期望的水平，而又不会牺牲信息的发射速率，这就是香农信道编码理论。对于有噪声的信道，存在可以实现可靠通信的信道编码。它能在发送速率R<C时达到所期望的任意小的水平,若R>C,则无差错传输是不可能的。检错与纠错能力

与最小码距d0有密切关系：

许用码组禁用码组A00001B

11110

许用码组禁用码组

000001010100111101110011可以用来检测出一位错误可纠正一位或检测两位错误AB0123d

0AB01234

5d

02.

为了纠正t个错误：d02t＋11.

为了检测e个错误：d0e＋13.为了同时检测e个错误，纠正t个错误：d0e＋t＋1ABd0ett三差错控制方式1.检错重发（ARQ）(包括停发等候重发、返回重发和选择重发)

能够发现错误

发收

应答信号

2.前向纠错（FEC）

可以纠正错误

发收

3.混合纠错（HEC）

可以发现和纠正错误

发收

应答信号

比较：译码复杂性、实时性和占用传输链路（单向还是双向）1233123ACKNAKACK等待时间发送端接收端123456234567891011123456234567891011从码组2开始重发NAKACK发现错误停发等候重发返回重发1234562789101121234562789101112重发码组2NAKACK发现错误选择重发

四、

纠错码分类1.分组码与卷积码：分组码：将信息码分组，为每组信息码后面附加若干位监督码元，且监督码元仅监督本码组中的信息位。

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

就是信息位在前，监督位在后的码字。非系统码:

信息位与监督位之间无特定的位置关系。五、常用的简单纠错编码1.

奇偶校验设信息位每组长度为n-1位，增加一位监督位，n位编码构成以下约束关系：接收端计算：奇偶校验可以用来检测单个或奇数个错误2.

纵向奇偶校验（LRC）－用于检测突发错误1110011111011101001110011010100111100111110111010011100110101001纵向排列原始数据1110011111011101001110011010100110101010突发错误接收方检验是否满足LRC。LRC

10101010监督码元

信息码元

0101101100010101001000110000111100011100001111111100010011111110110000监督码元

00111000010监督码元

10010113.

水平垂直奇偶校验它能发现某一行或某一列上所有奇数个错误以及长度不大于列数（或行数）的突发错误六、差错控制编码的效用

假设在随机信道中发“0”和发“1”的概率相同，可以证明，在码长为n的码组中恰好发生r个错误的概率为：当码长n＝7，误码率时

则有：可见采用差错控制编码，即使仅能纠正（或检测）1～2个错误，就能使误码率下降几个数量级。第二部分线性分组码分组码中，信息位和监督位之间由线性方程组联系的编码称作线性分组码，或者说监督码元是由信息码元的线性组合而产生。若监督位增加到2位，就可增加一个监督方程式，接收时就可计算2个校正子和，共有四种可能，除了00表示无错以外，其余3种就可以表示一位错码的的具体位置了。这里S称为校正子，若S＝0，表示无错，S＝1表示有错误，由于只用了一位监督位，因此只能表示有错与无错。奇偶校验码就是一种效率很高的线性分组码一般说来对于，对于r个监督位，可以计算r个校正子，它可以指出种错误图样，即个错误位置，因此对于（n，k）码。要想指出一位错码的所有可能位置，则要求：一、线性分组码的构成：设分组码中（n，k）中k＝4，为了纠正一位错误，则，取r＝3，则n＝7，用表示，用表示由3个监督方程式计算得到的校正子，并假设这3个校正子与误码对应的关系如下表所示：若纠正t个错误校正子表

S1S2S3

误码位置

S1S2S3

误码位置

001

101

010

110

100

111

011

000

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

监督位

信息位监督位

0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111二、线性分组码的生成和监督矩阵1.监督矩阵即：其中：

其中P为

阶矩阵，

为

阶单位阵，

具有形式称为典型形式的监督矩阵；线性代数理论告诉我们，典型形式的监督矩阵各行一定是线性无关的，非典型形式的监督矩阵可以通过矩阵的初等变换转化为典型形式的监督矩阵。2.生成矩阵对于所有的编码与信息位的关系：则其中Q为K

×

r阶矩阵，I

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

的生成矩阵称为典型生成矩阵它与典型化形式的关系为：

结论：由典型化的生成矩阵产生的是系统码组；典型化的生成矩阵的各行也必定是线性无关的，每一行都是一个许用码组，k行许用码组经过运算可以生成2个不同的码组；非典型形式的生成矩阵经过运算也一定可化为典型形式。k线性分组码的特性：1)

任意两个许用码组之和仍为许用码组－封闭性2)码的最小距离等于非零码的最小重量。三、线性分组码的伴随式译码发送码组为A，接收码组为R设E为传输错误图样，则：R－A＝E计算校正子或者校正子S只与E有关，若接收码字R中第i位有错，那么导出的伴随式恰好是矩阵H的第i列相同的位置。利用伴随式不仅可以判决接收码字中是否有错，而且可以指出差错的位置。对于前面的例子，一位错误图样为（1000000)，（0100000)，(0010000),(0001000)，(0000100)，(0000001)，(0000001)……….第三部分循环码一、特点：循环码是一种具有循环移位特性的线性分组码，这类码除了具有线性分组码的一般性质外，还具有循环性质带来的其它性能和特征，并可以用不太长的码长来实现，循环码本身的特性使编译设备比较容易实现。若

是一个码字，则C的每次循环移位都是一个码字。1.码多项式：例：(7，3)循环码序号信息码000000000000010011101001101110101311111101002110110100131011010011401001001115710010011106码多项式移位次数(7.3)循环码

按模运算规则：模n运算下，一整数m等于其被n除得到的余数．模２运算中，１＋１＝２＝０２＊３＝６＝０

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

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

二、循环码的生成多项式对于线性分组码来说只要找到它的生成矩阵就可确定所有的编码码字，而它的生成矩阵的每一行都是一个许用码组，循环码的某一个码字循环移位可得到它的码字。只要找到这个码字就可以得到生成矩阵。这个码字称为生成多项式（码字）结论：1)一个(n，k)循环码的每一个码多项式也必然是按模运算后某个余式，即一个(n，k)循环码的所有码字都可以通过k个许用码多项式循环移位得到。2)循环码完全由其码组长度n及生成多项式

g

(x)决定.2.(n－k)循环码的生成多项式g

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

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

3.若是一个(n－k)次多项式，且是的因式，则

一定能生成一个(n，k)循环码。4.

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

即

就是说阶数小于（n-1)能被整除的每个多项式都是循环码的许用码组，或必是的倍式因：则：上式表明多项式应该是的一个（n－k)次因式

生成多项式（7.k）循环码(n.k)dg(x)h(x)(7.6)

2(7.4)

3(7.3)

4(7.1)

6

生成矩阵可写为：例：对于一个（７，４）循环码，则由生成多项式：构成的生成矩阵为：典型阵为：监督矩阵三、循环码的系统码的编码实现系统码组中的最左边的k位是信息码元，随后是n－k位的监督码元，即码多项式为:因此：

有

m

(x)

x

除法求余得到r

(

x)n

－

k例：已知（７，４）循环码的生成多项式为若信息码为１００１，求编码码字因此即编码码组为：１００１０１１解：

S0

S1＋输入m。

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

存

器反馈输出

mS0S1S2

ef

000000110111011110011010111011001100000101000001000000反馈

e=S2-1+m0(n,k)循环码编码器Sn-k-1s1s0输出。。。。。。K1K2f输入四：循环码的译码校正子计算电路错误图样识别

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

a

b

c

七

级缓存器纠错后输出门(7.4)循环码完整译码器输出门5四级缓存器