Hamming and BCH Codes

By Fikreselam Gared(PhD)

Faculty of Electrical and Computer Engineering

Outline

1 Hamming Codes

2 BCH Codes

3 Parity Check matrix of BCH Codes

4 Syndrome Computation and decoding of BCH codes

Fikreselam G. Title: Hamming and BCH Codes 1 / 45

Hamming Codes

In the late 1949′ s Claud Shannon was developing information the-

ory and coding as a mathematical model for communication.

At the same time, Richard Hamming, a colleague of Shannon at

bell laboratories found a need for error correction in his work on
computers.

Hamming found a single error correcting binary Hamming codes

which remain important to this day, for theoretical and practical rea-
sons as well as historical.

Fikreselam G. Title: Hamming and BCH Codes 2 / 45

Hamming Codes

The binary (n, k) Hamming codes has the following properties

n = 2m − 1

k = 2m − m − 1

n−k =m

t=1

Fikreselam G. Title: Hamming and BCH Codes 3 / 45

Hamming Codes

To construct a single error correcting code we first assign k of the

n available positions as information positions.

Then n − k = m positions as check position.

The values in these k positions are to be determined in the encod-

ing process by even parity checks over selected information.

Fikreselam G. Title: Hamming and BCH Codes 4 / 45

Hamming Codes

The first parity check must use positions 1, 3, 5, 7, 9, ...

1 = 1, 3 = 11, 5 = 101, 7 = 111, ...

The second parity check must use positions 2, 3, 6, 7, 10, 11, ...

2 = 10, 3 = 11, 6 = 110, 7 = 111, 10 = 1011, ...

The third parity check must use positions 4, 5, 6, 7, 12, 13, ...

4 = 100, 5 = 101, 6 = 110, 7 = 111, 12 = 1100, ...

Fikreselam G. Title: Hamming and BCH Codes 5 / 45
Hamming Codes

Thus, the choice of positions 1, 2, 4, 8, ... is for checking position.

Check Position Positions Checked
1 1,3,5,7,9,11,13,15,17,...
2 2,3,6,7,10,11,14,15,18,...
4 4,5,6,7,12,13,14,15,20,...
8 8,9,10,11,12,13,14,15,20,...
. .
. .
. .

Fikreselam G. Title: Hamming and BCH Codes 6 / 45

Hamming Codes

Therefore, by checking the even parity of 1, 3, 5, 7, ... determine the

value in the first position.

Similarly by checking the even parity of 2, 3, 6, 7, ... determine the

value in the second position.

Using 4, 5, 6, 7, . . . determine the value in the third position and so

on.

The values for the position is terminated by n − k and checked

position is terminated by n.

Fikreselam G. Title: Hamming and BCH Codes 7 / 45

Hamming Codes

Example: n = 7, k = 4, m = n − k = 3, t = 1

Check Position (n − k = 3) Positions Checked

1 1,3,5,7=n
2 2,3,6,7
4 4,5,6,7

Fikreselam G. Title: Hamming and BCH Codes 8 / 45

Hamming Codes

pos.=1 pos.=2 pos.=3 pos.=4 pos.=5 pos.=6 pos.=7

0 0 0 0 0 0 0
1 1 0 1 0 0 1
0 1 0 1 0 1 0
1 0 0 0 0 1 1
1 0 0 1 1 0 0
0 1 0 0 1 0 1
1 1 0 0 1 1 0
0 0 0 1 1 1 1
1 1 1 0 0 0 0
0 0 1 1 0 0 1
1 0 1 1 0 1 0
0 1 1 0 0 1 1
0 1 1 1 1 0 0
1 0 1 0 1 0 1
0 0 1 0 1 1 0
1 1 1 1 1 1 1

Fikreselam G. Title: Hamming and BCH Codes 9 / 45

Error detection and correction in Hamming Codes

Let v = (1 1 1 0 0 0 0) and r = (1 1 1 0 0 1 0)

Position 1, 3, 5, 7 = 1100 which is even =⇒ 0

Position 2, 3, 6, 7 = 1110 which is odd =⇒ 1

Position 4, 5, 6, 7 = 0010 which is odd =⇒ 1

Read from bottom to up= 110 = 6. This means error in the sixth
position is detected.

Thus v̂ = (1 1 1 0 0 0 0)

Fikreselam G. Title: Hamming and BCH Codes 10 / 45

