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

1,第12章 差错控制编码,12.4 线性分组码,12.2 差错控制编码的基本原理,12.1 概 述,12.3 常用的简单编码,12.5 循环码,2,12.1 概述,产生错码的原因：乘性干扰引起的码间串扰，由均衡的办法纠正；加性干扰引起的信噪比降低，由信道编码改善；按照加性干扰造成错码的分布规律对信道分类：随机信道：错码随机出现，例如由白噪声引起的错码；突发信道：错码相对集中出现，例如脉冲干扰；混合信道：既有随机错码，又有突发错码；,1.基本概念,差错控制技术的种类：检错重发；前向纠错；混合差错控制；,3,12.2 差错控制编码的基本原理,1.纠错编码举例（分组码）,假设发送一个开关的断开、闭合两种状态：,若用1个bit表示，如下表：,若出现错码，接收端无法发现。,12.2.1.纠错编码的基本原理,4,12.2.1 纠错编码的基本原理,1.纠错编码举例（分组码）,假设发送一个开关的断开、闭合两种状态：,若用2个bit表示，如下表：,若接收端出现禁码，则说明检测到错误；但只能检测到1bit的错码，不能纠错；,5,12.2.1 纠错编码的基本原理,1.纠错编码举例（分组码）,假设发送一个开关的断开、闭合两种状态：,若用3个bit表示，如下表：,若接收端出现禁码，则说明检测到错误；能检测到不多于2bit的错码，且能够纠一个bit的错码；,6,2.分组码,12.2.2 纠错编码的基本概念,1.信息码元与监督码元,分组码的一般结构,分组码：将r个监督码元附加在由k个信息码元组成的信息码组上，构成一个有纠错功能的独立码组，并且监督码元仅与本码组中的信息码组有关，这种按组进行编码的方法称为分组码。,7,分组码 信息位 监督位，分组码符号：(n,k)分组码序列的参数n 编码序列中总码元数量；k 编码序列中信息码元数量；r 编码序列中监督码元数量；k/n 码率；(n-k)/k=r/k 冗余度；,2.分组码,12.2.2 纠错编码的基本概念,1.信息码元与监督码元,8,4.码重、码距与最小码距,码重：码组内“1”的个数；码距：两码组对应位取值不同的位数，又称汉明距离；最小码距(d0)：码距的最小值；,3.许用码组与禁用码组,总的码组数：2n；许用码组的数目：2k；禁用码组的数目：2n 2k；,12.2.2 纠错编码的基本概念,9,5.最小码距d0与纠错能力的关系,12.2.2 纠错编码的基本概念,检测e个错码：,10,5.最小码距d0与纠错能力的关系,12.2.2 纠错编码的基本概念,纠正t个错码：,11,5.最小码距d0与纠错能力的关系,12.2.2 纠错编码的基本概念,纠正t个错码，同时检测e个错误：,基本思路：错少时，检测到并纠过来；错多，只检测出来（可能会要求发端重新发一遍）；,12,6.编码增益,12.2.2 纠错编码的基本概念,在保持误码率不变的情况下，采用纠错编码所节省的信噪比称为编码增益，用分贝形式表示如下：,13,12.3 常用的简单编码,奇偶监督码：分为奇监督码和偶监督码两类。在奇偶监督码中，监督位只有1位，故码率等于k/(k+1)。偶监督码中，此监督位使码组中“1”的个数为偶数：式中，a0为监督位，其他位为信息位。奇监督码中，此监督位使码组中“1”的个数为奇数：,1.奇偶监督码,检错能力：可以检测奇数个错误,14,12.3 常用的简单编码,2.二维奇偶监督码,行监督位,列监督位,有可能检测偶数个错误；对构成矩形四角的错误无法检测；可以纠正某些错误。,15,12.3 常用的简单编码,循环码的一种，12.5节将介绍循环码,3.循环冗余校验码(CRC),16,12.4 线性分组码,1.基本概念 分组码:将r个监督码元附加在由k个信息码元组成的信息码组上，构成一个有纠错功能的独立码组，并且监督码元仅与本码组中的信息码组有关；线性分组码：监督位和信息位的关系由线性代数方程决定；汉明码:一种能纠正一个错码且编码效率较高的线性分组码；,17,2.线性分组码构造举例:(7,4)汉明码 设分组码（n,4）。为了纠正一位错误，由要求，则取，用a6 a5 a4 a3 a2 a1 a0表示这7个码元，a2 a1 a0为监督位，用S1 S2 S3表示校正子，规定校正子和错码位置的关系如下表：,12.4 线性分组码,18,2.线性分组码构造举例:(7,4)汉明码 分析上表，仅当一错码位置在a2,a4,a5 或 a6时，校正子S1为1，否则为0，则a2,a4,a5 和 a6构成偶监督关系：,12.4 线性分组码,同理：,发送端,19,12.4 线性分组码,发送端，计算加入监督位：,根据下表确定错码位置：,接收端，计算校正子：,2.线性分组码构造举例:(7,4)汉明码,20,2.线性分组码构造举例:(7,4)汉明码,12.4 线性分组码,可纠正1个错误,最小码距,编码效率,汉明码是一种高效码,21,3.监督矩阵,12.4 线性分组码,模2加,监督矩阵,22,3.监督矩阵,12.4 线性分组码,监督矩阵：确定码组中的信息位和监督位的关系。H 的行数就是监督关系式的数目，即监督位数 r；H 的每行中“1”的位置表示相应的码元参与监督关系；H 矩阵的各行应该是线性无关的；上例中的H 可以分成两部分：,式中，P 为r k阶矩阵，Ir为 r r 阶单位方阵，具有PIr形式的H矩阵称为典型阵。,23,4.生成矩阵,12.4 线性分组码,Q=PT,P,G：生成矩阵,24,4.生成矩阵,12.4 线性分组码,生成矩阵G的性质：具有IkQ形式的生成矩阵称为典型生成矩阵。典型G和典型H之间可以方便转换：H=PIr，Q=PT；由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为系统码。矩阵G的各行也必须是线性无关的。G的各行本身就是一个码组，如果已有k个线性无关的码组，则可以将其用来作为生成矩阵G，并由它生成其余码组。,25,5.伴随式与错误图样,12.4 线性分组码,错误图样E：,发送码组A是一个n列的行矩阵：接收码组R是一个n列的行矩阵：错误图样（错误矩阵）：发送码组和接收码组之差：若ei=0，表示该码元未错；若ei=1，表示该码元为错码。,26,12.4 线性分组码,伴随式（校正子矩阵）：,当H确定后，上式中S只与E 有关，而与A 无关。这意味着，S和错码E之间有确定的线性变换关系。若S和E有一一对应关系，则S 将能代表错码位置。,5.伴随式与错误图样,27,6.线性分组码的封闭性,12.4 线性分组码,若A1和A2是一种线性码中的两个码组，则(A1+A2)仍是其中一个码组。,由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1+A2)的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。,28,附：关于监督矩阵和生成矩阵的总结说明,监督矩阵H：确定码组中的信息位和监督位的关系。,典型阵,29,附：关于监督矩阵和生成矩阵的总结说明,生成矩阵G：,典型生成矩阵：对应系统码,【注】：典型生成矩阵和典型监督矩阵之间可以方便的转换：Q=PT。,30,12.5 循环码,12.5.1 循环码的基本原理,循环码的基本概念：循环码是线性分组码的一种，除了具有线性码的一般性质外，还具有循环性，即任一码组循环一位后仍然是该编码中的一个码组，举例如下：,31,12.5 循环码,12.5.1 循环码的基本原理,循环码的多项式表示法：一个长度为n的码组(an-1 an-2 a0)可以表示成：,【注】：式中x 的值没有任何意义，仅用它的幂代表码元的位置。,例：码组1 1 0 0 1 0 1可以表示为：,32,12.5 循环码,12.5.1 循环码的基本原理,码多项式的按模运算：若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即：例如：,33,12.5.1 循环码的基本原理,循环码生成矩阵G的构造：循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，xg(x)，x2g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G：,34,12.5.1 循环码的基本原理,循环码生成矩阵G的构造举例,上表中的编码为(7,3)循环码，n=7,k=3,n k=4，其中唯一的一个(n k)=4次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为：,35,12.5.1 循环码的基本原理,生成矩阵G：,或,所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。,非典型阵,循环码生成矩阵G的构造举例,36,12.5.1 循环码的基本原理,生成矩阵G：,或,非典型阵,画成典型生成矩阵G：,循环码生成矩阵G的构造举例,37,12.5.1 循环码的基本原理,生成多项式g(x)的补充说明,在循环码中除全“0”码组外，再没有连续k位均为“0”的码组，否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(n-k)次多项式；g(x)还是这种(n,k)码中次数为(n k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的。,38,12.5.1 循环码的基本原理,3.如何寻找任一(n,k)循环码的生成多项式,结论：生成多项式g(x)应该是(xn+1)的一个因子。,例：(x7+1)可以分解为：,39,附：矢量线性相关的定义,设v1，v2，vk是线性空间V中的一组非全零矢量，当且仅当存在有一组不全为零的标量c1，c2，ck使：,若在GF(2)上的矢量，则线性相关的定义：,GF(2)：该域中只有两个元素0,1,【注】：详细解释请参见纠错码原理与方法，王新梅 肖国镇 编著，西安电子科技大学出版社。,