第12章差错控制编码课件.ppt

1、1第第12章章 差错控制编码差错控制编码12.4 线性分组码线性分组码 12.2 差错控制编码的基本原理差错控制编码的基本原理 12.1 概概 述述12.3 常用的简单编码常用的简单编码 12.5 循环码循环码212.1 概述概述 产生错码的原因：产生错码的原因：乘性干扰乘性干扰引起的码间串扰，由均衡的办法纠正；引起的码间串扰，由均衡的办法纠正；加性干扰加性干扰引起的信噪比降低，由信道编码改善；引起的信噪比降低，由信道编码改善；按照加性干扰造成错码的分布规律对信道分类：按照加性干扰造成错码的分布规律对信道分类：随机信道：错码随机出现，例如由白噪声引起的错码；随机信道：错码随机出现，例如由白噪声

2、引起的错码；突发信道：错码相对集中出现，例如脉冲干扰；突发信道：错码相对集中出现，例如脉冲干扰；混合信道：既有随机错码，又有突发错码；混合信道：既有随机错码，又有突发错码；1.基本概念基本概念 差错控制技术的种类：差错控制技术的种类：检错重发；前向纠错；混合差错控制；检错重发；前向纠错；混合差错控制；312.2 差错控制编码的基本原理差错控制编码的基本原理1.纠错编码举例（分组码）纠错编码举例（分组码）假设发送一个开关的断开、闭合两种状态假设发送一个开关的断开、闭合两种状态：01断开断开闭合闭合若用若用1个个bit表示，如下表：表示，如下表：若出现错码，接收端无法发现。若出现错码，接收端无法发

3、现。12.2.1.纠错编码的基本原理纠错编码的基本原理412.2.1 纠错编码的基本原理纠错编码的基本原理1.纠错编码举例（分组码）纠错编码举例（分组码）假设发送一个开关的断开、闭合两种状态假设发送一个开关的断开、闭合两种状态：00110110断开断开闭合闭合禁码禁码若用若用2个个bit表示，如下表：表示，如下表：若接收端出现禁码，则说明检测到错误；若接收端出现禁码，则说明检测到错误；但只能检测到但只能检测到1bit的错码，不能纠错；的错码，不能纠错；512.2.1 纠错编码的基本原理纠错编码的基本原理1.纠错编码举例（分组码）纠错编码举例（分组码）假设发送一个开关的断开、闭合两种状态假设发送

4、一个开关的断开、闭合两种状态：000111001010011100101110断开断开闭合闭合禁码禁码若用若用3个个bit表示，如下表：表示，如下表：若接收端出现禁码，则说明检测到错误；若接收端出现禁码，则说明检测到错误；能检测到不多于能检测到不多于2bit的错码，且能够纠一个的错码，且能够纠一个bit的错码；的错码；62.分组码分组码12.2.2 纠错编码的基本概念纠错编码的基本概念1.信息码元与监督码元信息码元与监督码元 分组码的一般结构分组码的一般结构分组码分组码：将：将r个监督码元附加在由个监督码元附加在由k个信息码元组成的信息码组个信息码元组成的信息码组上，构成一个有纠错功能的独立码

5、组，并且上，构成一个有纠错功能的独立码组，并且监督码元仅与本码监督码元仅与本码组中的信息码组有关组中的信息码组有关，这种按组进行编码的方法称为分组码。，这种按组进行编码的方法称为分组码。7 分组码分组码 信息位信息位 监督位，分组码符号：监督位，分组码符号：(n,k)分组码序列的参数分组码序列的参数n 编码序列中编码序列中总码元总码元数量；数量；k 编码序列中编码序列中信息码元信息码元数量；数量；r 编码序列中编码序列中监督码元监督码元数量；数量；k/n 码率码率；(n-k)/k=r/k 冗余度冗余度；2.分组码分组码12.2.2 纠错编码的基本概念纠错编码的基本概念1.信息码元与监督码元信息

6、码元与监督码元84.码重、码距与最小码距码重、码距与最小码距 码重码重：码组内：码组内“1”的个数；的个数；码距码距：两码组对应位取值不同的位数，又称：两码组对应位取值不同的位数，又称汉明距离汉明距离；最小码距最小码距(d0)：码距的最小值；：码距的最小值；3.许用码组与禁用码组许用码组与禁用码组 总的码组数总的码组数：2n；许用码组的数目许用码组的数目：2k；禁用码组的数目禁用码组的数目：2n 2k；12.2.2 纠错编码的基本概念纠错编码的基本概念95.最小码距最小码距d0与纠错能力的关系与纠错能力的关系12.2.2 纠错编码的基本概念纠错编码的基本概念 检测检测e个错码：个错码：0123

