数字通信原理-纠错编码课件

《数字通信原理-纠错编码课件》由会员分享，可在线阅读，更多相关《数字通信原理-纠错编码课件（87页珍藏版）》请在装配图网上搜索。

1、第 10 章 差错控制编码 差错控制编码差错控制编码 10.1 概述概述 10.2 常用的几种简单分组码常用的几种简单分组码 10.3 线性分组码线性分组码 10.4 循环码循环码 10.5 卷积码卷积码第 10 章 差错控制编码 本章内容在数字通信系统中所处的位置：本章内容在数字通信系统中所处的位置：第 10 章 差错控制编码 差错控制编码，又称信道编码、可靠性编差错控制编码，又称信道编码、可靠性编码、抗干扰编码或纠错码，它是提高数字信号码、抗干扰编码或纠错码，它是提高数字信号传输传输可靠性可靠性的有效方法之一。它产生于的有效方法之一。它产生于2020世纪世纪5050年代初，发展到年代初，发

2、展到7070年代趋向成熟。本章将主年代趋向成熟。本章将主要分析要分析信道编码信道编码的基本原理、介绍常用的检错的基本原理、介绍常用的检错码、线性分组码及卷积码的构造原理及其应用。码、线性分组码及卷积码的构造原理及其应用。10.1 概概 述述 第 10 章 差错控制编码 一、信源编码和信道编码一、信源编码和信道编码 在数字通信中，根据不同的目的，编码可分在数字通信中，根据不同的目的，编码可分为为信源编码和信道编码信源编码和信道编码。信源编码信源编码是为了提高数字通信的有效性以及是为了提高数字通信的有效性以及使模拟信号数字化而采取的编码技术。使模拟信号数字化而采取的编码技术。信道编码信道编码是为了

3、降低误码率，提高数字通信是为了降低误码率，提高数字通信的可靠性而采取的编码。的可靠性而采取的编码。10.1 概概 述述 第 10 章 差错控制编码 数字信号在传输过程中受到干扰的影响，使信号波形变坏，发生误码，可以采用一些方法解决。差错出现原因v 外界噪声v 传输中码间串扰解决方法v 合理地设计基带信号，选择调制、解调方式，采用均衡技术，提高发送功率等因素，使误比特率降低。v 差错控制编码。第 10 章 差错控制编码 n 在信息码上附加一定位数的监督码元，使其与信息位按某在信息码上附加一定位数的监督码元，使其与信息位按某种规则相互关联；种规则相互关联；n 若数据在传输过程中发生差错，关联关系被

4、破坏，从而可若数据在传输过程中发生差错，关联关系被破坏，从而可 检出和检出和/或纠正错误或纠正错误。第 10 章 差错控制编码 n ：信息码与监督码之间的关系为线性关系；信息码与监督码之间的关系为线性关系；：信息码与监督码之间的关系为非线性关系。：信息码与监督码之间的关系为非线性关系。n ：监督码只与本组信息码有系；：监督码只与本组信息码有系；：监督码与本组和前面码组中的信息码有关。：监督码与本组和前面码组中的信息码有关。n ：编码后码组中信息码保持原图样顺序不变；编码后码组中信息码保持原图样顺序不变；：编码后码组中原信息码原图样发生变化。：编码后码组中原信息码原图样发生变化。第 10 章 差

5、错控制编码 n ：误码的位置随机（误码间无关联），随机误码：误码的位置随机（误码间无关联），随机误码 主要由白噪声引起。主要由白噪声引起。n ：误码成串出现，主要由强脉冲及雷电等突发的：误码成串出现，主要由强脉冲及雷电等突发的 强干扰引起。强干扰引起。n ：以上两种误码及产生原因的组合。：以上两种误码及产生原因的组合。第 10 章 差错控制编码 10.1.2 差错控制类型差错控制类型（ARQ ARQ Automatic Repeat Request）:在发送端采用在发送端采用具有具有检错检错功能的编码，接收端发现出错后自动请求重发功能的编码，接收端发现出错后自动请求重发.有以下三种方式：有以下