BCH Codes

BCH codes, named after their discoveries, Bose, Chaudhuri, and

Hocquenghem, are 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.

Non-binary BCH codes such as Reed-Solomon codes will be dis-

cussed in next chapter.

Fikreselam G. Title: Hamming and BCH Codes 11 / 45

BCH Codes

For any positive integers m ≥ 3 there exists a binary BCH code

with the following parameters:
Block length: n = 2m − 1
Number of parity check digits: n − k ≤ mt
Minimum distane dmin ≥ 2t + 1

We call this a t− error correcting BCH codes.

The generator polynomial of BCH code is specified in terms of its

root from GF (2m ).

Fikreselam G. Title: Hamming and BCH Codes 12 / 45

BCH Codes

Let α be a primitive element in GF (2m ). The generator polynomial

g(x) of the t−error-correcting BCH code of length n = 2m − 1 is the
lowest degree polynomial over GF (2m ) which has α, α2 , ..., α2t as
its roots.

g(αi ) = 0, 1 ≤ i ≤ 2t (1)

The conjugates of αi , 1 ≤ i ≤ 2t are also roots of g(x).

Fikreselam G. Title: Hamming and BCH Codes 13 / 45

BCH Codes

Let ϕi (x) be the minimal polynomial of αi . Then g(x) must be the

least common multiple of ϕi (x), 1 ≤ i ≤ 2t.

g(x) = LCM{ϕ1 (x), ϕ2 (x), ϕ3 (x), ϕ4 (x), ..., ϕ2t (x)}

for even i, i = i′ 2l . Where i′ is odd and l > [Link]

′ l
αi = (αi )2

′
is conjugate of αi .Thus, ϕi (x) = ϕi′ (x) .

Fikreselam G. Title: Hamming and BCH Codes 14 / 45

BCH Codes

Finally, g(x) can be defined as

g(x) = LCM{ϕ1 (x), ϕ3 (x), ϕ5 (x), ϕ7 (x), ..., ϕ2t−1 (x)} (2)

Since the degree of each minimal polynomial is m or less, the de-

gree of g(x) is at most mt and n − k ≤ mt. Where for small t,
n − k = mt.

Fikreselam G. Title: Hamming and BCH Codes 15 / 45

BCH Codes

m n k t
3 7 4 1
4 15 11 1
7 2
5 3
5 31 26 1
21 2
16 3
11 5
6 7
Fikreselam G. Title: Hamming and BCH Codes 16 / 45
BCH Codes

Example
Let α be a primitive element of GF (24 ) with primitive polynomial
p(x) = x4 + x + 1. Find g(x) for t = 1, 2, 3.

Conjugate roots Minimal Polynomial

0 x
α0 = 1 x+1
α, α2 , α4 , α8 x4 + x + 1
α3 , α6 , α9 , α12 x4 + x3 + x2 + x + 1
α5 , α10 x2 + x + 1
α7 , α11 , α13 , α14 x4 + x3 + 1
Fikreselam G. Title: Hamming and BCH Codes 17 / 45
BCH Codes

Example...
For t = 1
g(x) = LCM{ϕ1 (x)} = x4 + x + 1

For t = 2

g(x) = LCM{ϕ1 (x), ϕ3 (x)} = ϕ1 (x) × ϕ3 (x) = x8 + x7 + x6 + x4 + 1

For t = 3

g(x) = LCM{ϕ1 (x), ϕ3 (x), ϕ5 (x)} = x10 + x8 + x5 + x4 + x2 + x + 1

Fikreselam G. Title: Hamming and BCH Codes 18 / 45

Parity Check matrix of BCH Codes

A binary n−tuple v = (v0 , v1 , ..., vn−1 ) is a code word iff the polyno-
mial v(x) = v0 + v1 x + ... + vn−1 xn−1 has α, α2 , ..., α2t as a roots.

Therefore, for 1 ≤ i ≤ 2t

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

Fikreselam G. Title: Hamming and BCH Codes 19 / 45

Parity Check matrix of BCH Codes

For 1 ≤ i ≤ 2t, the code polynomial can be written as a matrix

product as

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

Fikreselam G. Title: Hamming and BCH Codes 20 / 45

Parity Check matrix of BCH Codes

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

Fikreselam G. Title: Hamming and BCH Codes 21 / 45

Parity Check matrix of BCH Codes

