西安电子科技大学：《纠错码》课程教学资源（课件讲义）BCH Codes

BCH Codes Yunghsiang S.Han（韩永祥) School of Electrical Engineering Intelligentization Dongguan University of Technology(东莞理工学院) China E-mail:yunghsiangh@gmail.com

BCH Codes Yunghsiang S. Han （韩永祥） School of Electrical Engineering & Intelligentization Dongguan University of Technology (东莞理工学院) China E-mail: yunghsiangh@gmail.com

Y.S.Han BCH codes 1 Description of BCH Code The Bose,Chaudhuri,and Hocquenghem(BCH)codes form a large class of powerful random error-correcting cyclic codes. This class of codes is a remarkable generalization of the Hamming code for multiple-error correction. We only consider binary BCH codes in this lecture note. Non-binary BCH codes such as Reed-Solomon codes will be discussed in next lecture note. For any positive integers m >3 and t<2m-1,there exists a binary BCH code with the following parameters: Block length: n=2m-1 Number of parity-check digits: n-k≤mt Minimum distance: dmin≥2t+1. School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han BCH codes 1 Description of BCH Code • The Bose, Chaudhuri, and Hocquenghem (BCH) codes form a large class of powerful random error-correcting cyclic codes. • This class of codes is a remarkable generalization of the Hamming code for multiple-error correction. • We only consider binary BCH codes in this lecture note. Non-binary BCH codes such as Reed-Solomon codes will be discussed in next lecture note. • For any positive integers m ≥ 3 and t < 2 m−1 , there exists a binary BCH code with the following parameters: Block length: n = 2m − 1 Number of parity-check digits: n − k ≤ mt Minimum distance: dmin ≥ 2t + 1. School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes 2 We call this code a t-error-correcting BCH code. Let a be a primitive element in GF(2T).The generator polynomial g(x)of the t-error-correcting BCH code of length 2m-1 is the lowest-degree polynomial over GF(2)which has a,a2,a3,.,a2t as its roots. 。g(a)=0for1≤i≤2 t and g(c)hasa,a2,,a2 and their conjugates as all its roots. Let (z)be the minimal polynomial of ai.Then g(x)must be the least common multiple of (),(),...,2(x),i.e., g(x)=LCM{p1(x),中2(x),,p(c)2t}. If i is an even integer,it can be expressed as i=i2e,where i' 29 is odd and >1.Then a=(ai is a conjugate of ai. School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han BCH codes 2 • We call this code a t-error-correcting BCH code. • Let α be a primitive element in GF(2m). The generator polynomial g(x) of the t-error-correcting BCH code of length 2 m − 1 is the lowest-degree polynomial over GF(2) which has α, α2 , α3 , . . . , α2t as its roots. • g(α i ) = 0 for 1 ≤ i ≤ 2t and g(x) has α, α2 , . . . , α2t and their conjugates as all its roots. • Let ϕi (x) be the minimal polynomial of α i . Then g(x) must be the least common multiple of ϕ1 (x), ϕ2 (x), . . . , ϕ2t (x), i.e., g(x) = LCM{ϕ1 (x), ϕ2 (x), . . . , ϕ(x) 2t }. • If i is an even integer, it can be expressed as i = i ′ 2 ℓ , where i ′ is odd and ℓ > 1. Then α i = ( α i ′ )2 ℓ is a conjugate of α i ′ . School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes Hence,p:(x)=中(r). ·g(x)=LCM{φ1(x),p3(x),,中2t-1(x)}. The degree of g(x)is at most mt.That is,the number of parity-check digits,n-k,of the code is at most equal to mt. If t is small,n-k is exactly equal to mt. Since a is a primitive element,the BCH codes defined are usually called primitive (or narrow-sense)BCH codes. School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han BCH codes 3 Hence, ϕi (x) = ϕi ′ (x). • g(x) = LCM{ϕ1 (x), ϕ3 (x), . . . , ϕ2t−1 (x)}. • The degree of g(x) is at most mt. That is, the number of parity-check digits, n − k, of the code is at most equal to mt. • If t is small, n − k is exactly equal to mt. • Since α is a primitive element, the BCH codes defined are usually called primitive (or narrow-sense) BCH codes. School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes Example Let a be a primitive element of GF(24)such that 1+a+a4=0.The minimal polynomials of a,a3,and a5 are p1(x)=1+x+x4, p3(a)=1+x+x2+x3+x4, p5(x)=1+x+x2, respectively.The double-error-correcting BCH code of length n=24-1=15 is generated by g(z)=LCM((x),3(x)} = (1+x+x4)(1+x+x2+x3+x4) =1+x4+x6+x7+x8 n-k=8 such that this is a(15,7,>5)code.Since the weight of the generator polynomial is 5,it is a (15,7,5)code. School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han BCH codes 4 Example • Let α be a primitive element of GF(24 ) such that 1 + α + α 4 = 0. The minimal polynomials of α, α3 , and α 5 are ϕ1 (x) = 1 + x + x 4 , ϕ3 (x) = 1 + x + x 2 + x 3 + x 4 , ϕ5 (x) = 1 + x + x 2 , respectively. The double-error-correcting BCH code of length n = 24 − 1 = 15 is generated by g(x) = LCM{ϕ1 (x), ϕ3 (x)} = (1 + x + x 4 )(1 + x + x 2 + x 3 + x 4 ) = 1 + x 4 + x 6 + x 7 + x 8 . n − k = 8 such that this is a (15, 7, ≥ 5) code. Since the weight of the generator polynomial is 5, it is a (15, 7, 5) code. School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes 5 The triple-error-correcting BCH code of length 15 is generated by g(x)=LCM{(x),3(x),(x)} =(1+x+x4)(1+x+x2+x3+x4)1+x+x2) =1+x+x2+x4+x5+x8+x10. n-k=10 such that this is a (15,5,>7)code.Since the weight of the generator polynomial is 7,it is a (15,5,7)code. The single-error-correcting BCH code of length 2m-1 is a Hamming code. School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han BCH codes 5 • The triple-error-correcting BCH code of length 15 is generated by g(x) = LCM{ϕ1 (x), ϕ3 (x), ϕ5 (x)} = (1 + x + x 4 )(1 + x + x 2 + x 3 + x 4 )(1 + x + x 2 ) = 1 + x + x 2 + x 4 + x 5 + x 8 + x 10 . n − k = 10 such that this is a (15, 5, ≥ 7) code. Since the weight of the generator polynomial is 7, it is a (15, 5, 7) code. • The single-error-correcting BCH code of length 2 m − 1 is a Hamming code. School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes 6 a a2 a4 a8 a16=a a3a6a12g24a48=a3 Representations of GF(24).p(z)=z4+z+1 =a9 Exponential Polynomial Binary Decimal Minimal Notation Notation Notation Notation Polynomial 0 0 0000 个 1 0001 ×+1 a1 Z 0010 2 x4+x+1 0100 x4+X+1 as 23 1000 8 X4+X3+X2+X+1 a4 Z+1 0011 3 x4+X+1 Q5 Z2+Z 0110 6 x2+X+1 z3+z2 1100 x4+x3土x2土x+1 z3+Z+1 1011 11 X4+x3+1 z2+1 0101 x4+X+1 z3+Z 1010 x4+x3+x2+X+1 Q10 z2+Z+1 0111 7 2+X+1 z3+z2+Z+1 1110 X4+x3+1 a12 Z3+z2+Z+1 1111 6 X4+x3+X2+X+1 Q13 23+z2+1 1101 x4+x3+1 Q14 z3+1 1001 9 X4+x3+1 School of Electrical Engineering Intelligentization, Dongguan University of Technology