7、BA汉明距离汉明距离ed0码距等于码距等于3的两个码组的两个码组 0de+1105.最小码距最小码距d0与纠错能力的关系与纠错能力的关系12.2.2 纠错编码的基本概念纠错编码的基本概念 纠正纠正t个错码：个错码：BtA汉明距离汉明距离012345td0码距等于码距等于5的两个码组的两个码组0d2t+1115.最小码距最小码距d0与纠错能力的关系与纠错能力的关系12.2.2 纠错编码的基本概念纠错编码的基本概念 纠正纠正t个错码，同时检测个错码，同时检测e个错误：个错误：0de+t+1(e t)AB1tt汉明距离汉明距离e码距等于码距等于(e+t+1)的两个码组的两个码组 基本思路：错少时，检

8、测到并纠过来；错多，只检测出来基本思路：错少时，检测到并纠过来；错多，只检测出来（可能会要求发端重新发一遍）；（可能会要求发端重新发一遍）；126.编码增益编码增益12.2.2 纠错编码的基本概念纠错编码的基本概念bbbbdBdB0000uBuBEEEEG=-(dB)G=-(dB)nnnn在保持在保持误码率不变误码率不变的情况下，采用纠错编码所的情况下，采用纠错编码所节省的信噪节省的信噪比比称为编码增益，用分贝形式表示如下：称为编码增益，用分贝形式表示如下：1312.3 常用的简单编码常用的简单编码奇偶监督码奇偶监督码：分为奇监督码和偶监督码两类。：分为奇监督码和偶监督码两类。在奇偶监督码中，

9、在奇偶监督码中，监督位只有监督位只有1位位，故码率等于，故码率等于k/(k+1)。偶监督码偶监督码中，此监督位使码组中中，此监督位使码组中“1”的个数为偶数：的个数为偶数：式中，式中，a0为监督位为监督位，其他位为信息位。，其他位为信息位。奇监督码奇监督码中，此监督位使码组中中，此监督位使码组中“1”的个数为奇数：的个数为奇数：1.奇偶监督码奇偶监督码n 1n 20aa=0an 1n 20aa=1a检错能力：可以检错能力：可以检测奇数个错误检测奇数个错误1412.3 常用的简单编码常用的简单编码2.二维奇偶监督码二维奇偶监督码111n-1n-21222n-1n-21m-1m-1m-1n-1n-

10、1n102n-21-210m-100aaaaaaaaacaccaca行监督位行监督位列监督位列监督位 有可能检测偶数个错有可能检测偶数个错误误；对构成对构成矩形四角矩形四角的错的错误无法检测；误无法检测；可以可以纠正某些错误纠正某些错误。1512.3 常用的简单编码常用的简单编码循环码的一种，循环码的一种，12.5节将介绍循环码节将介绍循环码3.循环冗余校验码循环冗余校验码(CRC)1612.4 线性分组码线性分组码1.基本概念基本概念v 分组码分组码:将将r个监督码元附加在由个监督码元附加在由k个信息码元组成的信息码组个信息码元组成的信息码组上，构成一个有纠错功能的独立码组，并且上，构成一个

11、有纠错功能的独立码组，并且监督码元仅与本码组监督码元仅与本码组中的信息码组有关中的信息码组有关；v 线性分组码线性分组码：监督位和信息位的关系由：监督位和信息位的关系由线性代数方程线性代数方程决定；决定；v 汉明码汉明码:一种能一种能纠正一个错码且编码效率较高纠正一个错码且编码效率较高的的线性分组码线性分组码；172.线性分组码构造举例线性分组码构造举例:(7,4)汉明码汉明码 设分组码（设分组码（n,4）。为了纠正一位错误，由）。为了纠正一位错误，由要求要求 ，则取，则取 ，用，用a6 a5 a4 a3 a2 a1 a0表表示这示这7个码元，个码元，a2 a1 a0为监督位，用为监督位，用S

12、1 S2 S3表示校正子，表示校正子，规规定定校正子和错码位置的关系如下表：校正子和错码位置的关系如下表：12.4 线性分组码线性分组码r2-1nr=3,n=7S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错无错r3182.线性分组码构造举例线性分组码构造举例:(7,4)汉明码汉明码 分析上表，仅当一错码位置在分析上表，仅当一错码位置在a2,a4,a5 或或 a6时，校正子时，校正子S1为为1，否则为，否则为0，则，则a2,a4,a5 和和 a6构成构成偶监督关系偶监督关系：12.4 线性分组码线性

