线性码及其应用.ppt

定义2码字X x1x2 xn的汉明重量是码字中非零码元的位数 用W X 表示 例如 W 1001 2 W 11010 3 由定义1和定义2知D X Y W X Y 定义3一组码字C包括若干码字C1 C2 Cn 所有这些码字相互间码距的最小的数值 称为该码组的最小码距d 简称码距d d minD Ci Cj minW Ci Cj i j 1 2 N i j 例如C 0111100 1011011 1101001 d 3 说明 为尽量避免码字受到干扰而出错 总是希望码字间有尽可能大的距离 最小码距代表了一个码组中最不利的情况 从安全出发 往往选用最小码距来分析码的检错纠错能力 第二节检错能力与纠错能力 1 码距为1时 能保证码字的唯一性 但不能检错和纠错 2 码距为2时 能检查出一位错误 但无法纠错 3 码距为3时 能检查出一位或两位错误 并且还可纠正一位错误 例 设码长为3 取000 111作为码字 其余为禁用码字 如接收端收到001 它是禁用码字 知道出错 由于001与000相差一个码元 与111相差两个码元 根据最大似然译码原则将001译为000 最大似然译码原则 当Ci为若干个发送码字中的一个 R为接收码字 若条件概率P R Ci 为最大 则认为码字Ci就是发送码字 结论 一 要检出码字中任意e个码元错误 必须使最小码距d满足d e 1 二 要纠正码字中任意t个码元错误 必须使最小码距d满足d 2t 1 三 要纠正码字中任意t个码元错误 并同时发现e个错误 e t 则最小码距d满足d t e 1 当码距d 2t 1时 码长为n的一个许用码字中可纠正的错误类型总数为 许用码字数Q 2 n 第三节寄偶监督码 寄偶监督码是最简单的一种检错码 是目前计算机系统用得最多的一种差错控制码 寄偶监督码的编码方式 是在n 1位信息元 Cn 1 Cn 2 C1 后面附加1位监督元C0 使得码字中 1 的数目保持为奇数或偶数 奇数监督 对应的监督方程为 Cn 1 Cn 2 C1 C0 1 偶数监督 对应的监督方程为 Cn 1 Cn 2 C1 C0 0 P169表5 1列出了用七位ASCII码表示的十个数字符号的寄偶校验位 判别方法 接收端收到编好的寄偶监督码后 用与发送端相同的规则检查 1 的个数是否仍保持奇数或偶数 从而确定传输过程中是否有错误 特点 能发现一位码元或所有奇数位码元出错的情况 但不能纠正任何错误以及发现偶数位码元错误 简单寄偶码的效率高 n 1 n 寄偶监督码的实现 1 硬件法 采用模二相加的异或电路 C1 C2 C3 C4 C5 C6 C7 C0 C0 2 软件法 见P170图5 6的流程图 为了改进差错控制性能 引入二维寄偶监督码 水平 垂直寄偶监督码 方阵码 纵横寄偶监督码 就是在水平方向进行寄偶监督的同时 再按垂直方向进行一次寄偶监督 如P171图5 7 图5 8 二维水平 斜向寄偶监督码 二维寄偶监督码特点 能检出每一行或每一列的两位或偶数位错误 可以用水平 垂直两个方向上的监督码元 来确定单个错误码元的位置 从而进行纠正 但它无法检出四个错误码元构成矩形 或平行四边形 四个顶点的错误图样 也无法检出双向成偶的错误图样 第五节监督矩阵与生成矩阵 设有待编码的消息序列为M m1m2 mk 对应的信息元序列 X1X2 Xk 为了进行差错控制 我们按线性代数关系来添加监督码元序列 Xk 1Xk 2 Xn 则称此码长n 信息元数k的码字序列 X1X2 Xk Xk 1Xk 2 Xn 为线性分组码 记为 n k 如果其最小码距为d 也可记为 n k d 或 n k d 其中监督元数r n k 用线性的监督方程组来表示 a11X1 a12X2 a1kXk Xk 1 a21X1 a22X2 a2kXk Xk 2 ar1X1 ar2X2 arkXk Xn 式中加号均表示模二加 或 a11X1 a12X2 a1kXk Xk 1 0 0 0 a21X1 a22X2 a2kXk 0 Xk 2 0 0 ar1X1 ar2X2 arkXk 0 0 Xn 0 若用矩阵表示 则 a11a12 a1k10 0 a21a22 a2k01 0 ar1ar2 ark00 1 X1X2 XkXk 1 Xk 0 简写为HX T 0 T H 监督矩阵 X T 行矩阵X X1X2 Xn 的转置矩阵 例5 1一个 7 3 码的信息元 X1X2X3 和监督元 X4X5X6X7 间的监督方程组为 X1 X3 X4 0X1 X2 X3 X5 0X1 X2 X6 0X2 X3 X7 0 求出对应信息元的监督元 解 列出各种信息元组合 依据监督方程组求出对应监督元如下表所示 信息元 监督元 编成码字 000001010011100101110111 00001101011110101110001110010100 00000000011101010011101110101001110101001111010011110100 还可以写出监督矩阵形式 HX 011000 1110100 1100010 0110001 T X1X2X3X4X5X6X7 0000 说明 1 编码中 往往在多种可能的码字排列中 选取少量的许用码字 2 任意两个码字逐位模二加 可以得到另一个码字 这种特性叫做封闭性 它是线性码的重要特点 3 由封闭性知 两个码字的码距 就是另一个码字的码重 所以 该组码字的最小码距就等于码字中码的最小重量 4 监督矩阵H A Ir A为rxk阶矩阵 Ir为r阶单位阵 r n k H起监督是否是码字的作用 5 在线性码组中 如果有一个码重为W的码字 则在H中必有与之相应的W列相加等于0 固称此W列线性相关 如果要求码组的最小码距为d 即要求码字的最小码重为d 则H中至少有d列相加之和为0 任意小于或等于d 1列线性无关 例如 例题中0011101是码字 码重为4 它应该满足监督方程组 即 HX T 011000 1110100 1100010 0110001 0011101 1101 1000 0100 0001 0000 下面讨论一下监督矩阵H与生成矩阵G的关系 HX T A Ir X1X2 Xk Xk 1Xk 2 Xn 0 T 或 A X1X2 Xk Ir Xk 1Xk 2 Xk 0 T 则 Xk 1Xk 2 Xn A X1X2 Xk A mk m1m2 令 X1X2 Xk Ik mk m1m2 X1X2 Xk Ik A m1m2 mk 两边取转置得 X MG X M为行矩阵的形式 G Ik A T 称为生成矩阵 利用G可由M直接生成码X 以前面的例题为例 知道A 可求出 A T 11001111101 Ik 00010001 设有信息元组m1m2m3 101则由X MG求出对应码字 1010011 G 100111001001110011101 可以观察G的三行分别是例5 1求出的第5 3 2个码字 这三个码字组成的G 能使求出的码字信息元在前 监督元在后 即构成的是系统码 如选其他三个码字组合成G 得出的码字信息元与监督元将是交错排列 即非系统码 由H A In k G Ik A T 则HG A In k A A 0 T Ik A 由这个等式可知G的每一行都是一个码字 生成矩阵G和监督矩阵H的关系 一个 n k 码字的监督矩阵H 正好是另一个 n n k n r 码字的生成矩阵G 反之亦然 我们称 n n k 码是 n k 码的对偶码 可以用下面这个图反映G和H的关系 注意理解 1001110 0100110 0011101 1011000 1110100 1100010 0010001 k r k r 此处有H 7 4 G 7 3 或H 7 3 G 7 4 如H 7 4 G 7 3 1001110 0100110 0011101 可以通过矩阵变换将上面矩阵化为典型监督矩阵形式 第六节伴随式与标准阵列 设发送的码序列X X1X2 Xi Xn 接收的码序列Y Y1Y2 Yi Yn 两者的差别E Y X e1e2 ei en 称为差错序列或错误图样 用监督矩阵来校验接收到的码字时 有 HY H X E HX HE T T T T HE T X是码字 HX 0 T 令S HY HE T T T 则S EH T S称为伴随式 或校验子 用它来检查接收码字中的错误 P182 184用例5 1的监督矩阵为例讨论了接收端可能遇到的几种错误情况 可以看出一种码的检错和纠错能力受码距的限制 超过此限度就会检不出错误 或者造成误判 注意S是一个r维的行矩阵 标准阵列问题 设有一个 n k 线性码 它共有2个码字C0 C1 C2 C 1 将它排列成下表所示形式 其中零码矢C0放在第一列 它的下面放置各种错误图样 当监督元有n k个时 在C0下放有2 1个错误图样 在C0以后各码字C1 C2 C2 1的同一列下 各放置一些元素 这些元素为该列码字与相应行的错误图样模二相加而成 我们称同一行的这些元素为陪集 C0下面那些错误图样称为陪集首 每一行对应着唯一的一个伴随式 如果将标准阵列预先存储在接收端 则当接收到某个错误码字序列时 可以按照相应的陪集位于哪一列 而依据最大似然法则将其译成该列之首的那个码字 k 2 k n k k 注意理解下表中错误图样与伴随式的关系 C0C1C2 C2 1伴随式S k E2E2 C1E2 C2 E2 C2 1 k E3E3 C1E3 C2 E3 C2 1 k E2E2 C1E2 C2 E2 C2 1 n k n k n k n k k 例5 2设码字X X1X2X3X4X5 中X1 X2为监督元 监督矩阵为 H 100010111 列出标准阵列 判断码字10010是否是正确码字 如果不是则它应该译为的正确码字是多少 解 第一步根据H求出所有许用码字C0 C1 C7 第二步确定错误图样的个数及形式 以及伴随式S的形式 第三步列出标准阵列表 C0C1C2C3C4C5C6C7伴随式0000000011001010011011001110101110011111S 001000011100001000101110111110110001101101 010000101101101011101000110010101001011110 100001001110101101100100101010011000111111 码字10010显然不是正确码字 检查它在陪集中位于C5这一列 因而按最大似然法则 将它改正错误后译为C5 即11010 说明 采用这种方法译码 需要存储2个陪集元素 n为码长 如果利用陪集首所列的错误图样和伴随式一一对应的关系列表则只需存2个陪集首 因而可以节省许多存储量 n n k 例如 发送码字为11010 接收端错误地接收为11110 由公式 S HY T T 100010111 11110 01 查出陪集首为00100 固原发送码字为11110 00100 11010 但是当 n k 码的码长n较大时即使只存储2个陪集首及伴随式 译码器所需内存仍然相当大 因此寻求好的译码方法和简化译码设备是编码理论和应用中的重要课题 n k 第七节汉明码 汉明码是一类能纠正一位错误的线性码 此类码及其变型广泛应用于计算机存储系统和数据通信中 对于任意正整数m 3 存在具有下列参数的汉明码 码长 n 2 1 m 信息位数 k 2 m 1 m 监督位数 r n k m 最小码距 dmin 3 纠错位数tc 1 例5 3取m 3 则n 7 k 4 为 n k 7 4 汉明码 如监督方程组为 x2 x3 x4 x5x1 x3 x4 x6x1 x2 x4 x7 则监督矩阵为 HX T 01111000110101101001 x1x2x7 0 T G 000011010010100101100001111 如果将监督位设在x1 x2和x4 我们可以把题中给出的监督方程组等价变换 得到下面方程组 x5 x6 x7 x4x3 x6 x7 x2x3 x5 x7 x1 H 0001111 0110011 1010101 则在输出端求出译码用的伴随式的码元 S HY s1 x4 x5 x6 x7s2 x2 x3 x6 x7s3 x1 x3 x5 x7 根据公式S HE得出 7 4 汉明码的一种校验表 如下表示 T T T 错位指示 伴随式 s1 s2 s3 无错 x1 x2 x3 x4 x5 x6 x7 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 由上表可见 输出检错时很方便 因为由伴随式的各码元的值正好得出等于错误位置的二进制数 例如 当信息元为x3x5x6x7 1100 可求出对应的监督元x1x2x4 011 最后的码字x1x2x3x4x5x6x7 0111100假设传输过程中x7发生了错误 则接收端接收到错误码字x1x2x3x4x5x6x7 0111101 求出伴随式的码元值s1s2s3 111 二进制数为7 由上表可以判断错误的位置在第七位x7 通过将x7取反 进行纠错得到正确码字 注意 汉明码是纠正一位错的完备码 如果将汉明码的参数tc 1 n 2 1 Q 2 且k 2 m 1代入前面讲的求最大许用码字数的公式 可以发现等式两边正好相等 所以称汉明码为完备码 它表明码的m位监督元的2种表达形式 正好全部用来指示码长n 2 1位的每一位上的错误 再加上完全无错的一种情况 因此监督元的利用是最充分的 m k m m m 第九节卷积码的基本概念 卷积码是伊莱亚斯 Elias 1955年提出来的 它的特点是 每一段时间内所编出的几个码元不但与此段时间内进入的K个信息元有关 而且也与前面几段 如m段 时间内的信息元有关 1 编码电路 下图是一个卷积码的编码电路 D D 输入 输出 1 2 j 1 j 2 设刚开始工作时 D1 D2的状态为0 输入信息元m1 1 求出相应的监督元P1 1 1 P1 2 1 则送入信道的第一段码字为111 再输入信息元m2 0 求出相应的监督元P2 1 1 P2 2 0 第二段码字为010 如果每一段时间内送入k个信息元 编码电路送出n个码元 称n个码元的一段为子码 当输入信息元为mj mj 1 mj 2 时 送出的子码序列为Cj Cj 1 Cj 2 mj Pj 1 Pj 2 mj 1 Pj 1 1 Pj 1 2 mj 2 Pj 2 1 Pj 2 2 可见第j段时间内所编成的子码Cj不仅与本段中输入的信息元mj有关 而且也与前面两个子码Cj 1 Cj 2有关 对后面的两个子码Cj 1 Cj 2也有影响 这种子码之间具有一环与一环相连的特点 因而卷积码称为连环码 前面讲的每一个子码的监督元 是本段时间内输入的信息组与前面m 2个子码的信息组的线性模二和 也就是与 m 1 k个信息元发生线性关系 此处k 1 固卷积码编出的也是线性码 m称为编码存储级数 N m 1 称为编码约束度 编码约束长度定义为 N m 1 n A n k m 卷积码表示有k个输入 n个输出 存储级数为m的线性码 如果将移位寄存器和模二相加器间的关系以及信息元序列都用多项式形式来表示 则卷积编码运算可以化为多项式的代数运算 例如书P198介绍了一个k 1 n 2的卷积码编码电路 2监督矩阵 将前面的 3 1 2 卷积码的两个监督方程改写为矩阵形式 0 mj 2 0 Pj 2 1 0 Pj 2 2 1 mj 1 0 Pj 1 1 0 Pj 1 2 1 mj 1 Pj 1 0 Pj 2 0 1 mj 2 0 Pj 2 1 0 Pj 2 2 0 mj 1 0 Pj 1 1 0 Pj 1 2 1 mj 0 Pj 1 1 Pj 2 0 用矩阵表示 000100110100000101 mj 2Pj 2 1Pj 2 2mj 1Pj 1 1Pj 1 2mjPj 1Pj 2 0 000100110100000101 其中h 0 0 称为基本监督矩阵 且 01 10 11 0 0000 001 3第一截分组码 由前面的编码电路可以看出 每一个信息元影响的子码数目是有限的 因此在译某个码元时 只需要在一个约束长度内来考虑 假设编码约束度N m 1