Note that v.H T = 0 for t− error correcting BCH codeword v.

For some i and j, αj is a conjugate of αi , then v(αj ) = 0 if and only

if v(αi ) = 0.

if the dot product of v and ith row of H is zero, then the inner
product of v and j th row of H is also zero. Thus, the j th row of H
can be omitted.

Fikreselam G. Title: Hamming and BCH Codes 22 / 45

Parity Check matrix of BCH Codes

Therefore the parity check matrix H can be written as

 
1 α α2 α3 α4 . . . αn−1
 
1 (α3 ) (α3 )2 (α3 )3 (α3 )4 . . . (α3 )n−1 
 
 
H = .
 
. . . . . . . . 
 
 
. . . . . . . . . 
 
2t−1 2t−1 2 2t−1 3 2t−1 4 2t−1 n−1
1 (α ) (α ) (α ) (α ) . . . (α )
(5)

Fikreselam G. Title: Hamming and BCH Codes 23 / 45

Parity Check matrix of BCH Codes

The binary (n − k) × n parity check matrix can be obtained by

1 Each element in GF (2m ) of H in (Eq.5) can be represented by m−
tuple over GF (2).

2 Each element of H is replaced by its corresponding m− tuple ar-

ranged in column form.

3 The arranged matrix is binary parity check matrix of BCH code.

Fikreselam G. Title: Hamming and BCH Codes 24 / 45

Parity Check matrix of BCH Codes

Example
Let t = 2 for (15, 7) BCH code. Determine the binary parity check matrix
over GF (24 ). Where p(x) = 1 + x + x4

 
1 α α2 α3 α4 α5 α6 α7 α8 α9 α10 α11 α12 α13 α14
1 α3 α6 α9 α12 α15 α18 α21 α24 α27 α30 α33 α36 α39 α42

Fikreselam G. Title: Hamming and BCH Codes 25 / 45

Parity Check matrix of BCH Codes

Example...
 
1 0 0 0 1 0 0 1 1 0 1 0 1 1 1
 
0 1 0 0 1 1 0 1 0 1 1 1 1 0 0
 
 
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
 
 
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
H= 
1 0 0 0 1 1 0 0 0 1 1 0 0 0 1
 
 
0 0 0 1 1 0 0 0 1 1 0 0 0 1 1
 
 
0 0 1 0 1 0 0 1 0 1 0 0 1 0 1
 
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1

Fikreselam G. Title: Hamming and BCH Codes 26 / 45

Syndrome Computation and decoding of BCH codes

Let v(x) = v0 + v1 x + ... + vn−1 xn−1 be transmitted codeword.

Let r(x) = r0 + r1 x + ... + rn−1 xn−1 be received vector.

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

The first step of decoding a code is to compute the syndrome from

the received vector.

For decoding t− error correcting primitive BCH code, the syndrome

is a 2t− tuple. Using H from (Eq. 4)
s = (s1 , s2 , ..., s2t ) = r.H T
Fikreselam G. Title: Hamming and BCH Codes 27 / 45
Syndrome Computation and decoding of BCH codes

For 1 ≤ i ≤ 2t, s = (s1 , s2 , ..., s2t ) = r.H T given as

si = r(αi ) = r0 + r1 αi + ... + rn−1 α(n−1)i

si can also be determined from the remainder of received vector

divided by minimal polynomial.

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

si = r(αi ) = ai (αi )ϕi (αi ) + bi (αi ) = bi (αi )

where ϕi (αi ) = 0
Fikreselam G. Title: Hamming and BCH Codes 28 / 45
Parity Check matrix of BCH Codes

Example
Let we have double error–correcting (15, 7) BCH code. . Where p(x) =
1 + x + x4 over GF (24 ). Determine the syndrome for r(x) = 1 + x.

Remind that ϕ1 (x) = ϕ2 (x) = ϕ4 (x) = 1 + x + x4 and ϕ3 (x) =

1 + x + x2 + x3 + x4 .
   
r(x) r(x)
s1 = r(α1 ) = Rem. = 1+α = α4 ; s2 = r(α2 ) = Rem. = 1+α2 = α8
ϕ1 (x) ϕ2 (x)

   
r(x) r(x)
s3 = r(α3 ) = Rem. = 1+α3 = α14 ; s4 = r(α4 ) = Rem. = 1+α4 = α
ϕ3 (x) ϕ4 (x)

