National Taiwan Ocean University Error Correcting Codes Spring 2003 Lecture 6: CRC Codes and BCH Codes National Taiwan Ocean University Announcement C

Size: px

Start display at page:

Download "National Taiwan Ocean University Error Correcting Codes Spring 2003 Lecture 6: CRC Codes and BCH Codes National Taiwan Ocean University Announcement C"

龛属濮
4 years ago
Views:

1 Error Correcting Codes Spring 2003 Lecture 6: CRC Codes and BCH Codes Announcement Course webpage: Textbook webpage: Reading Assignment: Chapters 3 and 4 Homework No.2 Due in April 9, 2003

2 Burst Error Detection with Cyclic Codes Cyclic codes are very effective in detecting burst errors. A q-ary cyclic (or shortened cyclic) code with generator polynomial g(x) of degree r (= n k for cyclic code) can detect all burst error patterns of length r or less. Example: The cyclic Hamming (7,4) code detects burst errors of length 3. But it detects only two random errors. Remark: In fact, many of longer burst error patterns can also be detected. A cluster of errors is called error burst. An error burst is of length l if all the errors are confined to l consecutive positions. e.g., e=( ) is an error burst of length 4. It can be end-around such as e=( ) is also of length 4. Burst Error Detection Let an error burst between positions i and (i + l 1) be represented by polynomial, e(x) = x i (e 0 +e 1 x+e 2 x 2 + +e l- 1x l-1 ), where x i + and x i+l-1 are the beginning and ending of the burst. For l r, where r is the order of the generator polynomial g(x), no error burst is divisible by g(x). Hence, its syndrome is nonzero. An (n, k) cyclic code can detect any burst of length n k or less (including end-around burst). Shorten cyclic codes generated using the same generated polynomial have the same detection performance although it is not an (n, k) code.

3 Burst Error Detection For burst length r+1, the fraction of undetectable error burst is q -(r-1) /(q 1).(e.g., for q = 2, q -(r-1) /(q 1) = 2 1-r.) Since the burst error patterns that cannot be detected are the scalar multiples of g(x) and their n cyclic shifts. For shortened codes, we consider only the (n r 1) noncyclic shifts. Thus, there are now (n r)(q 1) undetectable error patterns. But because the number of total possible error patterns is reduced to (n r)(q 1) 2 q r-1, the final result of the equation below is the same.) Burst Error Detection Total possible error patterns: There are q-1 possible symbols at the beginning and ending positions of a burst. The digits in between can be any of the q symbols. Similarly, the fraction of undetectable error bursts for burst length l > r+1 is

4 Shortened Cyclic Codes Suppose we wish to have information blocks of (k l) digits, but we use (n, k) code with l < k. Let m = (m 0,m 1,,m k-l+1,0,,0). If the code is a cyclic code in systematic form, the code words generated are c = (c 0,c 1,,c n-k-1,m 0,m 1,,m k-l+1,0,,0). There is no need to transmit the l zeros, since the receiver will know this (because we design it). The code length is reduced to n' = n l. In general, a code obtained from shortening a cyclic code is no longer cyclic. l l Shortened Cyclic Codes Shortened codes have error detection and correction capabilities that are at least as good as the original codes. Example:Consider the (7, 4) cyclic code generated by g(x) =1+x+x 3 The generator matrix of the (6, 3) shortened code is obtained by omitting the last row and column from G of the original (7,4) code.

5 Shortened Cyclic Codes and the parity-check matrix H' is obtained by omitting the last column of H. Decoding of Shortened Codes A shortened cyclic code (n l, k l) can be decoded by a decoder similar to the original (n, k) cyclic code. Let r(x) = r 0 + r 1 x + r 2 x r n-l-1 x n-l-1 be received polynomial. Suppose that r(x) is shifted into the syndrome register from the right end. (Fig. 4.5(b)) If the decoding circuit for the original cyclic code is used for decoding the shortened code, the proper syndrome for decoding the received digit r n-l-1 is equal to the remainder resulting from dividing x n-k+l r(x) by the generator polynomial g(x).