6、三种方式：第 10 章 差错控制编码 特点：特点：设备较简单；传输序列中冗余量较小；设备较简单；传输序列中冗余量较小；需要有反向信道支持；出错后重传造成延时较大。需要有反向信道支持；出错后重传造成延时较大。第 10 章 差错控制编码 2、前向纠错方式、前向纠错方式 （FECForward ErrorCorrection)发端发送能够纠正错误纠正错误的码，收端收到信码后自动地纠正传输中的错误特点：特点：无需反馈信道，无需重传，延时小；需反馈信道，无需重传，延时小；传输序列中冗余量较大。传输序列中冗余量较大。运用在移动通信系统、军事系统通信中。运用在移动通信系统、军事系统通信中。3、混合纠错方式、

7、混合纠错方式 HEC(Hybrid ErrorCorrection)混合纠错方式记作是FEC和ARQ方式的结合。出错较少时出错较少时FEC起作用；出错较多时起作用；出错较多时ARQ起作用起作用第 10 章 差错控制编码 图 10-1 差错控制方式 发端纠错码收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号总结：总结：第 10 章 差错控制编码 信道编码的核心问题信道编码的核心问题v 发现错误发现错误v 纠正错误纠正错误第 10 章 差错控制编码 v 码长：码字中码元的个数，通常用n表示。v码重：码字中非零码元的个数定义为该码字的重量，简称码重。如

8、“10011”码字的码重为3。v 码距：两个等长码字之间对应码元不同的数目，通常用d表示。两个码字对应位模2相加得到的新码组的重量就是这两个码字之间的距离。niii 1dAB （1）几个概念）几个概念第 10 章 差错控制编码 v 编码效率：信息码元数与码长之比，通常用 表示，其中k为信息码元的数目，n为码长。v最小码距：在一个码字集合中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为dmin或d0纠错码的抗干扰能力完全取决于许用码字之间的距纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越离，码的最小距离越大，说明码字间的最小差别越

9、大，抗干扰能力就越强。大，抗干扰能力就越强。nk第 10 章 差错控制编码 举例说明：假如要传送举例说明：假如要传送A、B两个消息两个消息编码一：消息A-“0”；消息B-“1”最小码距1若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。第 10 章 差错控制编码 编码二：消息A-“00”；消息B-“11”最小码距2若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力第 10 章 差错控制编码 编码三：消息

10、A-“000”；消息B-“111”最小码距3传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。例如收到110，认为是111。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。第 10 章 差错控制编码 一个码能检测e个错码，则要求其最小码dmine+1一个码能纠正t个错码，则要求其最小dmin2t+1一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1 (et)（2）最小码距与检错和纠错能力的关系）最小码距与检错和纠错能力的关系第 1

11、0 章 差错控制编码 v 奇偶监督码v 二维奇偶监督码（略，见附录）v 恒比码10.2 常用的几种简单分组码常用的几种简单分组码第 10 章 差错控制编码 10.2.1 奇偶监督码奇偶监督码 1 2 3kk 1123kk 1k 1123k123kk 1k 1123kkaa a.ar1aaaa.aa0aaaa.aaaa.aa1aaaa.a1 对对 位位码码元元校校验验位位偶偶校校验验 奇奇校校验验 奇偶监督码：在信息码元后附加一位监督位，使得码组中奇偶监督码“1”的个数为偶数或奇数。第 10 章 差错控制编码 序号 码长为4的奇奇监督码序号 码长为4的偶偶监督码 信息码元 监督码元 信息码元 监