13、分组码16542S=aaaa 同理：同理：654265316430aaaa=0aaaa=0aaaa=026531S=aaaa36430S=aaaa265416530643a=aaaa=aaaa=aaa发发送送端端1912.4 线性分组码线性分组码S1 S2 S3错码位置错码位置S1 S2 S3错码位置错码位置001010100011a0a1a2a3101110111000a4a5a6无错无错 发送端，计算加入监督位：发送端，计算加入监督位：根据下表确定错码位置：根据下表确定错码位置：接收端，计算校正子：接收端，计算校正子：265416530643a=aaaa=aaaa=aaa165422653

14、136430S=aaaaS=aaaaS=aaaa2.线性分组码构造举例线性分组码构造举例:(7,4)汉明码汉明码202.线性分组码构造举例线性分组码构造举例:(7,4)汉明码汉明码12.4 线性分组码线性分组码信息位信息位a6 a5 a4a3监督位监督位a2 a1 a0信息位信息位a6 a5 a4a3监督位监督位a2 a1 a000000001001000110100010101100111000011101110110101011000100010011010101111001101111011111111000100010010101001110d=3rrk2-1-r=n2-1可纠正可纠正

15、1个错误个错误v最小码距最小码距v编码效率编码效率时，r 1k/n1汉明码是一种高效码汉明码是一种高效码213.监督矩阵监督矩阵12.4 线性分组码线性分组码6542653164331042052010 a0 a0 a0 a01 a+1 a+1 a+1 a+=01 a+1 a+1 a+1 a+=01 a+1 a+1 a+1 a=0a0 a0 a0 a0 a 6543210aaa111010001101010a=010110010aaa模模2加加或TTTH A=0A H=01110100H=110101010110010=0006543210A=a a a a a a a监督矩阵监督矩阵6542

16、65316430aaaa=0aaaa=0aaaa=0223.监督矩阵监督矩阵12.4 线性分组码线性分组码监督矩阵：监督矩阵：确定码组中的信息位和监督位的关系。确定码组中的信息位和监督位的关系。v H 的的行数行数就是监督关系式的数目，即监督位数就是监督关系式的数目，即监督位数 r；v H 的的每行中每行中“1”的位置的位置表示相应的码元参与监督关系；表示相应的码元参与监督关系；v H 矩阵的各行应该是矩阵的各行应该是线性无关线性无关的；的；v 上例中的上例中的H 可以分成两部分：可以分成两部分：r1110 100H=1101 010=PI1011 001 式中，式中，P 为为r k阶矩阵阶矩

17、阵，Ir为为 r r 阶单位方阵阶单位方阵，具有，具有PIr形式的形式的H矩阵称为矩阵称为典型阵典型阵。1110100H=1101010101100123k1000 1110100 110G=I Q=0010 1010001 0114.生成矩阵生成矩阵12.4 线性分组码线性分组码65432106543A=a a a a a a a=a a a aG6251403aa1110aa=1101a1011aa21065436543111110a a a=a a a a=a a a aQ101011Q=PT265416530643a=aaaa=aaaa=aaaPG：生成矩阵：生成矩阵244.生成矩阵生

18、成矩阵12.4 线性分组码线性分组码 生成矩阵生成矩阵G的性质：的性质：v 具有具有IkQ形式形式的生成矩阵称为的生成矩阵称为典型生成矩阵典型生成矩阵。典型。典型G和典型和典型H之间可以方便转换：之间可以方便转换：H=PIr，Q=PT；v 由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位的位置不变，监督中，信息位的位置不变，监督位附加于其后。这种形式的码组称为位附加于其后。这种形式的码组称为系统码系统码。v 矩阵矩阵G的各行也必须是的各行也必须是线性无关线性无关的。的。v G的各行本身就是一个码组，如果已有的各行本身就是一个码组，如果已有k个线性无关的码组，个线性无关的码组，则可以

19、将其用来作为生成矩阵则可以将其用来作为生成矩阵G，并由它生成其余码组，并由它生成其余码组。255.伴随式与错误图样伴随式与错误图样12.4 线性分组码线性分组码 错误图样错误图样E：v 发送码组发送码组A是一个是一个n列的行矩阵：列的行矩阵：v 接收码组接收码组R是一个是一个n列的行矩阵：列的行矩阵：v 错误图样（错误矩阵）：发送码组和接收码组之差错误图样（错误矩阵）：发送码组和接收码组之差若若ei=0，表示该码元未错；，表示该码元未错；若若ei=1，表示该码元为错码，表示该码元为错码n-1n-210A=aaa an-1 n-21 0R=r rrrn-1n-210R-A=E=eee e当当ii

