BCH Codes

Yunghsiang S. Han

Department of Electrical Engineering,

National Taiwan University of Science and Technology
Taiwan
E-mail: yshan@[Link]
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.

Department of Electrical Engineering, National Taiwan University of Science and 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
2m − 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′

( ′ )2ℓ
i i i′
is odd and ℓ > 1. Then α = α is a conjugate of α .

Department of Electrical Engineering, National Taiwan University of Science and 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.

Department of Electrical Engineering, National Taiwan University of Science and 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 + x4 ,
ϕ3 (x) = 1 + x + x2 + x3 + x4 ,
ϕ5 (x) = 1 + x + x2 ,

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 + 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.

Department of Electrical Engineering, National Taiwan University of Science and 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 + 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.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 6

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




Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 7

Examples of Finite Fields

Primitive polynomial over GF(4)

GF(42) ! GF(4)[z]/z2+z+2, p(z) = z2+z+2
Exponential Polynomial Binary Decimal Minimal
Notation Notation Notation Notation 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 Operate on 11 5 x2 + x + 2
!5 2 02 2 x+2
!6 2z GF(4) 20 8 x2 +2x + 1
!7 2z + 3 23 11 x2 + 2x + 2
!=z !8 z+3 13 7 x2 + x + 3
!15 = 1 !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




Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 8

BCH Codes of Lengths Less than 210 − 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
For t small
n – k = mt 36 5 64 10 199 7 87 26 475 4
30 6 57 11 191 8 79 27 466 5

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 9

BCH Codes of Lengths Less than 210 − 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

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 10

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 11

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 12

Minimal Polynomials of the Elements in GF (26 )

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 13

Generator Polynomials of All BCH Codes of Length 63

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 14

Parity-Check Matrix of a BCH Code

• We can define a t-error-correcting BCH code of length
n = 2m − 1 in the following manner: A binary n-tuple
v = (v0 , v1 , . . . , vn−1 ) is a code word if and only if the
polynomial v(x) = v0 + v1 x + · · · + vn−1 xn−1 has α, α2 , . . . , α2t
as roots.
• Since αi is a root of v(x) for 1 ≤ i ≤ 2t, then

v(αi ) = v0 + v1 αi + v2 α2i + · · · + vn−1 α(n−1)i = 0.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 15

• This equality can be written as a matrix product as follows:

 
1
 
 α i 
 
 

(v0 , v1 , . . . , vn−1 )  α 2i =0 (1)

 .. 
 
 . 
α(n−1)i

for 1 ≤ i ≤ 2t.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 16

• Let
 
1 α α 2
α 3
··· α n−1
 
 1 2
(α ) (α )2 2 2 3
(α ) ··· 2 n−1
(α ) 
 
 
H =
 1 (α3 ) (α3 )2 (α3 )3 ··· (α3 )n−1  .
 (2)
 .. .. 
 
 . . 
1 (α2t ) (α2t )2 (α2t )3 ··· (α2t )n−1

• From (1), if v = (v0 , v1 , . . . , vn−1 ) is a code word in the

t-error-correcting BCH code, then
v · H T = 0.

• If an n-tuple v satisfies the above condition, αi is a root of the

polynomial v(x). Therefore, v must be a code word in the
t-error-correcting BCH code.
• H is a parity-check matrix of the code.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 17

• If for some i and j, αj is a conjugate of αi , then v(αj ) = 0 if

and only if v(αi ) = 0.
• The H matrix can be reduced to
 
1 α α2 α3 ··· α n−1
 
 1 (α3 ) (α3 )2 (α3 )3 ··· 3 n−1
(α ) 
 
 
H=  1 (α 5
) (α 5 2
) (α 5 3
) ··· (α5 )n−1  .

 . .. 
 .. 
 . 
1 (α2t−1 ) (α2t−1 )2 (α2t−1 )3 ··· (α2t−1 )n−1

• If each entry of H is replaced by its corresponding m-tuple

over GF (2) arranged in column form, we obtain a binary
parity-check matrix for the code.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 18

BCH Bound
• The t-error-correcting BCH code defined has minimum
distance at least 2t + 1.
Proof: We need to show that no 2t of fewer columns of H sum
to zero. Suppose that there exists a nonzero code vector v with
weight δ ≤ 2t. Let vj1 , vj2 , . . . , vjδ be the nonzero components
of v. Then

0 = v · HT
 
α j1 2 j1
(α ) ··· (α )2t j1
 
 α j2 2 j2
(α ) ··· (α )2t j2 
 
 j 
= (vj1 , vj2 , . . . , vjδ ) · 
 α 3
