第九章差错控制编码

第九章差错控制编码第一页，共101页。引言1纠错编码的基本原理2常用的简单编码3线性分组码4循环码5第9章差错控制编码67卷积码网格编码调制2008.82第二页，共101页。9.1引言信道解调信源编码加密调制解密译码信宿噪声同步系统信源编码信道编码差错控制ASKFSKPSKDPSK数字通信的组成A/D数据压缩2008.83第三页，共101页。数字通信中的编码分为：信道编码：信源编码：为提高信号传输的有效性而采取的措施。为提高信号传输的可靠性而采取的措施。亦称差错控制编码。2008.84第四页，共101页。

在通信过程中，会受到各种外来干扰，如脉冲干扰，随机噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起数据信息序列产生错误，称之为差错。2008.85第五页，共101页。差错的两大类型：

随机性错误：前后出错位之间无一定关系，随机、离散出现。

突发性错误：差错成串出现，且有一定相关性。实际信道中，上述两种错误常同时存在。

2008.86第六页，共101页。合理的设计基带信号时域/频域均衡发射功率的提高采用信道编码都能有效的提高传输可靠性。2008.87第七页，共101页。差错控制

在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性不强的原始数字信号变为带规律性或加强了规律性的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进行错误纠正。2008.88第八页，共101页。

1、差错控制方法（1）前向纠错法FEC

所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备复杂，传输效率↓。信源FEC编码信道FEC译码信宿（2）信息反馈法IF信息信号信息信号发端收端

方法和设备简单，无需纠检错编译系统。但需要双向信道，传输效率↓、实时性差。2008.89第九页，共101页。

(3)检错重发法ARQ

所发码具有检错能力，收端接收后判决是否出错，通过反向信道发送判决结果，发端据此决定是否重发。译码设备简单，对突发错误有效，要求有反馈信道。信源编码器正向信道译码器信宿缓存器重发控制器反向信道重发判决器工作过程：发送——检测——回复——重发或发送新的数据2008.810第十页，共101页。①停止等待方式

3221221ACKACKNACK发送端接收端

ARQ的三种实现方式：

特点：半双工工作，简单，要求的缓存量小，但等待时间较长，传输效率↓

2008.811第十一页，共101页。

②连续重发方式

6543254321065432543210ACK0ACK1NAK2ACK2ACK3退N步方式：从出错帧开始重发优缺点：传输效率↑，但重发的N帧中，大部分为正确，所以仍有浪费。发端缓存必须可存N帧。

2008.812第十二页，共101页。2987654321029876543210ACK0ACK1NACK2ACK3ACK4ACK5ACK2ACK6

只对出错信息重发，因此传输效率大大提高。但收发两端都要有足够的存储空间。

③选择重发方式

2008.813第十三页，共101页。反馈信道ARQFEC

编码器正向信道FEC

译码器ARQ

编码既有纠错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过ARQ方式进行重发。

(4)混合方式

2008.814第十四页，共101页。（1）根据各码组信息码和监督码的关系分：

线性码，非线性码根据监督码元是否仅与本组信息元有关

分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：

系统码，非系统码（3）纠错码的分类2008.815第十五页，共101页。根据码的用途分：

检错码，纠错码（4）根据码元的取值：

二进制码，多进制码（5）根据构造编码的数学方法：

代数码，几何码，算术码（6）本课程主要讨论纠随机错误的二进制线性分组码。2008.816第十六页，共101页。9、2纠错编码的基本原理1、几个术语码长：码组中码元的数目，常用n表示；码距：两等长码字C1、C2对应位上取值不同的数目，又称为汉明(Hamming)距离，记为d(c1,c2)。码重：码组中非零码元的数目，记为W；最小码距：在分组码(n,k)中，任意两个码字之间汉明距离的最小值，记为dmin。码距的大小关系到编码的检纠错能力。2008.817第十七页，共101页。n=3时，码距的几何说明：（a2a1a0

）a2a1a0（110）（011

）d=2110011（111）（000

）d=30001112008.818第十八页，共101页。A、B两消息，可用一位二进制数表示，A=1、B=0出错时无法判定。例

增加一个监督位，取11→A、00→B,若收到01或10时，

可知发生了错误，但不能纠正错误。再增加一个监督位，取111→A、000→B,如一位错：B→001A→110；若两位错011,110则只能发现不能纠错

因此这种（3.1）码，能纠正一个错，发现两个错。

但是(3.1)码中，数据位仅为1位，监督位为两位，传输效率↓↓

可以看出：差错控制是以牺牲传输效率为代价而换取了传输质量的提高的。纠检错能力与加入的监督元数目成正比。

