离散数学及其应用：群与编码课件.pptVIP

Groups and Coding Groups and Coding Coding of Binary Information and Error Detection Decoding and Error Correction Coding of Binary Information and Error Detection Encoding function Hamming distance Group Codes Parity check matrix Coding theory In today’s modern world of communication, data items are constantly being transmitted from point to point. The basic problem in transmission of data is that of receiving the data as sent and not receiving a distorted piece of data. Coding theory has developed techniques for introducing redundant information(引入冗余信息) in transmitted data that help in detecting, and sometimes in correcting, errors. Unit of information Message(消息) is a finite sequence of characters from a finite alphabet B = {0, l } Word(字) is a sequence of m 0s and l s. Groups The set B is a group under the binary operation + (mod 2 addition ) It follows that Bm = B ? B ? … ? B (n factors) is a group under the operator ? defined by (x1, x2,…, xm) ? (y1, y2 ,…, ym) = (x1 + y1, x2 + y2 , …, xm + ym) An element in Bm will be written as (b1,b2,..., bm) or more simply as b1b2...bm Transmission channel and Noise An element x ? Bm is sent through the transmission channel and is received as an element xt ? Bm. Transmission channel and Noise Noise(噪声) in the transmission channel may cause a 0 to be received as a l, or vice versa, lead x ? xt Encoding function - 编码函数 Choose: an integer nm and a one-to-one function e: Bm ? Bn e is called an (m, n) encoding function, representing every word in Bm as a word in Bn. If b ? Bm, then e(b) is called the code word(码字) representing b. Encoding function If the transmission channel is noiseless, then xt = x for all x in Bn. In this case x = e(b) is received for each b ? Bm, and since e is a known function, b may be identified. Encoding function In general, errors in transmission do occur. We will say that the code word x = e(b) has been transmitted with k or fewer errors if x and xt differ in at least 1 but no more than k positi