第9章-差错控制编码-

通信原理电子教案

第9章

差错控制编码

陕西科技大学2/1/20231研究的问题

9.1

引言9.2纠错编码的基本原理9.3

常用的简单编码9.3

线性分组码9.4

循环码9.5

卷积码9.6网格编码调制2/1/20232干扰乘性：均衡加性：调制解调体制、发送功率、最佳接收9.1引言

一、编码问题的提出

由于数字信号在传输过程中必不可免的受到干扰的影响，使码元波形变坏，故传输到接收端后可能发生错判。信道译码检/纠错编码若还不行，则需－－差错控制编码。目的：在数字通信系统中，为了提高数字信号传输的有效性而采取的编码称为信源编码；为了提高数字通信的可靠性而采取的编码称为信道编码。差错可控2/1/20233二、错误的类型随机性错误（白噪声引起） 特点：单个错，错误之间不相关。主要出现在无记忆信道。2.突发性错误(脉冲干扰引起） 特点：成串错，错误之间有相关性。主要出现在有记忆信道。错误传播。3.混合性错误2/1/20234三、差错控制的方式1.检错重发(ARQ)收发可检错的码特点:

1）双向通道

2）通信效率低

3）不适于实时通信

4）编、译码设备简单

5）编码效率高总码元

(nbit)=

信元(kbit)+督元(r

bit)。只检不纠，有错自动要求重发。2/1/202352.前向纠错(FEC)收发可纠错的码特点：

1）只需单向信道－－省信道！

2）通信效率高；

3）适于实时传输；

4)译码设备复杂。检错并纠错2/1/202363.反馈检验法收发原理：收端将信码原封不动地转发回发端，并与原发送信码相比较：发现错－－重发；否则：PASS特点:

需要双向通道；收发设备简单；传输效率低（最低）。2/1/202379.2纠错编码的基本原理

一.基本思想信元督元信元督元……信元和督元有一的函数关系，插入督元的过程就是一种编码的过程，接收端可检错纠错。显然，传输效率↓（引入冗余码）例：天气预报信元督元

000晴

011云

101阴

110雨三位码元有23=8种组合，实际使用了22=4种－－许用码组。其余001，010，100，111

为禁用码组。检错能力：可检错奇数个错；纠错能力：无。2/1/20238例：天气预报，可预报天晴信元督元

000111冗余量加大，禁用码组比例提高。检错能力：检2；纠错能力：纠1。许用码组2个，禁用码组6个晴阴2/1/20239二.纠错编码的分类线性码和非线性码分组码、卷积码和循环码系统码和非系统码三.分组码定义:将信息码分组，为每信息码附加若干个监督码编码，称为分组码。特点:

在分组码中，监督码元仅监督本码组中的信息码元。符号:(n,k),r=n–k码字:结构:an-1an-2…arar-1…a0k个信元r个督元码长－－n2/1/202310码组的重量和码距及纠错能力1.重量码组中非0元素的个数例:A=(10110)码重=32.码距

两两码组对应位上数值不同的个数，记为d。最小码距:

某种编码中各个码组间距离的最小值，记做d0

d0=dmin码距的几何意义:(n=3)各顶点沿立方体各边行走的几何距离。码元值：每一码组的三个码元值，就是此立方体各顶点的座标（a2a1a0）最小码距:

12/1/202311前例中：天气预报信元督元

000晴

011云

101阴

110雨四个许用码组之间的距离均为2。Why?摈弃d=1的码－－禁用码组。许用码组最小码距愈大，抗干扰能力愈强！确定最小码距的目的：决定编码的检纠错能力。2/1/2023123.d0与纠检错能力若要求检测e个错,则d0≧e+1

若要求纠正t个错,则d0≧2t+1

若要检测e纠正t

个错(同时),则

d0>e+t+1,

且e>t码距与检错和纠错能力的关系如图：t1te2/1/2023130123Ad0(a)012345ABttd0(b)ABt1te(c)图9-42/1/202314

9.3常用的简单编码

－－属于分组码一类。简单、实用。

一.奇偶监督码

满足:

偶监督码：码组中1的个数为偶数；奇监督码：码组中1的个数为奇数。检错能力:

所有奇数个错。一半！应用非常多。编码效率:2/1/202315二维奇偶监督码

－－进行横、纵向监督例:00001111010100110101000000110101101010横向监督纵向监督纠检错能力:

