计算机问题求解一论题4-7 代数编码 2019年04月24日
计算机问题求解 – 论题4-7 - 代数编码 2019年04月24日
问题1: 为什么易于发现错误,甚至易于 纠正错误的编码方案非常重要? 首先当然是因为编码无处不在, 不仅如此.… 无处不在到什么程度?
首先当然是因为编码无处不在, 不仅如此… 无处不在到什么程度?
p U 0 We will assume that transmission errors are q rare,and,that when they 1 do occur,they occur independently in 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: 要发现收到的报文中的错误。最 “straight forward的方法是什么? Example 1.One possible coding scheme would be to send a message several times and to compare the received copies with one another.Suppose that the message to be encoded is a binary n-tuple (1,x2,...,n).The message is encoded into a binary 3n-tuple by simply repeating the message three times: (x1,2,.,cn)→(1,c2,.,xn,x1,x2,.,En,1,c2,..,xn)
问题2: 要发现收到的报文中的错误,最 straight forward的方法是什么? Example 2.Even parity, Using even parity,the codes for A,B,and C now become A=010000012, B=010000102, C=110000112 Suppose an A is sent and a transmission error in the sixth bit is caused by noise over the communication channel so that (0100 0101)is received
问题2: 要发现收到的报文中的错误,最 “straight forward”的方法是什么? Received Word 000 001 010011 100 101 110 111 Transmitted 000 0 1 1 2 1 2 2 3 Codeword 111 3 2 1 2 1 1 0 Table 8.1.A repetition code Example 3.Suppose that our original message is either a 0 or a 1,and that 0 encodes to (000)and 1 encodes to (111).If only a single error occurs during transmission,we can detect and correct the error
问题2: 要发现甚至纠正收到的报文中的错误, 最“straight forward的方法是什么? 无论是发现,甚至在某种假设下发现及纠正错误,总有 冗余 的存在,必须的吗?
冗余 无论是发现,甚至在某种假设下发现及纠正错误,总有 的存在,必须的吗?
问题3: 我们必须考虑物理信道会出错,但又假设 出错“不多”,这是为什么? 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
阿题48 一个“貔码方案”究凳 是什么?