20、iii0,b=ae=1,ba2612.4 线性分组码线性分组码 伴随式（校正子矩阵）：伴随式（校正子矩阵）：TS=R HTA H=0 当当H确定后，上式中确定后，上式中S只与只与E 有关有关，而与，而与A 无关。无关。这意这意味着，味着，S和错码和错码E之间有确定的线性变换关系。之间有确定的线性变换关系。若若S和和E有一有一一对应关系，则一对应关系，则S 将能代表错码位置将能代表错码位置。R=A+ETS=E H5.伴随式与错误图样伴随式与错误图样276.线性分组码的封闭性线性分组码的封闭性12.4 线性分组码线性分组码 若若A1和和A2是一种线性码中的两个码组，则是一种线性码中的两个码组，则(

21、A1+A2)仍是仍是其中一个码组。其中一个码组。由于线性码具有封闭性，所以两个码组由于线性码具有封闭性，所以两个码组(A1和和A2)之间的之间的距离（即对应位不同的数目）必定是另一个码组距离（即对应位不同的数目）必定是另一个码组(A1+A2)的的重量（即重量（即“1”的数目）。因此，的数目）。因此，码的最小距离就是码的最码的最小距离就是码的最小重量（除全小重量（除全“0”码组外）码组外）。TT12AH =0,A H =0TTT1212AH +A H =(A+A)H =028附附：关于监督矩阵和生成矩阵的总结说明关于监督矩阵和生成矩阵的总结说明 监督监督矩阵矩阵H：确定码组中的信息位和监督位的关

22、系。确定码组中的信息位和监督位的关系。6543210aaa111010001101010a=010110010aaa或TTTH A=0A H=0r1110 100H=1101 010=PI1011 001典型阵典型阵29附附：关于监督矩阵和生成矩阵的总结说明关于监督矩阵和生成矩阵的总结说明65432106543A=a a a a a a a=a a a aG生成矩阵生成矩阵G：k1000 1110100 110G=I Q=0010 1010001 011典型生成矩阵：对应系统码典型生成矩阵：对应系统码【注注】：典型生成矩阵和典型监督矩阵之间可以方便的转换：典型生成矩阵和典型监督矩阵之间可以方便

23、的转换：Q=PT。3012.5 循环码循环码12.5.1 循环码的基本原理循环码的基本原理v 循环码的基本概念：循环码的基本概念：循环码是循环码是线性分组码线性分组码的一种，除了具有线性码的一般性的一种，除了具有线性码的一般性质外，还具有质外，还具有循环性循环性，即任一码组循环一位后仍然是该编码，即任一码组循环一位后仍然是该编码中的一个码组，举例如下：中的一个码组，举例如下：码组码组编号编号信息位信息位监督位监督位码组码组编号编号信息位信息位监督位监督位a6 a5 a4a3 a2 a1 a0a6 a5 a4a3 a2 a1 a0123400000101001100000111111010015

24、67810010111011110111100010100103112.5 循环码循环码12.5.1 循环码的基本原理循环码的基本原理v 循环码的多项式表示法：循环码的多项式表示法：一个长度为一个长度为n的码组的码组(an-1 an-2 a0)可以表示成：可以表示成：n-1n-2n-1n-210T(x)=a x+ax+a x+a【注注】：式中：式中x 的值没有任何意义的值没有任何意义，仅用它的，仅用它的幂代表码元的位置幂代表码元的位置。例：码组例：码组1 1 0 0 1 0 1可以表示为：可以表示为：65432652T(x)=1+1 x+0 x+0 x+1 x+0 x+1=x+x+x+1x x