Thus, s = (s1 , s2 , ..., s2t ) = (α4 , α8 , α14 , α)

Fikreselam G. Title: Hamming and BCH Codes 29 / 45

BCH decoding

For 1 ≤ i ≤ 2t, v(αi ) = 0. Therefore

si = r(αi ) = v(αi ) + e(αi ) = e(αi )

Suppose that the error pattern e(x) has q error patterns at the lo-
cations xj1 , xj2 , ..., xjq . Thus

e(x) = ej1 xj1 + ej2 xj2 + ... + ejq xjq

For Binary BCH codes ei ∈ GF (2):-

e(x) = xj1 + xj2 + ... + xjq

Fikreselam G. Title: Hamming and BCH Codes 30 / 45

BCH decoding

Syndrome can be determined from the error patterns as

s1 = e(α1 ) = αj1 + αj2 + ... + αjq

s2 = e(α2 ) = (αj1 )2 + (αj2 )2 + ... + (αjq )2

s2t = e(α2t ) = (αj1 )2t + (αj2 )2t + ... + (αjq )2t (6)

Since αj1 , αj2 , ..., αjq are unknown, any method for solving these
equations is a decoding algorithm for the BCH codes.
If once αj1 , αj2 , ..., αjq have been found the power j1 , j2 , ..., jq indi-
cates the error location in e(x).
Fikreselam G. Title: Hamming and BCH Codes 31 / 45
BCH decoding

Let error location number βl = αjl , 1 ≤ l ≤ q. Thus

s1 = β1 + β2 + ... + βq

s2 = (β1 )2 + (β2 )2 + ... + (βq )2

s2t = (β1 )2t + (β2 )2t + ... + (βq )2t (7)

Fikreselam G. Title: Hamming and BCH Codes 32 / 45

BCH decoding

Let the error location polynomial σ(x) be

σ(x) = (1 + β1 x)(1 + β2 x)...(1 + βq x)

= σ0 + σ1 x + σ2 x2 + ... + σq xq (8)

1 1 1
From (Eq.8), roots of σ(x) are β1 , β2 , ..., βq .

Inverse of error location numbers are roots of error location poly-

nomial.

But to determine the error location number, coefficients of error

location polynomial should be determined.
Fikreselam G. Title: Hamming and BCH Codes 33 / 45
BCH decoding

From (Eq.8), the relation between coefficients of σ(x) and βl is

given as

σ0 = 1

σ1 = β1 + β2 + ... + βq

σ2 = β1 β2 + β2 β3 + ... + βq−1 βq

σq = β1 β2 β3 ...βq (9)

Fikreselam G. Title: Hamming and BCH Codes 34 / 45

BCH decoding

Since σi is known as elementary symmetric function of βi , from

(Eq.7) and (Eq.9) σi′ s are related to the syndrome components by
the following newton’s identities.

s1 + σ1 = 0

s2 + σ1 s1 + 2σ2 = 0

s3 + σ1 s2 + σ2 s1 + 3σ3 = 0

s4 + σ1 s3 + σ2 s2 + σ3 s1 + 4σ4 = 0

sq + σ1 sq−1 + σ2 sq−2 + ... + qσq = 0 (10)

Fikreselam G. Title: Hamming and BCH Codes 35 / 45

BCH decoding

If it is possible to determine σ1 , σ2 , ..., σq from (Eq. 10), the error

location number β1 , β2 , ..., βq can be found by determining the roots
of error location polynomial σ(x).
1 Determine σ1 , σ2 , ..., σq
2 Form

σ(x) = σ0 + σ1 x + σ2 x2 + ... + σq xq

= (1 + β1 x) + (1 + β2 x) + ... + (1 + βq x)

3 Determine β1 , β2 , ..., βq
4 Determine αjl = βl , 1 ≤ l ≤ q and correct an error.

Fikreselam G. Title: Hamming and BCH Codes 36 / 45

BCH decoding

The question comes, how to find σ(x). One solution is iterative

algorithm called Berlkamp’s algorithm.

Note that µth error location polynomial

(µ) (µ) (µ)

σ (µ) (x) = 1 + σ1 x + σ2 x2 + ... + σlµ xlµ

Note that µth discrepancy from Newton’s identities

(µ) (µ) (µ)