仍可检错奇数个错还可检错偶数个错可纠正一些错码●适于检测突发性错误2/1/202316横比码(等重码)例:码重为31.010111100110110许用码组:C35=10禁用码组:25-10=22检错能力:可检测所有奇数个码元的错 和部分偶数个码元的错,但不能检测码组中“1”变为“0”与“0”变为“1”的错码数目相同的那些偶数错码编码效率:2/1/202317例：n=10,则k=5信元码监督码合成码校验码1011010110000000000010001011101111100000●接受端的检测三.正反码编码规则:●信息位(n/2)中有奇数个“1”,则监督位与信息位相同●信息位(n/2)中有偶数个“1”,则监督位是信息位的反码2/1/202318

9.4线性分组码定义：若分组码（n,k）,督元与信元的关系可用一线性方程组来描述，则该分组码（n,k）称为线性分组码。一、汉明码－－能纠一位错的线性分组码。定义：是一种能纠正一位错码，且编码效率较高的线性分组码。最小码距：d0=31.构造原理考察：定义一个监督方程（监督关系式、偶监督）：由于一位校正子只有两种取值，故只能表示有错或无错，不能指出错码的位置。2/1/202319推想:如果监督位增加一位（即变成两位），则可增加一个类似于上式的监督关系，即可获得两个校正子，于是可有S1S20001011－－无错可指示一个错码可能出现的位置，共有22-1=3个位置。2/1/202320再推广:S1S2……Sr00…….000…….1………………11….11－－无错2r-1

个错的可能位置显然：要求2r-1≥n（n=k+r），则可指示（仅一位错时）任一错码的位置－－包括信元、督元。 或： 2r≥k+r+1－－可指示一个错码可能出现的2r-1个位置。2/1/2023212.例:构造k=4的汉明码（1）确定r由2r≥k+r+1

得r=3，则n=

k+r=7－－

(7,4)

分组码2/1/202322（2）写出校正子的编码表

r=3

共有3个校正子

S1S2S3

错码位置S1S2S3

错码位置001a0101a4

010a1110a5100a2111a6

011a3

000无错（3）由校正子编码表得监督方程组－－校正子和哪些码元构成偶监督关系若S1S2S3=000

时,即无错－－得校验方程:偶监督关系2/1/202323得校验方程:即实际上确定了督元和信元之间的关系:校验方程督～信关系－－有了校正子编码表，督元不是随便选的！（4）给定了信元a6a5a4a3,可由“督～信关系”确定督元－－全部(7,4)码组。2/1/202324（4）给定了信元a6a5a4a3,可确定督元－－全部(7,4)码组2/1/202325二.线性分组码1.线性方程组和监督方程写成矩阵式:111010011010101011001a6a5a4a3a2a1a02/1/202326可见：H一旦确定，督元和信元之间的关系也就确定了。若:则称H为典型阵，一般，H总可以化为典型阵。111010011010101011001a6a5a4a3a2a1a02/1/2023272.生成矩阵矩阵形式:－－从督信方程入手由2/1/202328写成行阵形式:其中Q=PT。上式表明：信息位给定后，就产生了监督位！进一步，令生成矩阵

G=[Ik

Q]则，码组行阵 A=[a6a5a4a3]G2/1/202329例：生成矩阵讨论：●由具有

[Ik

Q]形式的生成矩阵称为典型生成阵。●由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后－－这种码称为系统码。码组行阵：2/1/202330一般形式:

A=[an-1an-2…ar]G3.G和H的关系由Q=PT

或P=QT

则:H=[P·Ir

]G=[Ik

·Q]综上：线性分组码的编码，就是根据其监督阵H或生成阵G将长为k的信息码编成长为n的码组。2/1/2023314.线性分组码的纠错译码过程－－怎样由含有错误的接收码组中的接收码组中恢复正确。

（1）错误图样设：发码组为A,接受码组为B

则 B–A=E(模2)－－错误行阵或错误图样：

E=[en-1en-2……e0]例:A=[1111111]B=[1001101]

则E=[0110010]2/1/202332（2）校正子（或称译码伴随式）B=A+E

代入上式，得结论：校正子S仅于错误图案有关，与发送码组无关。2/1/202333由收到的码组B，按式：BHT=S→S由S=ET

→

E按B+E=A

→

A由A

→原始信息（3）纠错译码过程

2/1/2023345.线性分组码的重要性（1）封闭性

设：

A1、A2

