通信原理第7章-信道编码和差错控制课件

第7章信道编码和差错控制7.1

概述7.2纠错编码的基本原理7.3

纠错编码系统的性能7.4奇偶监督码7.5

线性分组码7.6

循环码第7章信道编码和差错控制7.1概述●信源编码与信道编码●信源编码(有效性编码)●去除冗余●提高数字信号的有效性●模拟信号数字化

●信道编码(可靠性编码)●添加冗余●降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性●差错控制：包括信道编码在内的一切纠正错误手段●差错控制技术的种类

●检错重发

●能发现错码，但是不能确定错码的位置●通信系统需要有双向信道●前向纠错(FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码●反馈校验●将收到的码元转发回发送端，将它和原发送码元比较●缺点：需要双向信道，传输效率也较低●检错删除●在接收端发现错码后，立即将其删除●适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处7.1概述发送端接收端信源信道编码调制信道压缩编码解调信宿保密解码信道解码压缩解码保密编码噪声信源编码信源解码●信源编码与信道编码7.1概述发送端接收端信源信道编码调●自动要求重发(ARQ)系统●停止等待ARQ系统●拉后ARQ系统

7.1概述

接收数据ACKACKNAKACKACKNAKACK1233455t发送数据12334556t有错码组有错码组214365798接收数据有错码组有错码组91011101112576ACK1NAK5NAK9ACK55769521436798发送数据1011101112重发码组重发码组●自动要求重发(ARQ)系统7.1概述接收数据ACKAC

●自动要求重发(ARQ)系统●选择重发ARQ系统7.1概述选择重发ARQ系统9接收数据有错码组有错码组21436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9●ARQ和前向纠错比较

●优点●监督码元较少，即码率较高●检错的计算复杂度较低●能适应不同特性的信道●缺点●需要双向信道

●不适用于一点到多点的通信系统或广播系统●传输效率降低，可能因反复重发而造成事实上的通信中断●自动要求重发(ARQ)系统7.1概述选择重发ARQ系统●产生错码的原因●乘性干扰引起的码间串扰

●加性干扰引起的信噪比降低

●信道分类：按照加性干扰造成错码的统计特性不同划分●随机信道：错码随机出现，例如由白噪声引起的错码

●突发信道：错码相对集中出现，例如由脉冲干扰引起的错码●混合信道●编码序列的参数●n－编码序列中总码元数量

k－编码序列中信息码元数量

r－编码序列中差错控制码元数量 （差错控制码元，以后称为监督码元或监督位）

k/n－码率

(n-k)/k=r/k－冗余度

7.1概述●产生错码的原因7.1概述7.2纠错编码的基本原理●差错控制编码

●理论依据：香农信道编码定理对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值

●基本思想通过对信息码元序列作某种变换,使原来彼此相互独立,没有关联的信息码元序列,经过这种变换后,产生某种规律性或相关性,使在接收端可根据这种规律性来检查,以至纠正传输序列中的差错

●实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系

7.2纠错编码的基本原理●差错控制编码7.2纠错编码的基本原理●差错控制编码●简单例子

●假如要传送A、B两个消息，消息A----“0”；消息B----“1”若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力

●消息A----“00”；消息B----“11”若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力●消息A----“000”；消息B----“111”传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。●可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码元外添加了冗余码元（监督码元）。一般说来，添加的冗余越多，

码的检错、纠错能力越强，但信道的传输效率下降也越多。7.2纠错编码的基本原理●差错控制编码7.2纠错编码的基本原理●差错控制能力与编码效率

●设：有一种由3个二进制码元构成的编码，它共有23=8种不同的可能码组：

000–晴001–云010–阴011–雨

100–雪101–霜110–雾111–雹这时，若一个码组中发生错码，则将收到错误信息●若在此8种码组中仅允许使用4种来传送天气，例如：令 000–晴011–云101–阴110–雨为许用码组，其他4种不允许使用，称为禁用码组

这时，接收端有可能发现（检测到）码组中的一个错码。这种编码只能检测错码，不能纠正错码

●若规定只许用两个码组：例如

000–晴111–雨就能检测两个以下错码，或纠正一个错码7.2纠错编码的基本原理●差错控制能力与编码效率●分组码概念

●分组码＝信息位＋监督位分组码符号：(n,k)

其中，n－码组总长度

k－信息码元数目

r=n–k－监督码元数目 右表中的码组为(3,2)码

●分组码的一般结构：信息位监督位晴000云011阴101雨110k个信息位r个监督位an-1an-2...arar-1an-2...a0t码长n=k+r7.2纠错编码的基本原理●分组码概念信息位监督位晴000云011阴101雨110k个●码重码字中非零码元的数目●码距两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，称为汉明（Hamming）距离,简称码距●最小码距在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为d0●码距的几何意义：以n=3的编码为例一般而言，码距是n维空间中单位正多面体顶点之间的汉明距离

7.2纠错编码的基本原理(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1●码重7.2纠错编码的基本原理(0,0,0)(0,0,1)●最小码距与检、纠错能力关系●一个码能检测e个错码，则要求其最小码距

d0≥e+1

反之，若码的最小距离为d0，则最多能检测d0-1个错码

●一个码能纠正t个错码，则要求其最小码距

d0≥2t+1

反之，若码的最小距离为d0，则最多能纠正(d0-1)/2个错码

7.2纠错编码的基本原理0123BA汉明距离ed0码距等于3的两个码组BtA汉明距离012345td0码距等于5的两个码组●最小码距与检、纠错能力关系7.2纠错编码的基本原理012●最小码距与检、纠错能力关系

●一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距

d0≥e+t+1(e>t)7.2纠错编码的基本原理●最小码距与检、纠错能力关系7.2纠错编码的基本原理●误码率性能和带宽的关系采用编码降低误码率所付出的代价是带宽的增大10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能●误码率性能和带宽的关系10-610-510-410-310●功率和带宽的关系

采用编码以节省功率，并保持误码率不变，付出的代价也是带宽增大。

10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能●功率和带宽的关系10-610-510-410-310-21

●传输速率和带宽的关系 对于给定的传输系统，其传输速率和Eb/n0的关系：

式中，RB

－码元速率。 提高传输速率，采用编 码以保持误码率不变；付出 的代价仍是带宽增大10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能 ●传输速率和带宽的关系10-610-510-410-31●编码增益 定义：在保持误码率恒定条件下，采用纠错编码所节省的信 噪比Eb/n0

称为编码增益：

式中，

(Eb/n0)u

－未编码时的信噪比(dB) (Eb/n0)c

－编码后所需的信噪比(dB)7.3纠错编码系统的性能10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK●编码增益7.3纠错编码系统的性能10-610-510-4●一维奇偶监督码

●在信息码元后附加一位监督位，使得码组中“1”的个数为偶数或奇数,按照奇偶数分为奇数监督码和偶数监督码两类●(n,n-1)分组码，码率为(n-1)/n（或k/(k+1))●奇数监督码中，此监督位使码组中“1”的个数为奇数：式中，a0为监督位，其他位为信息位●偶数监督码中，此监督位使码组中“1”的个数为偶数： 式中，a0为监督位，其他位为信息位●检错能力－能够检测奇数个错码●应用：以随机错误为主的计算机通信系统，难于对付突发错误,计算机内部的数据传送，就是采用这种码7.4奇偶监督码信息位监督位晴000云011阴101雨110●一维奇偶监督码7.4奇偶监督码信息位监督位晴000云01●二维奇偶监督码

●有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点时，则检测不出●适合检测突发错码●能够纠正部分错码

7.4奇偶监督码●二维奇偶监督码7.4奇偶监督码●基本概念●代数码－利用代数关系式产生监督位的编码●线性分组码－代数码的一种，其 督位和信息位的关系由线性代数方程决定●汉明码－一种能够纠正一个错码的线性分组码●汉明码●发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”

码元个数为偶数

●接收端译码：

●计数接收码组中“1”码元个数是否为偶数，即计算：

S=an-1+an-2+…+a0………

………

…………

………

…………

……

（1）●S=0认为没错，S=1认为有错●（1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式7.5线性分组码●基本概念7.5线性分组码●汉明码●监督位增加到2位：有两个监督方程，两个伴随式；两个伴随式组合有四种（00表示无错，01、10、11表示一位错码的三种可能位置）●监督位增加到r位：可指示一位错码的（2r-1）个可能位置●一般说来，对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个

监督关系式来指示一位错码的n种可能位置，则要求：

2r-1≥n

即

2r≥k+r+1……

……

……

……

…

……

……

……

……

（2）

●举例：构造一（n，k)分组码，k=4并能纠正一位错码