Y. S. Han BCH codes 6

 Representations of GF(24 ). p(z) = z4 + z + 1 Exponential Notation Polynomial Notation Binary Notation Decimal Notation Minimal Polynomial 0 0 0000 0 x ! 0 1 0001 1 x + 1 ! 1 z 0010 2 x4 + x + 1 ! 2 z 2 0100 4 x4 + x + 1 ! 3 z 3 1000 8 x4 + x3 + x2 + x + 1 ! 4 z + 1 0011 3 x4 + x + 1 ! 5 z 2 + z 0110 6 x2 + x + 1 ! 6 z 3 + z2 1100 12 x4 + x3 + x2 + x + 1 ! 7 z 3 + z + 1 1011 11 x4 + x3 + 1 ! 8 z 2 + 1 0101 5 x4 + x + 1 ! 9 z 3 + z 1010 10 x4 + x3 + x2 + x + 1 ! 10 z 2 + z + 1 0111 7 x2 + x + 1 ! 11 z 3 + z2 + z + 1 1110 14 x4 + x3 + 1 ! 12 z 3 + z2 + z + 1 1111 15 x4 + x3 + x2 + x + 1 ! 13 z 3 + z2 + 1 1101 13 x4 + x3 + 1 ! 14 z 3 + 1 1001 9 x4 + x3 + 1 ! ! 2 ! 4 ! 8 ! 16 ! ! ! 3 ! 6 ! 12 ! 24 ! 48 ! ! 3 ! ! 9 School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes Examples of Finite Fields +,0123 ·,0123 0000 00123 00000 10123 1011 GF(4)→11032 GF2)[a]/ 210a /a2+a+1 22301 20231 311a+1 33210 30312 Primitive polynomial over GF(4) GF(42)=GF(4)[z]/z2+z+2,p(Z)=z2+z+2 8沿a Notaon NO沿a Notaton p68品a 0 0 00 0 A x+2 2+2 1 6 x2+X+3 3z+2 32 x2+3x+1 z+1 Operate on 1 x2+X+2 e GF(4) % 28 X+2 X2+2x+1 2z+3 23 x2+2x+2 a=Z z+3 x2+X+3 a15=1 2z+2 10 x2+2x+1 89 98 3z+1 2z+1 3z+3 x2+3x+1 x2+2x+2 15 x2+3x+3 School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y. S. Han BCH codes 7 Examples of Finite Fields

 GF(42 ) ! GF(4)[z]/z2+z+2, p(z) = z2+z+2 Exponential Notation Polynomial Notation Binary Notation Decimal Notation Minimal Polynomial 0 0 00 0 ! 0 1 01 1 x + 1 ! 1 z 10 4 x2 + x + 2 ! 2 z + 2 12 6 x2 + x + 3 ! 3 3z + 2 32 14 x2 + 3x + 1 ! 4 z + 1 11 5 x2 + x + 2 ! 5 2 02 2 x + 2 ! 6 2z 20 8 x2 +2x + 1 ! 7 2z + 3 23 11 x2 + 2x + 2 ! 8 z + 3 13 7 x2 + x + 3 ! 9 2z + 2 22 10 x2 + 2x + 1 ! 10 3 03 3 x + 3 ! 11 3z 30 12 x2 + 3x + 3 ! 12 3z + 1 31 13 x2 + 3x + 1 ! 13 2z + 1 21 9 x2 + 2x + 2 ! 14 3z + 3 33 15 x2 + 3x + 3 ! = z ! 15 = 1 Operate on GF(4) Primitive polynomial over GF(4) School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes BCH Codes of Lengths Less than 210-1(1) m n k t m n k t m n k t n n k t 3741 63 24 7 127501325518792557129 415111 1810 4314 179 10 63 30 7 2 16 36 171 11 55 31 3 1013 53126 1 7 15 13 45 43 7127 120 2 147 4 子 6 3 113 2 139 15 29 47 1 5 106 3 8255 247 1 21 55 6 7 99 4 19 59 66357 1 3 9 51 2 6 23 4 107 2 511 502 1 子 3 78 7 5 99 23 493 2 6 For t small 4 1 9 207 484 n-k=mt 36 5 10 199 7 2 475 30 6 57 11 191 8 79 27 4665 School of Electrical Engineering Intelligentization,Dongguan University of Technology