分别为一线性分组码的任意两个许用码组。则：A1+A2

仍为该线性分组码的许用码组。证：由假设知 A1HT=0、A2HT=0

所以 A1HT+A2HT=（A1+A2）HT＝0

即A1+A2也是一个码组。结论：线性码组中任意两个码字之和，仍为该线性码组之码字。（2）线性分组码的最小码距即为该码的最小重量: d0=Wmin（除全0码组）证：由封闭性得，两个码组之间的距离（之差），必是另一码组的重量。故最小码距即是码的最小重量！2/1/202335

9.5循环码

－－仍属于线性分组码

特点:

编译码设备简单，检纠错能力强。

9.5.1循环码的原理

具有线性分组码的所有性质之外，还具有循环性：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。2/1/202336码多项式T(x)（1）定义－－为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式。设：许用循环码A=(an-1

an-2…a1

a0)，则：它的码多项式表示为：其中：x仅是码元位置的标记。2/1/202337例:

设(7,3)循环码组为

(0111001)则相应码多项式为：反之，由码多项式易得出码组：(0111001)－－可由码组直接写出。2/1/202338（2）码多项式的按模运算1）整数的按模运算若一个整数m可以表示为:则在模n运算下，有m≡p（模n）。例：同样对于多项式而言，也有类似按模运算。2/1/202339其中：商Q(x)为多项式，余数R(x)的幂次低于N(x)的幂次。例:

求x4+x2+1

按模x3+1

运算的余式R(x)2）码多项式的按模运算 若则2/1/202340

3）循环性在循环码中，若T(x)

是一个长为n的许用码组，则xiT(x)

在按模xn+1运算下，亦是一个许用码组。即设：

T(x)

是长为n的许用码组多项式则：

T’(x)仍为该码组中的一个码多项式。例:

（7，3）码

T(x)=x6+x5+x2+1(1100101)－－前码组循环左移3位！2/1/202341由此类推可见：一个长为n的循环码，必为按模（xn+1）运算的一个余式。2/1/2023422.生成多项式g(x)（1）存在性

(n，k)循环码中有且仅有一个g(x)

g(x)=xn-k+……+1特点:

最高的次数:n-k=r；

最高次项和常数项系数必为1

。在循环码中，除了全0码组外，再也没有连续k位均为0的码组。即连0长度最多为k-1位！这唯一的n-k次多项式称为生成多项式，记为g(x)！2/1/202343（2）g(x)与生成矩阵G(x)的关系A=[an-1…ar

]GG=[IkQ]∵生成矩阵G的每一行都是一个码组；G是k行n列矩阵，∴只要找到k个已知码组，就能构成生成矩阵G！生成多项式确定后，则g(x)、x

g(x)、……、xk-1

g(x)都是码组，且这k个码组信息无关，因此可以用来构成生成矩阵。g(x)确定了→G(x)也就确定了→整个码组即确定！2/1/202344例:

(7，3)循环码，g(x)=x4+x2+x+1

求典型生成矩阵解:典型阵:可方便地直接写成码组形式2/1/202345（3）

g(x)与T(x)的关系－－（7，3）表明：所有T(x)都可以被g(x)整除，而且任一次数不大于(k-1)的多项式乘以g(x)都是码多项式。2/1/202346依据:

g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。证：任一循环多项式T(x)都是g(x)的倍式，即而生成多项式g(x)本身也是一个码组，即有由于码组T’(x)为一（n-k）次多项式，故xkT’(x) 为一n次多项式。由知，xkT’(x)在模（xn+1）的运算下，亦为一码组，故可写成（4）如何寻找g(x)2/1/202347上式左端分子和分母都是n次多项式，故商Q(x)＝1，因此上式可化成即将T(x)=h(x)g(x)、T’(x)=g(x)代入，并化简，得表明:

g(x)应该是xn+1的一个因式！结论:

g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。2/1/202348（4）如何寻找g(x)依据:

g(x)是xn+1的一个(n-k)次的因子，且常数项不为零。如(x7+1)=(x+1)(x3+x2+1)(x3+x+1)n=7（7，4）：x3+x2+1、x3+x+1（7，3）：(x+1)(x3+x2+1)、(x+1)(x3+x+1)（7，6）：x+12/1/202349例:

（7，3）循环码有多项式如下，找出（7，3）码的生成多项式g(x)。

（1）x4+x3+x （2）x3+x2+1（3）