●欲纠正一位错码，由（2）式知r≥3，取r=3，则n=k+r=7

●设7位码元为：a6a5

……a0；三个伴随式：S1、S2、S3；则可规定S1S2S3的

八种组合与一位错码的对应关系如下（也可规定为另一种对应关

系）：7.5线性分组码●汉明码7.5线性分组码7.5线性分组码●汉明码●举例：构造一（n，k)分组码，k=4并能纠正一位错码从上表可见：●当一位错码发生在a2、a4、a5或a6上时，S1为1；否则为0。

即a2、a4、a5和a6构成偶监督关系：

S1=a2+a4+a5+a6

同理，a1、a3、a5和a6构成偶监督关系：S2=a1+a3+a5+a6a0、a3、a4和a6构成偶监督关系：S3=a0+a3+a4+a67.5线性分组码●汉明码7.5线性分组码●汉明码●发端编码原则

信息码元a6

、a5

、a4、a3来源于待编码的信息序列；

监督码元a2

、a1、a0的取值应根据信息码元按监督关系式来决定，

即使上面三式中的S1、S2、S3均为0：

a2+a4+a5+a6=0

a1+a3+a5+a6=0……（3）

a0+a3+a4+a6=0a2=a4+a5+a6

a1=a3+a5+a6………

（4）