6 Decoding of Shortened Codes Since shifting r(x) into the syndrome register from the right end is equivalent to premultiplying r(x) by x n-k, the syndrome register must be cyclically shifted for another l times after the entire r(x) has been shifted into the register. These extra l shifts can be eliminated by modifying the connection of the syndrome register: (as shown below) Dividing x n-k+l r(x) by g(x), we obtain x n-k+l r(x) = a 1 (x)g(x) + s n-k+l (x) Next, we divide x n-k+l by g(x), x n-k+l = a 2 (x)g(x) + ρ (x) Decoding of Shortened Codes Let ρ (x) = ρ 0 + ρ 1 x + ρ 2 x ρ n-k-1 x n-k-1 be the remainder resulting from this division. That is ρ (x) = x n-k+l + a 2 (x)g(x) Combine the above two equations, a 1 (x)g(x) + s n-k+l (x) = a 2 (x)g(x)r(x) + ρ (x)r(x) Thus, ρ (x)r(x) = [a 1 (x)+a 2 (x)r(x)]g(x) + s n-k+l (x). The equation above suggests that we can obtain the syndrome s n-k+l (x) by multiplying r(x) by ρ (x) and dividing the product ρ (x)r(x) by g(x). Computing s n-k+l (x) this way, the extra l shifts of the syndrome register can be avoided.

7 Decoding of Shortened Codes As soon as the received polynomial r(x) has been shifted into the register, the contents in the register form the syndrome s n-k+l (x) and the first received digit is ready to be decoded. CRC Codes Cyclic Redundancy Check (CRC) Codes are errordetecting codes typically used in automatic repeat request (ARQ) systems. CRC codes have no error-correction capability but they can be used in combination with an error-correcting code to improve the performance of the system. CRC codes are (often) shortened cyclic codes. CRC codes are often (but not always) constructed of polynomials of the form g(x) = (x+1)p(x), where p(x) is a primitive polynomial of degree (r 1) that divides x 2r The (x+1) factor ensures that all odd weight error patterns are detectable.

8 CRC Codes Concatenated Coding System CRC Codes Remark 1: A primitive polynomial of degree m divides x 2m Now, m = r 1. For m = 16, n = Remark 2: Expurgated cyclic codes. It is a conversion of information bits to parity bits but keeping the total length n the same. For example, we increase the degree of the generator polynomial by multiplying a factor (x+1): g(x) = (x+1)p(x). Because (x+1) is a factor of x n 1 for any value of n, so the new generator is till a factor of x n 1 for the original value of n.

9 CRC Codes Remark 3: If the generator polynomial contains the factor of (x+1), its code words must all have even weight. Assuming the original generator polynomial is g(x) = p(x). A new code word generated by g(x) = (x+1)p(x) equals to the sum of an original codeword and its shifted copy. The total weight of these two sequences (original and its shifted copy) must be even. The mod-2 addition cancels only even 1 s of the two sequences counted together. Hence, the new code word has even weight. e.g., = bit CRC-CCITT g(x) = x 16 +x 12 +x 5 +1 = (x 15 +x 14 +x 13 +x 12 +x 4 +x 3 +x 2 +x+1)(x+1) The 16-bit CRC-CCITT is defined as the remainder obtained by dividing the message polynomial m(x)x 16 by g(x). The codewords are formed as a k-bit information sequence followed by a check pattern of 16 bits (two 8- bit bytes) at the end of message. The result is a (k+16, k) code.

10 16-bit CRC-CCITT Systematic encoder for CCITT polynomial code with g(x) = x 16 +x 12 +x bit CRC-CCITT In the encoding process, two zero bytes are added to the end of the message, which are used when computing the CRC. (This corresponds to m(x)x 16.) When a message is sent, these two zero bytes are replaced by the CRC bytes. At the receiver the decoder simply computes the CRC of the message part and adds the results to the CRC bytes, and then tests to see whether the result equals zero.

