计算机问题求解 - 算法在计算机科学中的地位.ppt

计算机问题求解 – 论题4-5 - 代数编码 2017年04月10日 问题1: 为什么易于发现错误，甚至易于纠正错误的编码方案非常重要？ 首先当然是因为编码无处不在，不仅如此… We will assume that transmission errors are rare, and, that when they do occur, they occur independently in each bit. 即使传输一个bit出错概率不大… 假如传输1个bit, 出错的概率是千分之五，假如要传500个bits，那么： 不出错的概率是：8.2%; 有一位错的概率是：20.4%; 有两位错的概率是；25.7%； 而两位以上错误的概率是：45.7% 问题2： 我们必须考虑物理信道会出错，但又假设出错“不多”，这是为什么？ 问题3： 要发现收到的报文中的错误，最“straight forward”的方法是什么？ 冗余 问题4： 一个“编码方案”究竟是什么？ 两个集合，两个函数 问题5： 关于m, n的大小，你能说点什么？ 其实，这n和m之间大小的差别就是“冗余” 问题5: 在上面的假设下，采用最大相似度的解码方法，你认为怎样的code word集合有利于发现并纠正错码？ 小提示：解码过程可以理解为从receive word定位到code word，再从code word解码到明文组，其中最迷惑解码人的是哪一步？ 问题6: 你能从第5个问题的思考中，理解码字hamming距离的本质，以及随后定义出来的编码系统的最小距离的用意吗？ 如果x=(1100), y=(1011),我们收到了一个码1110,我们可以得到什么结论？ 最小码距与纠错能力的关系 问题7： 在设计编码时怎么能比较方便地“控制”最小码距呢？ 再看编码函数： Z2m Z2n 问题8.1：什么是好的码字系统？ 问题8.2：我们是否应该为我们的设想选择一个数学工具来思考、保证？ 如何快速计算一个码字系统的最小距离？ 但是，这样算，仍然很慢！ 如何去构造一个群编码？Z2n群的子群？ 1，(0,0,…,0)必定在子群中； 2，任意一个码字，它是自身的逆； 3，确保所有的码字在加法运算下是封闭的！ 其实很难，而且对最小距离的控制没有“章法” 我们需要科学的方法来构造群编码：矩阵计算 矩阵计算帮我们找到群码 问题9: 相对于我们要解决的问题，我们现在走了多远？书上后面还有“一堆”定理，是用来解决什么问题的？ 9.1: 是否任意的矩阵H,都有null space? 9.2: 在已知信息分组(m)前提下，什么样的矩阵H, 能得到最好的null space（线性码）？ 两种特殊的矩阵 H是mn矩阵; G是n(n-m)矩阵 问题10: 构造出这样的矩阵G, 是为了什么? 再看编码函数： Z2n-m Z2n E(x)=Gx, 其中x长度为n-m；G生成矩阵为n*(n-m) E(x)=Gx 问题9: 书上例12想说明什么? 线性码的数学基础 取决于A矩阵和待编码信息！ 你能“看出”101如何编码为长度为6的码字？ 101 1 1 0 线性码的数学基础 问题10: 现在我们离“目标”还有多远？ 查错和纠错能力如何标定？ 查错和纠错能力如何实现？ 重新审视一下矩阵H 问题11： 现在你“悟”到了什么吗？ 线性码的查错能力 证明的关键：ei是什么？H ei是什么？ ei作为code word，会带来什么性质？ 假如H的第k列全0，则Hek=0，所以ek是code word, 但w(ek)=1。 假如ei是codeword, 则Hei=0，则H的第i列必然全是0。 线性码的纠错能力 证明的关键： codeword中恰含两个1当且仅当该码是ei+ej当且仅当H中有两列是一样的。注意：codeword中恰含两个1就是该codeword恰好是ei+ej (ij) 注意： 的充分必要条件显然是：H的第i列和第j列完全一样。 你如何设计奇偶校验矩阵使得能够完成一位纠错编码？ 终于到最后一步了…… 问题12： 怎么解码？ 如果只有一个错，利用syndrome: Hx，可以判断错在哪里。 基本原理：The syndrome of a received word depends solely on the error and not on the transmitted code word. 群的意义不仅在于编码 解码时总是用陪集中权最小的元素，即coset leader。这正体现了“最大近似解码”原则。 Open Topics 请查阅资料，介绍曼哈顿距离、欧几里得距离、契比雪夫距离分别是什么意思，他们的典型应用