(α2 )j3 ··· (α2t )j3 

 . .. .. 
 .. 
 . . 
α jδ (α2 )jδ · · · (α2t )jδ

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 19

 
α j1 j1 2
(α ) ··· j1 2t
(α )
 
 α j2 j2 2
(α ) ··· j2 2t
(α ) 
 
 j 
= (1, 1, . . . , 1) · 
 α
3
(αj3 )2 ··· (αj3 )2t .

 . .. .. 
 .. 
 . . 
αjδ (αjδ )2 ··· (αjδ )2t

The equality above implies the following equality:

 
α j1
(α ) · · · (α )
j1 2 j1 δ
 
 αj2 (αj2 )2 · · · (αj2 )δ 
 
 j 

(1, 1, . . . , 1) ·  α 3 j3 2 j3 δ 
(α ) · · · (α )  = 0,
 . .. .. 
 .. 
 . . 
αjδ (αjδ )2 · · · (αjδ )δ

which the second matrix on the left is a δ × δ square matrix.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 20

To satisfy the above equality, the determinant of the δ × δ

matrix must be zero. That is,

α j1 (αj1 )2 ··· (αj1 )δ

α j2 (αj2 )2 ··· (αj2 )δ
α j3 (αj3 )2 ··· (αj3 )δ = 0.
.. .. ..
. . .
αjδ (αjδ )2 ··· (αjδ )δ

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 21

Then

1 α j1 ··· αj1 (δ−1)

1 α j2 ··· αj2 (δ−1)
αj1 +j2 +···+jδ · 1 α j3 ··· αj3 (δ−1) = 0.
.. .. ..
. . .
1 α jδ ··· αjδ (δ−1)

The determinant in the equality above is a Vandermonde

determinant which is nonzero. Contradiction!
• The parameter 2t + 1 is usually called the designed distance of
the t-error-correcting BCH code.
• The true minimum distance of the code might be larger than
2t + 1.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 22

Syndrome Calculation
• Let
r(x) = r0 + r1 x + r2 x2 + · · · + rn−1 xn−1
be the received vector and e(x) the error pattern. Then

r(x) = v(x) + e(x).

• The syndrome is a 2t-tuple,

S = (S1 , S2 , . . . , S2t ) = r · H T ,

where H is given by (2).

•
Si = r(αi ) = r0 + r1 αi + r2 α2i + · · · + rn−1 α(n−1)i
for 1 ≤ i ≤ 2t.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 23

• Dividing r(x) by the minimal polynomial ϕi (x) of αi , we have

r(x) = ai (x)ϕi (x) + bi (x),

where bi (x) is the remainder with degree less than that of

ϕi (x).
• Since ϕi (αi ) = 0, we have

Si = r(αi ) = bi (αi ).

• Since α1 , α2 , . . . , α2t are roots of each code polynomial,

v(αi ) = 0 for 1 ≤ i ≤ 2t.
• Then Si = e(αi ) for 1 ≤ i ≤ 2t.
• We now consider a general case that is also good for non-binary
case.
• Suppose that the error pattern e(x) has v errors at locations

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 24

0 ≤ j1 < j2 < · · · < jv ≤ n. That is,

e(x) = ej1 xj1 + ej2 xj2 + · · · + ejv xjv .

S1 = ej1 αj1 + ej2 αj2 + · · · + ejv αjv

S2 = ej1 (αj1 )2 + ej2 (αj2 )2 + · · · + ejv (αjv )2
S3 = ej1 (αj1 )3 + ej2 (αj2 )3 + · · · + ejv (αjv )3
..
.
S2t = ej1 (αj1 )2t + ej2 (αj2 )2t + · · · + ejv (αjv )2t , (3)

where ej1 , ej2 , . . . , ejv , and αj1 , αj2 , . . . , αjv are unknown.
• Any method for solving these equations is a decoding algorithm
for the BCH codes.
• Let Yi = eji , Xi = αji , 1 ≤ i ≤ v.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 25

• (3) can be rewritten as follows:

S1 = Y1 X1 + Y2 X2 + · · · + Yv Xv
S2 = Y1 X12 + Y2 X22 + · · · + Yv Xv2
S3 = Y1 X13 + Y2 X23 + · · · + Yv Xv3
..
.
S2t = Y1 X12t + Y2 X22t + · · · + Yv Xv2t . (4)

• We need to transfer the above set of non-linear equations into a

set of linear equations.
• Consider the error-locator polynomial

Λ(x) = (1 − X1 x)(1 − X2 x) · · · (1 − Xv x)
= 1 + Λ1 x + Λ2 x2 + · · · + Λv xv . (5)