a0=a3+a4+a6

于是，给定信息位后，根据上式算出各监督位，于是该编码的所有码组如下表：●汉明码的编码效率较高，其编码效率：

该汉明码的码率较高：k/n=4/7≈57%。与相同码长、能纠正一位错码的其他分组码相比，该码效率最高，且实现简单。7.5线性分组码●汉明码1·a6+1·a5+1·a4+0·a3+1·a2+0·a1+0·a0=01·a6+1·a5+0·a4+1·a3+0·a2+1·a1+0·a0=01·a6+0·a5+1·a4+1·a3+0·a2+0·a1+1·a0=0………(5)7.5线性分组码●线性分组码●监督矩阵由（7，4）汉明码出发，（3）式可改写成：写成矩阵形式：……………(6)可化简为：H·AT=0T

或A·HT=0其中，

H=称为线性分组码的监督矩阵1·a6+1·a5+1·a4+0●

r×n阶矩阵●监督矩阵H确定了编码时监督码元与信息码元的关系●把具有[P·Ir]形式的H矩阵称为典型形式的监督矩阵，其中P为r×k阶

矩阵,Ir为r×r阶单位方阵●

H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关7.5线性分组码●线性分组码●监督矩阵●生成矩阵

（4）式也可写成矩阵形式，即

对（7）式两侧作矩阵转置，得：其中Q=PT可见，Q为k×r阶矩阵