2、纠错或检错的原理2008.819第十九页，共101页。分组码的三个参数码长n，信息位k，最小距离d0，

用符号(n,k,d0)表示k个信息元an-1an-2……arar-1……

a0r个监督元码长：n=k+rR=k/n为编码效率，d0一定(纠错能力一定)时，k/n大，效率高。

对被传输的信息序列分组，每组为k个信息元，对每组按某种关系附加(n-k)个监督码元(校验)，形成为n位的码字。这种方法构成的码组称为分组码。2008.820第二十页，共101页。

3、分组码的纠(检)错能力与最小码距d0的关系

任一（

n，k）分组码，若要在码字内能：

1/检测e个随机错误，则要求：

d0≥e+1

2/纠正t个随机错误，则要求：

d0≥2t+1

3/纠正t个同时检测e(e>t)个随机错误，则要求：d0≥

e+t+12008.821第二十一页，共101页。纠（检）错能力的几何解释

A1

d0eA2（a）

A1

A2

d0et（c）

A1

d0tA2（b）A2t2008.822第二十二页，共101页。例：一个码集，只有两个许用码：0000、1111，试求其纠、检错能力和编码效率。2008.823第二十三页，共101页。4、对纠错编码的要求纠、检错能力强，编码效率高，码长短，编码规律简单。例：一个码集，只有两个许用码：0000、1111，试求其纠检错能力和编码效率。解：根据码距的定义，则该码集d0=4，1/用于检错，e≤d0

–1=3，即可检3个错误；2/用于纠错，t≤(d0–1)/2=3/2，取整，即可纠1个错误；3/同时用于纠、检错，d0≥

e+t+1（e＞t）取：e=2，t=1，则可满足上式，即可检2个错误同时纠一个错；R=k/n=1/4编码效率：2008.824第二十四页，共101页。5.差错控制编码的效用

假设在随机信道中，发送“0”和“1”的错误概率相等，都等于p，且p＜＜1，在码长为n的码组中，发生r个错误的概率为：2008.825第二十五页，共101页。例如：当n=7，p=10¯³时，则有：

由此可见，即使仅能纠正1-2个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实际应用价值。2008.826第二十六页，共101页。6.有扰信道编码定理（Shannon第二定理）

对于给定的有扰信道，若信道容量为C，只要发送端以低于C的信息速率Rb发送信息，则一定存在一种编码方法，使得译码错误概率P随着码长n的增加，按指数下降至任意小的值，表示为Pe-nE(Rb)E(Rb)为误差指数，Rb<C时，E(Rb)>0。

Rbmax=C=Blog2(1+S/N)（bit/s）2008.827第二十七页，共101页。系统带宽和信噪比的矛盾：由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。2008.828第二十八页，共101页。编码性能举例未采用纠错编码时， 若接收信噪比等于

7dB，编码前误码率 约为810-4，图中A

点，在采用纠错编码 后，误码率降至约4

10-5，图中B点。这样， 不增大发送功率 就能 降低误码率约一个半 数量级。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)2008.829第二十九页，共101页。由图还可以看出，若 保持误码率在10-5， 图中C点，未采用编 码时，约需要信噪比

Eb/n0=10.5dB。在 采用这种编码时，约 需要信噪比7.5dB，图 中D点。可以节省功率

2dB。通常称这2dB为

编码增益。上面两种情况付出的代 价是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)2008.830第三十页，共101页。传输速率和Eb/n0的关系 对于给定的传输系统 式中，RB为码元速率。 若希望提高传输速率， 由上式看出势必使信 噪比下降，误码率增 大。假设系统原来工作 在图中C点，提高速率后 由C点升到E点。但加用 纠错编码后，仍可将误码 率降到D点。这时付出的 代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)2008.831第三十一页，共101页。9-3常用的简单编码1、奇偶监督码：

k=n-1,r=1的线性码。特点：码组中的1个数是奇数（奇监督码）或偶数（偶监督码）。偶监督时，要满足：奇监督时，要满足：两者的校验能力相同，均只能检测出奇数个错误。R=k/n=n-1/n=1-1/n编码效率：2008.832第三十二页，共101页。序码字序码字号信息码元监督元号信息码元监督元

a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110

码长5的偶监督码2008.833第三十三页，共101页。

偶监督码编码器a4a3a2a1+信息组a0a1a2a3a4码字2008.834第三十四页，共101页。b3b0b1b2b4+接收码组BS检错信号偶监督码的检错电路2008.835第三十五页，共101页。例：一数据序列：

