计算机问题求解一论题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,我们可以得到什么结论?