……………(7)●r×n阶矩阵7.5线性分组码●线性分组码……………(构造矩阵G：在Q矩阵的左边加上一个k×k阶矩阵，即G=[IkQ]=称为线性码的生成矩阵●生成矩阵G的性质：

●

k×n阶矩阵

●编码方法完全由生成矩阵G确定●把具有[Ik·Q]形式的G矩阵称为典型形式的生成矩阵，其中，Ik为k×k阶单位方阵，Q为k×r阶矩阵●由典型生成矩阵产生的分组码一定是系统码●

G矩阵的各行应线性无关，每行均为许用码组7.5线性分组码●线性分组码●生成矩阵构造矩阵G：在Q矩阵的左边加上一个k×k阶矩阵，即7.5●错误图样 设：发送码组A是一个n列的行矩阵： 接收码组是一个n列的行矩阵B： 令接收码组和发送码组之差为

E就是错码的行矩阵 －称为错误图样 式中，

(i=0,1,…,n-1)

若ei=0，表示该码元未错；若ei=1，表示该码元为错码B–A=E(模2)7.5线性分组码●错误图样B–A=E(模2)7.5线性分组码●校正子矩阵

B–A=E可以改写成B=A+E

上式表示发送码组A与错码矩阵E之和等于接收码组B

例如，若发送码组A=[1000111]

错码矩阵E=[0000100]

则接收码组B=[1000011]

在接收端解码时，将接收码组B代入式

AHT=0

中A的位置进行计算。若接收码组中无错码，则B=A。代入后，该式仍成立，即有

BHT=0

只有当错码未超出检测能力时，上式才不成立。 假设，这时该式的右端等于S，即有

BHT=S

将B=A+E代入上式，得到:S=(A+E)HT=AHT+EH

T7.5线性分组码●校正子矩阵7.5线性分组码●校正子矩阵

S=(A+E)HT=AHT+EHT

上式右端第一项等于0，所以

S=EHT

－校正子矩阵当H确定后，上式中S只与E有关，而与A无关这意味着，S和错码E之间有确定的线性变换关系。 若S和E有一一对应关系，则S将能代表错码位置。●线性分组码的性质●封闭性：若A1和A2是一种线性码中的两个码组，则(A1+A2)仍是其中一个码组

『证』若A1和A2是两个码组，则有：A1HT=0,A2HT=0

将上两式相加，得出

A1HT+A2HT=(A1+A2)HT=0

所以(A1+A2)也是一个码组。●码的最小距离等于非零码的最小重量7.5线性分组码●校正子矩阵 7.5线性分组码

●循环码的概念： 循环性是指任一码组循环一位后仍然是该编码中的一个码组。

●例：一种(7,3)循环码的全部码组如下

表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组码组编号信息位监督位码组编号信息位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a010000000510010112001011161011100301011107110010140111001811100107.6循环码 ●循环码的概念：码组信息位监督位码组信息位监督位A6a5●循环码的概念●一般情况若(an-1

an-2…a0)是循环码的一个码组，则循环移位后的码组： (an-2

an-3…a0

an-1)(an-3

an-4…an-1

an-2) ……(a0

an-1…a2

a1)

仍然是该编码中的码组●多项式表示法 一个长度为n的码组(an-1

an-2…a0)可以表示成

上式中x的值没有任何意义，仅用它的幂代表码元的位置例：码组1100101可以表示为7.6循环码●循环码的概念7.6循环码●循环码的运算

●整数的按模运算 一般说来，若一个整数m可以表示为 式中，Q为整数，则在模n运算下，有

m

p(模n)

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

●定理1：在循环码中，设T(x)是一个长度为n的码组，若 则T(x)也是该编码中的一个码组，并且T(x)是码组T(x)向左循环移位i次的结果例：一循环码为1100101，即 若给定i=3，则有 上式对应的码组为0101110，它正是T(x)向左移3位的结果

●结论：一个长为n的循环码必定为按模(xn+1)运算的一个余式

7.6循环码●循环码的运算7.6循环码●循环码的生成有了生成矩阵G，就可以由k个信息位得出整个码组：

●例：式中，生成矩阵G的每一行都是一个码组●因此，若能找到k个已知的码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。●在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)

位皆为“0”的码组，则g(x)，xg(x)，x2g(x)，，xk-1g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G7.6循环码●循环码的生成7.6循环码●循环码的生成

●在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。●g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(n–k)的唯一一个多项式●我们称这唯一的(n–k)次多项式g(x)为码的生成多项式。一旦确定了

g(x)，则整个(n,k)循环码就被确定了

因此，循环码的生成矩阵G可以写成7.6循环码●循环码的生成7.6循环码●循环码的生成●例：

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

g(x)=x4+x2+x+1码组编号信息位监督位码组编号信息位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a010000000510010112001011161011100301011107110010140111001811100107.6循环码

将此g(x)代入上矩阵，得到 或此循环码组的多项式表示式T(x)：

●结论：所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k–1)的多项式乘g(x)都是码多项式●循环码的生成码组信息位监督位码组信息位监督位A6a5a4a●寻求码生成多项式因为任意一个循环码T(x)都是g(x)的倍式，故它可以写成

T(x)=h(x)g(x)

而生成多项式g(x)本身也是一个码组，即有

T

(x)=g(x)

由于码组T

(x)是一个(n–k)次多项式，故xkT

(x)是一个n次多项式由 可知，xk

T

