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

计算机问题求解一论题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 一个“貔码方案”究凳 是什么？