{11100

10111

01101

10001

10101}试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力∣∣∣

∣2008.836第三十六页，共101页。例：一数据序列：

{11100

10111

01101

10001

10101}试对其进行（6，5）偶校验编码，写出码序列并分析其抗干扰能力解：（6，5）,将数据序列每5码元分组，并作：的运算可得出编码数据序列：{111001∣101110∣011011∣100010∣101011}只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。∣∣∣

∣2008.837第三十七页，共101页。2、水平垂直奇偶校验码：

又称行列监督码或二维奇偶监督码。特点：对水平方向和垂直方向的码元同时实施奇偶监督。110010100000100001101001111000011100111000001010101010111000111100行列监督码2008.838第三十八页，共101页。适于监测突发错误：逐行传输时，能检测长度bm+1的突发错误;逐列传输时,能检测长度bL+1的突发错误；还能纠正一些仅在一行中的单个错误。其中m为行数，L为列数2008.839第三十九页，共101页。3、恒比码：

又称等重码或定1码。特点：码组中0，1的个数保持不变。若码长为n，码重为w，则此码的码字个数为：Cnw，禁用码字个数为：2n-Cnw例如：我国的电报，每个汉字用四个10进制数表示，每位10进制数就采用3：2恒比码构成的5位码组来表示。码字的个数C53=10检错能力较强，可检出所有奇数和部分偶数错误。2008.840第四十页，共101页。数字码字0123456789011010101111001101101101000111101011110001110100113:2恒比码如：我国的电报，每个汉字用四个10进制数表示，每位10进制数就采用3：2恒比码构成的5位码组来表示。码字的个数C53=102008.841第四十一页，共101页。4、正反码：

简单的可纠错编码，信元数等于监督元数特点：信息位中，有奇数个1时，监督位重复信息位；信息位中，有偶数个1时，监督位取信息位的反码；可纠一位、检测所有两位错和部分两位以上的错误。例：11001→11001∣1100110001→10001∣01110(n,k)其中k=n/2编码效率：R=k/n=1/22008.842第四十二页，共101页。9.4线性分组码9.4.1基本概念

可用线性方程组表述码的规律性的分组码称为线性分组码。线性码建立在代数学群论基础上，线性码各许用码的集合构成代数学中的群，因此，又称为群码。2008.843第四十三页，共101页。

1.含有全零码字。

2.任意两个许用码字之和仍是一个许用码字。（封闭性）

3.最小码距d0等于非零码字的最小重量即d0=wmin

（由此性质可以方便的确定出线性分组码的最小码距，进而明确其纠错能力。）在群中只有一种运算，就是模2和。线性分组码的性质：2008.844第四十四页，共101页。

奇偶监督码是一种最简单的线性码，我们曾经作了偶校验的例子。称为监督方程。接收时，为了检测传输时是否有错，还要做同样的计算：这里S称为校正子，上式也称伴随式。奇偶监督码中只有一位监督码，因此只能表示有否错误。2008.845第四十五页，共101页。当监督位增加，则监督方程增加，校正子增加。r位监督码除了用全“0”表示无错外，可表示种错误图样。(n,k)码可纠错的错误图样数为：

我们把接收码组R与发射码组C的差称为错误图样，用E表示：E=C-R，或者C=R+E

(n,k)中，信息码为k位，可传输M=2k种信息，当增加r位的监督位后，有2n种状态，但只取2k种为许用状态，其他为禁用，(n,k)码可检测的错误图样数为2n-2k2n-k-1=2r-1不可检测的错误图样数为2k-12008.846第四十六页，共101页。2n-k-1++……+=对于能纠正t个错误的线性分组码(n,k)应满足：是错i位的个数。如果满足，则有可能构造出纠正一位或一位以上的线性码。i=1时，

即对于码组长度为n，信息码元k位，监督元r，2008.847第四十七页，共101页。下面我们通过例子来说明如何构造线性码。

思考：

设(n，k)中，k=4，要求能纠一位错，取

r=？2008.848第四十八页，共101页。

解：

(n，k)线性分组码，k=4，要求能纠一位错，现取r=3，可指示23-1=7种错误，码长n=4+3=7，表示为：C=[C6C5C4C3C2C1C0]其中C6C5C4C3为信息码元，C2C1C0为监督元由r=3，可有三个监督方程和校正子，设为s1s2s3恰好满足,故可纠一位错。2008.849第四十九页，共101页。设s1s2s3三位校正子与误码位置的对应关系为：000001010100011101110111误码位置无错

