南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）代数编码

计算机问题求解一论题4-5 代数编码 2017年04月10日

计算机问题求解 – 论题4-5 - 代数编码 2017年04月10日

间题1： 为什么易于发现错误， 甚至易于纠正错误的编 码方案非常重要？ 首先当然是因为编码无处不在，不仅如此

首先当然是因为编码无处不在，不仅如此…

p 0 We will assume that q transmission errors are rare, and,that when they do occur, q they occur independently in 1 each bit. Figure 8.2.Binary symmetric channel The probability that no errors occur during the transmission of a binary codeword of length n is p".For example,if p =0.999 and a message consisting of 10,000 bits is sent,then the probability of a perfect transmission is (0.999)10,000≈0.00005

We will assume that transmission errors are rare, and, that when they do occur, they occur independently in each bit

即使传输一个bit出错概率不大. Theorem 8.1 If a binary n-tuple (1,...,n)is transmitted across a binary symmetric channel with probability p that no error will occur in each coor- dinate,then the probability that there are errors in exactly k coordinates is pn-k 假如传输1个bit,出错的概率是千分之五，假如要传500个bits,那么： 不出错的概率是：8.2%； 有一位错的概率是：20.4%；有两位错的概率是；25.7%； 而两位以上错误的概率是：45.7%

即使传输一个bit出错概率不大… 假如传输1个bit, 出错的概率是千分之五，假如要传500个bits，那么： 不出错的概率是：8.2%; 有一位错的概率是：20.4%; 有两位错的概率是；25.7%； 而两位以上错误的概率是：45.7%

问题2： 我们必须考虑物理信道会出错，但又假 设出错“不多”，这是为什么？ We will also assume that a received n-tuple is decoded into a codeword that is closest to it;that is,we assume that the receiver uses maximum-likelihood decoding

问题3： 要发现收到的报文中的错误。最 “straight forward的方法是什么？ Ex Example 2.Even parity,a commonly used coding scheme,is much more tin efficient than the simple repetition scheme. The ASCII(American Standard 冗余 tin there are only 27=128 ASCII characters.What can or should be done with the extra bit?Using the full eight bits,we can detect single transmission errors.For example,the ASCII codes for A,B,and C are

冗余

阿题48 一个“貔码方案”究凳 是什么？

两个集合，两个函数 If we are to develop efficient error-detecting and error-correcting codes,we will need more sophisticated mathematical tools.Group theory will allow faster methods of encoding and decoding messages.A code is an (n,m)- block code if the information that is to be coded can be divided into blocks of m binary digits,each of which can be encoded into n binary digits.More specifically,an (n,m)-block code consists of an encoding function E:Z→Z and a decoding function D:z5→Z 问题58 其实，这n和m之间大小的差别就是“冗余” 关于m,m的大小，你能说点什么？

两个集合，两个函数 其实，这n和m之间大小的差别就是“冗余

间题5： 在上面的假设下，采用最大相似度的解码 方法，你认为怎样的code word集合有利 于发现并纠正错码？ 小提示：解码过程可以理解为从receive word定位到 code word,再从code word解码到明文组，其中最迷惑 解码人的是哪一步？

小提示：解码过程可以理解为从receive word定位到 code word，再从code word解码到明文组，其中最迷惑 解码人的是哪一步？

问题6： 你能从第5个间题的思考中，理解码字 hamming距离的本质，以及随后定义出来 的编码系统的最小距离的用意吗？ Ifx=(1100)andy=(1010) are codewords,then d(x,y)=2.If x is transmitted and a single error occurs,then y can never be received. 如果=(1100)，y=(1011),我们收到了 一个码1110，我们可以得到什么结论？

如果x=(1100), y=(1011),我们收到了 一个码1110,我们可以得到什么结论？