Yunghsiang S. Han - NTPU

1 BCHC odesYunghsiang S. HanGraduate Institute of Communication Engineering,National Taipei UniversityTaiwanE-mail: S. HanBCH codes1 Description of BCH Codes The Bose, Chaudhuri, and Hocquenghem (BCH) codes form alarge class of powerful random error-correcting cyclic codes. This class of codes is a remarkable generalization of theHamming code for multiple-error correction. We only consider binary BCH codes in this lecture BCH codes such as Reed-Solomon codes will bediscussed in next lecture note. For any positive integersm 3 andt<2m 1, there exists abinary BCH code with the following parameters:Block length:n=2m 1 Number of parity-check digits:n k mtMinimum distance:dmin 2t+ Institute of Communication Engineering, National Taipei UniversityY.

2 S. HanBCH codes2 We call this code at-error-correctingBCH code . Let be a primitive element inGF(2m). The generatorpolynomialg(x) of thet-error-correcting BCH code of length2m 1 is thelowest-degree polynomialoverGF(2) which has , 2, 3, .. , 2tas its roots. g( i) = 0 for 1 i 2tandg(x) has , 2, .. , 2tand theirconjugates as all its roots. Let i(x) be the minimal polynomial of i. Theng(x) must betheleast common multipleof 1(x), 2(x), .. , 2t(x), ,g(x) = LCM{ 1(x), 2(x), .. , (x)2t}. Ifiis an even integer, it can be expressed asi=i 2!, wherei isGraduate Institute of Communication Engineering, National Taipei UniversityY.

3 S. HanBCH codes3odd and">1. Then i=( i )2!is a conjugate of i . Hence, i(x)= i (x). g(x) = LCM{ 1(x), 3(x), .. , 2t 1(x)}. The degree ofg(x) is at mostmt. That is, the number ofparity-check digits,n k, of the code is at most equal tomt. Iftis small,n kis exactly equal tomt. Since is a primitive element, the BCH codes defined are usuallycalledprimitive(ornarrow-sense) BCH Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes4 Example Let be a primitive element ofGF(24) such that 1 + + 4= minimal polynomials of , 3,and 5are 1(x) = 1 +x+x4, 3(x) = 1 +x+x2+x3+x4, 5(x) = 1 +x+x2,respectively.

4 The double-error-correcting BCH code of lengthn=24 1 = 15 is generated byg(x) = LCM{ 1(x), 3(x)}= (1 +x+x4)(1 +x+x2+x3+x4)= 1 +x4+x6+x7+ k= 8 such that this is a (15,7, 5) code . Since the weight ofGraduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes5the generator polynomial is 5, it is a (15,7,5) code . The triple-error-correcting BCH code of length 15 is generated byg(x) = LCM{ 1(x), 3(x), 5(x)}= (1 +x+x4)(1 +x+x2+x3+x4)(1 +x+x2)= 1 +x+x2+x4+x5+x8+ k= 10 such that this is a (15,5, 7) code . Since the weightof the generator polynomial is 7, it is a (15,5,7) code .

5 The single-error-correcting BCH code of length 2m 1 is aHamming Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes6 Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes7 Examples of Finite Fields Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes8 BCH Codes of Lengths Less than 210 1 (1) Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes9 BCH Codes of Lengths Less than 210 1 (2) Graduate Institute of Communication Engineering, National Taipei UniversityY.

6 S. HanBCH codes10 Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes11 Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes12 Minimal Polynomials of the Elements inGF(26)Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes13 Generator Polynomials of All BCH Codes of Length 63 Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes14 Parity-Check Matrix of a BCH code We can define at-error-correcting BCH code of lengthn=2m 1 in the following manner: A binaryn-tuplev=(v0,v1.)

7 , vn 1) is a code word if and only if the polynomialv(x)=v0+v1x+ +vn 1xn 1has , 2, .. , 2tas roots. Since iis a root ofv(x) for 1 i 2t, thenv( i)=v0+v1 i+v2 2i+ +vn 1 (n 1)i= Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes15 This equality can be written as a matrix product as follows:(v0,v1, .. , vn 1) 1 i (n 1)i =0(1)for 1 i Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes16 LetH= 1 2 3 n 11( 2)( 2)2( 2)3 ( 2)n 11( 3)( 3)2( 3)3 ( 3)n ( 2t)( 2t)2( 2t)3 ( 2t)n 1 .(2) From (1), ifv=(v0,v1, .. , vn 1) is a code word in thet-error-correcting BCH code , thenv HT=0.

8 If ann-tuplevsatisfies the above condition, iis a root of thepolynomialv(x). Therefore,vmust be a code word in thet-error-correcting BCH Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes17 His a parity-check matrix of the code . If for someiandj, jis a conjugate of i, thenv( j) = 0 if andonly ifv( i) = 0. TheHmatrix can be reduced toH= 1 2 3 n 11( 3)( 3)2( 3)3 ( 3)n 11( 5)( 5)2( 5)3 ( 5)n ( 2t 1)( 2t 1)2( 2t 1)3 ( 2t 1)n 1 . If each entry ofHis replaced by its correspondingm-tuple overGF(2) arranged in column form, we obtain a binary parity-checkmatrix for the Institute of Communication Engineering, National Taipei UniversityY.

9 S. HanBCH codes18 BCH Bound Thet-error-correcting BCH code defined has minimum distanceat least 2t+ :We need to show that no 2tof fewer columns ofHsumto zero. Suppose that there exists a nonzero code vectorvwithweight 2t. Letvj1,vj2, .. , vj be the nonzero components ofv. Then0=v HT=(vj1,vj2, .. , vj ) j1( 2)j1 ( 2t)j1 j2( 2)j2 ( 2t)j2 j3( 2)j3 ( 2t) j ( 2)j ( 2t)j Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes19= (1,1, .. ,1) j1( j1)2 ( j1)2t j2( j2)2 ( j2)2t j3( j3)2 ( j3) j ( j )2 ( j )2t .The equality above implies the following equality:(1,1.)

10 ,1) j1( j1)2 ( j1) j2( j2)2 ( j2) j3( j3)2 ( j3) .. j ( j )2 ( j ) =0,Graduate Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes20which the second matrix on the left is a square matrix. Tosatisfy the above equality, the determinant of the matrixmust be zero. That is, j1( j1)2 ( j1) j2( j2)2 ( j2) j3( j3)2 ( j3) .. j ( j )2 ( j ) = Institute of Communication Engineering, National Taipei UniversityY. S. HanBCH codes21 Then j1+j2+ +j 1 j1 j1( 1)1 j2 j2( 1)1 j3 j3( 1)..1 j j ( 1) = determinant in the equality above is aVandermondedeterminantwhich isnonzero.