(x)在模(xn+1)运算下也是一个码组，所以有 上式左端分子和分母都是n次多项式，故相除的商式Q(x)=1。因此，上式可以写成7.6循环码●寻求码生成多项式7.6循环码●寻求码生成多项式将T(x)=h(x)g(x)和T

(x)=g(x)代入 化简后，得到上式表明，生成多项式g(x)应该是(xn+1)的一个因子例：(x7+1)可以分解为 为了求出(7,3)循环码的生成多项式g(x)，需要从上式中找到一个

(n–k)=4次的因子。这样的因子有两个，即

以上两式都可以作为生成多项式 选用的生成多项式不同，产生出的循环码码组也不同

7.6循环码●寻求码生成多项式7.6循环码●循环码的编码方法

●用xn-k乘m(x)；这一运算实际上是在信息码后附加上(n–k)个“0”。例如，信息码为110，它写成多项式为m(x)=x2+x

当n–k=7–3=4时，xn-km(x)=x4(x2+x)=x6+x5，它表示码组1100000●用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即有例如，若选定g(x)=x4+x2+x+1，则有上式是用码多项式表示的运算。它和下式等效：●编出的码组T(x)为：T(x)=xn-km(x)+r(x)

在上例中，T(x)=1100000+101=1100101 7.6循环码●循环码的编码方法7.6循环码●循环码的解码方法

●在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即：式中，余项r(x)应为零；否则，有误码。●当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出了。●在纠错时：●用生成多项式g(x)除接收码组R(x)，得出余式r(x)●按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)●从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)7.6循环码●循环码的解码方法7.6循环码第7章小结7.1

概述7.2纠错编码的基本原理7.3

纠错编码系统的性能7.4奇偶监督码7.5

线性分组码7.6

循环码第7章小结7.1概述第7章信道编码和差错控制7.1

概述7.2纠错编码的基本原理7.3

纠错编码系统的性能7.4奇偶监督码7.5

线性分组码7.6

循环码第7章信道编码和差错控制7.1概述●信源编码与信道编码●信源编码(有效性编码)●去除冗余●提高数字信号的有效性●模拟信号数字化

●信道编码(可靠性编码)●添加冗余●降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性●差错控制：包括信道编码在内的一切纠正错误手段●差错控制技术的种类

●检错重发

