Block-CodesPPT課件

1、Block Codes,By Mo Fanlu,1,Block Codes,Linear Block Codes Important Linear Block Codes Cyclic Codes,Outline,2,Introduction to linear block codes We assume that the out put of an information source is a sequence of the binary digits 0 and 1. In block coding, this binary information sequence is segment

2、ed into message blocks of fixed length; There are a total of distinct messages.,Linear Block Codes,The encoder, according to certain rules, transforms each input message u into a binary n-tuple v with nk.,Encoder,Figure 1: Encoding of an ( n, k ) linear block code,3,Linear Block Codes,Generator matr

3、ix,4,Linear Block Codes,A desirable property for a linear block code to possess is the systematic structure of the code words, as shown in Figure 2:,Redundant checking part,Message part,n-k digits,k digits,Figure 2: Systematic format of a code word,5,Linear Block Codes,This implies that,6,Linear Blo

4、ck Codes,H is a parity-check matrix of the ( n, k ) linear code generated by the matrix of G.,Figure 3: Encoding circuit for a linear systematic,To channel,7,Linear Block Codes,Syndrome and error detection,This n-tuple is called the error vector( or error pattern ), which simply displays the positio

5、n where the received vector r differ from the transmitted codeword v. When r is received, the decoder computes the following (n-k)-tuple:,which is called the syndrome of r. The syndrome digits are as follows:,8,Linear Block Codes,The syndrome s computed from the received vector r depends only on the

6、 error pattern e and not on the transmitted codeword v. Because r is the vector sum of v and e, it follows:,Multiplying out yields the following linear relationship between the syndrome digits and the error digits :,Because this n-k linear equations do not have a unique solution but have solutions.

7、In other word, there are error patterns that result in the same syndrome, and the true error pattern e is just one of them.,To minimize the probability of a decoding error, the most probable error pattern is chosen as the true error vector. If the channel is BSC channel, the most probable pattern is

8、 the one that has the smallest number of nonzero digits.,9,Linear Block Codes,The minimum distance of a block code,and,Given a block code C, the minimum hamming distance of C, denoted by dmin, is defined as:,10,Linear Block Codes,Error-detecting and error-correcting capabilities of a block code,A,B,

9、C,If the minimum distance of a block code C Is , any two distinct codewords of C differ in at least places. For this code C, no error pattern of or fewer errors can change one codeword into another. The random-error-detecting capability of a block code withe minimum distance is .,Figure 3: Error-det

10、ecting capabilities of a block code,11,Linear Block Codes,A,B,Error-detecting and error-correcting capabilities of a block code,Figure 3: Error-correcting capabilities of a block code,A block code with minimum distance guarantee correction of all the error patterns of or fewer errors. The parameter

11、is called the t-error-correcting-capability of the code.,12,Linear Block Codes,Standard array and syndrome decoding,A standard array,13,Linear Block Codes,A method to partition the possible received vectors into disjoint subsets such that each subset contain one and only one codeword is described.,T

12、o minimize the probability of a decoding error, the error patterns that are most likely to occur for a given channel should be chosen as the coset leaders. For BSC, an error pattern of smaller weight is more probable than an error pattern of lager weight. As a result, the decoding based on the stand

13、ard array is the minimum distance decoding(the maximum likelihood decoding).,14,Linear Block Codes,All the n-tuples of a coset have the same syndrome. The syndromes for different coset are different.,Because the syndrome of an n-tuple is an (n-k)-tuple, and there are distinct (n-k)-tuples. There is

14、a one-to-one correspondence between a coset and a (n-k)-tuple, so we can form a decoding table, which is much simpler to use than a standard array.,This described decoding scheme is called the syndrome decoding or table-look up decoding.,15,Important Linear Block Codes,Hamming Codes,For any positive

15、 integer , there exists a Hamming code with the following parameters:,Code length: Number of information symbols: Number of parity-check symbols: Error-correcting capability:,The parity-check matrix H of this code consists of all the nonzero m-tuples as its columns. In systematic form, the columns o

16、f H are arranged in the following form:,where Im is an identity matrix, and the submatrix Q consists of Columns that are the m-tuples of weight 2 or more.,16,Important Linear Block Codes,The generator matrix of the code is :,If we form the standard array for the Hamming code of length , all the -tup