Y. S. Han BCH codes 8 BCH Codes of Lengths Less than 2 10 − 1 (1) m n k t m n k t m n k t n k t n k t 3 7 4 1 63 24 7 127 50 13 255 187 9 255 71 29 4 15 11 1 18 10 43 14 179 10 63 30 7 2 16 11 36 15 171 11 55 31 5 3 10 13 29 21 163 12 47 42 5 31 26 1 7 15 22 23 155 13 45 43 21 2 7 127 120 1 15 27 147 14 37 45 16 3 113 2 8 31 139 15 29 47 11 5 106 3 8 255 247 1 131 18 21 55 6 7 99 4 239 2 123 19 13 59 6 63 57 1 92 5 231 3 115 21 9 63 51 2 85 6 223 4 107 22 511 502 1 45 3 78 7 215 5 99 23 493 2 39 4 71 9 207 6 91 25 484 3 36 5 64 10 199 7 87 26 475 4 30 6 57 11 191 8 79 27 466 5 For t small n – k = mt School of Electrical Engineering & Intelligentization, Dongguan University of Technology

Y.S.Han BCH codes BCH Codes of Lengths Less than 210-1(2) n k t n k t n 个 t n k t 511457 6 511322 22 511193 43 511 58 91 1023 9339 448 7 313 184 吗 923 10 439 25 46 0 95 91311 430 9 31 109 903 421 4第57薪璃幼4第20 672 28 893 3 119 883 403 12 10 121 873 15 394 56 1013 1 863 16 0防新够 14 31 1023 1003 2 85817 993 983 18 637383911 59121110466 5886235 973 5 963 6 340 20 953 > 331 21 202 42 67 1 943 School of Electrical Engineering Intelligentization,Donggu uan University of Technology

Y. S. Han BCH codes 9 BCH Codes of Lengths Less than 2 10 − 1 (2) n k t n k t n k t n k t n k t 511 457 6 511 322 22 511 193 43 511 58 91 1023 933 9 448 7 313 23 184 45 49 93 923 10 439 8 304 25 175 46 40 95 913 11 430 9 295 26 166 47 31 109 903 12 421 10 286 27 157 51 28 111 893 13 412 11 277 28 148 53 19 119 883 14 403 12 268 29 139 54 10 121 873 15 394 13 259 30 130 55 1013 1 863 16 385 14 250 31 121 58 1023 1003 2 858 17 376 15 241 36 112 59 993 3 367 16 238 37 103 61 983 4 358 18 229 38 94 62 973 5 349 19 220 39 85 63 963 6 340 20 211 41 76 85 953 7 331 21 202 42 67 87 943 8 School of Electrical Engineering & Intelligentization, Dongguan University of Technology