11 16-bit CRC-CCITT A CRC constructed by an (n, k) cyclic code is capable of detecting any error burst of length n k or less. Also, the fraction of undetectable error burst of length n k+1 is ) ( 2 -(n-k-1) as discussed earlier. Thus, CRC-16 has a very good burst error detection ability: % CRC-16 ANSI (American National Standards Institute) g(x) = x 16 +x 15 +x 2 +1= (x 15 +x+1 )(x+1 ) CRC used in spread spectrum cellular system (IS-95 CDMA) g(x)=x 30 +x 29 +x 21 +x 20 +x 15 +x 13 +x 12 +x 11 +x 8 +x 7 +x 6 +x 2 +x+1 CRC used in ATM protocol (CRC-ATM) g(x) = x 8 +x 2 +x+1 BCH Codes 1. Introduction 2. Primitive BCH Codes 3. Generator Polynomial of Binary BCH Codes 4. Minimum Distance of Binary BCH Codes 5. Decoding of BCH Codes 6. Syndrome and Error Pattern 7. Error-Location Polynomial 8. Peterson s Direct-Solution 9. Direct Solutions of Some Simple Cases 10. Computation of Error-Location Numbers 11. Peterson-Gorenstein-Zierler Decoding Algorithm 12. BCH Codes as Industry Standards

12 Introduction BCH (Bose Chaudhuri Hocquenghem) Codes form a large class of multiple random error-correcting codes. They were first discovered by A. Hocquenghem in 1959 and independently by R. C. Bose and D. K. Ray- Chaudhuri in BCH codes are cyclic codes. The original applications of BCH codes were restricted to binary codes of length 2 m 1 for some integer m. These were extended later by Gorenstein and Zieler (1961) to the nonbinary codes with symbols from Galois field GF(q). Introduction The first decoding algorithm for binary BCH codes was devised by Peterson in Since then, Peterson s algorithm has been refined by Berlekamp, Massey, Chien, Forney, and many others.

13 Primitive BCH Codes For any integer m 3 and t < 2 m 1 (choose m and t), there exists a primitive BCH code with the following parameters: n = 2 m 1 n k mt d min 2t+1 This code can correct t or fewer random errors over a span of 2 m 1 bit positions. The code is a t-errorcorrecting BCH code. For example, for m = 6, t = 3 n = = 63, n k = 6 x 3 =18, d min = 2 x 3+1=7 This is a triple-error-correcting (63, 45) BCH code. Generator Polynomial of Binary BCH Codes Let α be a primitive element in GF(2 m ). For 1 i t, let φ 2i-1 (x) be the minimum polynomial of the field element α 2i 1. The degree of φ 2i-1 (x) is m or a factor of m. The generator polynomial g(x) of a t-error-correcting primitive BCH codes of length 2 m 1 is given by g(x) = LCM{φ 1 (x), φ 3 (x),, φ 2t-1 (x)}. Note that the degree of g(x) is mt or less. Hence the number of parity-check bits, n k, of the code is at most mt.

14 Generator Polynomial of Binary BCH Codes Note that the generator polynomial of the binary BCH code is originally found to be the least common multiple of the minimum polynomials φ 1, φ 2,, φ 2t, i.e., g(x) = LCM{φ 1 (x), φ 2 (x), φ 3 (x),, φ 2t-1 (x), φ 2t (x)}. However, generally, every even power of α in GF(2 m ) has the same minimal polynomial as some preceding odd power of α in GF(2 m ). As a consequence, the generator polynomial of the t-error-correcting binary BCH code can be reduced to g(x) = LCM{φ 1 (x), φ 3 (x),, φ 2t-1 (x)}. Example For m = 4, t = 3, let α be a primitive element in GF(2 4 ). which is constructed based on the primitive polynomial p(x) =1+x+x 4 φ 1 (x) =1+x+x 4 corresponding to α φ 3 (x) =1+x+x 2 +x 3 +x 4 corresponding to α 3 φ 5 (x) =1+x+x 2 corresponding to α 5 g(x) = LCM{φ 1 (x), φ 3 (x), φ 5 (x)}= φ 1 (x)φ 3 (x)φ 5 (x) = 1+x+x 2 +x 4 +x 5 +x 8 +x 10 The code is a (15, 5) cyclic code.

15 Remarks Remark 1: BCH code is a cyclic code. We look for a good generator polynomial, g(x). It must divide x n +1. Recall that a primitive polynomial of degree m divides x 2m Remark 2: The construction of φ 2i-1 (x). For example, i =1, φ 1 (x) must contain the factor (x α). However, its coefficients of must be all binary. Hence, we include the conjugate root, α 2l=1 = α 2, into the polynomial; that is, φ 1 (x) = (x α)(x α 2 ) = x 2 (α+α 2 )x+α 3 = x 2 x+α 3 Unfortunately, its coefficients are not all binary. Remarks We further include two more conjugate roots α 4, α 8 and therefore, φ 1 (x) = (x α)(x α 2 )(x α 4 )(x α 8 ) = 1+x+x 4 Similarly, φ 3 (x) = 1+x+x 2 +x 3 +x 4 contains roots α 3,(α 3 ) 2l=1 =α 6, (α 3 ) 2l=2 =α 12,(α 3 ) 2l=3 =α 24 =α 9, and φ 5 (x) = 1+x+x 2 contains roots α 5,(α 5 ) 2l=1 =α 10. Remark 3: Even-indexed φ 2i (x). We will show that all the roots of φ 2i (x) are contained in the odd-indexed φ j (x), where j < i. An even index 2i can be expressed as 2i = j2 l, where j is an odd number and l 1. Clearly, α 2i = α j2l is a conjugate of α j and therefore, α 2i and α j have the same minimal polynomial; that is, φ 2i (x) = φ j (x).

16 Constructing a BCH Code The steps of constructing a BCH code are as follows: Choose a primitive polynomial of degree m and construct GF(2 nm ). Find the minimal polynomial φ 2i 1 (x) of α 2i-1 for i =1,,t. Obtain g(x) = LCM{φ 1 (x), φ 3 (x),, φ 2t-1 (x)}. Determine k from the relation deg(g(x)) = n k. Find the minimum distance d min 2t+1 Minimum Distance of Binary BCH Codes Consider a t-error-correcting BCH code of length n=2 m 1 with generator polynomial g(x). g(x) has as α, α 2, α 3,, α 2t roots, i.e. g(α i ) = 0, for 1 i 2t. Since a code polynomial c(x) is a multiple of g(x), c(x) also has α, α 2, α 3,, α 2t as roots, i.e. c(α i ) = c 0 +c 1 α i +c 2 α 2i + +c n-1 α (n-1)i =0, for 1 i 2t. (**) A polynomial c(x) of degree less than 2 m 1is a code polynomial if and only if it has α, α 2,, α 2t as roots.

17 Minimum Distance of Binary BCH Codes Rewrite eqn.(**) in the following form: = 0, for 1 i 2t. Put all 2t equations together, the parity check matrix of this code is Minimum Distance of Binary BCH Codes 2t It is clear that ch T = (0 0 0). H is the parity-check matrix of the t-error correcting primitive q-ary BCH code of length n=q m 1. Each entry of H is represented by an m-tuple over GF(q) in column form. A binary polynomial c(x) of degree less than 2 m 1 is a code polynomial if and only if it has α, α 2,, α 2t as roots. We will show that the minimum weight of any codeword is at least 2t+1. Therefore, the minimum distance of the BCH code is at least 2t+1.

18 Minimum Distance of Binary BCH Codes Let c = (c 0 c 1 c n 1 ) be a nonzero codeword whose nonzero components are c j1, c j2,, c js. Hence, its Hamming weight s. Our proof is by contradiction. Suppose s 2t (hypothesis). We will show that this assumption is invalid. From the parity check equation, 0 = ch T = (c 0 c 1 c n 1 ) Minimum Distance of Binary BCH Codes Pick up the s rows of H T that correspond to the s nonzero coefficients: 0 =(c j1 c j2 c js ) = (c j1 c j2 c js )

19 Minimum Distance of Binary BCH Codes We then retain the first s columns of the H T matrix: 0 = (c j1 c j2 c js ) Since all the components of c j1, c j2,, c js are nonzero, the determinant of the remaining H T matrix must be zero. That is, = 0 Minimum Distance of Binary BCH Codes The above determinant can be simplified as follows: α j1+j2+ +js = 0 This implies that the determinant = = 0

20 Minimum Distance of Binary BCH Codes Note that is a Vandermonde determinant and = (α ji α jk ). Hence, ch T = 0 cannot be true. This implies that our hypothesis that the weight s 2t is invalid. Therefore, the minimum weight of any nonzero codeword is at least 2t+1. Hence, 2t+1 is a lower bound on the minimum distance of a t-error-correcting BCH code. In many cases, the true minimum distance is greater than 2t+1.) (Lin and Costello, pp )

ENGG1410-F Tutorial 6

ENGG1410-F Tutorial 6 Jianwen Zhao Department of Computer Science and Engineering The Chinese University of Hong Kong 1/16 Problem 1. Matrix Diagonalization Diagonalize the following matrix: A = [ ] 1 2 4 3 2/16 Solution The