《差错控制编码_3课件》由会员分享，可在线阅读，更多相关《差错控制编码_3课件（39页珍藏版）》请在金锄头文库上搜索。
1、1,第12章 差错控制编码,12.4 线性分组码,12.2 差错控制编码的基本原理,12.1 概 述,12.3 常用的简单编码,12.5 循环码,2,12.1 概述,产生错码的原因： 乘性干扰引起的码间串扰，由均衡的办法纠正； 加性干扰引起的信噪比降低，由信道编码改善； 按照加性干扰造成错码的分布规律对信道分类： 随机信道：错码随机出现，例如由白噪声引起的错码； 突发信道：错码相对集中出现，例如脉冲干扰； 混合信道：既有随机错码，又有突发错码；,1. 基本概念,差错控制技术的种类： 检错重发；前向纠错；混合差错控制；,3,12.2 差错控制编码的基本原理,1. 纠错编码举例（分组码）,假设发送
2、一个开关的断开、闭合两种状态：,若用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
3、.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”的个数； 码距：两
4、码组对应位取值不同的位数，又称汉明距离； 最小码距(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.
5、 编码增益,12.2.2 纠错编码的基本概念,在保持误码率不变的情况下，采用纠错编码所节省的信噪 比称为编码增益，用分贝形式表示如下：,13,12.3 常用的简单编码,奇偶监督码 ：分为奇监督码和偶监督码两类。 在奇偶监督码中，监督位只有1位，故码率等于k/(k+1)。 偶监督码中，此监督位使码组中“1”的个数为偶数： 式中，a0为监督位，其他位为信息位。 奇监督码中，此监督位使码组中“1”的个数为奇数：,1. 奇偶监督码,检错能力：可以检测奇数个错误,14,12.3 常用的简单编码,2. 二维奇偶监督码,行监督位,列监督位,有可能检测偶数个错误； 对构成矩形四角的错误无法检测； 可以纠正某些
6、错误。,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
7、 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.
8、 监督矩阵,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之间可以
9、方便转换： 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 有关
10、，而与A 无关。 这意味着，S和错码E之间有确定的线性变换关系。若S和E有一一对应关系，则S 将能代表错码位置。,5. 伴随式与错误图样,27,6. 线性分组码的封闭性,12.4 线性分组码,若A1和A2是一种线性码中的两个码组，则(A1+A2)仍是其中一个码组。,由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1 + A2)的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。,28,附：关于监督矩阵和生成矩阵的总结说明,监督矩阵H：确定码组中的信息位和监督位的关系。,典型阵,29,附：关于监督矩阵和生成矩阵的总
11、结说明,生成矩阵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.
12、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 =
13、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”的码组，否则，在经过若干次循环移位后将得
14、到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,【注】：详细解释请参见纠错码原理与方法，王新梅 肖国镇 编著，西安电子科技大学出版社。,
