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

计算机问题求解一论题4-7 代数编码 2021年04月19日

计算机问题求解 – 论题4-7 - 代数编码 2021年04月19日

问题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 (x1,22,...,n).The message is encoded into a binary 3n-tuple by simply repeating the message three times: x1,c2,.,xn)→(x1,2,,cn,x1,x2,,xn,x1,2,·,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的方法是什么？ 无论是发现，甚至在某种假设下发现及纠正错误，总有 冗余 的存在，必须的吗？

冗余 无论是发现，甚至在某种假设下发现及纠正错误，总有 的存在，必须的吗？

问题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

问题4.1： 一个编码方案”究竞是什么？ 问题4.2 那么，一个好“编码方案”究竟是 好在哪里？

两个集合，两个函数 If we are to develop efficient error-detecting and error-correcting codes,we will need more sophisticated mathematical tools.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四→Z5 and a decoding function D:Z→Z. 问题58 其实，这n和m之间大小的差别就是“冗余” 关于m,m的大小，你能说点什么？

两个集合，两个函数 其实，这n和m之间大小的差别就是“冗余” If we are to develop efficient error-detecting and error-correcting codes, we will need more sophisticated mathematical tools. 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