●能发现错码，但是不能确定错码的位置●通信系统需要有双向信道●前向纠错(FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码●反馈校验●将收到的码元转发回发送端，将它和原发送码元比较●缺点：需要双向信道，传输效率也较低●检错删除●在接收端发现错码后，立即将其删除●适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处7.1概述发送端接收端信源信道编码调制信道压缩编码解调信宿保密解码信道解码压缩解码保密编码噪声信源编码信源解码●信源编码与信道编码7.1概述发送端接收端信源信道编码调●自动要求重发(ARQ)系统●停止等待ARQ系统●拉后ARQ系统

7.1概述

接收数据ACKACKNAKACKACKNAKACK1233455t发送数据12334556t有错码组有错码组214365798接收数据有错码组有错码组91011101112576ACK1NAK5NAK9ACK55769521436798发送数据1011101112重发码组重发码组●自动要求重发(ARQ)系统7.1概述接收数据ACKAC

●自动要求重发(ARQ)系统●选择重发ARQ系统7.1概述选择重发ARQ系统9接收数据有错码组有错码组21436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9●ARQ和前向纠错比较

●优点●监督码元较少，即码率较高●检错的计算复杂度较低●能适应不同特性的信道●缺点●需要双向信道

●不适用于一点到多点的通信系统或广播系统●传输效率降低，可能因反复重发而造成事实上的通信中断●自动要求重发(ARQ)系统7.1概述选择重发ARQ系统●产生错码的原因●乘性干扰引起的码间串扰

●加性干扰引起的信噪比降低

●信道分类：按照加性干扰造成错码的统计特性不同划分●随机信道：错码随机出现，例如由白噪声引起的错码

●突发信道：错码相对集中出现，例如由脉冲干扰引起的错码●混合信道●编码序列的参数●n－编码序列中总码元数量

k－编码序列中信息码元数量

r－编码序列中差错控制码元数量 （差错控制码元，以后称为监督码元或监督位）

k/n－码率

(n-k)/k=r/k－冗余度

7.1概述●产生错码的原因7.1概述7.2纠错编码的基本原理●差错控制编码

●理论依据：香农信道编码定理对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值

●基本思想通过对信息码元序列作某种变换,使原来彼此相互独立,没有关联的信息码元序列,经过这种变换后,产生某种规律性或相关性,使在接收端可根据这种规律性来检查,以至纠正传输序列中的差错

●实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系

7.2纠错编码的基本原理●差错控制编码7.2纠错编码的基本原理●差错控制编码●简单例子

●假如要传送A、B两个消息，消息A----“0”；消息B----“1”若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力

●消息A----“00”；消息B----“11”若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力●消息A----“000”；消息B----“111”传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。●可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码元外添加了冗余码元（监督码元）。一般说来，添加的冗余越多，

码的检错、纠错能力越强，但信道的传输效率下降也越多。7.2纠错编码的基本原理●差错控制编码7.2纠错编码的基本原理●差错控制能力与编码效率

●设：有一种由3个二进制码元构成的编码，它共有23=8种不同的可能码组：

000–晴001–云010–阴011–雨

100–雪101–霜110–雾111–雹这时，若一个码组中发生错码，则将收到错误信息●若在此8种码组中仅允许使用4种来传送天气，例如：令 000–晴011–云101–阴110–雨为许用码组，其他4种不允许使用，称为禁用码组

这时，接收端有可能发现（检测到）码组中的一个错码。这种编码只能检测错码，不能纠正错码

●若规定只许用两个码组：例如

000–晴111–雨就能检测两个以下错码，或纠正一个错码7.2纠错编码的基本原理●差错控制能力与编码效率●分组码概念

●分组码＝信息位＋监督位分组码符号：(n,k)

其中，n－码组总长度

k－信息码元数目

r=n–k－监督码元数目 右表中的码组为(3,2)码

●分组码的一般结构：信息位监督位晴000云011阴101雨110k个信息位r个监督位an-1an-2...arar-1an-2...a0t码长n=k+r7.2纠错编码的基本原理●分组码概念信息位监督位晴000云011阴101雨110k个●码重码字中非零码元的数目●码距两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，称为汉明（Hamming）距离,简称码距●最小码距在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为d0●码距的几何意义：以n=3的编码为例一般而言，码距是n维空间中单位正多面体顶点之间的汉明距离

7.2纠错编码的基本原理(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1●码重7.2纠错编码的基本原理(0,0,0)(0,0,1)●最小码距与检、纠错能力关系●一个码能检测e个错码，则要求其最小码距

d0≥e+1

反之，若码的最小距离为d0，则最多能检测d0-1个错码

●一个码能纠正t个错码，则要求其最小码距

d0≥2t+1

反之，若码的最小距离为d0，则最多能纠正(d0-1)/2个错码

7.2纠错编码的基本原理0123BA汉明距离ed0码距等于3的两个码组BtA汉明距离012345td0码距等于5的两个码组●最小码距与检、纠错能力关系7.2纠错编码的基本原理012●最小码距与检、纠错能力关系

●一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距

d0≥e+t+1(e>t)7.2纠错编码的基本原理●最小码距与检、纠错能力关系7.2纠错编码的基本原理●误码率性能和带宽的关系采用编码降低误码率所付出的代价是带宽的增大10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能●误码率性能和带宽的关系10-610-510-410-310●功率和带宽的关系

采用编码以节省功率，并保持误码率不变，付出的代价也是带宽增大。

10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能●功率和带宽的关系10-610-510-410-310-21

●传输速率和带宽的关系 对于给定的传输系统，其传输速率和Eb/n0的关系：

式中，RB

－码元速率。 提高传输速率，采用编 码以保持误码率不变；付出 的代价仍是带宽增大10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3纠错编码系统的性能 ●传输速率和带宽的关系10-610-510-410-31●编码增益 定义：在保持误码率恒定条件下，采用纠错编码所节省的信 噪比Eb/n0

称为编码增益：

式中，

(Eb/n0)u

－未编码时的信噪比(dB) (Eb/n0)c

－编码后所需的信噪比(dB)7.3纠错编码系统的性能10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK●编码增益7.3纠错编码系统的性能10-610-510-4●一维奇偶监督码

●在信息码元后附加一位监督位，使得码组中“1”的个数为偶数或奇数,按照奇偶数分为奇数监督码和偶数监督码两类●(n,n-1)分组码，码率为(n-1)/n（或k/(k+1))●奇数监督码中，此监督位使码组中“1”的个数为奇数：式中，a0为监督位，其他位为信息位●偶数监督码中，此监督位使码组中“1”的个数为偶数： 式中，a0为监督位，其他位为信息位●检错能力－能够检测奇数个错码●应用：以随机错误为主的计算机通信系统，难于对付突发错误,计算机内部的数据传送，就是采用这种码7.4奇偶监督码信息位监督位晴000云011阴101雨110●一维奇偶监督码7.4奇偶监督码信息位监督位晴000云01●二维奇偶监督码

●有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点时，则检测不出●适合检测突发错码●能够纠正部分错码

7.4奇偶监督码●二维奇偶监督码7.4奇偶监督码●基本概念●代数码－利用代数关系式产生监督位的编码●线性分组码－代数码的一种，其 督位和信息位的关系由线性代数方程决定●汉明码－一种能够纠正一个错码的线性分组码●汉明码●发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”

码元个数为偶数

●接收端译码：

●计数接收码组中“1”码元个数是否为偶数，即计算：

S=an-1+an-2+…+a0………

………

…………

………

…………

……

（1）●S=0认为没错，S=1认为有错●（1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式7.5线性分组码●基本概念7.5线性分组码●汉明码●监督位增加到2位：有两个监督方程，两个伴随式；两个伴随式组合有四种（00表示无错，01、10、11表示一位错码的三种可能位置）●监督位增加到r位：可指示一位错码的（2r-1）个可能位置●一般说来，对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个

监督关系式来指示一位错码的n种可能位置，则要求：

2r-1≥n

即

2r≥k+r+1……

……

……

……

…

……

……

……

……

（2）

●举例：构造一（n，k)分组码，k=4并能纠正一位错码

