BCH Code

UnIT IV : PART I

Sumit Kumar Choubey

March 22, 2020

1
 Table of contents

1. Description of BCH Codes

Encoding Examples

2. Parity-Check Matrix of a BCH Code

3. BCH Bound

4. Syndrome Calculation
Peterson–Gorenstein–Zierler algorithm

2
BCH codes

“ In coding theory, the BCH codes or Bose–Chaudhuri–Hocquenghem codes form

a class of cyclic error correcting codes that are constructed using polynomials
over a finite field (also called Galois field). BCH codes were invented in 1959 by
French mathematician Alexis Hocquenghem, and independently in 1960 by
Raj Bose and D. K. Ray-Chaudhuri. The name Bose–Chaudhuri–Hocquenghem
(and the acronym BCH) arises from the initials of the inventors’ surnames
(mistakenly, in the case of Ray-Chaudhuri).

3
Description of BCH Codes

4
 Description of BCH Codes
• The Bose, Chaudhuri, and Hocquenghem (BCH) codes form a large class of pow-
erful 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:

BCH Code Parameters

Parameters Value

Block length n = 2m − 1
Number of parity-check digits n − k ⩽ mt
Minimum distance dmin ⩾ 2t + 1
5
 Description of BCH Codes…

• 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 , α3 , . . . , α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), . . . , ϕ2t (X)}

6
 Description of BCH Codes…
′ ′
• If i is an even integer, it can be expressed as i = i 2l , where i is odd and l > 1.
′ l ( ′ )2l ( ′ )2l
2
αi = αi ⇒ αi = αi ⇒ αi = αi

′
• Then αi is a conjugate of αi . hence,

ϕi (X) = ϕi ′ (X)

