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