第二十讲西电通院考研复试资料(试题+课件).ppt

2020 1 27 1 第七章 线性分组码 7 1分组码的概念 7 2线性分组码 7 4循环码 7 5卷积码 2020 1 27 2 7 2线性分组码 实用纠错译码算法的预备知识 差错向量和伴随式定义6 1 8设 信道的输入为码字u 信道的输出为向量y 称向量e y u为差错向量 或差错图样 请注意 此时y u e 向量的加减法是对应分量的 modD 加减法 定义6 1 9 p195 设信道的输出为y 记s yHT其中H是一致校验矩阵 称N L维行向量s为y的伴随式 有以下的结论 2020 1 27 3 7 2线性分组码 1 当两个差错向量相同时 它们的伴随式相同 这就是说 伴随式s的值仅仅与信道传输错误有关 与输入信道的码字无关 证明s yHT u e HT uHT eHT eHT 证完 2 两个差错向量的伴随式相同 当且仅当它们的差向量是码字 证明设有两个差错向量e 1 和e 2 e 1 HT e 2 HT 当且仅当 e 1 e 2 HT 全0的N L维行向量 当且仅当 e 1 e 2 是码字 证完 2020 1 27 4 7 2线性分组码 3 给定一个差错向量e 则与e具有相同伴随式的所有差错向量恰好是e加上所有码字 换句话说 设s是一个伴随式 以s为伴随式的全体差错向量 就是以s为伴随式的一个差错向量加上全体码字 4 伴随式s是N L维行向量 因此有DN L个不同的伴随式 差错向量e是N维行向量 因此有DN个不同的差错向量 具有相同伴随式的差错向量的个数为DL DLDN L DN 定义在以s为伴随式的全体差错向量中 Hamming重量最小的差错向量称为s的陪集首 记为e s s可能有不止一个Hamming重量最小的差错向量 任意选择一个作为陪集首e s 即可 2020 1 27 5 7 2线性分组码 5 对信道的输出向量y 计算伴随式s yHT 以s为地址查找陪集首e s 计算u y e s 则u就是在所有码字中与y的Hamming距离最小的码字 证明首先 u y e s 是码字 这是因为uHT yHT e s HT s s 全0的N L维行向量 其次 对任意另一个码字c y c HT yHT cHT yHT s 这就是说 y c 是以s为伴随式的一个差错向量 另一方面 y u e s 是以s为伴随式的Hamming重量最小的差错向量 所以w y u w y c 即d y u w y c 证完 2020 1 27 6 7 2线性分组码 实用纠错译码算法预计算对每个伴随式 即N L维行向量 s 寻找s的陪集首e s 并以s为地址存储e s 预计算的总体计算量很大 但有许多技巧可以大幅度地减少计算量 现场纠错译码 1 对信道的输出向量y 计算伴随式s yHT 2 以s为地址查找陪集首e s 3 将输出向量y译为码字u y e s 结束 u就是在所有码字中与y的Hamming距离最小的码字 2020 1 27 7 7 2线性分组码 现场纠错译码的计算量计算量最大的是第 2 步 因为s是N L维行向量 所以查找s的计算量是logDN L N L logD 而不是DN L 总之 计算量远远小于直接使用最小距离准则的计算量DL 2020 1 27 8 7 2线性分组码 线性分组码的检错能力和纠错能力定义6 1 3线性分组码的最小Hamming距离定义为两个不同码字的Hamming距离的最小值 记为dmin 线性分组码的最小Hamming重量定义为非全0码字的Hamming重量的最小值 记为wmin 2020 1 27 9 7 2线性分组码 引理1dmin wmin 证明设两个不同的码字u 1 和u 2 使得dmin d u 1 u 2 w u 1 u 2 注意到 u 1 u 2 是一个非全0码字 所以dmin wmin 设一个非全0码字u 使得wmin w u w u 全0码字 d u 全0码字 所以dmin wmin 证完 2020 1 27 10 7 2线性分组码 引理2设信道的输入为码字u 信道的输出为向量y 差错向量为e y u 则 1 当w e dmin yHT肯定不是全0的N L维向量 因而发现信道传输错误 2 当w e dmin 1 2 下方取整 由上述实用纠错译码算法肯定将y译为真正的原发码字u 而不会将y译为其它码字 2020 1 27 11 7 2线性分组码 证明 1 当w e dmin 1 2 w e d y u 因此 所有码字中 u与y的Hamming距离最小 证完 2020 1 27 12 7 2线性分组码 引理3设信道的输入为码字u 信道的输出为向量y 差错向量为e y u 当w e dmin 1 2 下方取整 由上述实用纠错译码算法未必将y译为u 证明设信道的输入为码字u 设另一个码字c恰好满足d c u dmin 设输出向量是这样的y d c u d c y d y u 三角不等式变为等式 w e d y u dmin 1 2 1 dmin 1 2 请注意 这样的输出向量y存在 而且此时d c y d c u d y u dmin dmin 1 2 1 dmin 1 dmin 1 2 2020 1 27 13 d y u dmin 1 2 1 d c y dmin 1 dmin 1 2 当dmin是奇数时 d y u dmin 1 2 1 d c y dmin 1 2 故d c y d y u 当dmin是偶数时 d y u dmin 2 d c y dmin 2 故d c y d y u 这就是说 当dmin是奇数时 将y译为c而不是u 当dmin是偶数时 将y译为c或u都符合最小距离准则 证完 2020 1 27 14 7 2线性分组码 对引理2和引理3的解释设信道真正的输入码字为u 信道的输出向量为y 真正的差错向量为e y u 采用实用纠错译码算法 接收y 计算伴随式s yHT 以s为地址查找e s 计算c y e s 认为陪集首e s 就是差错向量 认为c就是输入码字 引理2告诉我们 如果w e dmin 1 2 则e s e 因而c u 引理3告诉我们 如果w e dmin 1 2 则未必e s e 因而未必c u 换句话说 如果w e dmin 1 2 则e一定是s eHT的陪集首 如果w e dmin 1 2 则e未必是s eHT的陪集首 2020 1 27 15 7 2线性分组码 定理6 1 4设真正的差错向量为e w e t时肯定正确译码 当且仅当dmin 2t 1 推论设真正的差错向量为e 肯定正确译码的概率为 2020 1 27 16 7 2线性分组码 定理6 1 4说明 dmin是线性分组码纠错能力的一个指标 dmin越大 dmin 1 2 就越大 肯定正确译码的概率也越大 当N比L大得越多 码字在所有N维向量中占的比例越小 越容易使得dmin大 问题是 当N和L都确定时 如何设计码使得dmin大 纠正一种误解 dmin越大 肯定正确译码的概率越大 决不能说 dmin越大 正确译码的概率越大 怎么回事 肯定正确译码 w e dmin 1 2 不能肯定正确译码 w e dmin 1 2 请注意 P 肯定正确译码 P 不能肯定正确译码 1 这就是说 肯定正确译码 的概率越大 不能肯定正确译码 的概率越小 然而 正确译码 肯定正确译码 不能肯定正确译码中的一部分 一个线性分组码 dmin小 肯定正确译码的概率小 但 不能肯定正确译码中的一部分 的概率很大 则正确译码的概率也可能很大 2020 1 27 17 7 2线性分组码 问答回答 肯定正确译码 不能肯定正确译码 肯定不能正确译码 1 w e dmin 1 2 2 w e dmin 1 2 3 e是一个码字 4 e不是一个码字 2020 1 27 18 7 2线性分组码 例6 1 8求一致校验矩阵 码字集合 译码预计算 简化计算量 显然是系统码 2020 1 27 19 7 2线性分组码 信息向量 码字000 000000100 011100010 101010001 110001110 110110101 101101011 011011111 000111 伴随式s 陪集首e s 000 000000100 100000010 010000001 001000110 000100101 000010011 000001111 100100 2020 1 27 20 7 2线性分组码 dmin 3 dmin 1 2 1 当真正的差错向量的Hamming重量不超过1时 肯定正确译码 当真正的差错向量的Hamming重量超过1时 未必正确译码 肯定正确译码的概率为 1 p 6 6 1 p 5p 正确译码的概率为 1 p 6 6 1 p 5p 1 p 4