ch11差错控制编码习题课1.ppt

第11章差错控制编码习题课 孟华志peaceandlove 2008 6 6 主要题型及解法 一 已经给出线性分组码的各个码字 要求求出最小码距 并判断其检错 纠错能力 解法 根据线性分组码的重要性质 线性分组码的最小码距等于非零码的最小码重即可求出 而码重就是指码字中1的个数 根据P331 332的检纠错编码定理求解分组码的检错 纠错能力 主要题型及解法 二 关于汉明码的题目 解法 1 对于 n k 汉明码 根据汉明码的定义 可得 n 2r 1 其中r n k 为汉明码的监督位的数目 所以k n r 2r 1 r 根据编码效率的公式求编码效率 2 汉明码最大的特点是可以纠正1位错误 主要题型及解法 三 给出非典型的生成矩阵G或监督 校验 矩阵H 1 要求其对应的H或G 2 求其所有系统码字 3 判断其检错 纠错能力 解法 1 先将G或H进行初等行 列 变换化成典型阵的形式 再根据G和H的转换关系直接写出对应的H或G 主要题型及解法 2 对于所有的线性分组码 都可以用A MG来求码字 码字的个数由k确定 个数为2k 假定k 3 则M 000 001 010 011 100 101 110 111 共8个 则用每个M乘以G即可得到所有码字 注意模2加法和乘法的规律 巧妙地计算以避免出错 3 根据线性分组码的最小码距等于其非零码元的最小码重即可求的最小码距d0 求出d0即可判断其检错 纠错能力 主要题型及解法 四 给出 n k 线性分组码的监督关系方程组求其H和G 判断某个码是否该分组码的码字 解法 首先根据监督方程写出对应的监督矩阵H 然后将其化成标准形式 即可求出对应的G 然后计算伴随式S BHT 若S 0 则B是该 n k 码的码字 否则B不是该 n k 码的码字 主要题型及解法 五 关于循环码的题目 1 给出 n k 循环码的生成多项式g x 求其对应的生成矩阵G和监督矩阵H 解法 根据 五 关于循环码的题目 contd 可求出G x 将其变化成典型矩阵G 根据G可求出H 2 求某个信息码元组M对应的码字 解法1 因为循环码首先是线性分组码 故可根据A MG求其码字 解法2 利用循环码的性质求解 根据M即可写出M x 则用xn kM x g x 即可得到r x 则A x xn kM x r x 即得A 五 关于循环码的题目 contd 3 给出 n k 循环码的生成多项式g x 再给出接受码组B x 要求判断码组在传输中是否出错 解法 利用循环码g x 的重要性质求解 g x 为r n k次码多项式 其次数最低 且所有其它码多项式A x 都能被g x 整除 假定传输正确 则有B x A x 则必定有B x 能被g x 整除 故判断方法如下 用长除法计算B x g x 若能整除则判断传输没有出错 否则肯定出错 第11章习题选讲 例1 已知某线性分组码的8个码字为 000000 001110 010101 011011 100011 101101 110110 111000 求该码的最小码距 并判断其纠检错能力 解 由于线性分组码的封闭性和码距的定义可得知 线性分组码的最小码距等于非全零码的最小码重 故有 例1 contd 故由观察法即可得出由纠错编码定理可得其检纠错能力如下 1 能发现2个错误码元 2 能纠正1个错误码元 例2 一个码长为15的汉明码 其监督码元有多少位 编码效率是多少 用其作纠错码能够纠正几位错误 解 由汉明码的定义有 n 2r 1 15 故有r 4 所以编码效率汉明码能纠正1位错误 例3 已知 7 3 线性分组码的生成矩阵为求其监督矩阵 写出该 7 3 码的系统码 并判断其纠检错能力 解 先用初等行变换将生成矩阵化成典型阵 如下所示 K 3 所以共有23 8个系统码字 再根据A MG 即可分别求出各个码字 举例如下 其它码字分别为 故由线性分组码的性质可得其最小码距d0为4 由检纠错编码定理可得 能发现3位错误 能纠正1位错误 能发现2位错误的同时纠正1位错误 HEC混合纠错方式 例4 已知某 7 4 循环码的生成多项式g x x3 x 1 试求 1 监督矩阵H和生成矩阵G 2 写出该循环码的所有码字 并求其最小码距 3 求M 1010时对应的码字 4 若B 1001101 判断其是否是该分组码的码字 解 1 2 方法一 利用A MG求解 其中M共有16种不同的组合 求解除所有码字后 即可用观察法得出循环码的最小码距为3 方法二 利用求出A x 即可求出A x 对应的码字A 3 方法一 直接利用第 2 小题的结果即可 方法二 方法三 4 方法一 利用长除法求出