dµ = sµ+1 + σ1 sµ + σ2 sµ−1 + ... + σlµ sµ+1−lµ

Fikreselam G. Title: Hamming and BCH Codes 37 / 45

Berlkamp’s Iterative Algorithm for BCH Decoding

Steps for Berlkamp’s Iterative Algorithm

1 compute syndrome from r(x).

2 Find a minimum degree polynomial σ (1) (x) whose coefficients sat-

isfy the first Newton’s identity of (Eq.10).i.e.

s1 + σ1 = 1 =⇒ σ1 = s1

Then σ (1) (x) = 1 + s1 x

Fikreselam G. Title: Hamming and BCH Codes 38 / 45

Berlkamp’s Iterative Algorithm for BCH Decoding

Steps ...
3 Compute the discrepancy for µ = 1. If dµ = 0 the coefficients
of σ (1) (x) satisfies the first two Newton’s identity of (Eq.10). Then
σ (2) (x) = σ (1) (x). Otherwise use the correction factor to determine
σ (2) (x).i.e.


 σ (1) (x),
 if d1 = 0
σ (2) (x) =
 σ (1) (x) + CF,

if d1 ̸= 0

Where CF is a correction factor

Fikreselam G. Title: Hamming and BCH Codes 39 / 45

Berlkamp’s Iterative Algorithm for BCH Decoding

The correction factor CF in computing σ (µ+1) (x) is given as

CF = dµ d−1
ρ x
(µ−ρ) (ρ)
σ (x)

Then
σ (µ+1) (x) = σ (µ) (x) + dµ d−1
ρ x
(µ−ρ) (ρ)
σ (x)

Go back to the steps priori to the µth step and determine a polynomial

σ (ρ) (x) such that the ρth discrepancy dρ ̸= 0 and ρ − lρ (lρ is the degree

of σ (ρ) (x) ) has the largest value.

Fikreselam G. Title: Hamming and BCH Codes 40 / 45

Berlkamp’s Iterative Algorithm for BCH Decoding

Steps ...
3 Following the second step, find the minimum degree polynomial σ (3) (x)
from σ (2) (x) such tat coefficients of σ (3) (x) satisfy the first three
Newton’s identity of (Eq.10).


 σ (2) (x),
 if d2 = 0
σ (3) (x) =
 σ (2) (x) + CF,

if d2 ̸= 0

4 Iteration will continue until σ (2t) (x) is obtained and fill the iteration
table. Finally the error location polynomial is

Fikreselam G. σ(x) = σ (2t) (x)

Title: Hamming and BCH Codes 41 / 45
Berlkamp’s Iterative Algorithm for BCH Decoding

Summary of Iteration Table

µ σ µ (x) dµ lµ µ − lµ
-1 1 1 0 -1
0 1 s1 0 0
1
2
.
.
2t

Fikreselam G. Title: Hamming and BCH Codes 42 / 45

BCH decoding

Example
Let r(x) = x3 + x5 + x12 and we have triple error–correcting (15, 5)
BCH code. Where p(x) = 1 + x + x4 over GF (24 ). Determine the error
location polynomials and error polynomial.

The syndromes are

s = (1, 1, α10 , 1, α10 , α5 )

Following the steps mentioned before the iteration table will be

summarized next
Fikreselam G. Title: Hamming and BCH Codes 43 / 45
BCH Decoding:Example...

µ σ µ (x) dµ lµ µ − lµ
-1 1 1 0 -1
0 1 1 0 0
1 1+x 0 1 0
5
2 1+x α 1 1
5 2
3 1+x+α x 0 2 1 (ρ = 0)
4 1 + x + α5 x2 α10 2 2
5 3
5 1+x+α x 0 3 2 (ρ = 2)
5 3
6 1+x+α x

σ(x) = 1 + x + α5 x3

Fikreselam G. Title: Hamming and BCH Codes 44 / 45

BCH decoding:Example...

Next, determine roots of error location polynomials for all elements

of GF (24 ).

x = β1−1 = α3 ; x = β2−1 = α10 ; x = β3−1 = α12

The error location numbers are

1 1 1
β1 = 3
= α12 ; β2 = 10 = α5 ; β3 = 12 = α3
α α α

Thus, error polynomial e(x) = xj1 + xj2 + xj3 = x3 + x5 + x12

Fikreselam G. Title: Hamming and BCH Codes 45 / 45