⇒ g(X) = LCM{ϕ1 (X), ϕ2 (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.
7
 Encoding Example · · · I

Problem 1 Find the generator polynomial for the BCH code with block length
May 2018 SPPU n = 15 and error correcting capability tC = 2. Use primitive polyn-
imial X4 + X + 1 over GF(24 ).

Solutin :: here tC = 2 and we know that g(X) = LCM{ϕ1 (X), ϕ2 (X), . . . , ϕ2tC −1 (X)}

⇒ g(X) = LCM{ϕ1 (X), ϕ2 (X), ϕ3 (X)}

and, ϕ1 (X) = ϕ2 (X) {∵ α is Conjugate of α2 }

⇒ g(X) = LCM{ϕ1 (X), ϕ3 (X)}
ϕ1 (X) = X4 + X + 1 and, ϕ2 (X) = X4 + X3 + X2 + X + 1
g(X) = (X4 + X + 1) × (X4 + X3 + X2 + X + 1)
g(X) = X8 + X7 + X6 + X4 + 1
8
 Encoding Example · · · II

Calculation
ϕ1 (X) = (X + α) × (X + α2 ) × (X + α4 ) × (X + α8 )
of ϕ1 (X)
ϕ1 (X) = (X2 + (α + α2 )X + α3 ) × (X2 + (α4 + α8 )X + α12 )
ϕ1 (X) = (X2 +α5 X+α3 ) × (X2 +α5 X+α12 ) {∵ α+α2 = α5 = α4 +α8 }
ϕ1 (X) = X4 +(α5 +α5 )X3 +(α3 +α10 +α12 )X2 +(α8 +α2 )X+α15
◀ α5 +α5 = 0 ▶ ◀ α3 +α10 +α12 = α3 +α2 +α+1+α3 +α2 +α+1 = 0 ▶
◀ α2 + α8 = α2 + α2 + 1 = 1 ▶ ◀ α15 = 1 ▶
ϕ1 (X) = X4 + X + 1

Hint : Refer Slide 11 for GF(24 )

9
 Encoding Example · · · III

Calculation
ϕ3 (X) = (X + α3 ) × (X + α6 ) × (X + α9 ) × (X + α12 )
of ϕ3 (X)
ϕ3 (X) = (X2 + (α3 + α12 )X + α15 ) × (X2 + (α6 + α9 )X + α15 )
ϕ3 (X) = (X2 +α10 X+1)×(X2 +α5 X+1) {α3 +α12 = α10 & α6 +α9 = α5 }
ϕ3 (X) = X4 + (α10 + α5 )X3 + (1 + 1 + α15 )X2 + (α10 + α5 )X + 1

◀ α5 + α10 = α2 + α + α2 + α + 1 = 1 ▶ ◀ α15 = 1 ▶

ϕ3 (X) = X4 + X3 + X2 + X + 1

Hint : Refer Slide 11 For GF(24 )

10
 Galois Field

GF(24 ) using primitive polynomial X4 + X + 1

Exponential Form Polynomial Form Exponential Form Polynmial Form

α0 1 α8 α2 + 1
α1 α α9 α3 + α
α2 α2 α10 α2 + α + 1
α3 α3 α11 α3 + α2 + α
α4 α + 1 α12 α3 + α2 + α + 1
α5 α2 + α α13 α3 + α2 + 1
α6 α3 + α2 α14 α3 + 1
α7 α3 + α + 1 α15 1

11
Parity-Check Matrix of a BCH Code

12
 Parity-Check Matrix of a BCH Code · · · I

We can define a t-error-correcting BCH code of length n = 2m −1 in the following

manner :

Definition A binary n-tuple v = (vn−1 , . . . , v1 , v0 ) is a code word if and

only if the polynomial v(X) = vn−1 Xn−1 + . . . + v1 X + v0 has
{α, α2 , α3 , . . . , α2t } as its roots.

• Since αi is a root of v(X) for 1 ⩽ i ⩽ 2t, then

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

13
 Parity-Check Matrix of a BCH Code · · · II

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

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

• Let  
α(n−1) α(n−2) ··· α2 α 1
 (α2 )(n−1) (α2 )(n−2) ··· (α2 )2 α2 1
 
 3 (n−1) (α3 )(n−2) ··· (α3 )2 α3 1
HBCH =  (α ) 
 .. .. .. .. .. .. 
 . . . . . .
(α2t )(n−1) (α2t )(n−2) · · · (α2t )2 α2t 1
14
 Parity-Check Matrix of a BCH Code · · · III

• Then
T
v · HBCH
• 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.
• HBCH is a parity-check matrix of the code.
• If for some i and j, αj is a conjugate of αi , then v(αj ) = 0 if and only if v(αi ) = 0.
So HBCH can be modified as
 
α(n−1) α(n−2) ··· α2 α 1
 (α3 )(n−1) (α3 )(n−2) ··· (α3 )2 α3 1
 
 (α5 )(n−1) 5 (n−2) ··· 5 2 5 1
HBCH =  (α ) (α ) α 
 .. .. .. .. .. .. 
 . . . . . .
(α2t−1 )(n−1) (α2t−1 )(n−2) · · · (α2t−1 )2 α2t−1 1
15
 Parity-Check Matrix of a BCH Code · · · IV

Binary Parity If each entry of HBCH is replaced by its corresponding m-tuple over
Check Matrix GF(2) arranged in column form, we obtain a binary parity-check
matrix for the code.

16
 BCH Bound

Theorem The t-error-correcting BCH code defined has minimum distance

at least 2t + 1.

The parameter 2t+1 is usually called the designed distance of the t-error-
1 correcting BCH code.

2 The true minimum distance of the code might be larger than 2t + 1.

17
Syndrome Calculation

18
 Syndrome Calculation · · · I

• Let
r(X) = rn−1 Xn−1 + · · · + r2 X2 + r1 X + r0
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 · HTBCH

•
Si = r(αi ) = rn−1 α(n−1)i + · · · + r2 α2i + r1 αi + r0 ∀ 1 ⩽ i ⩽ 2t

19
 Syndrome Calculation · · · II

• 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 α, α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.

20
 Syndrome Calculation · · · III

2t-tuple Suppose that the error pattern e(X) has v errors at locations {0 ⩽
Syndrome j1 < j2 < · · · < jv ⩽ n}. That is, e(X) = ej1 Xj1 + ej2 Xj2 + · · · +
ejv Xjv So,
S1 = ej1 αj1 + ej2 αj2 + · · · + ejv αjv
S2 = ej1 (α2 )j1 + ej2 (α2 )j2 + · · · + ejv (α2 )jv
S3 = ej1 (α3 )j1 + ej2 (α3 )j2 + · · · + ejv (α3 )jv
..
.

S2t = ej1 (α2t )j1 + ej2 (α2t )j2 + · · · + ejv (α2t )jv
where ej1 , ejv 2 , . . . , ejv , and αj1 , αj2 , . . . , αjv are unknown.
 Any method for solving these equations is a decoding algo-
rithm for the BCH codes.

21
 Syndrome Calculation · · · IV

• Let Yi = eji , Zi = αji , 1 ⩽ i ⩽ v.

• Then 2t syndrome equations can be rewritten as follows

S1 = Y1 Z1 + Y2 Z2 + · · · + Yv Zv

S2 = Y1 Z21 + Y2 Z22 + · · · + Yv Z2v

S3 = Y1 Z31 + Y2 Z32 + · · · + Yv Z3v
..
.

S1 = Y1 Z2t 2t 2t
1 + Y2 Z2 + · · · + Yv Zv

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

22
 Syndrome Calculation · · · V

• Consider the error-locator polynomial

Λ(X) = (1 − Z1 X)(1 − Z2 X) · · · (1 − Zv X) = 1 + Λ1 X + Λ2 X2 + · · · + Λv Xv

• Multiplying above equation by Yi Zj+v

i , where 1 ⩽ j ⩽ v, and set X = Z−1
i we
have

0 = Yi Zj+v
i i + Λ2 Z i + · · · + Λv Z i )
(1 + Λ1 Z−1 −2 −v
∀ 1⩽i⩽v

• Summing all above v equations, we have

∑
v ∑
v ∑
v ∑
v
0= Yi Zj+v
i + Yi Λ1 Zj+v−1
i + Yi Λ2 Zj+v−2
i + ··· + Yi Λv Zji
i=1 i=1 i=1 i=1

Λ1 Sj+v−1 + Λ2 Sj+v−2 + · · · + Λv Sj = −Sj+v ∀ 1⩽j⩽v

23
 Syndrome Calculation · · · VI

• Putting the above equations into matrix form we have

    
S1 S2 ··· Sv Λv −Sv+1
 S2 · · · Sv+1     
 S3  Λv−1  −Sv+2 
 .. .. .. ..   ..  =  .. 
 . . . .  .   . 
Sv Sv+1 · · · 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.

24
 Syndrome Calculation · · · VII

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

 
S1 S2 ··· Su
 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.

25
 Peterson–Gorenstein–Zierler algorithm I
Peterson’s algorithm is the step 2 of the generalized BCH decoding procedure. Peter-
son’s algorithm is used to calculate the error locator polynomial coefficients Λ1 , Λ2 , . . . , Λv
of error locator polynomial :

Λ(X) = 1 + Λ1 X + Λ2 X2 + · · · + Λv Xv

Now the procedure of the Peterson–Gorenstein–Zierler algorithm. Expect we have at

least 2t syndromes S1 , S2 , . . . , S2v .

Start by generating the Syndrome matrix S with elements that are syn-
drome values  
S1 S2 ··· Sv
1  S2 S · · · S 
 3 v+1 
S =  .. .. .. .. 
 . . . . 
Sv Sv+1 · · · S2v−1

26
 Peterson–Gorenstein–Zierler algorithm II

Generate a C vector with elements

 
−Sv+1
2 −Sv+2 
 
C =  .. 
 . 
−S2v

Let Λ denote the unknown polynomial coefficients, which are given by

 
Λv
3 Λv−1 
 
Λ =  .. 
 . 
Λ1

27
 Peterson–Gorenstein–Zierler algorithm III

Form the matrix equation

4 S·Λ=C

If the determinant of matrix S is nonzero, then we can actually find an

5
inverse of this matrix and solve for the values of unknown Λ values.

If det(S) = 0, continue from the beginning of Peterson’s decoding by

6 making smaller S

7 After you have values of Λ , you have the error locator polynomial.

8 Stop Peterson procedure.

28
 Example I

Problem 2 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 ).

Solution : The syndromes can be calculated as follows:

syndromes

syndromes Polynomial Simplified syndromes Polynomial Simplified

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

29
 Example II

Set v = 3, we have    12 
S1 S2 S3 α α9 0
M = S2 S3 S4  =  α9 0 α3 
S3 S4 S5 0 α12 1
det(M) = 0
Set v = 2, we have [ ] [ 12 ]
S1 S2 α α9
M= =
S2 S3 α9 0
det(M) ̸= 0
We then calculate [ ]
−1 0 α6
M = 6
α α9
Hence,
30
 Example III

[ ] [ ][ ] [ 9 ]
Λ2 0 α6 0 α
= 6 = 12
Λ1 α α9 α3 α
and
Λ(X) = 1 + Λ1 X + Λ2 X2 = 1 + α12 X + α9 X2 =

Λ(X) = (1 + α2 X)(1 + α7 X) = α9 (X + α13 )(X + α8 )

so
e(X) = X13 + X8

31
I’d love to hear your thoughts, issues, questions and comments.

32