17、les of weight 1 can be used as coset leaders. The number of -tuples of weight 1 is . Because n-k=m, the code has cosets.,A t-error-correcting code is called a perfect code if its standard array has all the error patterns of t or fewer errors and no others coset leaders.,Hamming code can easily be de

18、coded with the table-lookup scheme .,17,Important Linear Block Codes,Shortened Hamming code,We may delete any l columns from the parity-check matrix H of a Hamming code. This deletion result in a matrix H.,Code length: Number of information symbols: Number of parity-check symbols: Error-correcting c

19、apability:,If we delete from the submatrix Q all the columns of even weight, we obtain an matrix:,Because for a columns of weight 3 in Q, there exist three columns in Im such that . Thus, the shortened Hamming code with H as a parity-check matrix has a minimum distance of exactly 4.,18,Important Lin

20、ear Block Codes,Shortened Hamming code,The distance-4 shortened Hamming code can be used for correcting all error patterns of single error and simultaneously detecting all error patterns of double errors. When a single error occurs during the transmission of a code vector, the resultant syndrome is

21、nonzero, and it contains an odd number of 1s. When double errors occur, the resultant syndrome is also nonzero, and it contains an even number of 1s.,Decoding of the shortened Hamming code: If the syndrome s is zero, we assume that no error occurred. If s is nonzero and it contains an odd number of

22、1s, we assume that a single error occurred. The error pattern of a single error that corresponds to s is added to the received vector for error correction. If s is nonzero and it contains an even number od 1s, an uncorrectable error pattern has been detected.,19,Important Linear Block Codes,Reed-Mul

23、ler Codes,For any integers m and r with ,there exists a binary rth-order Rm code, denoted by Rm ( r, m ).,Code length: Dimension: Minimum distance:,where is the binomial coefficient.,which consists of alternating all-zero and all-one -tuples.,20,For m=4, we have the following four 16-tuples:,For sim

24、plicity, we use ab for a.b.,The rth-order RM code, RM( r, m ), of length is generated by the following set of independent vectors:,Important Linear Block Codes,21,Important Linear Block Codes,There are,vectors in GRM( r, m ). Therefor, the dimension of the code is k( r, m ).,To explain the Reed deco

25、ding algorithm for RM codes, we can assume m=4 and r=2. The second-order RM code of length n=16 is generated by the following 11 vectors.,This is a (16,11) code with a minimum distance of 4.,22,Important Linear Block Codes,Suppose,is the message to be encoded. Then, the corresponding codeword is:,Th

26、ese four sums give four independent determinations of the information bit from the code bits. If there is a single transmission error in the received vector, the error can affect only one determination of .,23,Important Linear Block Codes,These sums are called check-sums, which are simply the estima

27、tes of . Then the is decoded based on the following majority-logic decision rule: is taken to be equal to the value assumed by the majority in . If there is a tie, a random choice of the value is made.,Similar independent determinations of information bits can be made from the code bits. After decod

28、ing of , the vector,is subtracted from r.,24,Important Linear Block Codes,Then we can decode by using the majority-logic decision rules. After decode , we remove the effect of :,25,Cyclic Codes,Description of cyclic codes,An ( n, k) linear code C is called a cyclic code if every cyclic shift of a co

29、de word in C is also a codeword in C.,26,Cyclic Codes,Let be a nonzero code polynomial on minimum degree in C, and g(X) is unique. The constant term g0 must be 1, because when g0=0, then,The nonzero code polynomial of minimum degree in an ( n , k ) cyclic code C is of the following form:,27,Cyclic C

30、odes,Because , are the cyclic shifts of the g(X). Therefore, they are code polynomials in C. A linear combination of :,is also a code polynomial. A binary polynomial of degree n-1 or less is a code polynomial and only if it is a multiple of g(X).,Every code polynomial v(X) in an ( n , k ) cyclic cod

31、e can be expressed in the following form:,28,Cyclic Codes,If the coefficients of u(X) are the k information digits to be decoded, v(X) is the corresponding code polynomial. g(X) is called the generator polynomial of the code. The degree of g(X)is equal to the number of parity-check digits of the cod

32、e.,29,Cyclic Codes,If,Where a(X) and b(X) are the quotient and the remainder, respectively. Because the degree of g(X) is n-k, the degree of b(X) must be n-k-1 or less.,This polynomial is a multiple of the generator polynomial g(X) and therefor it is a code polynomial of the cyclic code generated by g(X). The corresponding codeword is:,30,Cyclic Codes,31,Cyclic Codes,Generator and parity-c