《通信原理第十二章-差错控制xin课件.ppt》由会员分享，可在线阅读，更多相关《通信原理第十二章-差错控制xin课件.ppt（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第12章章差错控制编码差错控制编码第12章 差错控制编码内容简介：12.1 引言12.2 纠错编码的原理12.3 常用的简单编码12.4 线性分组码 12.5 循环码第12章 差错控制编码主要内容：1.基本概念：码重,码距,检错能力,纠错能力2.常用编码3.线性分组码 4.循环码第12章 差错控制编码回放信信道道解解调调信信源源编编码码加加密密调调制制解解密密译译码码信信宿宿噪噪声声同步系统同步系统信源编码信源编码 信道编码信道编码 误差控制误差控制ASKFSKPSKDPSK数字通信的组成数字通信的组成A/DA/D数据压缩数据压缩第12章 差错控制编码 在通信过程中，会受到各种外来干扰，如脉
2、冲干扰，随机噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起数据信息序列产生错误，称之为差错。实际信道中，上述两种错误常同时存在。随机性错误：前后出错位之间无一定关系，随机、离散出现。突发性错误：差错成串出现，且有一定相关性。差错的两大类型：差错的两大类型：合理的设计基带信号合理的设计基带信号时域时域/频域均衡频域均衡 都能有效的提高传输可靠性。都能有效的提高传输可靠性。发射功率的提高发射功率的提高第12章 差错控制编码12.1 12.1 引言引言数字通信中的编码分为：数字通信中的编码分为：信道编码：信道编码：信源编码：信源编码：为提高信号传输的有效性而采取的措施。
3、为提高信号传输的有效性而采取的措施。为提高信号传输的可靠性而采取为提高信号传输的可靠性而采取 的措施。亦称差错控制编码。的措施。亦称差错控制编码。在发送端利用信道编码器在数据信息中增加一些在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性不强的原始数字监督信息，使不带规律性或规律性不强的原始数字信号变为带规律性或加强了规律性的数字信号，信道信号变为带规律性或加强了规律性的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进译码器则利用这些规律性来鉴别是否发生错误，或进行错误纠正。行错误纠正。差错控制差错控制第12章 差错控制编码 1、差错控制方法（1）前向纠错法）
4、前向纠错法FEC 所发码具有纠错能力，收端接收后自动纠错，无需反向所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备复杂，信道。实时性好，但译码设备复杂，传输效率传输效率。信源FEC编码信道FEC译码信宿（2）信息反馈法）信息反馈法IF信息信号信息信号信息信号信息信号发端发端收端收端 方法和设备简单，无需纠检错编译系统。但需要双向方法和设备简单，无需纠检错编译系统。但需要双向信道，信道，传输效率传输效率、实时性差、实时性差。第12章 差错控制编码 (3)检错重发法ARQ 所发码具有检错能力，收端接收后判决是否出错，通过所发码具有检错能力，收端接收后判决是否出错，通过反向
5、信道发送判决结果，发端据此决定是否重发。反向信道发送判决结果，发端据此决定是否重发。译码设备简单，对突发错误有效，要求有反馈信道。译码设备简单，对突发错误有效，要求有反馈信道。信源信源编码器编码器正向信道正向信道译码器译码器信宿信宿缓存器缓存器重发控制器重发控制器反向信道反向信道重发判决器重发判决器工作过程：发送工作过程：发送检测检测回复回复重发或发送新的数据重发或发送新的数据第12章 差错控制编码停止等待方式停止等待方式 3221221发送端发送端接收端接收端ARQ的三种实现方式：特点：半双工工作，简单，要求的缓存量小，但等待时间较长，特点：半双工工作，简单，要求的缓存量小，但等待时间较长，
6、传输效率传输效率 第12章 差错控制编码 连续重发方式 6543254321065432543210退退N N步方式：从出错帧开始重发步方式：从出错帧开始重发 例例N=4N=4 优缺点：传输效率优缺点：传输效率，但重发的，但重发的N N帧中，大部分为正确，所以帧中，大部分为正确，所以 仍有浪费。发端缓存必须可存仍有浪费。发端缓存必须可存N N帧。帧。第12章 差错控制编码2987654321029876543210 只对出错信息重发，因此传输效率大大提高只对出错信息重发，因此传输效率大大提高。但收发。但收发两端都要有足够的存储空间。两端都要有足够的存储空间。选择重发方式 第12章 差错控制编码
7、反馈信道反馈信道ARQFEC编码器编码器正向信道正向信道FEC译码器译码器ARQ 编码既有纠错能力也有检错能力，收端收到信息码组后编码既有纠错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过在收端进行检测。在纠错范围内：纠正；超出范围：通过ARQARQ方式进行重发。方式进行重发。(4)混合方式 第12章 差错控制编码（1）根据各码组信息码和监督码的关系分：根据各码组信息码和监督码的关系分：线性码，非线性码线性码，非线性码根据监督码元是否仅与本组信息元有关根据监督码元是否仅与本组信息元有关 分组码，卷积码分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：根
8、据纠错码组中信息元是否隐蔽分：系统码，非系统码系统码，非系统码（3）根据码的用途分：根据码的用途分：检错码检错码 ，纠错码，纠错码（4）根据根据码元的取值码元的取值：二进制码，多进制码二进制码，多进制码（5）根据根据构造编码的数学方法构造编码的数学方法：代数码，几何码，算术码代数码，几何码，算术码（6）2、纠错码的分类第12章 差错控制编码12.2 纠错编码的基本原理1、几个术语几个术语本课程主要讨论纠随机错误的二进制线性分组码。本课程主要讨论纠随机错误的二进制线性分组码。码长：码组中码元的数目，常用码长：码组中码元的数目，常用n 表示；表示；码距：两等长码字码距：两等长码字C1、C2对应位上
9、取值不同的数目，又称对应位上取值不同的数目，又称 为汉明为汉明(Hamming)距离，记为距离，记为d(c1,c2)。码重：码组中非零码元的数目，记为码重：码组中非零码元的数目，记为W；最小码距：在分组码最小码距：在分组码(n,k)中，任意两个码字之间汉明距离的最中，任意两个码字之间汉明距离的最 小值，记为小值，记为dmin。码距的大小关系到编码的纠检错能力。码距的大小关系到编码的纠检错能力。例：例：10011 w=3 01101 d=4第12章 差错控制编码n=3时，码距的几何说明：时，码距的几何说明：（a2 a1 a0）a2a1a0（110）（011）d=2110011（111）（000）
10、d=3000111第12章 差错控制编码A A、B B两消息，可用一位二进制数表示，两消息，可用一位二进制数表示，A=1A=1、B=0B=0出错时无法判定出错时无法判定。例例 增加一个监督位，取增加一个监督位，取11A11A、00B,00B,若收到若收到0101或或1010时，时，可知发生了错误，但不能纠正错误。可知发生了错误，但不能纠正错误。再增加一个监督位，取再增加一个监督位，取111A111A、000B,000B,如一位错：如一位错：B001 A110B001 A110；若两位若两位错错011,110011,110则则只能只能发现发现不能不能纠错纠错 因此因此这种（这种（3.13.1）码
11、，能纠正一个错，发现两个错。）码，能纠正一个错，发现两个错。但是但是 (3.1)(3.1)码中，数据位仅为码中，数据位仅为1 1位，监督位为两位，位，监督位为两位，传输效率传输效率 可以看出：差错控制是以牺牲传输效率为代价可以看出：差错控制是以牺牲传输效率为代价而换取了传输质量的提高的。纠检错能力与加入的而换取了传输质量的提高的。纠检错能力与加入的监督元数目成正比。监督元数目成正比。2、纠错或检错的原理第12章 差错控制编码分组码的三个参数分组码的三个参数码长码长 n，信息位信息位 k，最小距离最小距离 d0，用符号用符号(n,k,d0)表示表示k个信息元个信息元an-1 an-2 ar ar
12、-1 a0 r个监督元个监督元码长：码长：n=k+rR=k/n为为编码效率编码效率，d0一定一定(纠错能力一定纠错能力一定)时，时，k/n大，效率高。大，效率高。对被传输的信息序列分组，每组为对被传输的信息序列分组，每组为k个信息元，对每组个信息元，对每组按某种关系附加按某种关系附加(n-k)个监督码元个监督码元(校验校验)，形成为，形成为n位的码字。位的码字。这种方法构成的码组称为这种方法构成的码组称为分组码分组码。第12章 差错控制编码分组码的表示：符号（分组码的表示：符号（n，k）n 码组的总位数码组的总位数k 码组中信息码元的数目码组中信息码元的数目r =n-k 监督码元的数目监督码元
13、的数目编码效率编码效率R R越大，信息位比重大，有效性越高。越大，信息位比重大，有效性越高。第12章 差错控制编码 3、分组码的纠(检)错能力与最小码距d0的关系 任一任一（n n，k k）分组码，若要在码字内能：分组码，若要在码字内能：1/1/检测检测e e个随机错误，则要求：个随机错误，则要求：d d0 e+1e+1 2/2/纠正纠正t t个随机错误，则要求：个随机错误，则要求：d d0 0 2 2t+1t+1 3/3/纠正纠正t t个同时检测个同时检测e e(et)(et)个随机错误，则个随机错误，则 要求：要求：d d0 0 e e+t+1+t+1 第12章 差错控制编码纠（检）错能力
14、的几何解释 A1 d 0eA2（a）A1 A2 d 0et（c）A1 d 0tA2（b）A2t第12章 差错控制编码e检错能力检错能力 t纠错能力纠错能力（1）时能检出时能检出e e个或个或e e个以下错码。个以下错码。（2）（3）时能纠正时能纠正t t个或个或t t个以下错码。个以下错码。时能检出时能检出t t个或个或e e个以下错码。个以下错码。第12章 差错控制编码4、对纠错编码的要求对纠错编码的要求 纠、检错能力强，编码效率高，码长短，纠、检错能力强，编码效率高，码长短，纠、检错能力强，编码效率高，码长短，纠、检错能力强，编码效率高，码长短，编码编码编码编码规律简单。规律简单。规律简单
15、。规律简单。例：例：一个码集，只有两个许用码：一个码集，只有两个许用码：0000、1111，试求其纠检错能力和编码效率。试求其纠检错能力和编码效率。解：解：根据码距的定义，则该码集根据码距的定义，则该码集d 0=4，1/用于检错，e d d0 1=3，即可检3个错误；2/用于纠错，t (d d01)/2=3/2，取整，即可纠1个错误；3/同时用于纠、检错，d d0 e+t+1 e+t+1 （e et t）取：e=2，t=1，则可满足上式，即可检2个错误 同时纠一个错；R=k/n=1/4编码效率：编码效率：编码效率：编码效率：第12章 差错控制编码5.差错控制编码的效用：假设在随机信道中，发送假
16、设在随机信道中，发送“0”和和“1”的错误概率相等，都的错误概率相等，都等于等于p，且，且p1，在码长为在码长为n的码组中，发生的码组中，发生r个错误的概率个错误的概率为：为：例如：当例如：当n=7，p=10时，则有：时，则有：由此可见，即使仅能纠正由此可见，即使仅能纠正1-2个错误，也可使误码率下降个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实际应用价值。几个数量级。所以差错控制编码具有较大的实际应用价值。第12章 差错控制编码例例12-1 12-1 已知已知8 8个码组为：（个码组为：（O00000O00000），（），（001110001110），），（01010101
17、0101），（），（011011011011），（），（100011100011），），（1O11011O1101），），（110110110110），（），（111000111000），），（1 1）求以上码组的最小码距；（）求以上码组的最小码距；（2 2）若此）若此8 8个码组用于检错，个码组用于检错，可检出几位错？（可检出几位错？（3 3）若用于纠错码，能纠几位？（）若用于纠错码，能纠几位？（4 4）若同时用于纠错和检错，纠错、检错性能如何？若同时用于纠错和检错，纠错、检错性能如何？（1）（2）（3）（4）第12章 差错控制编码例例12-2 12-2 已知两码组（已知两码组（000000
18、00）和（）和（11111111），若该码组），若该码组用于检错，能检出几位错码？若用于纠错，能纠用于检错，能检出几位错码？若用于纠错，能纠正几位错码？若同时用于纠错和检错，问各能纠、正几位错码？若同时用于纠错和检错，问各能纠、检几位错码？检几位错码？（1）（2）（3）第12章 差错控制编码一一.奇偶监督码奇偶监督码在信息为后加一位校验位在信息为后加一位校验位12.312.3 常用的简单编码常用的简单编码 奇监督码奇监督码偶监督码偶监督码特点：只能检测出奇数个错码，不能检测出偶数特点：只能检测出奇数个错码，不能检测出偶数奇偶监督码：奇偶监督码：k=n-1,r=1k=n-1,r=1的线性码。的线
19、性码。特点：特点：码组中的码组中的1 1个数是奇数（奇监督码）个数是奇数（奇监督码）或偶数（偶监督码）。或偶数（偶监督码）。第12章 差错控制编码序序 码码 字字 序序 码码 字字号号 信息码元信息码元 监督元监督元 号号 信息码元信息码元 监督元监督元 a4 a3 a2 a1 a0 a4 a3 a2 a1 a0 0 0 0 0 0 0 8 1 0 0 0 1 1 0 0 0 1 1 9 1 0 0 1 0 2 0 0 1 0 1 10 1 0 1 0 0 3 0 0 1 1 0 11 1 0 1 1 1 4 0 1 0 0 1 12 1 1 0 0 0 5 0 1 0 1 0 13 1 1
20、0 1 1 6 0 1 1 0 0 14 1 1 1 0 1 7 0 1 1 1 1 15 1 1 1 1 0 码长码长5 5的偶监督码的偶监督码第12章 差错控制编码 偶监督码编码器a4a3a2a1+信息组信息组a0a1a2a3a4码字码字第12章 差错控制编码偶监督码的检错电路b3b0b1b2b4+接收码组BS检错信号第12章 差错控制编码例：一数据序列：例：一数据序列：1110011100 1011110111 0110101101 1000110001 1010110101 试对其进行（试对其进行（6 6，5 5）偶校验编码，写出码序列）偶校验编码，写出码序列并分析其抗干扰能力并分析其
21、抗干扰能力解：解：（6 6，5 5）,将数据序列每将数据序列每5 5码元分组，码元分组，并作：并作：的运算的运算可得出编码数据序列：可得出编码数据序列：11100111001110111101110001101011011110001100010010101101011 1 只能检测出奇数个错误，不能发现偶数个错误，只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。也不能纠错。第12章 差错控制编码二二.二维奇偶监督码二维奇偶监督码行监督位行监督位列监督位列监督位第12章 差错控制编码水平垂直奇偶校验水平垂直奇偶校验码：码：又称行列监督码或二维奇偶监督码。又称行列监督码或二维奇偶监督码。特
22、点：特点：对水平方向和垂直方向的码元同时实施奇偶监督。对水平方向和垂直方向的码元同时实施奇偶监督。1 1 0 0 1 0 1 0 0 0 00 1 0 0 0 0 1 1 0 1 00 1 1 1 1 0 0 0 0 1 11 0 0 1 1 1 0 0 0 0 01 0 1 0 1 0 1 0 1 0 11 1 0 0 0 1 1 1 1 0 0行行列列监监督督码码第12章 差错控制编码特点：特点：（1）能检测出每一行（列）中的奇数个或偶数个错码，）能检测出每一行（列）中的奇数个或偶数个错码，但不能检测出行列同时成偶数个出现的错码。但不能检测出行列同时成偶数个出现的错码。（2）能检测突发性错
23、误（成串错码）。）能检测突发性错误（成串错码）。（3）能纠正错码。）能纠正错码。第12章 差错控制编码恒比码：恒比码：又称等重码或定又称等重码或定1 1码。码。特点：特点：码组中码组中0 0，1 1的个数保持不变。的个数保持不变。若码长为若码长为n n，码重为码重为w w，则此码的码字个数则此码的码字个数 为：为：C Cn nw w，禁用码字个数为：禁用码字个数为：2 2n n-C Cn nw w例如：我国的电报，每个汉字用四个例如：我国的电报，每个汉字用四个1010进制数表进制数表 示，每位示，每位1010进制数就采用进制数就采用 3 3：2 2 恒比码构恒比码构 成的成的5 5位码组来表示
24、。位码组来表示。码字的个数码字的个数C C5 53 3=10=10检错能力较强，可检出所奇数和部分偶数错误。检错能力较强，可检出所奇数和部分偶数错误。第12章 差错控制编码作业：正反码：正反码：简单的可纠错编码，信元数等于监督元数简单的可纠错编码，信元数等于监督元数特点：特点：信息位中，有奇数个信息位中，有奇数个1 1时，监督位重复信息位；时，监督位重复信息位；信息位中，有偶数个信息位中，有偶数个1 1时，监督位取信息位的反码；时，监督位取信息位的反码；可纠一位、检测所有两位错和部分两位以上的错误。可纠一位、检测所有两位错和部分两位以上的错误。例：例：11001 1100111001 1100
25、1110011100110001 1000110001 100010111001110(n,k)(n,k)其中其中k=n/2 k=n/2 编码效率：编码效率：R=k/n=1/2R=k/n=1/2第12章 差错控制编码 四四.正反码正反码例：信息位：例：信息位：11001 11001 监督位：监督位：1100111001 信息位：信息位：10001 10001 监督位：监督位：01110011101.1.编码规则：编码规则：（1 1）当信息位中有奇数个）当信息位中有奇数个1 1时，监督位是信息位时，监督位是信息位的简单重复。的简单重复。（2 2）当信息位中有偶数个）当信息位中有偶数个1 1时，监
26、督位是信息位时，监督位是信息位的反码。的反码。第12章 差错控制编码例：例：11001 11001 1100111001=00000=00000 10001 01110=11111 10001 01110=111112.2.译码方法译码方法（1 1）将码组中的信息码与监督码进行模）将码组中的信息码与监督码进行模2 2加得合加得合成码组。成码组。（2 2）若信息码中有奇数个）若信息码中有奇数个1 1，则合成码组即为，则合成码组即为检验码组。检验码组。若信息码中有偶数个若信息码中有偶数个1 1，则合成码组的反，则合成码组的反码即为检验码组。码即为检验码组。（3 3）观察检验码组中）观察检验码组中1
27、 1的个数，按的个数，按p278p278进行检错进行检错和纠错。和纠错。第12章 差错控制编码12.4 线性分组码l 线性分组码中信息码元和监督码元是用线性方程联系起来的。线性码建立在代数学群论基础上，线性码各许用码组的集合构成代数学中的群，因此，又称群码。l主要性质 任意两许用码组之和(模2和)仍为一许用码组。(封闭性)码的最小距离等于非零码的最小重量。第12章 差错控制编码奇偶监督码是一种最简单的线性码，偶校验奇偶监督码是一种最简单的线性码，偶校验时时lS称为校正子，又称伴随式。S=0无错，S=1 有错。l一般，由r个监督方程式计算得r个校正子，可以用来指示2r-1种错误，对于一位误码来说
28、，就可以指示2r-1个误码位置。l对于(n,k)码，如果满足2r-1n 则可能构造出纠正一位或一位以上错误的线性码。第12章 差错控制编码设分组码设分组码(n,k)中中k=4,为纠正一位错码为纠正一位错码,要求要求r3,则则 n=k+r=7S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错一一.以（以（7，4）分组码为例）分组码为例第12章 差错控制编码计算监督位判断错码位置按上述方法构造的纠正单个错误的线性分组码称为汉明码。码长 n=2r 1 信息位 k=2r 1 r 监督位r（1）（2）第12章 差错控制编码码字：码字：
29、A=A=（）其中信息位：其中信息位：监督位监督位：若分组码可用下列线性方程组表示：若分组码可用下列线性方程组表示：（“+”为模为模2加加 ）则：该分组码为（则：该分组码为（7 7，4 4）线性分组码（共有）线性分组码（共有1616个个码字）码字）第12章 差错控制编码表表 9-2(7,4)码的码字表码的码字表 第12章 差错控制编码性质：性质：（1 1）封闭性：任意）封闭性：任意2 2个许用码组之和（模个许用码组之和（模2 2加）仍加）仍为一个许用码组。为一个许用码组。（2 2）有零元：）有零元：（3 3）有负元：）有负元：（4 4）结合律成立：）结合律成立：（任一码字即为本身的负元）（任一码
30、字即为本身的负元）编码速率编码速率=第12章 差错控制编码l（1）改写为表示成矩阵形式=PIr二.监督矩阵H第12章 差错控制编码用矩阵表示为：用矩阵表示为：并记为：并记为：第12章 差错控制编码H阵可表示为：阵可表示为：（阶）（阶单位阵）矩阵矩阵H H称为（称为（7 7，4 4）线性分组码得监督矩阵。上式）线性分组码得监督矩阵。上式也称为典型监督矩阵。若不是典型监督矩阵要用也称为典型监督矩阵。若不是典型监督矩阵要用初等变换化成典型矩阵。初等变换化成典型矩阵。第12章 差错控制编码三三.生成矩阵生成矩阵G G 若信息码元已知，通过监督矩阵可以求出监若信息码元已知，通过监督矩阵可以求出监督码元。
31、督码元。用矩阵表示：用矩阵表示：或或第12章 差错控制编码 将上式扩展可以由已知信息码元求得整个码将上式扩展可以由已知信息码元求得整个码组。组。令：令：G称为生成矩阵第12章 差错控制编码典型监督矩阵和典型生成矩阵存在以下关系式：典型监督矩阵和典型生成矩阵存在以下关系式：例：（例：（7，4）第12章 差错控制编码全部码字为：全部码字为：第12章 差错控制编码四四.伴随式（校正子）伴随式（校正子）S S 设发送码字为设发送码字为 ，接收码字为，接收码字为 ，由于干扰，噪声可能引入误差，使接收码组与，由于干扰，噪声可能引入误差，使接收码组与发送码组不同，因此有发送码组不同，因此有 ，其中，其中 是
32、传输中产生的错误行矩阵。对于二进制码元有是传输中产生的错误行矩阵。对于二进制码元有:E矩阵中哪一位码元为矩阵中哪一位码元为1就表示接收码字中对就表示接收码字中对应位有错。应位有错。E称为错误图样。称为错误图样。模模2第12章 差错控制编码 在接收端用在接收端用H来检测接收来检测接收B中的错码。中的错码。令：令：伴随式或校正子：伴随式或校正子：如果如果B与与A相同，则：相同，则：否则：否则：又又 表示校正子表示校正子S仅与信道的错误图样仅与信道的错误图样E有关，而与有关，而与发送的码字发送的码字A无关。无关。第12章 差错控制编码表表 9-3(7,4)码码S与与E的对应关系的对应关系 第12章
33、差错控制编码五五.如何利用如何利用S S完成纠错完成纠错对（对（7，4）线性分组码）线性分组码设设B中最高位有错，错误图样中最高位有错，错误图样它的转置它的转置恰好是典型恰好是典型H阵的第一列。阵的第一列。第12章 差错控制编码同理可求出：同理可求出：若次高位有错若次高位有错，即，即 恰好是恰好是H的第二列。的第二列。因此，在接收码组中只错一位码元情况下，因此，在接收码组中只错一位码元情况下，计算出的校正子计算出的校正子S总是和典型监督矩阵总是和典型监督矩阵 中的某中的某一行相同。一行相同。例：例：与第三列相同与第三列相同第12章 差错控制编码正确码组为：正确码组为：六六.汉明码汉明码 汉明码
34、是一种可以纠正单个随机错误的线性汉明码是一种可以纠正单个随机错误的线性分组码。它的最小码距分组码。它的最小码距 ，监督元位数，监督元位数 ，码长，码长 ，信息元位数，信息元位数 ，编码效率，编码效率当当r很大时，很大时，因此是一种高效码。，因此是一种高效码。第12章 差错控制编码 上例中的（上例中的（7，4）线性分组码就是汉明码，）线性分组码就是汉明码，并且任意调换并且任意调换H矩阵中各列的结果不会影响纠，矩阵中各列的结果不会影响纠，检错能力。检错能力。第12章 差错控制编码例例 设设 且有且有3个接收码组个接收码组l验证3个接收码组是否发生差错？l若在某码组中有错码，错码的校正子是什么？然后
35、再指出发生错码的码字中，哪位有错？第12章 差错控制编码解：解：1）若无错，则错误图样为）若无错，则错误图样为0，S为为0B1无错B2错B3错2）S2=H 第1列 E=1 0 0 0 0 0 第1位错同理 S3=H 第3列 E=0 0 1 0 0 0 第3位错第12章 差错控制编码12.5 循环码循环码 一一.概念概念1.循环码：循环码：线性分组码线性分组码 （1）封闭性）封闭性 （2）循环性：循环码中任一许用码组经过循环）循环性：循环码中任一许用码组经过循环移位之后，所得到的码组仍为一许用码组。移位之后，所得到的码组仍为一许用码组。2.码多项式码多项式循环码的一许用码组循环码的一许用码组可表
36、示为：可表示为：其中：其中：x为码元位置标记，不考虑其取值。为码元位置标记，不考虑其取值。码元码元 只取只取“1”或或“0”。第12章 差错控制编码例例:(7，3）循环码中第二个码组）循环码中第二个码组 如何实现移位：乘一个如何实现移位：乘一个x相当于码左移一位。相当于码左移一位。3.按模运算按模运算若若（的次数小于的次数小于 ）则：则：称为称为 按模按模 运算后的运算后的余式。余式。第12章 差错控制编码例：例：4.规律规律（1）循环码中，将许用码组）循环码中，将许用码组 左移左移一位得到的码字记为：一位得到的码字记为：。其码多。其码多项式为：项式为：可以证明：可以证明：第12章 差错控制编
37、码（2）根据循环码的定义，）根据循环码的定义，均为许用均为许用码字。码字。因此下列结论：若因此下列结论：若 是许用码字，则是许用码字，则 在按模在按模 运算下，也是许用码字。运算下，也是许用码字。即：若即：若则则 也是许用码字。也是许用码字。例例:(7，3）循环码）循环码则：则：那么那么其码字为其码字为 。第12章 差错控制编码二二.生成多项式与生成矩阵生成多项式与生成矩阵G G1.(n，k)循环码码组集合中（全循环码码组集合中（全“0”除外）最除外）最高阶数最小的多项式高阶数最小的多项式（n-k）阶）阶称为生成多项称为生成多项式，记为式，记为g(x)。2.集合中其它码多项式都是集合中其它码多
38、项式都是 运算下运算下的余式。的余式。即可以由生成多项式即可以由生成多项式g(x)产生循环码的全部码产生循环码的全部码字。字。第12章 差错控制编码3.生成矩阵生成矩阵G循环码的生成矩阵多项式可以写成循环码的生成矩阵多项式可以写成以（以（7，3）循环码为例）循环码为例经线性变换，将经线性变换，将G整理成典型生成矩阵。整理成典型生成矩阵。第12章 差错控制编码整个码组可表示为：整个码组可表示为：任意一个码多项式都能被任意一个码多项式都能被g(x)整除。整除。第12章 差错控制编码三三.监督多项式、监督矩阵监督多项式、监督矩阵1.对于对于(n，k)循环码，循环码，可分解成可分解成g(x)和其它和其
39、它因式的乘积。因式的乘积。记为：记为：称称h(x)为监督多项式，其矩阵形式为：为监督多项式，其矩阵形式为：以（以（7，3）循环码为例）循环码为例第12章 差错控制编码2.对于（对于（7，3）循环码，）循环码，g(x)的最高次为的最高次为4所以，有两种方案所以，有两种方案第一种方案：第一种方案：第12章 差错控制编码码字：码字：第二种方案：第二种方案：码字：码字：第12章 差错控制编码例例:已知已知(7，4）循环码的生成多项式为）循环码的生成多项式为（1）求典型生成矩阵和典型监督矩阵；）求典型生成矩阵和典型监督矩阵；（2）输入信息码为）输入信息码为11001011，求编码后的系统码；，求编码后的
40、系统码；（3）全部码组；）全部码组；（4）纠、检错能力）纠、检错能力 解：解：第12章 差错控制编码第12章 差错控制编码全部码字为：全部码字为：第12章 差错控制编码四四.编码电路编码电路1.对于对于(n，k)循环码中，可用多项式表示为：循环码中，可用多项式表示为：其中：其中：m(x)为不大于（为不大于（k-1）次的多项式，代表信息码）次的多项式，代表信息码元。元。r(x)为不大于为不大于(r-1)次的多项式，代表监督码元。次的多项式，代表监督码元。或：或：第12章 差错控制编码该式提供了循环码编码的数学依据。该式提供了循环码编码的数学依据。2.步骤：步骤：（1）信息多项式）信息多项式m(x
41、)左移左移n-k位。（相当于位。（相当于 ）（2）求其模）求其模g(x)的余式的余式r(x)（3）余式的系数作监督码元，附加在信息码元之后形）余式的系数作监督码元，附加在信息码元之后形成循环码。成循环码。第12章 差错控制编码例例:已知已知(7，3）循环码的生成多项式为）循环码的生成多项式为求信息位为求信息位为101时的码字。时的码字。解：解：第12章 差错控制编码3.编码电路编码电路门1门2 首先，四级移位寄存器清零，三位信息码元到来时首先，四级移位寄存器清零，三位信息码元到来时，门，门1 1断开，门断开，门2 2接通，直接输出信息元。第接通，直接输出信息元。第3 3次移位脉次移位脉冲来时将
42、除法电路运算所得的余数存入四级移位寄存器冲来时将除法电路运算所得的余数存入四级移位寄存器，第，第4747次移位时，门次移位时，门2 2断开，门断开，门1 1接通，输出监督码元接通，输出监督码元（即余数）。当一个码字输出完毕后就将移位寄存器清（即余数）。当一个码字输出完毕后就将移位寄存器清零，等待下一组信息码元输入后重新编码。零，等待下一组信息码元输入后重新编码。第12章 差错控制编码4.解码解码（1）只检错）只检错设发送码组为设发送码组为A，接收码组为，接收码组为B。B不出错时，有不出错时，有B(x)=A(x)则：则：能整除。能整除。余数不为余数不为0时，时，B有错。有错。第12章 差错控制编
43、码框图：框图：（2）纠错）纠错用用B(x)除以除以g(x)得到余式得到余式按余式按余式 用查表的方法或通过某种运算得到用查表的方法或通过某种运算得到E(x)。第12章 差错控制编码例：例：12-6 12-6 令令 为为(7(7，4)4)循环码的生成多项循环码的生成多项式。式。(1)(1)求出该循环码的生成矩阵和监督矩阵；求出该循环码的生成矩阵和监督矩阵；(2)(2)若两个信息码组分别为若两个信息码组分别为(1001)(1001)和和(0110),(0110),求出这两求出这两个循环码组；个循环码组；(3)(3)画出其编码器原理框图。画出其编码器原理框图。解：（解：（1）第12章 差错控制编码（
44、2）（3）第12章 差错控制编码（4）第12章 差错控制编码9.6 卷积码卷积码 在编码器复杂性相同的情况下在编码器复杂性相同的情况下,卷积码的卷积码的性能优于分组码性能优于分组码.l卷积码把k个信息位编n位,k和n通常很小,特别适宜于串行形式传输,延时小.ln 个码元与当前段的k个信息位有关,而且与前N-1段的信息有关,编码过程相互关联的码元为Nn个.lN或nN称为卷积码的约束长度,l常把卷积码记作(n,k,N)第12章 差错控制编码卷积码的一般结构卷积码的一般结构 编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周第12章 差错
45、控制编码 由上图可以看到，由上图可以看到，n个输出比特不仅与当前的个输出比特不仅与当前的k个输入信息有关，还与前（个输入信息有关，还与前（N-1）k个信息有关。个信息有关。通常将通常将N称为约束长度，（有的书的约束长度为称为约束长度，（有的书的约束长度为Nn）。）。常把卷积码记为：常把卷积码记为：（n，k，N）其编码效率为：其编码效率为：k/n第12章 差错控制编码卷积码的图解表示卷积码的图解表示 （3，1，2）卷积码编码器 a 状态m1m2为00，b 状态m1m2为01，c 状态m1m2为10，d 状态m1m2为11。M2 M1+输入序列 mjmjy1，jY2，j第12章 差错控制编码（3，
46、1，2）卷积码的树状图000000111000111001110000111001110011100010101aababcdabcdabcd111001110011100010101000111001110011100010101bcdabcdabcdabcda第12章 差错控制编码（3，1，2）卷积码的网格图abcd000000000000000111111111111111011011011001001001001110110110110010010010101101101100第12章 差错控制编码（3，1，2）卷积码的状态图aabbccda1111101010000111000010
47、10abcd111000110101100001011010第12章 差错控制编码在前述编码器中，若起始状态为在前述编码器中，若起始状态为a，输入序列为，输入序列为11010111，求输出序列和状态变化路径，求输出序列和状态变化路径abcd000000000000000111111111111111011011011001001001001110110110110010010010101101101100第12章 差错控制编码对于（对于（n，k，N）卷积码的一般情况，有如）卷积码的一般情况，有如下结论：下结论：l对应于每组k个输入比特，编码后产生n个输出比特。l树状图每个节点引出2k条支路。l网格图和状态图都有2k(N-1)种可能的状态，每个状态引出2k条支路，同时也有2k条支路从其它状态或本状态引入。