12、督码元 0000100000 1001010011 2010020101 3011130110 4100041001 5101151010 6110161100 7111071111表：码长为4的奇、偶监督码第 10 章 差错控制编码 v只能检测出单个或奇数个错误，不能检测偶数个错误v不能纠错。v 应用：以随机错误为主的计算机通信系统，难于对付突发错误v 编码效率=k/n=k/(k+1)，是一种高效率码。10.2.2二维奇偶监督码见附录二维奇偶监督码见附录 第 10 章 差错控制编码 表表 10-1 3 2 恒比码恒比码（是一种五中取三码）（是一种五中取三码）10.2.3 恒比码恒比码 码字中

13、码字中1 1的数目与的数目与0 0的数目保持恒定比例的数目保持恒定比例的码称为恒比码。又的码称为恒比码。又称等重码，定称等重码，定1 1码。码。这种码在检测时，这种码在检测时，通过计算接收码元中通过计算接收码元中1 1的数目是否正确，就的数目是否正确，就知道有无错误。知道有无错误。第 10 章 差错控制编码 线性分组码：先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码。若附加的监督码和信息码由一些线性代数方程相则称为线性分组码。用符号(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。1、基本概念、基本概念10.3 线性分组码（重点）线性分组码（重

14、点）第 10 章 差错控制编码 现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是监督元，可用下列线性方程组来描述该分组码，产生监督元。346035614562aaaaaaaaaaaa第 10 章 差错控制编码 表表 10-2(7,4)码的码字表码的码字表 第 10 章 差错控制编码 2、线性分组码的性质、线性分组码的性质v任意两个许用码组之和（逐位模2和）仍为一许用码组，即具有封闭性。v最小码距=非零码的最小码重（1的个数）。第 10 章 差错控制编码 10.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩

15、阵G 第 10 章 差错控制编码 其中,P为rk阶矩阵，Ir为rr阶单位矩阵。可以写成H=P Ir形式的矩阵称为典型监督矩阵。HAT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。并简记为 第 10 章 差错控制编码 v rn阶矩阵v 监督矩阵H确定了编码时监督码元与信息码元的关系v 把具有PIr形式的H矩阵称为典型形式的监督矩阵，其中P为r k阶矩阵,Ir为r r阶单位方阵v H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关监督矩阵H特点第 10 章 差错控制编码 若把监督方程补充为下列方程 第 10 章 差错控制编码 可改写为矩阵形式

16、第 10 章 差错控制编码 1101000101010001100101110001GQIGkTPQ110101011111第 10 章 差错控制编码 vk n阶矩阵v把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中，Ik为kk阶单位方阵，Q为k r阶矩阵v由典型生成矩阵产生的分组码一定是系统码vG矩阵的各行应线性无关，每行均为许用码组生成矩阵G特点第 10 章 差错控制编码 已知（6，3）汉明码(能纠正单个错误的线性分组码)的生成矩阵如下，(1)列出所有许用码组;(2)最小码距d0;(3)检错纠错能力(4)编码效率100101G010011001110 第 10 章 差错控制编码 543

17、AaaaG（1）信息码信息码编码码字编码码字码重码重0 0 00 0 0 0 0 000 0 10 0 1 1 1 030 1 00 1 0 0 1 130 1 10 1 11 0 141 0 01 0 0 1 0 131 0 11 0 1 0 1 141 1 01 1 0 1 1 041 1 1 1 1 1 0 0 03第 10 章 差错控制编码（3）（4）000e=d-1=2d-1t=12et1det21 该该码码可可以以检检2 2位位错错该该码码可可以以纠纠1 1位位错错该该码码不不能能同同时时检检 位位错错与与纠纠 位位错错。k350%n6 （2）0d3 第 10 章 差错控制编码 1

18、101000101010001100101110001设（设（7,4）线性码的生成矩阵）线性码的生成矩阵G为：为：当信息位为当信息位为0001时，时，（1）试求其后的监督位。）试求其后的监督位。（2）监督矩阵）监督矩阵H第 10 章 差错控制编码 6543AaaaaG 解：解：（1）10001110100110A0 0 0 10 0 0 1 0 1 100101010001011第 10 章 差错控制编码（2）监督矩阵）监督矩阵H根据生成矩阵和监督矩阵的关系：根据生成矩阵和监督矩阵的关系：G=IkQ，H=PIr其中其中P=QT，可得监督矩阵可得监督矩阵H为：为：1001101010101100

19、10111第 10 章 差错控制编码 v错误矩阵/错误图样E：设发送码组为A，接收码组为B，则错误矩阵 n 1n 210n 1n 210Aaa.a aBbb.b b n 1n 210iiiiiiiEBAee.e e1baeba0ba 该该位位有有错错该该位位无无错错10.3.3 伴随式伴随式(校正子校正子)S 第 10 章 差错控制编码 v接收端计算校正子S，即S=BHT=(A+E)HT=AHT+EHT=0+EHT=EHT 校正子只与E有关，即错误图样与校正子之间有确定的关系.确定错误图样与校正子的关系表。可从表中找得错码位置，加以纠正。第 10 章 差错控制编码 表表 10-3(7,4)码码

20、S与与E的对应关系的对应关系 第 10 章 差错控制编码 v以（7，4）汉明码为例设发送码组A=（0001011）接收码组 B=（0000011）则收端译码过程如下：计算校正子 T111110101SBH0 0 0 0 0 1 1011011100010001 查表得b3为错误位置，即可纠正（0001011）第 10 章 差错控制编码 10.4 循循 环环 码码 循环码是一种重要的线性分组码。这种码的编码和解码设备都不太复杂，且有较强的检（纠）错能力。共n位，通常前k位为信息位，后r位为监督位。10.4.1 10.4.1 循环码的编码原理循环码的编码原理第 10 章 差错控制编码 循环码的特点

21、：v 封闭性；v 循环性；即码中任一码组循环一位(将最右端的码元移到左端或反之）以后，仍为该码中的一个码组。第 10 章 差错控制编码 若(an-1,an-2,a1,a0)是一(n,k)循环码的码组，则(an-2,an-3,a1,a0,an-1)(an-3,an-4,a0,an-1,an-2)(a0,an-1,an-2,an-3,a2,a1)也都是该循环码的码组。第 10 章 差错控制编码 表一种（表一种（7 7，3 3）循环码的全部码字）循环码的全部码字序序号号码字码字序序号号码字码字信息位信息位a6 a5 a4a6 a5 a4监督位监督位a3 a2 a1 a0a3 a2 a1 a0信息位信

22、息位a6 a5 a4a6 a5 a4监督位监督位a3 a2 a1 a0a3 a2 a1 a01 1000000000000005 5100100101110112 2001001011101116 6101101110011003 3010010111011107 7110110010101014 4011011100110018 811111100100010第 10 章 差错控制编码 把码长为n的码组中的各码元当作n-1次多项式的系数若码组A=（an-1，an-2，a1，a0)，则其相应的码多项式为(以降幂顺序排列以降幂顺序排列)：A(x)=an-1xn-1+an-1xn-2+a1x+a0

23、对于（7，3）循环码的任意码组可表示为：A(x)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0如码组（1100101）对应的码多项式可表示为A7(x)=1x6+1 x5+0 x4+0 x3+1 x2+0 x+1 =x6+x5+x2+11、码多项式、码多项式A(x)第 10 章 差错控制编码 表表 10-4(7,3)循环码循环码 写出各个码写出各个码字多项式？字多项式？最低次多项最低次多项式的次数是式的次数是多少？多少？第 10 章 差错控制编码 10.4.1 生成多项式及生成矩阵生成多项式及生成矩阵 如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多

24、项式。在(n,k)循环码中任意码多项式A(x)都是最低次(r次次)码多项式的倍式。如表 10-4 的(7,3)循环码中，1)()(2341xxxxAxg第 10 章 差错控制编码)()()()()()1()()(0)(27320 xgxxAxgxxAxgxxAxgxA其它码多项式都是g(x)的倍式，即 第 10 章 差错控制编码 可以证明生成多项式可以证明生成多项式g(x)具有以下特性：具有以下特性：（1）g(x)是一个常数项为是一个常数项为1的的 次次多项式；多项式；（2）g(x)是是 的一个因式；的一个因式；（3）该循环码中其它码多项式都是该循环码中其它码多项式都是g(x)的倍式。的倍式。

25、knr1nx4243212(7 3)()()1;()1g xg xxxxgxxxx对于，循环码，符合码生成多项式条件的有两个可以构造出两种循环码组；它们的d0、检错、纠错能力相同第 10 章 差错控制编码 g(x)，xk-1g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x)注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵。)()()()()(21xgxxgxgxxgxXGkk循环码的循环码的生成矩阵生成矩阵常用多项式的形式来表示常用多项式的形式来表示 第 10 章 差错控制编码 例如(7,3)循环码，n=7,k=3,r=4,其生成多项式及生成矩阵分别

26、为 第 10 章 差错控制编码 1111111111010011010011100010101100010100111001110100010101110100110001010110001001110011101001011000010110000000例：已知（例：已知（7，4）循环码的全部码组为：）循环码的全部码组为：试写出该循环码的生成多项式试写出该循环码的生成多项式g(x)和生成和生成矩阵矩阵G，并将，并将G化成典型矩阵。化成典型矩阵。第 10 章 差错控制编码 解：解：n=7，k=4，n-k=3上述码组中的上述码组中的(n-k)=3次码多项式为第次码多项式为第2组，它所组，它所对应

27、的码多项式对应的码多项式g(x)即为生成多项式：即为生成多项式：g(x)=x3+x+1。生成矩阵为：生成矩阵为：364325321423x g(x)xxxx g(x)xxxG(x)x g(x)xxxg(x)xx110110001000101010110001001110010110001011000010110001011 第 10 章 差错控制编码 10.4.2 监督多项式及监督矩阵监督多项式及监督矩阵1)(1)(111xhxhxxgxxhkkkn其中g(x)是常数项为 1 的r次多项式，是生成多项式；h(x)是常数项为 1 的k次多项式，称为监督多项式。同理，可得监督矩阵H)(*)(*)(

28、*)(1xhxxhxhxxHkn第 10 章 差错控制编码 是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+x3+x2+1，则 其中 1)(*12211xhxhxhxxhkkkk1)(*1)(1)(3237xxxhxxxgxxh111()1kkkh xxhxh x第 10 章 差错控制编码 1)(324235346xxxxxxxxxxxxH1101000011010000110100001101H第 10 章 差错控制编码 10.4.3 编码方法和电路编码方法和电路 思路思路：在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次,常数

29、项为1的多项式作为g(x)。设编码前的信息多项式m(x)为 12321)(kkxaxaxaaxm循环码的码多项式可表示为)()()(xRxmxxAr用xr乘m(x)，相当于把信息码后附加上r个“0”第 10 章 差错控制编码 用g(x)除xr m(x)，得到商式Q(x)和余式为R(x)编出码组为：A(x)=xr m(x)+R(x)xgxRxQxgxmxr第 10 章 差错控制编码 11)1(1)()(24222456xxxxxxxxxxxxgxmxkn即余式即余式r(x)=x2+1于是，对应码组于是，对应码组A(x)=xn-k m(x)+r(x）=x6+x5+x2+1 编码为编码为110010

30、1例题例题 设（设（7，3）循环码的生成多项式为）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为，待编码信息位为110，求对应循，求对应循环码码组。环码码组。解：解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5第 10 章 差错控制编码 编码电路：编码电路：由除法电路除法电路和适当的控制电路控制电路构成。除法电路：由移位寄存器和加法器构成。第 10 章 差错控制编码 图 10-3(7,3)循环码编码电路 编码电路：由除法电路除法电路和适当的控制电路控制电路(用用一双刀双掷开关K代替)构成。1、g(x)的次数为移位寄存器的级数。2、g(x)的非零系数对应

31、于移位寄存器的反馈抽头。abcd1122输出输入mef1)(24xxxxg)(xg1x2x4x信码第 10 章 差错控制编码 1、图中有4级移存器，分别用a,b,c,d表示。2、当信息位输入时，开关K倒向下，输入信码一方面送入除法器进行运算，另一方面直接输出，当k个移位脉冲后，移位寄存器中的数据即为除法余数，即监督码元。3、在信息位全部进入除法器后，开关转向上，这时输出端接到移存器，将移存器存储的除法余项依次取出，同时切断反馈线。4、用这种方法编出的码组，前面是原来的k个信息位，后面是n-k个监督位。因此它是系统分组码。第 10 章 差错控制编码 表表 10-5(7,3)循环码的编码过程循环码

32、的编码过程 开关接2开关接1a b c d 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 010110.4.4 译码方法和电路译码方法和电路(略略)第 10 章 差错控制编码 10.6 卷卷 积积 码码 10.6.1 基本概念基本概念 1、卷积码：用(n,k,m)表示，每个(n,k)码段(字码)中的n个码元不仅与该码段内的k个信息元有关，而且与前面m个信息元有关（有记忆性）。2、编码器：由k个输入，n个输出，m个移位寄存器和一些辅助电路构成的有记忆系统。第 10 章 差错控制编码 例：例：卷积码卷积码(2,1,2)编码器编码器 m1m2数据输入码字输出S1S2S3C1C2 起

33、始状态，各级移位寄存器清零，即S2S3为00。S1等于当前输入数据，移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定：第 10 章 差错控制编码 3123211SSCSSSC表(2,1,2)编码器的工作过程 第 10 章 差错控制编码 编码约束度：每编码约束度：每1位数据，将影响位数据，将影响(m+1)个输出字个输出字码，称码，称(m+1)为编码约束度。例（为编码约束度。例（2，1，2）编码）编码约束度为约束度为3。约束长度：每个子码有约束长度：每个子码有n个码元，在卷积码中有个码元，在卷积码中有约束关系的最大码元长度为约束关系的最大码元长度为(m+1).n，称为约束，称为约束长度。

34、例（长度。例（2，1，2）约束长度为）约束长度为6。第 10 章 差错控制编码 10.6.2 卷积码的描述（用图解法）卷积码的描述（用图解法）1.树图树图 图图 7-6(2,1,2)码的树图码的树图 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb0110cdc0011abd1001cd1101c0010db1001a1100数码起点状态a00b01c10d11上半部下半部数码1101第 10 章 差错控制编码 2状态图状态图用状态图来描述。下图就是该（用状态图来描述。下图就是该（2，1，2）卷积码编码器的）卷积码编码器的状态图。状态图。在

35、图中有在图中有4个节点个节点a、b、c、d，同样分别表示，同样分别表示S3S2的的4种可种可能状态。每个节点有两条线离开该节点，实线表示输入数据能状态。每个节点有两条线离开该节点，实线表示输入数据为为0，虚线表示输入数据为，虚线表示输入数据为1，线旁的数字即为输出码字。，线旁的数字即为输出码字。图（图（2 2，1 1，2 2）卷积码的状态图）卷积码的状态图第 10 章 差错控制编码 3.格图格图 图图(2,1,2)码码的格图的格图 a00起点aaaaaabbbccccbbcbddddd0000000000000000001001010101010101101010101111111111111

36、0101010010110.5.3 卷积码的译码（概率译码，略）卷积码的译码（概率译码，略）第 10 章 差错控制编码 3 3格图格图 格图也称网络或篱笆图，它由状态图在时间上展开格图也称网络或篱笆图，它由状态图在时间上展开而得到，如图所示。图中画出所有可能数据输入时，状而得到，如图所示。图中画出所有可能数据输入时，状态转移的全部可能轨迹，实线表示数据为态转移的全部可能轨迹，实线表示数据为0 0，虚线表示数，虚线表示数据为据为1 1，线旁数字为输出码字，节点表示状态。，线旁数字为输出码字，节点表示状态。以上的以上的3 3种卷积码的描述方法，不但有助于求解输出码种卷积码的描述方法，不但有助于求解

37、输出码字，了解编码工作过程，而且对研究解码方法也很有用。字，了解编码工作过程，而且对研究解码方法也很有用。图图 （2 2，1 1，2 2）卷积码的格图）卷积码的格图第 10 章 差错控制编码 三、卷积码的译码（略）三、卷积码的译码（略）卷积码的译码可分为卷积码的译码可分为代数代数译码和译码和概率概率译码两大类。译码两大类。代数译码是利用生成矩阵和监督矩阵来代数译码是利用生成矩阵和监督矩阵来译码，最主要的方法是大数逻辑译码。译码，最主要的方法是大数逻辑译码。概率译码比较实用的有两种：维特比译概率译码比较实用的有两种：维特比译码和序列译码。目前，概率译码已成为卷码和序列译码。目前，概率译码已成为卷

38、积码最主要的译码方法。积码最主要的译码方法。第 10 章 差错控制编码 本章小结：1、信源编码、信道编码的概念和区别2、线性分组码、循环码的相关概念、编码、译码作业：10-12、10-13、10-20、10-24、10-25第 10 章 差错控制编码 v 将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶监督码，但发送时按列的顺序传输v 接收端将码元排成发送时的方阵形式，再按行进行奇偶校验v 能够发现某行上所有奇数个错误以及突发长度不大于方阵行数的突发错误v 编码效率附录：附录：2、水平奇偶监督码、水平奇偶监督码pqpqp(q1)信信息息码码元元共共 行行 列列第 10 章 差错控制编码

39、 信 息 码 元监督码元1110000000111010011010100001110110001000010011001110111水平奇偶监督码水平奇偶监督码111011100110000.0110110101第一个码元第二个码元第三个码元第十个码元监督码元第 10 章 差错控制编码 水平奇偶监督码接收端出现突发误码示例水平奇偶监督码接收端出现突发误码示例信 息 码 元监督码元11100000001110100110101000011101100010000100110011101111101结论：结论：能够发现突发长度不大于方阵能够发现突发长度不大于方阵行数的突发错误行数的突发错误第 1

40、0 章 差错控制编码 v 又称为方阵码、行列监督码、二维奇偶监督码。v 将水平奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输v 接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验3、水平垂直奇偶监督码、水平垂直奇偶监督码第 10 章 差错控制编码 v 能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误；v 有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好构成矩形时，则检测不出v 可纠正一些错误mn(m1)(n1)编编码码效效率率信信息息码码元元共共m m行行n n列列v 第 10

41、 章 差错控制编码 信 息 码 元监督码元1110000000111010011010100001110110001000010011001110111监督码元01101010011表表 水平垂直奇偶监督码水平垂直奇偶监督码发送顺序第 10 章 差错控制编码 水平垂直奇偶监督码接收端纠错示例水平垂直奇偶监督码接收端纠错示例信 息 码 元监督码元1110000000111010011010100001110110001000010011001110111监督码元01101010011011例如：当码组中仅在一行有奇数个错误时，能例如：当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。够

42、确定错误位置，并纠正它。第 10 章 差错控制编码 水平垂直奇偶监督码接收端检错示例水平垂直奇偶监督码接收端检错示例信 息 码 元监督码元1110000000111010011010100001110110001000010011001110111监督码元01101010011011构成矩形的偶数个误码检测不出。构成矩形的偶数个误码检测不出。00第 10 章 差错控制编码 水平垂直奇偶监督码接收端检错示例水平垂直奇偶监督码接收端检错示例信 息 码 元监督码元1110000000111010011010100001110110001000010011001110111监督码元0110101001101有可能检测出偶数个误码。有可能检测出偶数个误码。001