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
12、ar-1 a0 r个监督元个监督元码长：码长：n=k+rR=k/n为为编码效率编码效率，d0一定一定(纠错能力一定纠错能力一定)时，时，k/n大，效率高。大，效率高。对被传输的信息序列分组，每组为对被传输的信息序列分组，每组为k个信息元，对每组个信息元，对每组按某种关系附加按某种关系附加(n-k)个监督码元个监督码元(校验校验)，形成为，形成为n位的码字。位的码字。这种方法构成的码组称为这种方法构成的码组称为分组码分组码。第12章 差错控制编码分组码的表示：符号（分组码的表示：符号（n，k）n 码组的总位数码组的总位数k 码组中信息码元的数目码组中信息码元的数目r =n-k 监督码元的数目监督
13、码元的数目编码效率编码效率nrnkR/1/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纠错能力纠错能力10ed（1）时能检出时能检出e e个或个或e e个以下错码。个以下错码。（2）（3）120 td 时能纠正时能纠正t t个或个或t t个以下错码。个以下错码。时能检出时能检出t t个或个或e e个以下错码。个以下错码。)(10teted第12章 差错控制编码4、对纠错编码的要求、对纠错编码的要求例：例：一个码集，只有两个许用码：一个码集，只有两个许用码：0000、1111，试求其纠检错能力和编码效率。试求其纠检错能力和编码效率。解：解：根据码距
15、的定义，则该码集根据码距的定义，则该码集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.差错控制编码的效用：假设在随机信道中，发送假设在随机信道中，发送“0”和和“1”的错误概率相等，都的错误概率相等，都等于等于p，且，且p1，在码长为，在码长为n的码组中，发生的码组中，发生r个错误的概率个错误的概率为：为：rrnrrrnnprnrn
16、ppCrP)!(!)1()(例如：当例如：当n=7，p=10时，则有：时，则有：371077)1(pP5227101.221)!27(!2!7)2(ppP8337105.335)!37(!3!7)3(ppP 由此可见，即使仅能纠正由此可见，即使仅能纠正1-2个错误，也可使误码率下降个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实际应用价值。几个数量级。所以差错控制编码具有较大的实际应用价值。第12章 差错控制编码例例12-1 12-1 已知已知8 8个码组为：（个码组为：（O00000O00000），（），（001110001110），），（010101010101），（），（
17、011011011011），（），（100011100011），），（1O11011O1101），），（110110110110），（），（111000111000），），（1 1）求以上码组的最小码距；（）求以上码组的最小码距；（2 2）若此）若此8 8个码组用于检错，个码组用于检错，可检出几位错？（可检出几位错？（3 3）若用于纠错码，能纠几位？（）若用于纠错码，能纠几位？（4 4）若同时用于纠错和检错，纠错、检错性能如何？若同时用于纠错和检错，纠错、检错性能如何？30d10 ed13 e2e120 td123 t1t10ted （1）（2）（3）（4）第12章 差错控制编码例例12-2
18、12-2 已知两码组（已知两码组（00000000）和（）和（11111111），若该码组），若该码组用于检错，能检出几位错码？若用于纠错，能纠用于检错，能检出几位错码？若用于纠错，能纠正几位错码？若同时用于纠错和检错，问各能纠、正几位错码？若同时用于纠错和检错，问各能纠、检几位错码？检几位错码？40d14 e3e124 t1t14te1t2e （1）（2）（3）第12章 差错控制编码一一.奇偶监督码奇偶监督码在信息为后加一位校验位在信息为后加一位校验位12.3 12.3 常用的简单编码常用的简单编码00121aaaann 奇监督码奇监督码偶监督码偶监督码特点：只能检测出奇数个错码，不能检测出
19、偶数特点：只能检测出奇数个错码，不能检测出偶数10121aaaann奇偶监督码：奇偶监督码：k=n-1,r=1k=n-1,r=1的线性码。的线性码。特点：特点：码组中的码组中的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
20、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 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码字码字12340aaaaa第12章 差错控制编码偶监督码的检错电路01234bbbbbsb3b0b1b2b4+接收码组BS检错信号有错无错10第12章 差错控制编码例：一数据序列：例：一数据序列：1110011100 10
21、11110111 0110101101 1000110001 1010110101 试对其进行（试对其进行（6 6，5 5）偶校验编码，写出码序列）偶校验编码，写出码序列并分析其抗干扰能力并分析其抗干扰能力解：解：（6 6，5 5）,将数据序列每将数据序列每5 5码元分组，码元分组，123450aaaaaa并作：并作：的运算的运算可得出编码数据序列：可得出编码数据序列：11100111001110111101110001101011011110001100010010101101011 1 只能检测出奇数个错误，不能发现偶数个错误，只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。也不能纠
22、错。第12章 差错控制编码二二.二维奇偶监督码二维奇偶监督码012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn 行监督位行监督位列监督位列监督位第12章 差错控制编码水平垂直奇偶校验水平垂直奇偶校验码：码：又称行列监督码或二维奇偶监督码。又称行列监督码或二维奇偶监督码。特点：特点：对水平方向和垂直方向的码元同时实施奇偶监督。对水平方向和垂直方向的码元同时实施奇偶监督。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
23、1 0 1 0 1 0 1 0 11 1 0 0 0 1 1 1 1 0 0行行列列监监督督码码第12章 差错控制编码特点：特点：（1）能检测出每一行（列）中的奇数个或偶数个错码，）能检测出每一行（列）中的奇数个或偶数个错码，但不能检测出行列同时成偶数个出现的错码。但不能检测出行列同时成偶数个出现的错码。（2）能检测突发性错误（成串错码）。）能检测突发性错误（成串错码）。（3）能纠正错码。）能纠正错码。第12章 差错控制编码恒比码：恒比码：又称等重码或定又称等重码或定1 1码。码。特点：特点：码组中码组中0 0，1 1的个数保持不变。的个数保持不变。若码长为若码长为n n，码重为，码重为w w
24、，则此码的码字个数，则此码的码字个数 为：为：C Cn nw w，禁用码字个数为：，禁用码字个数为：2 2n n-C-Cn nw w例如：我国的电报，每个汉字用四个例如：我国的电报，每个汉字用四个1010进制数表进制数表 示，每位示，每位1010进制数就采用进制数就采用 3 3：2 2 恒比码构恒比码构 成的成的5 5位码组来表示。位码组来表示。码字的个数码字的个数C C5 53 3=10=10检错能力较强，可检出所奇数和部分偶数错误。检错能力较强，可检出所奇数和部分偶数错误。第12章 差错控制编码作业：正反码：正反码：简单的可纠错编码，信元数等于监督元数简单的可纠错编码，信元数等于监督元数特
25、点：特点：信息位中，有奇数个信息位中，有奇数个1 1时，监督位重复信息位；时，监督位重复信息位；信息位中，有偶数个信息位中，有偶数个1 1时，监督位取信息位的反码；时，监督位取信息位的反码；可纠一位、检测所有两位错和部分两位以上的错误。可纠一位、检测所有两位错和部分两位以上的错误。例：例：11001 1100111001 11001110011100110001 1000110001 100010111001110(n,k)(n,k)其中其中k=n/2 k=n/2 编码效率：编码效率：R=k/n=1/2R=k/n=1/2第12章 差错控制编码 四四.正反码正反码例：信息位：例：信息位：1100
26、1 11001 监督位：监督位：1100111001 信息位：信息位：10001 10001 监督位：监督位：01110011101.1.编码规则：编码规则：（1 1）当信息位中有奇数个）当信息位中有奇数个1 1时，监督位是信息位时，监督位是信息位的简单重复。的简单重复。（2 2）当信息位中有偶数个）当信息位中有偶数个1 1时，监督位是信息位时，监督位是信息位的反码。的反码。第12章 差错控制编码例：例：11001 1100111001 11001=00000=00000 10001 01110=11111 10001 01110=111112.2.译码方法译码方法（1 1）将码组中的信息码与
27、监督码进行模）将码组中的信息码与监督码进行模2 2加得合加得合成码组。成码组。（2 2）若信息码中有奇数个）若信息码中有奇数个1 1，则合成码组即为，则合成码组即为检验码组。检验码组。若信息码中有偶数个若信息码中有偶数个1 1，则合成码组的反，则合成码组的反码即为检验码组。码即为检验码组。（3 3）观察检验码组中）观察检验码组中1 1的个数，按的个数，按p278p278进行检错进行检错和纠错。和纠错。第12章 差错控制编码12.4 线性分组码l 线性分组码中信息码元和监督码元是用线性方程联系起来的。线性码建立在代数学群论基础上，线性码各许用码组的集合构成代数学中的群，因此，又称群码。l主要性质
28、 任意两许用码组之和(模2和)仍为一许用码组。(封闭性)码的最小距离等于非零码的最小重量。第12章 差错控制编码奇偶监督码是一种最简单的线性码，偶校验奇偶监督码是一种最简单的线性码，偶校验时时lS称为校正子，又称伴随式。S=0无错，S=1 有错。l一般，由r个监督方程式计算得r个校正子，可以用来指示2r-1种错误，对于一位误码来说，就可以指示2r-1个误码位置。l对于(n,k)码，如果满足2r-1n 则可能构造出纠正一位或一位以上错误的线性码。021aaaSnn第12章 差错控制编码设分组码设分组码(n,k)中中k=4,为纠正一位错码为纠正一位错码,要求要求r3,则则 n=k+r=7S1S2S
29、3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错一一.以（以（7，4）分组码为例）分组码为例第12章 差错控制编码024561aaaaS013562aaaaS003463aaaaS4562aaaa3561aaaa3460aaaa计算监督位判断错码位置按上述方法构造的纠正单个错误的线性分组码称为汉明码。码长 n=2r 1 信息位 k=2r 1 r 监督位r（1）（2）第12章 差错控制编码码字：码字：A=A=（）3456aaaa012aaa其中信息位：其中信息位：监督位监督位：3456aaaa012aaa若分组码可用下列线性方程组表示
30、：若分组码可用下列线性方程组表示：346035614562aaaaaaaaaaaa（“+”为模为模2加加 ）则：该分组码为（则：该分组码为（7 7，4 4）线性分组码（共有）线性分组码（共有1616个个码字）码字）第12章 差错控制编码表表 9-2(7,4)码的码字表码的码字表 第12章 差错控制编码性质：性质：（1 1）封闭性：任意）封闭性：任意2 2个许用码组之和（模个许用码组之和（模2 2加）仍加）仍为一个许用码组。为一个许用码组。（2 2）有零元：）有零元：（3 3）有负元：）有负元：（4 4）结合律成立：）结合律成立：iioAAAoiiAAA)()(432432AAAAAA（任一码字
31、即为本身的负元）（任一码字即为本身的负元）nrrrnkrrr11211212编码速率编码速率=第12章 差错控制编码l（1）改写为000101110123456aaaaaaa001010110123456aaaaaaa010011010123456aaaaaaa表示成矩阵形式1001101010101100101110123456aaaaaaa=000PIr二.监督矩阵H第12章 差错控制编码0001011001110101011101000123456aaaaaaa用矩阵表示为：用矩阵表示为：并记为：并记为：OHAOAHTTT或第12章 差错控制编码H阵可表示为：阵可表示为：rPIH1001
32、10101010110010111PkrrIrr（阶）（阶单位阵）矩阵矩阵H H称为（称为（7 7，4 4）线性分组码得监督矩阵。上式）线性分组码得监督矩阵。上式也称为典型监督矩阵。若不是典型监督矩阵要用也称为典型监督矩阵。若不是典型监督矩阵要用初等变换化成典型矩阵。初等变换化成典型矩阵。第12章 差错控制编码三三.生成矩阵生成矩阵G G 若信息码元已知，通过监督矩阵可以求出监若信息码元已知，通过监督矩阵可以求出监督码元。督码元。346035614562aaaaaaaaaaaa345603456134562110110110111aaaaaaaaaaaaaaa34563456012110110
33、110111aaaaaaaaPaaa用矩阵表示：用矩阵表示：11010101111134563456012aaaaPaaaaaaaT或或第12章 差错控制编码 将上式扩展可以由已知信息码元求得整个码将上式扩展可以由已知信息码元求得整个码组。组。110100010101000110010111000134560123456aaaaaaaaaaaTPIG41101000101010001100101110001令：令：G称为生成矩阵第12章 差错控制编码典型监督矩阵和典型生成矩阵存在以下关系式：典型监督矩阵和典型生成矩阵存在以下关系式：rTrIQIPHTkkPIQIG),(knknr例：（例：（7
34、，4）rIPH100110101010110010111TkPIG1101000101010001100101110001第12章 差错控制编码 34560123456aaaaaaaaaaa1101000101010001100101110001全部码字为：全部码字为：000111011001101011010011001001111001010100110100000000001111111001011101010111000011100110101001010011001111000130d10 ed2e120 td1t第12章 差错控制编码四四.伴随式（校正子）伴随式（校正子）S S 设
35、发送码字为设发送码字为 ，接收码字，接收码字为为 ，由于干扰，噪声可能引入，由于干扰，噪声可能引入误差，使接收码组与发送码组不同，因此误差，使接收码组与发送码组不同，因此有有 ，其中，其中 是传输中产是传输中产生的错误行矩阵。对于二进制码元有生的错误行矩阵。对于二进制码元有:E矩阵中哪一位码元为矩阵中哪一位码元为1就表示接收码字中就表示接收码字中对应位有错。对应位有错。E称为错误图样。称为错误图样。021aaaAnn0121bbbbBnnEAB021eeeEnnABABE模模2第12章 差错控制编码 在接收端用在接收端用H来检测接收来检测接收B中的错码。中的错码。令：令：THBS伴随式或校正子
36、：伴随式或校正子：如果如果B与与A相同，则：相同，则：0TTHAHBS否则：否则：0THBS又又EABTTTTTHEHEHAHEAHBS)(表示校正子表示校正子S仅与信道的错误图样仅与信道的错误图样E有关，而与有关，而与发送的码字发送的码字A无关。无关。第12章 差错控制编码表表 9-3(7,4)码码S与与E的对应关系的对应关系 第12章 差错控制编码五五.如何利用如何利用S S完成纠错完成纠错对（对（7，4）线性分组码）线性分组码100110101010110010111H设设B中最高位有错，错误图样中最高位有错，错误图样0000001E1110000001TTHHES它的转置它的转置111
37、TS恰好是典型恰好是典型H阵的第一列。阵的第一列。第12章 差错控制编码同理可求出：同理可求出：若次高位有错若次高位有错011S，即，即 恰好是恰好是H的第二列。的第二列。TS 因此，在接收码组中只错一位码元情况下，因此，在接收码组中只错一位码元情况下，计算出的校正子计算出的校正子S总是和典型监督矩阵总是和典型监督矩阵 中的中的某一行相同。某一行相同。TH例：例：1010000B1011010000HBHSTT与第三列相同与第三列相同第12章 差错控制编码0000100E正确码组为：正确码组为：101010000001001010000EBA六六.汉明码汉明码 汉明码是一种可以纠正单个随机错误
38、的线性汉明码是一种可以纠正单个随机错误的线性分组码。它的最小码距分组码。它的最小码距 ，监督元位数，监督元位数 ，码长，码长 ，信息元位，信息元位数数 ，编码效率，编码效率当当r很大时，很大时，因此是一种高效码。，因此是一种高效码。30d)2(rknr12 rnrkr121211212rrrrrnkR1R第12章 差错控制编码 上例中的（上例中的（7，4）线性分组码就是汉明码，）线性分组码就是汉明码，并且任意调换并且任意调换H矩阵中各列的结果不会影响纠，矩阵中各列的结果不会影响纠，检错能力。检错能力。第12章 差错控制编码例例 设设 且有且有3个接收码组个接收码组l验证3个接收码组是否发生差错
39、？l若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？100101010110001011H1011101B1101012B1100003B第12章 差错控制编码解：解：1）若无错，则错误图样为）若无错，则错误图样为0，S为为000011THBSB1无错10122THBSB2错11033THBSB3错2）S2=H 第1列 E=1 0 0 0 0 0 第1位错同理 S3=H 第3列 E=0 0 1 0 0 0 第3位错TEHS 第12章 差错控制编码12.5 循环码循环码 一一.概念概念1.循环码：循环码：线性分组码线性分组码 （1）封闭性）封闭性 ),(kn（2）循
40、环性：循环码中任一许用码组经过循环）循环性：循环码中任一许用码组经过循环移位之后，所得到的码组仍为一许用码组。移位之后，所得到的码组仍为一许用码组。2.码多项式码多项式循环码的一许用码组循环码的一许用码组可表示为：可表示为：),(0121aaaaAnn012211)(axaxaxaxAnnnn其中：其中：x为码元位置标记，不考虑其取值。为码元位置标记，不考虑其取值。码元码元 只取只取“1”或或“0”。)1,1,0(niai第12章 差错控制编码例例:(7，3）循环码中第二个码组）循环码中第二个码组 1110100)(1234562xxxxxxxA)0010111(2A124xxx如何实现移位：
41、乘一个如何实现移位：乘一个x相当于码左移一位。相当于码左移一位。xxxxxxA2352)()0101110(A3.按模运算按模运算若若)()()()()(xNxRxQxNxM（的次数小于的次数小于 ）则：则：)()()(xNxRxM模)(xR)(xN称为称为 按模按模 运算后运算后的余式。的余式。)(xM)(xN第12章 差错控制编码例：例：1 133xx模 1 113224xxxxx模4.规律规律（1）循环码中，将许用码组）循环码中，将许用码组 左移左移一位得到的码字记为：一位得到的码字记为：。其。其码多项式为：码多项式为：可以证明：可以证明：),(0121aaaaAnn),(1032)1(
42、nnnaaaaA102312)1()(nnnnnaxaxaxaxA 1)()()1(nxxAxxA模 1)()()(niixxAxAx模第12章 差错控制编码（2）根据循环码的定义，）根据循环码的定义，均为均为许用码字。许用码字。因此下列结论：若因此下列结论：若 是许用码字，则是许用码字，则 在按模在按模 运算下，也是许用码字。运算下，也是许用码字。)()3()2()1(,iAAAA)(xA)(xAxi1nx即：若即：若 1)()()(niixxAxAx模则则 也是许用码字。也是许用码字。)()(xAi例例:(7，3）循环码）循环码)0101110(3A则：则：1)(125xxxxA7n那么那
43、么 1)(734534583xxxxxxxxxxAx模其码字为其码字为 。4A第12章 差错控制编码二二.生成多项式与生成矩阵生成多项式与生成矩阵G G1.(n，k)循环码码组集合中（全循环码码组集合中（全“0”除外）最除外）最高阶数最小的多项式高阶数最小的多项式（n-k）阶）阶称为生成多项称为生成多项式，记为式，记为g(x)。2.集合中其它码多项式都是集合中其它码多项式都是 运算运算下的余式。下的余式。即可以由生成多项式即可以由生成多项式g(x)产生循环码的全部码产生循环码的全部码字。字。)1()(nixngx模第12章 差错控制编码3.生成矩阵生成矩阵G循环码的生成矩阵多项式可以写成循环码
44、的生成矩阵多项式可以写成_)()()()()(21xgxxgxgxxgxxGkk以（以（7，3）循环码为例）循环码为例1)(24xxxxg)()()()(2xgxxgxgxxG111010001110100011101G经线性变换，将经线性变换，将G整理成典型生成矩阵。整理成典型生成矩阵。第12章 差错控制编码TkPIG111010001110101101001整个码组可表示为：整个码组可表示为：)()()()()(2456456xgxxgxgxaaaxGaaaxA任意一个码多项式都能被任意一个码多项式都能被g(x)整除。整除。)()()(4526xgaxxgaxgxa)()(4526xgax
45、axa第12章 差错控制编码三三.监督多项式、监督矩阵监督多项式、监督矩阵1.对于对于(n，k)循环码，循环码，可分解成可分解成g(x)和其和其它因式的乘积。它因式的乘积。)()(1xhxgxn1nx记为：记为：称称h(x)为监督多项式，其矩阵形式为：为监督多项式，其矩阵形式为：kIPH 以（以（7，3）循环码为例）循环码为例111001111101TP1000101010011100101100001011H第12章 差错控制编码)1)(1)(1(13237xxxxxx2.对于（对于（7，3）循环码，）循环码，g(x)的最高次为的最高次为4所以，有两种方案所以，有两种方案)1()1(1233
46、47xxxxxx)1()1(324xxxxx第一种方案：第一种方案：1)(234xxxxg101110011100100111001101110001011100010111G1)(23xxxh第12章 差错控制编码码字：码字：01011101110010101110000000000010111100101111001010111001第二种方案：第二种方案：1)(3xxxh1)(24xxxxg111010001110101101001111010001110100011101G码字：码字：100111001110101110100000000001001111010011001110111
47、01001第12章 差错控制编码例例:已知已知(7，4）循环码的生成多项式为）循环码的生成多项式为（1）求典型生成矩阵和典型监督矩阵；）求典型生成矩阵和典型监督矩阵；（2）输入信息码为）输入信息码为11001011，求编码后的系统码；，求编码后的系统码；（3）全部码组；）全部码组；（4）纠、检错能力）纠、检错能力 123 xx解：解：1)(23xxxg)()()()()(23xgxxgxgxxgxxGTkPIG10110001110100110001001100011011000010110000101100001011第12章 差错控制编码100111001001110011101rIPH0
48、011101)(1101)(1010011)(0011)()()(213456xGxAxGxAxGaaaaxA第12章 差错控制编码全部码字为：全部码字为：100111000101100111010110001001011001110100101100000000001111111010011100010111010011001110110001011101001011000130d10 ed2e120 td1t第12章 差错控制编码四四.编码电路编码电路1.对于对于(n，k)循环码中，可用多项式表示为：循环码中，可用多项式表示为：)()()(xrxxmxAkn其中：其中：m(x)为不大于（为
49、不大于（k-1）次的多项式，代表信息码）次的多项式，代表信息码元。元。r(x)为不大于为不大于(r-1)次的多项式，代表监督码元。次的多项式，代表监督码元。)()()(xhxgxA)()()()(xgxhxrxxmkn)()()()(xrxgxhxxmkn或：或：第12章 差错控制编码)()()()()(xgxrxhxgxmxkn)()()(xgxrxmxkn模该式提供了循环码编码的数学依据。该式提供了循环码编码的数学依据。2.步骤：步骤：（1）信息多项式）信息多项式m(x)左移左移n-k位。（相当于位。（相当于 ）（2）求其模）求其模g(x)的余式的余式r(x)（3）余式的系数作监督码元，附
50、加在信息码元之后形）余式的系数作监督码元，附加在信息码元之后形成循环码。成循环码。knxxm)(第12章 差错控制编码例例:已知已知(7，3）循环码的生成多项式为）循环码的生成多项式为求信息位为求信息位为101时的码字。时的码字。解：解：1)(24xxxxg1)(24xxxxg)()()()(2xgxxgxgxxG111010001110101101001111010001110100011101G0011101)(101)()()(1456xGxAxGaaaxA第12章 差错控制编码3.编码电路编码电路1D2D3D4D门1门2输入信息码元输出码组 首先，四级移位寄存器清零，三位信息码元到来首