C0C1C2C3C4C5C6S1S2S3于是监督码元C2C1C0应由以下监督方程决定。C2=C6+C5+C4C1=C6+C5+C3C0=C6+C4+C3←监督元与信息元之间的线性方程组s1=C2+C6+C5+C4=0s2=C1+C6+C5+C3=0s3=C0+C6+C4+C3=02008.850第五十页，共101页。于是得到(7，4)线性分组码如下：

序码字号信息元

监督元

8100011191001100101010010111011001121100001131101010141110100151111111

序码字号信息元

监督元

00000000100010112001010130011110401001105010110160110011701110002008.851第五十一页，共101页。9.4.2监督矩阵将前面的监督方程改写成矩阵的形式，

C=[C6C5C4C3C2C1C0]可看成为编码矢量，于是有：记做：监督方程2008.852第五十二页，共101页。H--监督矩阵

不满足以上关系的为非典型矩阵，典型矩阵和非典型矩阵之间可以转换。2/H矩阵各行是线性无关的。行数---监督元的个数r列数---码组长度nIr为r阶单位阵1/当有H=[PIr]时称为典型矩阵，2008.853第五十三页，共101页。利用监督方程，我们可以对线性码的封闭性加以证明即H阵与编码码字的转置乘积为0，可用来作为判断接收码组是否错的依据。2008.854第五十四页，共101页。

设监督方程A1、A2均为线性码集合中的许用码组，因此有令两许用码组相加

A1+A2带入监督方程，有：因此，A1+A2亦为许用码组。2008.855第五十五页，共101页。9.4.3生成矩阵

当给出信息组后，如何方便迅速地求出整个编码码组，即如何生成编码矢量？C2=C6+C5+C4C1=C6+C5+C3C0=C6+C4+C3由监督元与信息元之间的关系：或者可以写成：2008.856第五十六页，共101页。令则有：给Q的左边，加一个k×k阶的单位矩阵，则构成：G=[IkQ]称为生成矩阵，且为典型形式。典型G矩阵行数----信息元的个数k列数----码组长度n每行本身就是一个许用码组于是有：矩阵和非典型矩阵之间可以转换。2008.857第五十七页，共101页。码字的前面k位为信息位，后面位为监督位一般情况，定义线性分组码的码字有如下形式：信息码元监督位信息位编码码字系统形式的线性分组码

编码

2008.858第五十八页，共101页。设信息组生成矩阵编码码组2008.859第五十九页，共101页。1）由G和信息组即可产生全部码字.通过典型生成矩阵产生的一定是系统码。2008.860第六十页，共101页。

（1）试确定(n,k)，并求H；

(2)写出监督元与信息元的关系式及该（n,k）码的全部码字；

(3)确定最小码距及检错能力。例：设已知2008.861第六十一页，共101页。解：求H，需确定P，应将已知的那个G转换成典型形式，求出Q，再利用求出G。H=[PIr]=2008.862第六十二页，共101页。

(2)

设C=于是有：监督元与信息元的关系式2008.863第六十三页，共101页。用三位二进制数的所有8种状态带入，可得到所有码字如右表。

序号码字

00000001001011201011030111014100101510111061100117111000(3)确定最小码距及检错能力所以有：d0=3可用于检两位错或纠一位错。利用性质知：最小码距d0等于非零码字的最小重量即d0=wmin2008.864第六十四页，共101页。9.4.4校正子S发送端经过编码后给出：接收端收到的码组为：两者的差记为：表示第i位无错表示第i位有错E称为错误图样。共有2n个错误图样。当E为全零错误图样时，R=C没有传输错误;2008.865第六十五页，共101页。可利用E检出或纠正错误；传输中的错误超出了可纠错的范围。但可能有两种情况：(n,k)可检测的错误图样数为2n-2k(n,k)可纠错的错误图样数为2n-k-1这时的错误图样称为不可检测的错误图样一般来讲，E=0，则R=C，可满足监督方程E≠0，则R≠C，不满足监督方程检错：当S=0时，认为E=0，当S0时，认为E0,校正子S的计算即校正子只与错误图样E有关。2008.866第六十六页，共101页。构造标准阵列的一般方法如下：1）用概率译码确定各伴随式S对应的差错图案E，共对；2）表格为列，行，先确定第一行和第一列，第一行为个码字，第一列为；3）各列对应的元素为第一列的和该列的之和；陪集首

译码时，计算伴随式S，查表获得错误图样E，最后恢复出发送码字C＝E＋R。2008.867第六十七页，共101页。例：已知监督矩阵：若接收为：R=[0000011]，试确定是否错误，若接收错误，试进行纠错。2008.868第六十八页，共101页。R=[0000011]，解：计算校正子2008.869第六十九页，共101页。000001010100011101110111误码位置无错