• Multiplying (5) by Yi Xij+v , where 1 ≤ j ≤ v, and set x = Xi−1

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 26

we have
( )
0= Yi Xij+v 1+ Λ1 Xi−1 + Λ2 Xi−2 + ··· + Λv Xi−v ,

for 1 ≤ i ≤ v.
• Summing all above v equations, we have
∑
v ( )
0 = Yi Xij+v + Λ1 Xij+v−1 + ··· + Λv Xij
i=1
∑v ∑
v ∑
v
= Yi Xij+v + Λ1 Yi Xij+v−1 + · · · + Λv Yi Xij
i=1 i=1 i=1
= Sj+v + Λ1 Sj+v−1 + Λ2 Sj+v−2 + · · · + Λv Sj .

• We have

Λ1 Sj+v−1 + Λ2 Sj+v−2 + · · · + Λv Sj = −Sj+v

for 1 ≤ j ≤ v.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 27

• Putting the above equations into matrix form we have

    
S S2 · · · Sv−1 Sv Λv −Sv+1
 1    
    
 S2 S3 ··· Sv Sv+1   Λv−1   −Sv+2 
     . (6)
 ..   ..  =  .. 
 .  .   . 
    
Sv Sv+1 ··· S2v−2 S2v−1 Λ1 −S2v

• Since v ≤ t, S1 , S2 , . . . , S2v are all known. Then we can solve

for Λ1 , Λ2 , . . . , Λv .
• We still need to find the smallest v such that the above system
of equations has a unique solution.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 28

• Let the matrix of syndromes, M , be defined as follows:

 
S S2 ··· Su
 1 
 
 S2 S3 · · · Su+1 
M =  .. .. ..
.

 . . . 
 
Su Su+1 ··· S2u−1

• M is nonsingular if u is equal to v, the number of errors that

actually occurred. M is singular if u > v.
Proof: Let
 
1 1 ··· 1
 
 
 X1 X2 ··· Xu 
A=
 .. .. ..


 . . . 
 
X1u−1 X2u−1 ··· Xuu−1

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 29

with Aij = Xji−1 and

 
Y1 X1 0 ··· 0
 
 
 0 Y2 X2 ··· 0 
B=
 .. .. ..


 . . . 
 
0 0 ··· Yu Xu

with Bij = Yi Xi δij , where


 1 i=j
δij = .
 0 i=
̸ j

We have
( ) ∑
u ∑
u
T
ABA ij = Xℓi−1 Yℓ Xℓ δℓk Xkj−1
ℓ=1 k=1

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 30

∑
u
= Xℓi−1 Yℓ Xℓ Xℓj−1
ℓ=1
∑u
= Yℓ Xℓi+j−1 = Mij .
ℓ=1

Hence, M = ABAT . If u > v, then det(B) = 0 and then

det(M ) = det(A) det(B) det(AT ) = 0. If u = v, then
det(B) ̸= 0. Since A is a Vandermonde matrix with Xi ̸= Xj ,
i ̸= j, det(A) ̸= 0. Hence, det(M ) ̸= 0.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 31

The Peterson-Gorenstein-Zierler Algorithm

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 32

Example
Consider the triple-error-correcting (15, 5) BCH code with
g(x) = 1 + x + x2 + x4 + x5 + x8 + x10 . Assume that the received
vector is r(x) = x2 + x7 . The operating finite field is GF (24 ). Then
the syndromes can be calculated as follows:

S1 = α7 + α2 = α12
S2 = α14 + α4 = α9
S3 = α21 + α6 = 0
S4 = α28 + α8 = α3
S5 = α35 + α10 = α0 = 1
S6 = α42 + α12 = 0.

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 33

Set v = 3, we have

S1 S2 S3
det(M ) = S2 S3 S4
S3 S4 S5

α12 α9 0
= α9 0 α3 = 0.
0 α3 1

Set v = 2, we have

S1 S2 α12 α9
det(M ) = = ̸= 0.
9
S2 S3 α 0

Department of Electrical Engineering, National Taiwan University of Science and Technology

Y. S. Han BCH codes 34

We then calculate  
0 α6
M −1 =  .
α6 α9
Hence,
[ ] [ ] [ 9
]
Λ2 −1 0 α
=M =
Λ1 α3 α12
and

Λ(x) = 1 + α12 x + α9 x2
( 2
)( 7
)
= 1+α x 1+α x
( )( )
= α x−α
9 8
x−α .13

Since 1/α8 = α7 and 1/α13 = α2 , we found the error locations.

Department of Electrical Engineering, National Taiwan University of Science and Technology