差错控制编码景春国课件

第9章 差错控制编码,第9章 差错控制编码,9.1 引言 9.2 常用简单分组码 9.3 线性分组码 9.4 循环码,纠错编码的分类 （1）按照信道编码的不同功能，可以将它分为检错码和纠错码。 （2）按照信息码元和监督码元之间的检验关系，可以将它分为线性码和非线性码。 （3）按照信息码元和监督码元之间的约束方式不同，可以将它分为分组码和卷积码。 （4）按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。 （5）按照纠正错误的类型不同，可以将它分为纠正随机错误码和纠正突发错误码。,1. 分组码 分组码一般可用(n,k)表示。其中，k是每组二进制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。 nkr为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元， 组成长为n的码字。 在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n2k个码字未被选用，称为禁用码组。,在分组码中，非零码元的数目称为码字的汉明(Hamming)重量， 简称码重。 例如，码字 10110，码重w=3。 两个等长码组之间相应位取值不同的数目称为这两个码组的汉明(Hamming)距离， 简称码距。 例如 11000 与 10011之间的距离d=3。 码组集中任意两个码字之间距离的最小值称为码的最小距离，用d表示。最小码距是码的一个重要参数， 它是衡量码检错、纠错能力的依据。,纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。 分组码的最小汉明距离d0与检错和纠错能力之间满足下列关系： （1）当码字用于检测错误时，如果要检测e个错误，则 d0 e + 1 ； （2）当码字用于纠正错误时，如果要纠正t个错误，则 d0 2 t + 1 ；,（3）若码字用于纠 t 个错误，同时 检 e个错误时（e t），则 d 0 t + e + 1 。,2. 编码效率 用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。我们定义 编码效率 来衡量 有效性: k / n 其中, k是信息元的个数，n为码长。,对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。 实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。,假设在随机信道中，“1”、“0”发送等概，误码率相同为p，且p«1，则容易证明，在码长为n的码组中正好发生r的错码概率为 。,例如，当码长n=7， p=103时，则有 P7(1)7p=7×10-3 P7(2)21p2=2.1×10-5 P7(3)35p3=3.5×10-8 可见 采用 差错控制编码，若能纠正12个误码，就可使误码率下降几个数量级。,差错控制的作用（效果）,9.4 线性分组码,1 基本概念 分组码 将信息码分组，每组由信码附加若干监督码组成。分组码一般用符号（n ,k）表示，k为每组信码位数；n为每组编码总位数，又称为码长；rn-k为每组中监督码元数。 代数码 建立在代数学基础上的编码称为代数码 线性码 码组的信息码和监督码间约束关系按一组线性代数方程组构成。线性码是一种代数码。 由此可见，将分组码和线性码的概念结合一起，即为线性分组码。,2 线性分组码的编码原理 用 特定的代数方程 描述 信息码 与 监督码 之间的约束关系，称该方程 为 监督方程。 接收端 依照 监督方程式 进行计算，计算结果 称“校正子” ，或 “伴随式” 。 编码的 每个监督位 对应 一个监督方程 和 一个校正子。 对（n , k）码，由rnk个监督方程计算得到的校正子有r位码元，可给出 2r1种 误码图样。 当出现一位误码时，会有2r1种错误位置，由r位校正子取值会确定误码的确切位置，从而能纠错。 显然，当,以（7,4）码讨论线性分组码的构造,即n=7, k=4, r=3，编码后7位码组为 A=(a6, a5, a4, a3, a2, a1, a0), 其中 a6, a5, a4, a3为信息码，a2, a1, a0 为 监督码，必存在 三个 校正子 S2, S1, S0 。 校正子码组 (S2, S1, S0) 与 误码位置 如表9-4所示由表可得出如下结论,时，有可能构造出纠正一位甚至一位以上误码的线性分组码。,当a0、a3、a4或a6位置误码时，S2=1，否则S2=0； 当a1、a3、a5或a6位置误码时，S1=1，否则S1=0； 当a2、a4、a5或a6位置误码时，S0=1，否则S0=0； 表中共列出2317种误码位置，而当S2,S1,S0均为0时，表示无误码。由上述结论可得三个校正子计算方程：,表9-4,S0= a6+a5+a4+a2 , S1= a6+a5+a3+a1 , S2= a6+a4+a3+a0 进而得到下面的方程组形式：,(9.4-7)式 为 监督码生成方程组，在发端可利用该方程组构造(7,4)码。 接收端收到每个码组后，计算出S3、S2和S1，如不全为0，则无误码。 否则，可按表9-4确定误码的位置，并予以纠正。,(9.4-7),3 监督矩阵H和生成矩阵G 将（7 , 4）码的 三个 监督方程式 可重新 改写为如下形式：,上式可以记作：H AT 0 T 或 A H T 0 ，其中,也可用 矩阵形式 来表示：,或 表示为：,监督矩阵 H,这里 G 称为 生成矩阵，利用它 可产生 整个码组：,这时 Q P T，如果在 Q矩阵 的 左边 再加上一个k×k的单位矩阵，就形成了一个新矩阵G：,4 校正子S 设发送组码A，在传输过程中有可能出现误码，这时接收到的码组为B。则收发码组之差为：,则 接收端 利用 接收到的 码组B 计算 校正子： S = B H T = (A+E) H T = A H T + E H T = E H T 因此，校正子仅与E有关，即错误图样与校正子之间有确定的关系。,其中：,6 线性分组码的主要性质如下： （1）任意 两 许用码 之和 仍为 一 许用码 ，也就是说，线性分组码 具有 封闭性； （2）码组间的 最小码距 等于 非零码 的 最小码重,奇偶校验 时 的 监督关系 ，在接收端解码时，实际上就是在计算： S = bn-1+ bn-2+ b1+ b0 若S0，则 无错； 若S1 就认为 有错。,例 设 一 线性码 生成矩阵,确定 ( n , k ) 码 中 的 n 和 k 值，并求出 监督矩阵 H 写出 监督码位 的 关系式 ，以及 该 ( n , k ) 码 的 所有 可用码组 。 确定 该 线性码 的 最小码距 。,解：1 从已知的生成矩阵的行列数可知：n = 6 ，k = 3；,将 生成矩阵 化成 典型矩阵,监督矩阵为：,2 由 H 矩阵 可确定 监督关系：,由,3 由于线性码的最小码距 就是 非0码的 最小码重，所以该分组码的 最小码距 为 d0 = 3。,可得 许用码组 为：,9.5 循环码,循环码 仍然是 一种 线性分组码 。是研究最成熟的一种编码；是建立在严密代数编码理论基础上；纠、检错能力强；编、译码方法 和 电路 都不太复杂。 循环码 除有 线性分组码 一般性质 外，还有 两个主要特征。 1封闭性 循环码的码组中 任意两个 码组之和（模2和）仍为 一 准用码组 。 2循环性 设一个（n,k）循环码 为 （an-1 ，an-2 ，a1 ，a0）， 在 n 次 左移 或 右移 的 循环 中 形成的编码，仍然是 准用循环码 。,在代数理论中，为了便于计算，常用 码多项式 表示 码字。 (n , k) 循环码的码字，其 码多项式 以 降幂顺序排列 为,循环码T=（an-1，an-2，a1，a0）左移一位，变成T(1)=（an-2，an-3， a0，a n-1），用多项式表示有,T(1) (x) an2 x n1 + an3 x n2 + ， + a0 x 1 + a n1 x 0,表中 N6 码组 可表示为 x6 + x5 + x2 + 1,左移 i 位 后的 码多项式 有,码多项式的按模运算性质 整数运算中，若一整数m表示为,则在模n运算下，有mp（模n）。 任一多项式F(x)除以一个 n次多项式N(x) ，可得到商式Q(x)，和一个阶数 小于 n 的余式R(x)，即 ：,码多项式 T(x) 左移i位后的结果。实际上，利用码多项式的 x i T(x) T(i)(x) 模 (x n+1),该式说明，欲使码多项式左移i位，可将被移码多项式T(x)左乘x i，对其取模 (x n+1)即可。 现以简单地左移一位为例,x T(x)= an-1x n + an-2 x n-1 +，+ a1x2 + a0x an-2x n-1+an-3 x n-2+，+a1x2+a0x +an-1x0 = T(1)(x) 模 (x n+1),长度为n的许用码组，必是按模(x n+1)运算的余式。,例 某循环码T=（1100101），将其表示为码多项式，并写出左移2位后的码多项式。,解： T(x)= x 6+ x 5+x 2+1 x 2 T(x) = x 8+ x 7+x4+x 2 = Q (x) (x7+1)+ T(2)(x),则 Q (x)=x+1 T(2)(x)= x4+ x2+x+1 即 T(2) =（0010111）,利用 带余除法,循环码的生成多项式和生成矩阵 循环码中次数最低的码多项式 称为 生成多项式，用g(x)表示。可以证明生成多项式g(x)具有以下特性： （1） g(x)是一个常数项为1的 次多项式； （2） g(x)是 的一个因式； （3）该循环码中其它码多项式都是g(x)的倍式。,g(x)是前k1位为“0”的码组。循环码中，除全“0”码外，连续“0”最多是k1位，否则循环将得到k位为“0”； g(x)是（n，k）码中次数为nk的唯一多项式，否则，两个相加会出现连续“0”多于k位； g(x) 称为 码生成多项式。,一旦 生成多项式 g(x) 确定 后，该循环码的生成矩阵 就可以确定。,显然，上式不符合 形式，所以 此生成矩阵 不是 典型形式。,当 n=7 , k=3 , r=4 , g(x)=x4+x2+x+1 .,可以得到整个码组.,T(x) 可以 被 g(x) 整除 .,循环码的编、译码方法 1、编码过程 首先需要根据给定循环码的参数确定生成多项式g(x) ，然后，利用循环码的编码特点，即所有循环码多项式T(x)都可以被g(x)整除，来定义码多项式T(x)。 下面就将以上各步处理加以解释： （1）用 x nk 乘 m(x)。这一运算实际上是把信息码后附加上（nk）个“0”。 （2）用 g(x) 除 x nk . m(x) , 求 商 Q(x) 和余式r(x) ，也就是,这样我们 就得到了 余式 r(x) 。,例如，（7，3）若选定g(x) = x4+ x2+x+1，m(x)=x2+x,则,上式相当于,2、译码过程 接收端译码要求有二: 检错和纠错。检错为目的，译码较简单,纠错较复杂.,检错译码 任一码组多项式T(x)都应能被生成多项式g(x)整除。 故只需对接收码组R(x)用原生成多项式g(x)去除，若能整除（余数为0），接收码无误码，R(x)=T(x)； 若不能整除（余数不为0），接收码有误码，R(x)T(x)。,纠错译码 为了纠错要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。因此，纠错可按如下步骤进行： (1) 用生成多项式g(x)除接收码组R(x)=T(x)+E(x)，得出余式r(x)，这一步与检错译码相同； (2) 按余式r(x)用查表