C0C1C2C3C4C5C6S1S2S3错误图样：

E=[0001000]对照校正子与误码位置，确定错误图样：2008.870第七十页，共101页。于是：R`=R+E=[0000011]+[0001000]由于，当只发生一位错码时，矩阵E中只有一个非零元素，与H的转置相乘的结果是选出其中的一列，即校正子与H矩阵的哪一列相同，则该列即为码元发生错误的位置。

=[0001011]2008.871第七十一页，共101页。(n，k)线性分组码编、译码过程小结：

编码过程：设线性分组码为(n，k)，信息码为：1)根据生成矩阵或监督矩阵，2)由C=MG0

求出所有码字，且为系统码。H0=[PIr]G0=[IkQ]求出典型生成矩阵；2008.872第七十二页，共101页。译码过程：1）由收到的码组R计算校正子S；2）由S判决是否有错并通过找出错误图样；3）按照R+E=C计算并还原C；4）将码组C还原成原信息组M。2008.873第七十三页，共101页。9.4.5汉明码汉明码是用于纠一位错误的线性分组码。特点：最小码距：

纠错能力：编码效率：2008.874第七十四页，共101页。例n=15的汉明码，其监督位为多少？编码效率为多少？2008.875第七十五页，共101页。解：于是其信息位有15-4=11位此汉明码为（15，11）码编码效率：其监督位有15-11=4位2008.876第七十六页，共101页。

汉明码是线性分组码，因此其监督矩阵同样有n列、r行，当监督位数给定后，即可构造出汉明码。例，r=3

H矩阵的n列由除了全零以外的个r位码构成，每码组出现一次且全部出现。（H不唯一）构造2008.877第七十七页，共101页。得到的汉明码如下所示：信息位监督位信息位监督位a6a5a4a300000001001000110100010101100111a2a1a0000011101110110101011000a6a5a4a310001001101010101100110111101111a2a1a01111000100010010101001112008.878第七十八页，共101页。（7，4）汉明码编码器a6a5a4a3信息组a0a1a2a3a4码字++a5a6+2008.879第七十九页，共101页。完备码

纠正单个错误的汉明码中，r位校正子码组与误码图样一一对应，最充分地利用了监督位所能提供的信息。

在一般情况下，对于能纠正t个错误的线性分组码(n，k)，应满足以下不等式：

因此，汉明码也是纠一位错的线性分组码中，编码效率最高的。2008.880第八十页，共101页。

上式取等号时，校正子与误码不超过t个的所有图样一一对应，监督码元得到最充分的利用，这种线性分组码即完备码。

除汉明码外，迄今为止，找到的唯一能纠正多个错误的完备码为(23，12)戈雷码。t=3汉明码就是一种完备码。

该式亦称为汉明界，它给出已知k和t时，所需要的监督位数。2008.881第八十一页，共101页。

但此时构成的则非汉明码。

通常选择码重最小的矢量优先。例试构造一个k=5的可纠一个错的线性分组码1/计算最短的码长；2/构造H；3/求生成矩阵G；4/求信息组为(10101)的编码码字C。2008.882第八十二页，共101页。解：1/因为t等于1,且要求k=5,可用试探法确定n设：n-k=3，则不满足纠错要求；

设：n-k=4，则满足纠错要求；于是取n=9，此时r=n-k=4，(9,5)线性分组码2008.883第八十三页，共101页。2/r=4，四位码共有种状态，除全零外都可用于构造H矩阵。

为了构造典型矩阵，选1000，0100，0010，0001四码组，然后从其余的11个码组中，再选出5个，通常按照码重从小到大选择。PIr实际只需9个2008.884第八十四页，共101页。4/M=[1010

1]C=MG=[101010110]Q3/求生成矩阵已知

Ik于是有：2008.885第八十五页，共101页。9.5循环码9.5.1循环码原理

循环码是线性分组码的一个重要子类，也是目前研究最成熟的一类码。它不仅有封闭性，且还有循环性。(n，k)码组则将所有码元向左循环一位，得到的：也是许用码组是许用码组。即2008.886第八十六页，共101页。

若线性分组码的任一码组循环移位所得码组仍在该码组集中，则此码为循环码。（7，3）循环码序号码字

0000000010011101201001113011101041001110510100116110100171110100循环码的循环圈数≥2W=00W=42156734

同一循环圈内，码字的重量相同2008.887第八十七页，共101页。序号码字

0000000100100120100103011011410010051