25、3212.5 循环码循环码12.5.1 循环码的基本原理循环码的基本原理v 码多项式的按模运算：码多项式的按模运算：若任意一个多项式若任意一个多项式F(x)被一个被一个n次多项式次多项式N(x)除除，得到商，得到商式式Q(x)和一个和一个次数小于次数小于n的余式的余式R(x)，即：，即：例如：例如：模模模3342235423x1(x+1)x+x+1x+x+1(x+1)x+x+x+1x+1(x+1)模F(x)=N(x)Q(x)+R(x),F(x)R(x)(N(x)3312.5.1 循环码的基本原理循环码的基本原理v 循环码生成矩阵循环码生成矩阵G的构造：的构造：循环码中，一个循环码中，一个(n,

26、k)码有码有2k个不同的码组。若用个不同的码组。若用g(x)表示其表示其中中前前(k-1)位皆为位皆为“0”的码组，则的码组，则g(x)，xg(x)，x2g(x)，xk-1 g(x)都是码组，而且这都是码组，而且这k个码组是线性无关的。因此它们可以用个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵来构成此循环码的生成矩阵G：k-1k-2xg(x)xg(x)G(x)=xg(x)g(x)3412.5.1 循环码的基本原理循环码的基本原理v 循环码生成矩阵循环码生成矩阵G的构造举例的构造举例 上表中的编码为上表中的编码为(7,3)循环码循环码，n=7,k=3,n k=4，其，其中唯一的一个

27、中唯一的一个(n k)=4次码多项式代表的码组是第二码组次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为：，与它对应的码多项式，即生成多项式，为：42g(x)=x+x+x+1码组码组编号编号信息位信息位监督位监督位码组码组编号编号信息位信息位监督位监督位a6 a5 a4a3 a2 a1 a0a6 a5 a4a3 a2 a1 a012340000010100110000011111101001567810010111011110111100010100103512.5.1 循环码的基本原理循环码的基本原理1011100G=01011100010111 生成矩阵生

28、成矩阵G：2x g(x)G(x)=xg(x)g(x)265465422654654x g(x)T(x)=a a a G(x)=a a a xg(x)g(x)=a x g(x)+a xg(x)+a g(x)=(a x+a x+a)g(x)或或 所有码多项式所有码多项式T(x)都能够被都能够被g(x)整除整除，而且任意一个次，而且任意一个次数数不大于不大于(k 1)的多项式乘的多项式乘g(x)都是码多项式。都是码多项式。42g(x)=x+x+x+1非典型阵非典型阵v 循环码生成矩阵循环码生成矩阵G的构造举例的构造举例 3612.5.1 循环码的基本原理循环码的基本原理1011100G=010111

29、00010111 生成矩阵生成矩阵G：2x g(x)G(x)=xg(x)g(x)或或42g(x)=x+x+x+1非典型阵非典型阵 画成画成典型生成矩阵典型生成矩阵G：1001011G=01011100010111v 循环码生成矩阵循环码生成矩阵G的构造举例的构造举例 3712.5.1 循环码的基本原理循环码的基本原理v 生成多项式生成多项式g(x)的补充说明的补充说明 w在循环码中除全在循环码中除全“0”码组外，再没有连续码组外，再没有连续k位均为位均为“0”的码组，的码组，否则，在经过若干次循环移位后将得到否则，在经过若干次循环移位后将得到k位信息位全为位信息位全为“0”，但，但监督位不全为

30、监督位不全为“0”的一个码组。这在线性码中显然是不可能的。的一个码组。这在线性码中显然是不可能的。因此，因此，g(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n-k)次多项式次多项式；w g(x)还是这种还是这种(n,k)码中次数为码中次数为(n k)的唯一一个多项式的唯一一个多项式。因。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于码组，且此码组多项式的次数将小于(n k)，即连续，即连续“0”的个的个数多于数多于(k 1)。显然，这是与前面的结论矛盾的。显然，这是与前面的结论矛盾的。

31、3812.5.1 循环码的基本原理循环码的基本原理3.如何寻找任如何寻找任一一(n,k)循环码的生成多项式循环码的生成多项式 结论：生成多项式结论：生成多项式g(x)应该是应该是(xn+1)的一个因子。的一个因子。例：例：(x7+1)可以分解为：可以分解为：7323x+1=(x+1)(x+x+1)(x+x+1)或43242g(x)=x+x+x+1 x+x+x+1(7,3)或323g(x)=x+x+1 x+x+1(7,4)39附附：矢量线性相关的定义矢量线性相关的定义 设设v1，v2，vk是线性空间是线性空间V中的一组非全零矢量，当中的一组非全零矢量，当且仅当存在有一组且仅当存在有一组不全为零不全为零的标量的标量c1，c2，ck使：使：1122kkic v+c v+c v=0(cF;i=1,2,k)若在若在GF(2)上的矢量，则线性相关的定义：上的矢量，则线性相关的定义：1122kkic v+c v+c v=0(cGF(2);i=1,2,k)GF(2)：该域中只有两个元素：该域中只有两个元素0,1【注注】：详细解释请参见：详细解释请参见纠错码纠错码原理与方法原理与方法，王新梅王新梅 肖肖国镇国镇 编著，西安电子科技大学出版社。编著，西安电子科技大学出版社。