●欲纠正一位错码，由（2）式知r≥3，取r=3，则n=k+r=7

●设7位码元为：a6a5

……a0；三个伴随式：S1、S2、S3；则可规定S1S2S3的

八种组合与一位错码的对应关系如下（也可规定为另一种对应关

系）：7.5线性分组码●汉明码7.5线性分组码7.5线性分组码●汉明码●举例：构造一（n，k)分组码，k=4并能纠正一位错码从上表可见：●当一位错码发生在a2、a4、a5或a6上时，S1为1；否则为0。

即a2、a4、a5和a6构成偶监督关系：

S1=a2+a4+a5+a6

同理，a1、a3、a5和a6构成偶监督关系：S2=a1+a3+a5+a6a0、a3、a4和a6构成偶监督关系：S3=a0+a3+a4+a67.5线性分组码●汉明码7.5线性分组码●汉明码●发端编码原则

信息码元a6

、a5

、a4、a3来源于待编码的信息序列；

监督码元a2

、a1、a0的取值应根据信息码元按监督关系式来决定，

即使上面三式中的S1、S2、S3均为0：

a2+a4+a5+a6=0

a1+a3+a5+a6=0……（3）

a0+a3+a4+a6=0a2=a4+a5+a6

a1=a3+a5+a6………

（4）

a0=a3+a4+a6

于是，给定信息位后，根据上式算出各监督位，于是该编码的所有码组如下表：●汉明码的编码效率较高，其编码效率：

该汉明码的码率较高：k/n=4/7≈57%。与相同码长、能纠正一位错码的其他分组码相比，该码效率最高，且实现简单。7.5线性分组码●汉明码1·a6+1·a5+1·a4+0·a3+1·a2+0·a1+0·a0=01·a6+1·a5+0·a4+1·a3+0·a2+1·a1+0·a0=01·a6+0·a5+1·a4+1·a3+0·a2+0·a1+1·a0=0………(5)7.5线性分组码●线性分组码●监督矩阵由（7，4）汉明码出发，（3）式可改写成：写成矩阵形式：……………(6)可化简为：H·AT=0T

或A·HT=0其中，

H=称为线性分组码的监督矩阵1·a6+1·a5+1·a4+0●

r×n阶矩阵●监督矩阵H确定了编码时监督码元与信息码元的关系●把具有[P·Ir]形式的H矩阵称为典型形式的监督矩阵，其中P为r×k阶

矩阵,Ir为r×r阶单位方阵●

H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关7.5线性分组码●线性分组码●监督矩阵●生成矩阵

（4）式也可写成矩阵形式，即

对（7）式两侧作矩阵转置，得：其中Q=PT可见，Q为k×r阶矩阵

……………(7)●r×n阶矩阵7.5线性分组码●线性分组码……………(构造矩阵G：在Q矩阵的左边加上一个k×k阶矩阵，即G=[IkQ]=称为线性码的生成矩阵●生成矩阵G的性质：

●

k×n阶矩阵

●编码方法完全由生成矩阵G确定●把具有[Ik·Q]形式的G矩阵称为典型形式的生成矩阵，其中，Ik为k×k阶单位方阵，Q为k×r阶矩阵●由典型生成矩阵产生的分组码一定是系统码●

G矩阵的各行应线性无关，每行均为许用码组7.5线性分组码●线性分组码●生成矩阵构造矩阵G：在Q矩阵的左边加上一个k×k阶矩阵，即7.5●错误图样 设：发送码组A是一个n列的行矩阵： 接收码组是一个n列的行矩阵B： 令接收码组和发送码组之差为

E就是错码的行矩阵 －称为错误图样 式中，

(i=0,1,…,n-1)

若ei=0，表示该码元未错；若ei=1，表示该码元为错码B–A=E(模2)7.5线性分组码●错误图样B–A=E(模2)7.5线性分组码●校正子矩阵

B–A=E可以改写成B=A+E

上式表示发送码组A与错码矩阵E之和等于接收码组B

例如，若发送码组A=[1000111]

错码矩阵E=[0000100]

则接收码组B=[1000011]

在接收端解码时，将接收码组B代入式

AHT=0

中A的位置进行计算。若接收码组中无错码，则B=A。代入后，该式仍成立，即有

BHT=0

只有当错码未超出检测能力时，上式才不成立。 假设，这时该式的右端等于S，即有

BHT=S

将B=A+E代入上式，得到:S=(A+E)HT=AHT+EH

T7.5线性分组码●校正子矩阵7.5线性分组码●校正子矩阵

S=(A+E)HT=AHT+EHT

上式右端第一项等于0，所以

S=EHT

－校正子矩阵当H确定后，上式中S只与E有关，而与A无关这意味着，S和错码E之间有确定的线性变换关系。 若S和E有一一对应关系，则S将能代表错码位置。●线性分组码的性质●封闭性：若A1和A2是一种线性码中的两个码组，则(A1+A2)仍是其中一个码组

『证』若A1和A2是两个码组，则有：A1HT=0,A2HT=0

将上两式相加，得出

A1HT+A2HT=(A1+A2)HT=0

所以(A1+A2)也是一个码组。●码的最小距离等于非零码的最小重量7.5线性分组码●校正子矩阵 7.5线性分组码

●循环码的概念： 循环性是指任一码组循环一位后仍然是该编码中的一个码组。

●例：一种(7,3)循环码的全部码组如下

表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组码组编号信息位监督位码组编号信息位监督位A6a5a4a3a2a1a0a6a5a4A3a2a1a010000000510010112001011161011100301011107110010140111001811100107.6循环码 ●循环码的概念：码组信息位监督位码组信息位监督位A6a5●循环码的概念●一般情况若(an-1

an-2…a0)是循环码的一个码组，则循环移位后的码组： (an-2

an-3…a0

an-1)(an-3

an-4…an-1

an-2) ……(a0

an-1…a2

a1)

仍然是该编码中的码组●多项式表示法 一个长度为n的码组(an-1

an-2…a0)可以表示成

上式中x的值没有任何意义，仅用它的幂代表码元的位置例：码组1100101可以表示为7.6循环码●循环码的概念7.6循环码●循环码的运算

●整数的按模运算 一般说来，若一个整数m可以表示为 式中，Q为整数，则在模n运算下，有

m

p(模n)

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

●定理1：在循环码中，设T(x)是一个长度为n的码组，若 则T(x)也是该编码中的一个码组，并且T(x)是码组T(x)向左循环移位i次的结果例：一循环码为1100101，即