EE 387, John Gill, Stanford University Notes #7, Handout #28

Definition of BCH codes

BCH codes are cyclic codes over GF(q) (the channel alphabet) that are defined
by a (d−1) × n check matrix over GF(q m) (the decoder alphabet):
 
b 2b (n−1)b
1 α α ··· α
 
1 αb+1 α2(b+1) · · · α(n−1)(b+1) 
H = . .. .. ... .. 
. 
1 αb+d−2 α2(b+d−2) · · · α(n−1)(b+d−2)
Design parameters:
• α is an element of GF(q m) of order n
• b is any integer (0 ≤ b < n is sufficient)
• d is an integer with 2 ≤ d ≤ n (d = 1 and d = n + 1 are trivial cases)
Rows of H are the first n powers of consecutive powers of α.

EE 387 Notes #7, Page 1

Special cases of BCH codes

A primitive BCH code is a BCH code defined using a primitive element α.
If α is a primitive element of GF(q m), then the blocklength is n = q m − 1.
This is the maximum possible blocklength for decoder alphabet GF(q m).
A narrow-sense BCH code is a BCH code with b = 1.
Some decoding formulas simplify when b = 1. However, b 6= 1 is usually used.
The parity-check matrix for a t-error-correcting primitive narrow-sense BCH code is
 
1 α α2 · · · α(n−1)
1
. α2 α4 · · · α2(n−1)  ,
. .. .. ... .. 
1 α2t α4t · · · α2t(n−1)
where n = q m − 1 and α is an n-th root of unity in GF(q m).
Each row of H is a row of the finite field Fourier transform matrix of size n.
Codewords are n-tuples whose spectra have 0’s at 2t consecutive frequencies.

EE 387 Notes #7, Page 2

 Reed-Solomon codes
Reed-Solomon codes are BCH codes where decoder alphabet = channel alphabet.
Minimal polynomials over GF(Q) of elements of GF(Q) have degree 1.
Thus the generator polynomial of a t-error-correcting Reed-Solomon code is
g(x) = (x − αb)(x − αb+1) · · · (x − αb+2t−1)
= g0 + g1x + · · · + g2t−1x2t−1 + x2t ,
where g0, g1 . . . , g2t−1 are elements of GF(Q).
The minimum distance is 2t + 1, independent of the choice of α and b.
Usually α is chosen to be primitive in order to maximize blocklength.
The base exponent b can be chosen to reduce encoder/decoder complexity.

EE 387 Notes #7, Page 3

Reed-Solomon code: example

Audio compact discs and CD-ROMs use 2EC Reed-Solomon codes over GF(28).
The primitive polynomial used to define field arithmetic is x8 + x4 + x3 + x2 + 1.
The base exponent is b = 0.
The generator polynomial of the (255,251) Reed-Solomon code is
g(x) = (x + 1)(x + α)(x + α2)(x + α3)
= x4 + α75x3 + α249x2 + α78x + α6
= x4 + 0fx3 + 36x2 + 78x + 40 .

In the hexadecimal representations of the coefficients, the most significant bit is on

the left; that is, 1 = 01, α = 02, α2 = 04, and so on.

There are no prime trinomials of degree 8; in fact, there are no prime trinomials of degree 8m for any m .

EE 387 Notes #7, Page 4

 (15,7,5) BCH code: parity-check matrix
Parity-check matrix of (15, 7, 5) binary BCH code:
 
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
1 α α2 α3 · · · α14

0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
H= 3 6 9 42
=  
1 α α α ··· α 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

Since rows of H are linearly independent, there are 28 syndromes. There are
15 15
1+ + = 121 < 27 < 28
1 2
error patterns of weight 2. This code does not achieve the Hamming bound.
A systematic parity-check matrix can be found using the generator polynomial.

There is no (15,8) binary linear block code with minimum distance 5 .

EE 387 Notes #7, Page 5

(15,7,5) BCH code: generator polynomial

Generator polynomial is lcm of minimal polynomials of α, α2, α3, α4 :
g(x) = f1(x)f3(x) = (x4 + x + 1)(x4 + x3 + x2 + x + 1)
= x8 + x7 + x6 + x4 + 1 = 1 + x4 + x6 + x7 + x8
BCH codes are cyclic, hence have shift register encoders and syndrome circuits:
m(x)

c(x)

Modified error trapping can be used for (15, 7, 5) binary BCH code.
Any 2 -bit error pattern can be rotated into the 8 check positions. However, two error trapping passes may be needed.

EE 387 Notes #7, Page 6

 (15,5,7) BCH code
The generator polynomial of a 3EC BCH code is defined by zeroes α, α3, α5 :
g(x) = f1(x)f3(x)f5(x) = (x4 + x + 1)(x4 + x3 + x2 + x + 1)(x2 + x + 1)
= x10 + x8 + x5 + x4 + x2 + x + 1
Parity-check matrix is 3 × 15 over GF(24) or 12 × 15 over GF(2):
 
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
2 14
 
1 α α ··· α 1
 0 0 0 1 1 0 0 0 1 1 0 0 0 1

 3 6 42 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1
H = 1 α α · · · α  = 
0 0 1 0 1 0 0 1 0 1 0 0 1 0

1
5 10 70
1 α α ··· α
 
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1
 
1 0 1 1 0 1 1 0 1 1 0 1 1 0 1
 
0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
 
0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The last two rows are linearly redundant ⇒ 10 check equations ⇒ k = 5.

EE 387 Notes #7, Page 7

(15,5,7) BCH code: redundant rows

H has two redundant rows:
• bottom row is zero
• next to last row is same as previous row
H has 10 independent rows and defines a (15, 5) binary cyclic code.
Parity-check polynomial h(x) = (x4 + x3 + 1)(x + 1) includes all the prime
divisors of x15 − 1 that are not included in g(x).
The dual of this BCH code is a (15, 10) expurgated Hamming code with d∗ = 4.
The (15, 5) BCH code is obtained from the (15, 4) maximum-length code by
augmentation — including the complements of the original codewords.
The weight enumerator is A(x) = 1 + 15x7 + 15x8 + x15 .

EE 387 Notes #7, Page 8

 (31,16,7) BCH code
Zeroes of codewords are α, α3, α5 in GF(25). Parity-check matrix:
 
1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0
0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1
 
0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0
 
0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0
 
0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1
 
1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0
 
0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1
 
H= 0

0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1

0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1 0
 
0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1
 
 
1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 1
 
0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1
 
0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1
 
0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0
0 0 1 1 0 1 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1

Generator polynomial: x15 + x11 + x10 + x9 + x8 + x7 + x5 + x3 + x2 + x + 1.

It is not obvious that every set of 6 columns of H is linearly independent!
For blocklength 31, all binary BCH codes with d∗ = 7 have 15 check bits.
The expanded code with (n, k, d∗) = (32, 16, 8) is a Reed-Muller code.
EE 387 Notes #7, Page 9

BCH codes with decoder alphabet GF(16)

Suppose that α is primitive in GF(16).
The following parity-check matrix defines a primitive, narrow-sense BCH code over
each channel alphabet that is a subfield of GF(16).
 
1 α α2 · · · α14
1 α2 α4 · · · α28
H =  1 α3 α6 · · · α42


1 α4 α8 · · · α56
The three possible channel alphabets are GF(2) , GF(22) , and GF(24):
The BCH codes corresponding to these channels alphabets are
• (15,7) binary BCH code over GF(2) (presented earlier in lecture)
• (15,9) BCH code over GF(4)
• (15,11) Reed-Solomon code over GF(16)
The blocklengths in symbols are 15; blocklengths in bits are 15, 30, and 60.

EE 387 Notes #7, Page 10

 Channel alphabet GF(16)
The four rows of H are linearly independent over GF(24) (BCH bound, later).
Thus H defines a (15, 11) code over GF(24) with minimum distance 5.
This code is a (15, 11) 2EC Reed-Solomon code over GF(16).
Using table of powers of α (Blahut p. 86), we can find generator polynomial:
g(x) = (x + α)(x + α2)(x + α3)(x + α4)
= α10 + α3x + α6x2 + α13x3 + x4 = 7 + 8 x + E x2 + D x3 + x4
Coefficients of generator polynomial are computed using GF(24) arithmetic.
Coefficients can be expressed either in exponential or binary representation.
• exponential notation simplifies multiplication (add exponents mod 15)
• binary notation simplifies addition (exclusive-or of 4-bit values)
Hardware implementations use bit vectors and often log/antilog tables.

EE 387 Notes #7, Page 11

Channel alphabet GF(4)

Let GF(4) be {0, 1, β, δ}, where δ = β + 1 = β 2 .
GF(16) consists of 2-tuples over GF(4) using primitive polynomial x2 + x + β.
H defines a BCH code over subfield GF(4).
 
1 0 β β 1 β 0 δ δ β δ 0 1 1 δ
0 1 1 δ 1 0 β β 1 β 0 δ δ β δ
 
1 β 1 0 δ δ 1 δ 0 β β δ β 0 1
 
 
0 1 1 β 1 0 δ δ 1 δ 0 β β δ β
H[22] =  
1 β 0 β 1 1 β 0 β 1 1 β 0 β 1
 
0 δ β β δ 0 δ β β δ 0 δ β β δ
 
1 1 δ 1 0 β β 1 β 0 δ δ β δ 0
0 1 1 δ 1 0 β β 1 β 0 δ δ β δ

The final two rows, corresponding to conjugate α4 over GF(4), are redundant.
(Row 7 equals row 1 + row 2, while row 8 equals row 2).
Thus g(x) = f1(x)f2(x)f3 (x) has degree 6 ⇒ (15, 9, 5) code over GF(4) .

EE 387 Notes #7, Page 12

 Channel alphabet GF(2)
This 16 × 15 matrix has redundant rows over GF(2). Every row in the second and
fourth blocks is a linear combination of the first four rows.
 
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
 
1 0 1 0 1 1 1 1 0 0 0 1 0 0 1
 
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0
0 1 0 1 1 1 1 0 0 0 1 0 0 1 1
 
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
H[21] =  
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
 
1 1 1 1 0 0 0 1 0 0 1 1 0 1 0
0 1 0 1 1 1 1 0 0 0 1 0 0 1 1
 
0 0 1 1 0 1 0 1 1 1 1 0 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1

When we delete the redundant rows of H , we obtain the parity-check matrix of the
(15, 7) 2EC BCH code over GF(2) shown earlier.

EE 387 Notes #7, Page 13

Vandermonde matrix
Definition: The µ × µ Vandermonde matrix V (X1, . . . , Xµ) is
 
1 1 ··· 1
 X1 X2 ··· Xµ 
V = .. .. ... .. .
X1µ−1 X2µ−1 · · · Xµµ−1

One application of Vandermonde matrices is for polynomial interpolation.

Given values of f (x) of degree µ − 1 at µ distinct points X1, . . . , Xµ ,
Yi = f (Xi) = f0 + f1Xi + · · · + fµ−1X µ−1 (i = 1, . . . , µ)
the coefficients of f (x) can be found by solving the matrix equation
   
Y1 Y2 . . . Yµ = f0 f1 . . . fµ−1 V (X1, . . . , Xµ) .

EE 387 Notes #7, Page 14

 Nonsingular Vandermonde matrix
Lemma: The Vandermonde matrix V (X1, . . . , Xµ) is nonsingular if and only if the
parameters X1, . . . , Xµ are distinct. In fact,
Y µ i−1
Y Y
det V (X1, . . . , Xµ) = (Xi − Xj ) = (Xi − Xj ) .
i>j i=1 j=1
Proof : The determinant is a polynomial in µ variables, X1, . . . , Xµ .
As a polynomial in Xi , its zeroes are Xj for j 6= i.
Thus Xi − Xj is a factor of the determinant for every pair (i, j) with i > j .
These are all the factors because the degree of det V (X1, . . . , Xµ) is
µ(µ − 1) µ
0 + 1 + · · · + (µ − 2) + (µ − 1) = = .
2 2
The coefficient of the main diagonal monomial
Yµ
Xii−1 = 1 · X2 · X32 · . . . · Xµµ−1
i=1
equals 1 in both the determinant and the above formula for the determinant.
EE 387 Notes #7, Page 15

BCH bound
Theorem: A BCH code whose parity-check matrix has d − 1 rows has dmin ≥ d.
Proof : Every set of d − 1 columns of H is linearly independent over GF(q m).
To see this, consider a submatrix consisting of columns i1, . . . , id−1 .
 
i1 b id−1 b
α ··· α
 i1(b+1)
· · · αid−1(b+1) 

 α
det .. ... ..  =
 
i1 (b+d−2) id−1 (b+d−2)
α ··· α
 
1 ··· 1
 αi1 · · · αid−1 
 
i1 b id−1 b
(α · · · α ) det . ... ..  6= 0
 . 
(d−2)i1 (d−2)id−1
α ··· α
This determinant is nonzero because αi1 6= 0, . . . , αid−1 6= 0 and the second matrix
is a Vandermonde matrix with distinct columns.
EE 387 Notes #7, Page 16
 Design of BCH codes
Codewords of BCH code have zeroes that are d − 1 consecutive powers of α.
Conjugates over channel alphabet GF(q) are also zeroes.
The degree of the generator polynomial is the total number of conjugates.
Example: Channel alphabet GF(2), decoder alphabet GF(26).
The first six conjugacy classes, represented by exponents:
{0} {1, 2, 4, 8, 16, 32} {3, 6, 12, 24, 48, 33}
{5, 10, 20, 40, 17, 34} {7, 14, 28, 56, 49, 35} {9, 18, 36}
• d∗ = 5 requires 4 powers. Exponents {1, 2, 3, 4} ⇒ 12 conjugates.
• d∗ = 9 requires 8 powers. Exponents {1, . . . , 8} ⇒ 24 conjugates.
• d∗ = 11 requires 10 powers. Exponents {1, . . . , 10} ⇒ 27 conjugates.
• d∗ = 4 requires 3 powers.
◦ Exponents {1, 2, 3} ⇒ 12 conjugates.
◦ Better: {0, 1, 2} ⇒ 7 conjugates (expurgated code)
EE 387 Notes #7, Page 17

GF(256): powers of primitive element

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 01 02 04 08 10 20 40 80 1D 3A 74 E8 CD 87 13 26
16 4C 98 2D 5A B4 75 EA C9 8F 03 06 0C 18 30 60 C0
32 9D 27 4E 9C 25 4A 94 35 6A D4 B5 77 EE C1 9F 23
48 46 8C 05 0A 14 28 50 A0 5D BA 69 D2 B9 6F DE A1
64 5F BE 61 C2 99 2F 5E BC 65 CA 89 0F 1E 3C 78 F0
80 FD E7 D3 BB 6B D6 B1 7F FE E1 DF A3 5B B6 71 E2
96 D9 AF 43 86 11 22 44 88 0D 1A 34 68 D0 BD 67 CE
112 81 1F 3E 7C F8 ED C7 93 3B 76 EC C5 97 33 66 CC
128 85 17 2E 5C B8 6D DA A9 4F 9E 21 42 84 15 2A 54
144 A8 4D 9A 29 52 A4 55 AA 49 92 39 72 E4 D5 B7 73
160 E6 D1 BF 63 C6 91 3F 7E FC E5 D7 B3 7B F6 F1 FF
176 E3 DB AB 4B 96 31 62 C4 95 37 6E DC A5 57 AE 41
192 82 19 32 64 C8 8D 07 0E 1C 38 70 E0 DD A7 53 A6
208 51 A2 59 B2 79 F2 F9 EF C3 9B 2B 56 AC 45 8A 09
224 12 24 48 90 3D 7A F4 F5 F7 F3 FB EB CB 8B 0B 16
240 2C 58 B0 7D FA E9 CF 83 1B 36 6C D8 AD 47 8E 01

EE 387 Notes #7, Page 18

 Decoder alphabet GF(256)
Narrow-sense primitive 2EC BCH codes over GF(2), GF(22), GF(24), GF(28)
can be defined by the same parity-check matrix:
 
1 α α2 · · · α254
1 α2 α4 · · · α508 
H =  1 α3 α6 · · · α752 


1 α4 α8 · · · α1016
Generator polynomials lcm(f1(x), . . . , f4(x)) have coefficients from subfields.
GF(22) = {0, 1, α85, α170} = {00 , 01 , D6 , D7 }
GF(24) = {0, 1, α17, . . . , α238} = span{01 , 0B , 98 , D6 }

Subfield Degree Polynomial coefficients

GF(28) 4 01 1E D8 E7 74
GF(24) 8 01 D6 01 DD 0B 98 98 98 D7
GF(22) 12 01 01 00 D7 00 00 00 D6 D7 D7 01 D7 01
GF(2) 16 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1
EE 387 Notes #7, Page 19

Encoding and syndrome circuits

Binary BCH codes are defined using GF(2m) but are still cyclic over GF(2).
Shift registers can be used for encoding and for syndrome computation.
The (31, 21) binary primitive 2EC BCH code with generator polynomial
(x5 + x2 + 1)(x5 + x4 + x3 + x2 + 1) = 1 + x3 + x5 + x6 + x8 + x9 + x10
has the following shift register encoder.
m(x)

c(x)

Syndrome s(x) mod g(x) used for error detection has a similar circuit.

EE 387 Notes #7, Page 20

 Encoder for (255,251) Reed-Solomon code
0
m0 1
2
3
4
5
6
7
m7
0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

00000010 00011110 01101100 11110000

00000001 00001111 00110110 01111000
10111000 10111111 00011011 00111100
0 1 0 1 1 1 0 0 α6 1 1 1 0 0 1 1 1 α78 1 0 1 1 0 1 0 1 α249 0 0 0 1 1 1 1 0 α75
00101110 11001011 11100010 00001111
00010111 11011101 01110001 10111111
10110011 11010110 10000000 11100111
11100001 01101011 00000000 11001011
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0 0 0 0

1 1 1 1

2 2 2 2

3 3 3 3

4 4 4 4

5 5 5 5

6 6 6 6

7 7 7 7

EE 387 Notes #7, Page 21

Reed-Solomon encoder
A Reed-Solomon code with d∗ = 8 has the following generator polynomial:
g(x) = (x + α−3)(x + α−2)(x + α−1)(x + 1)(x + α+1)(x + α+2)(x + α+3)
= x7 + 6bx6 + 09x5 + 9ex4 + 9ex3 + 09x2 + 6bx + 1
Since the reciprocals of its zeroes are also zeroes, g(x) is its mirror image.
Thus the encoder corresponding to g(x) has only 3 distinct scalers.
m(x)

9e 09 6b

c(x)

EE 387 Notes #7, Page 22

 Generator matrix for (255,223) 4EC BCH code

EE 387 Notes #7, Page 23

Decoding algorithms for BCH codes

Decoding BCH and Reed-Solomon codes consists of the following major steps.
1. Compute partial syndromes Si = r(αi) for i = b, . . . , b + d − 2.
ν
Y
2. Find coefficients Λ1, . . . , Λν of error-locator polynomial Λ(x) = (1−xXi )
i=1
by solving linear equations with constant coefficients Sb, . . . , Sb+d−2 .
3. Find the zeroes X1−1, . . . , Xν−1 of Λ(x). If there are ν symbol errors, they are
in locations i1, . . . , iν where X1 = αi1 , . . . , Xν = αiν .
4. Solve linear equations, whose “constant” coefficients are powers of Xi , for
error magnitudes Y1, . . . , Yν . (Not needed for channel alphabet GF(2).)
Efficient procedures for solving linear systems of equations in steps 2 and 4:
• Berlekamp, Massey (step 2)
• Forney (step 4)
• Sugiyama-Kasahara-Hirasawa-Namekawa (“Euclidean”) (steps 2 and 4)

EE 387 Notes #7, Page 24

 Error locations and magnitudes
Suppose there are ν ≤ t errors in locations i1, . . . , iν .
Let the error magnitudes be ei1 , . . . , eiν (values in GF(q), channel alphabet).
The error polynomial is
e(x) = ei1 xi1 + · · · + eiν xiν .
The senseword r(x) can be written r(x) = c(x) + e(x).
The partial syndromes are values in decoder alphabet GF(q m) :
Sj = r(αj ) = c(αj ) + e(αj ) = e(αj )
= ei1 αji1 + · · · + eiν αjiν = ei1 αi1j + · · · + eiν αiν j .
Change of variables:
• error locators: X1 = α i1 , . . . , Xν = α iν
• error magnitudes: Y1 = ei1 , . . . , Yν = eiν (just renaming)

EE 387 Notes #7, Page 25

Syndrome equations
Error locators are elements of the decoder alphabet GF(q m).
Error magnitudes are elements of the channel alphabet GF(q).
Important special case: Yi = 1 for channel alphabet GF(2).
For today, assume narrow-sense BCH code (b = 1) with d = 2t + 1.
Partial syndromes are constants in system of 2t equations in 2ν unknowns:
S 1 = Y1 X 1 + · · · + Yν X ν
S2 = Y1X12 + · · · + Yν Xν2
..
S2t = Y1X12t + · · · + Yν Xν2t
This is an algebraic system of equations of degree 2t.
Goal: reduce to one-variable polynomial equation with ν solutions.

EE 387 Notes #7, Page 26

 Error-locator polynomial
The error-locator polynomial Λ(x) is defined by
Λ(x) = (1 − xX1)(1 − xX2) · · · (1 − xXν )
ν
Y
= (1 − xXi)
i=1
Yν ν
Y
= (−Xi) · (x − Xi−1)
i=1 i=1

= 1 + Λ1x + · · · + Λν xν .

The zeroes of Λ(x) are X1−1, . . . , Xν−1 — the reciprocals of error locators.
The degree of Λ(x) is the number of errors. elegant!

The decoder must determine ν as well as the error locations.

The Peterson-Gorenstein-Zierler decoder can be used to find Λ(x) from Sj .
PGZ is not efficient for large t but is easy to understand.

EE 387 Notes #7, Page 27

PGZ decoder example

Syndromes for 2EC narrow-sense BCH code with decoder alphabet GF(2m):
Sj = Y1X1j + Y2X2j , j = 1, . . . , 4
Suppose two errors. Then zeroes of Λ(x) = 1 + Λ1x + Λ2x2 are X1−1, X2−1 .
· Y1 X13
0=1+ Λ1X1−1 + Λ2X1−2 −−−→ Y1X13 + Λ1Y1X12 + Λ2Y1X1 = 0
· Y2 X23
0=1+ Λ1X2−1 + Λ2X2−2 −−−→ Y2X23 + Λ1Y2X22 + Λ2Y2X2 = 0
(Y1X13 + Y2X23) + Λ1(Y1X12 + Y2X22) + Λ2(Y
| 1X1 {z
+ Y2X}2) = 0
| {z } | {z }
S3 S2 S1

Similarly, multiplying by YiXi4 and summing gives another equation:

(Y1X14 + Y2X24) + Λ1(Y1X13 + Y2X23) + Λ2(Y1X12 + Y2X22) = 0
| {z } | {z } | {z }
S4 S3 S2

We have obtained two linear equations in the unknowns Λ1, Λ2 :

    
S3 + S2 Λ1 + S1 Λ2 = 0 S1 S2 Λ2 S3
⇒ = − .
S4 + S3 Λ1 + S3 Λ2 = 0 S2 S3 Λ1 S4
EE 387 Notes #7, Page 28
 PGZ decoder example (2)
The determinant of the coefficient matrix is:
S1S3 − S22 = Y1Y2(X1X23 + X13X2) = Y1Y2X1X2(X1 + X2)2 6= 0
because Yi 6= 0, Xi 6= 0, and X1 6= X2 . So we can solve for Λ1, Λ2 .
   
S1 S2 S S
M2 = ⇒ M2−1 = ∆−1 3 2
S2 S3 S2 S1
where ∆ = det M2 = S1S3 + S22 . Coefficients of Λ(x) are given by
      2 
Λ2 −1 S3 S2 S3 −1 S3 + S2 S4
= ∆ = ∆
Λ1 S2 S1 S4 S2 S3 + S1 S4
The error locator polynomial is Λ(x) = 1 + Λ1x + Λ2x2 , where
S2 S3 + S1 S4 S32 + S2S4
Λ1 = , Λ2 = .
S1S3 + S22 S1S3 + S22
The common denominator ∆ = S1S3 + S22 need be computed only once.
Computation of Λ1 , Λ2 uses 8 multiplications and one inversion in GF(2m) .
EE 387 Notes #7, Page 29

PGZ decoder example (3)

Next find two zeroes X1−1, X2−1 of Λ(x) (perhaps by exhaustive search).
If Λ(x) does not have two distinct zeroes, an uncorrectable error has occurred.
Finally find the error magnitudes:
   −1  
Y1 X1 X2 S1
=
Y2 X12 X22 S2
 2  
1 X2 X2 S1
=
X1X2(X1 + X2) X12 X1 S2
Matrix-vector product gives error magnitudes:
X22S1 + X2S2 X2 S1 + S2
Y1 = =
X1X2(X1 + X2) X1(X1 + X2)
X12S1 + X1S2 X1 S1 + S2
Y2 = =
X1X2(X1 + X2) X2(X1 + X2)

Computation of Y1 , Y2 takes about 6 multiplications and 2 reciprocals.

EE 387 Notes #7, Page 30
 PGZ decoder example (4)
If M2 is singular, that is, S1S3 + S22 = 0, then we solve the simpler equation
M1 [ Λ1 ] = [ S2 ] ⇒ [ S1 ][ Λ1 ] = [ S2 ]
The error locator polynomial has degree 1:
S2 S1
Λ(x) = 1 + Λ1x = 1 + x ⇒ X1−1 =
S1 S2
If S2 6= 0 then the single error locator is the reciprocal of the zero of Λ(x):
S2 Y1X12
X1 = =
S1 Y1 X 1
Error magnitude is obtained from S1 = Y1X1 :
S1 S2 Y 2X 2
Y1 = = 1 = 1 21 .
X1 S2 Y1 X 1
Finally we check S4 = Y1X14 . If not, an uncorrectable error has been detected.

EE 387 Notes #7, Page 31

PGZ in general
By definition of the error locator polynomial, Λ(Xi−1) = 0:
1 + Λ1Xi−1 + · · · + Λν Xi−ν = 0 (i = 1, . . . , ν)

Multiply this equation by YiXij+ν for any j ≥ 1:

YiXij+ν + Λ1YiXij+ν−1 + · · · + Λν YiXij = 0

This equation has only positive powers of Xi . Now sum over i:
ν
X ν
X ν
X
YiXij+ν + Λ1 YiXij+ν−1 + · · · + Λν YiXij = 0
i=1 i=1 i=1

Thus if j ≥ 1 and j + ν ≤ 2t, that is, 1 ≤ j ≤ 2t − ν ,

Sj+ν + Λ1Sj+ν−1 + · · · + Λν Sj = 0
We have obtained 2t − ν ≥ ν linear equations in ν unknowns Λ1, . . . , Λ2 :
Sj Λν + Sj+1Λν−1 + · · · + Sj+ν−1Λ1 = −Sj+ν

EE 387 Notes #7, Page 32

 Linear equations for Λ1, . . . , Λν
The first ν linear equations for Λ1, . . . , Λν have a ν × ν coefficient matrix:
    
S1 S2 · · · Sν Λν −Sν+1
S2 S3 · · · Sν+1  Λν−1 −Sν+2
  ..  =  .. 
 . .. ..     
 . ...
Sν Sν+1 · · · S2ν−1 Λ1 −S2ν
For any µ = 1, 2, . . . , t, let Mµ be the matrix
 
S1 S2 ··· Sµ
 S2 S3 ··· Sµ+1 
Mµ =  .. .. ... .. .
Sµ Sµ+1 · · · S2µ−1

Lemma: Suppose that there are ν ≤ t symbol errors. Then Mν is nonsingular, but
Mµ is singular for µ > ν .

Matrices that are constant along anti-diagonals are called Hankel matrices.

EE 387 Notes #7, Page 33

Determining number of errors ν

Proof : Syndrome equations are satisfied if we define Xi = 0 when ν < i ≤ t.
 Pµ Pµ µ

1
Y i X i · · · Y i X
 P1µ Pµ1 i
 
S1 · · · Sµ 2 µ+1 
. . . Y i X · · · Y i X
Mµ =  .. .. ..  =  1 i 1
... i
 
. ...
P ..

Sµ · · · S2µ−1

µ µ P µ 2µ−1
1 Yi Xi ··· 1 Yi Xi
 
  1 ··· 1
Y1 X1 · · · YµXµ  X
.
. . . .
. 1 · · · Xµ 
=  . . .  ·  ..

... ... 

.
Y1 X1µ · · · YµXµµ
 
X1µ−1 · · · Xµµ−1

1 1 1 · · · X1µ−1
     
··· Y1X1 · · · 0
=  ... ... ...  ·  ..
. ... ...  ·  ... . . . ... 
X1µ−1 · · · Xµµ−1 0 · · · YµXµ 1 · · · Xµµ−1

If i ≤ ν then Xi 6= 0 and Yi 6= 0. Therefore Mν is the product of nonsingular

Vandermonde and diagonal matrices and is nonsingular.
But if µ > ν the middle matrix has a zero element YµXµ on its diagonal.
The middle matrix is singular for µ > ν and therefore Mµ is singular.
EE 387 Notes #7, Page 34
 Peterson-Gorenstein-Zierler (PGZ) decoder: summary
1. Compute partial syndromes Sj = r(αj ).
2. Find largest ν ≤ t such that det Mν 6= 0.
3. Solve the following linear system for the coefficients of Λ(x).
Mν [ Λν , . . . , Λ1 ]T = [ −Sν+1, . . . , −S2ν ]T
4. Find X1−1, . . . , Xν−1 , the zeroes of Λ(x), in GF(q m), the decoder alphabet.
If Λ(x) has < ν distinct zeroes, an uncorrectable error has occurred.
5. Solve following system of linear equations for error magnitudes Y1, . . . , Yν .
Y1 X 1 + · · · + Yν X ν = S 1
Y1X12 + · · · + Yν Xν2 = S2
.. ..
Y1X1ν + · · · + Yν Xνν = Sν
.. ..
2t 2t
Y1X1 + · · · + Yν Xν = S2t

Ω(X −1 )
The Forney algorithm, Yi = − i , is a “closed” form solution for step 5.
Λ′ (X −1)
i
EE 387 Notes #7, Page 35

3EC Reed-Solomon code

Narrow-sense BCH codes usually do not have the simplest generator polynomial or
parity-check matrices.
For that reason, Reed-Solomon codes are usually defined using b = 0.
The following matrix defines a three error correcting Reed-Solomon code:
 
1 1 1 1 ··· 1
1
 α α2 α3 · · · αn−1 
1 α2 α4 α6 · · · α2(n−1)
H= 
1
 α3 α6 α9 · · · α3(n−1) 
1 α4 α8 α12 · · · α4(n−1)
1 α5 α10 α15 · · · α5(n−1)

The generator polynomial is

g(x) = (x + 1)(x + α)(x + α2)(x + α3)(x + α4)(x + α5)

Another trick to reduce encoder complexity is to choose b so that the generator polynomial is reversible — inverses of
zeroes are also zeroes — so half as many scalers are needed in the encoding circuit.
EE 387 Notes #7, Page 36
 3EC Reed-Solomon decoding (1)
The partial syndromes defined by Sj = r(αj ) for j = 0, . . . , 5 satisfy the equations
S0 = Y1 + Y2 + Y3
S1 = Y1 X 1 + Y2 X 2 + Y3 X 3
S2 = Y1X12 + Y2X22 + Y3X32
S3 = Y1X13 + Y2X23 + Y3X33
S4 = Y1X14 + Y2X24 + Y3X34
S5 = Y1X15 + Y2X25 + Y3X35
where X1, X2, X3 are error location numbers and Y1, Y2, Y3 are error magnitudes.
The coefficients of the error locator polynomial Λ(x) satisfy the linear equations:
    
S0 S1 S2 Λ3 S3
S 1 S 2 S 3  Λ 2  = S 4 
S2 S3 S4 Λ1 S5

EE 387 Notes #7, Page 37

3EC Reed-Solomon decoding (2)

If there are three errors, then the solutions can be found using Cramer’s rule:
Λ0 = S2(S1S3 + S2S2) + S3(S0S3 + S1S2) + S4(S0S2 + S1S1)
Λ1 = S3(S1S3 + S2S2) + S4(S0S3 + S1S2) + S5(S0S2 + S1S1)
Λ2 = S3(S1S4 + S2S3) + S4(S0S4 + S2S2) + S5(S0S3 + S1S2)
Λ3 = S3(S2S4 + S3S3) + S4(S1S4 + S2S3) + S5(S1S3 + S2S2)
Note that we can choose Λ0 = 1 by dividing the other coefficients by Λ0 .
Let X1, X2, X3 be the zeroes of
Λ(x) = Λ0 + Λ1x + Λ2x2 + Λ3x3 .
The location of the incorrect symbols are i1, i2, i3 , where
X1 = α i1 , X2 = α i2 , X3 = α i3 .

EE 387 Notes #7, Page 38

 3EC Reed-Solomon decoding (3)
Finally, the error magnitudes Y1, Y2, Y3 can be found by solving equations that use
the first three syndrome components, S0, S1, S2 :
S2 + S1(X2 + X3) + S0X2X3
Y1 =
(X1 + X2)(X1 + X3)
S2 + S1(X1 + X3) + S0X1X3
Y2 =
(X2 + X1)(X2 + X3)
S2 + S1(X1 + X2) + S0X1X2
Y3 =
(X3 + X1)(X3 + X2)

Starting from the partial syndromes S0, S1, . . . , S5 , approximately 30 Galois field
multiplications and 3 Galois field divisions are needed to perform decoding.
This estimate does not count the effort needed to find the zeroes of Λ(x).

EE 387 Notes #7, Page 39

Partial syndrome circuits for GF(32)

Horner’s method: α α3
5 5 5 5

r(x)
S1 S3

Multiplication by
   
0 1 0 0 0 0 0 0 1 0
α, α3 uses matrices: 0 0 1 0 0 0 0 0 0 1
Mα = 0 0 0 1 0 , Mα3 = 1 0 1 0 0
   
(α5 + α2 + 1 = 0) 0 0 0 0 1 0 1 0 1 0
1 0 1 0 0 0 0 1 0 1

Circuit for
r(α) and r(α3)
4 4
3 3
2 2
1 1
r(x) 0 0

EE 387 Notes #7, Page 40

 Partial syndrome circuit for (255,251) R-S code

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

10000000 01000000 00100000 00010000

01000000 00100000 00010000 00001000
00100000 00010000 00001000 00000100
00010000 0 00001000 1 0 0 0 0 0 1 0 0 a2 00000010 3
00001000 a 00000100 a 00000010 00000001 a
00000100 00000010 00000001 10111000
00000010 00000001 10111000 01011100
00000001 10111000 01011100 00101110
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0 0 0 0

1 1 1 1

2 2 2 2

3 3 3 3

4 4 4 4

5 5 5 5

6 6 6 6

7 7 7 7

r0 0
1
2
3
4
5
6
r7 7

EE 387 Notes #7, Page 41

Chien search
The Chien search is a clever method for finding zeroes of the error locator
polynomial by brute force.
The Chien search evaluates Λ(αi) for i = 1, 2, . . . , n using ν constant
multiplications instead of ν general multiplications.
Key idea: use ν state variables Q1, . . . , Qν such that at time i
Qj = Λj αji , j = 1, . . . , ν .
Each state variable is updated by multiplication by a constant:
Qj → Qj αj , i = 1, . . . , n .
ν
X
Sum of state variables at time i is Qj = Λ(αi) − 1.
j=1

An error location is identified whenever this sum equals −1.

EE 387 Notes #7, Page 42

 Chien search circuit #1
Memory elements are initialized with coefficients of error locator polynomial, i.e.,
Λj = 0 for j = ν + 1, . . . , t.
α α2 αt

Λ1 Λ2 Λt Σ /ERRLOC

Output signal ERRLOC is true when Λ(αi) = 0.

Since the zeroes of Λ(x) are the reciprocals of the error location numbers, ERRLOC
is true for values of i such that α−i = αn−i = Xl .
As i runs from 1 to n, error locations are detected from msb down to lsb.
Chien search can also be run backwards, using scalers for α−1, . . . , α−t .

EE 387 Notes #7, Page 43

Chien search circuit #2

Double-speed Chien search: evaluate Λ(α2i) and Λ(α2i+1) at same time.
α2 α4 α2t

1
Λ1 Λ2 Λt
Σ /ERRLOC0

α α2 αt
1

Σ /ERRLOC1

ERRLOC0 (ERRLOC1) is asserted when an even (odd) error location is found.

This circuit is more efficient than two separate copies of the Chien search engine
because the memory storage elements are shared.

EE 387 Notes #7, Page 44

 Chien search circuit #3
Scaler α2j usually requires more gates than scaler αj for small values of j .
We can reduce cost of double-speed Chien search by using α2j = αj · αj

α α2 αt

α α2 αt
1
Λ1 Λ2 Λt
Σ /ERRLOC1

Σ /ERRLOC0

The cascade of two scalers for αi may be slightly slower than one scaler for α2i .

EE 387 Notes #7, Page 45

PGZ decoder: review

1. Compute partial syndromes Sj = r(αj ).
2. Solve a linear system of equations for coefficients of Λ(x):
Mν [ Λν , . . . , Λ1 ]T = [ −Sν+1, . . . , −S2ν ]T
where ν is the largest number ≤ t such that det Mν 6= 0.
3. Find the zeroes of Λ(x) are X1−1, . . . , Xν−1 , which are the reciprocals of the
error locators X1 = αi1 , . . . , Xν = αiν .
4. Solve a system of linear equations for the error magnitudes Y1, . . . , Yν .
Y1 X 1 + · · · + Yν X ν = S 1
Y1X12 + · · · + Yν Xν2 = S2
.. ..
Y1X12t + · · · + Yν Xν2t = S2t

The Forney algorithm (1965) is a simple closed formula for Y1, . . . , Yν .

EE 387 Notes #7, Page 46

 Forney Algorithm
Consider a BCH code defined by the zeroes αb, αb+1, . . . , αb+2t−1 .
Forney algorithm: the error magnitude Yi corresponding to error locator Xi is
Xi1−bΩ(Xi−1)
Yi = − ,
Λ′(Xi−1)
where Λ′(x) is the formal derivative of the error-locator polynomial,
ν
X
′
Λ (x) = iΛixi−1 ,
i=1

and Ω(x) is the error evaluator polynomial, S(x)Λ(x) mod x2t .

The Forney algorithm is slightly simpler for narrow-sense BCH codes (b = 1):
Ω(Xi−1)
Yi = − ′ −1 .
Λ (Xi )
Fact: Forney’s algorithm uses 2ν 2 multiplications to compute all error magnitudes.

EE 387 Notes #7, Page 47

Partial syndrome polynomial

Definition: The partial syndrome polynomial for a narrow-sense BCH code is the
generating function of the sequence S1, S2, . . . , S2t :
S(x) = S1 + S2x + S3x2 + · · · + S2tx2t−1 .
For the BCH code defined by αb, . . . , αb+2t−1 , the partial syndrome polynomial is
S(x) = Sb + Sb+1x + · · · + Sb+2t−1x2t−1 .
The PGZ decoder uses linear equations for coefficients of Λ(x), j = 1, . . . , 2t − ν .
Sj Λν + · · · + Sj+ν−1Λ1 + Sj+ν = 0 narrow sense codes
Sb+j−1Λν + · · · + Sb+j+ν−2Λ1 + Sb+j+ν−1 = 0 general BCH codes

In both cases, the left hand side is the coefficient of xν+j−1 in the polynomial
product S(x)Λ(x).

We can define partial syndromes Si for every i > 0 . However, the decoder can compute only the first 2t values.

EE 387 Notes #7, Page 48

 Error evaluator polynomial
Definition: The error evaluator polynomial Ω(x) is defined by the key equation:
Ω(x) = S(x)Λ(x) mod x2t ,
where S(x) is partial syndrome polynomial and Λ(x) is error-locator polynomial.
The coefficient of xν+j−1 in S(x)Λ(x) is 0 if 1 ≤ j ≤ 2t − ν by PGZ equations.


Therefore deg S(x)Λ(x) mod x2t < ν if there are ν ≤ t errors.
The error evaluator polynomial can be computed explicitly from Λ(x):
Ω0 = Sb
Ω1 = Sb+1 + SbΛ1
Ω2 = Sb+2 + Sb+1Λ1 + SbΛ2
..
Ων−1 = Sb+ν−1 + Sb+ν−2Λ1 + · · · + SbΛν−1

Multiply-accumulates needed: 0 + 1 + · · · + ν − 2 = 12 (ν − 1)(ν − 2) ≈ 21 ν 2

EE 387 Notes #7, Page 49

Formal derivative
We can obtain a closed formula for Yi in terms of Ω(x), Λ(x), and Xi .
First we need the notion of the formal derivative of a polynomial.
Definition: The formal derivative of
f (x) = f0 + f1x + f2x2 + · · · + fnxn

is the polynomial

f ′(x) = f1 + 2f2x + 3f3x2 + · · · + nfnxn−1

Most of the familiar properties of derivatives hold. In particular, product rules:

(f (x)g(x))′ = f ′(x)g(x) + f (x)g ′(x)
Yn ′ X n Y
fi(x) = fi′(x) fj (x)
i=1 i=1 j6=i

Formal derivatives of polynomials are defined algebraically, not by taking limits.

EE 387 Notes #7, Page 50
 Properties of formal derivatives
Fact: A polynomial f (x) over GF(q) has a repeated zero β iff f ′(x) = 0.
Proof : If β is a zero of f (x), then x − β is a factor of f (x):
f (x) = f1(x)(x − β) ⇒ f ′(x) = f1(x) + f1′ (x)(x − β) ⇒ f ′(β) = f1(β) .
Thus β is a repeated zero — f (x) has factor (x − β)2 — if and only if f ′(β) = 0.
Over GF(2m), the formal derivative has only even powers of the indeterminant:
f ′(x) = f1 + 2f2x + 3f3x2 + · · · + nfnxn−1 = f1 + 3f3x2 + 5f5x4 + · · ·
since 2 = 1 + 1 = 0 , 4 = 2 + 2 = 2(1 + 1) = 0 , and so on.
So the formal derivative Λ′(x) has at most ν/2 nonzero coefficients.
Since Λ′(x) is a polynomial in x2 of degree < ν/2, we can compute Λ′(β) using
one squaring and ≤ ν/2 multiply-accumulate operations.

Note that f ′′ (x) = 0 for all polynomials over GF(2m) .

EE 387 Notes #7, Page 51

Forney algorithm: derivation (1)

We can express error evaluator Ω(x) in terms of error location numbers Xi and
error magnitudes Yi .
First we derive a closed formula for S(x).
2t−1
X
S(x) = Sb+j xj
j=0
2t−1
XX ν
= YiXib+j xj
j=0 i=1
ν 2t−1 ν
X X X 1 − (Xix)2t
= YiXib Xij xj = YiXib
i=1 j=0 i=1
1 − Xi x

ν
Y

Next we use the definition Λ(x) = 1 − Xlx to compute S(x)Λ(x).
l=1

EE 387 Notes #7, Page 52

 Forney algorithm: derivation (2)
ν   Yν
X 1 − (Xix)2t
S(x)Λ(x) = YiXib · (1 − Xlx)
i=1
1 − Xi x
l=1
ν 
X Y 


= YiXib (1 − Xlx) 1 − (Xix) 2t

i=1 l6=i
ν
X Y ν
X Y
= YiXib (1 − Xlx) − YiXib(Xix)2t (1 − Xlx)
i=1 l6=i i=1 l6=i

The second sum in the final expression is a polynomial in x of degree ≥ 2t.

Thus the remainder modulo x2t of the second sum is 0.
Therefore
ν
X Y
2t
Ω(x) = S(x)Λ(x) mod x = YiXib (1 − Xlx) .
i=1 l6=i

EE 387 Notes #7, Page 53

Forney algorithm: derivation (3)

We just found Ω(x) in terms Xi and Yi . Next use the product formula for Λ′(x):
Y ν ′ X ν Y
′
Λ (x) = (1 − Xlx) = (−Xl) (1 − Xj x) .
l=1 l=1 j6=l

When we evaluate Λ′(x) at Xi−1 , only one term in the sum is nonzero:
Y
Λ′(Xi−1) = −Xi (1 − Xj Xi−1) .
j6=i

Similarly, the value of Ω(x) at Xi−1 includes only one term from the sum:
ν
X Y Y
Ω(Xi−1) = Yl Xlb (1 − Xj Xi−1) = YiXib (1 − Xj Xi−1) .
l=1 j6=l j6=i

Thus
Ω(Xi−1) YiXib −1
−(b−1) Ω(Xi )
= ⇒ Yi = −Xi .
Λ′(Xi−1) −Xi Λ′(Xi−1)

EE 387 Notes #7, Page 54

 Forney algorithm during Chien search
t
Error magnitudes Yl can be computed by a Chien-search-like circuit:

α α2 αt αb−1
m
m
1
Ω1 Ω2 Ωt
m
m Σ Yi
Ω(αi )

α α2 αt

Λ′1 Λ′
m 2
m Λ′t Σ
Λ′(αi )

At each time i, the values of Ω(αi) and Λ′(αi) are available.

Thus Yl can be computed by one division and one multiplication by α−i(b−1) .

EE 387 Notes #7, Page 55

Forney algorithm: summary

Suppose that a BCH code is defined by zeroes αb, αb+1, . . . , αb+2t−1 .
Suppose that the error-locator polynomial has degree ν .
The error evaluator polynomial consists of the first ν terms of S(x)Λ(x).
Pν
The formal derivative Λ′(x) is i=1 iΛixi−1 .
Then the error magnitude Yi corresponding to error location number Xi is
Xi1−bΩ(Xi−1)
Yi = − ,
Λ′(Xi−1)
Computation of the coefficients of Ω(x) uses ≈ ν 2/2 multiplications.
Computation of Yi needs ν + (ν − 1) + 2 = 2ν + 1 multiplications + one reciprocal.
Forney’s algorithm finds all ν error magnitudes using ≈ 2.5ν 2 multiplications.
When GF(2m) is the decoder alphabet, Λ′(x) has only ν/2 nonzero coefficients,
which reduces the total operation count to 2ν 2 multiplications.

EE 387 Notes #7, Page 56

 Euclidean BCH decoding algorithm
Sugiyama, Kasahara, Hirasawa, Namekawa (1975). The key equation is
Ω(x) = S(x)Λ(x) mod x2t ⇒ Ω(x) = S(x)Λ(x) + b(x)x2t
for some polynomial b(x) of degree < ν .
Suppose that the extended Euclidean algorithm is used to calculate gcd(S(x), x2t).
For i = 1, 2, . . .:
ri(x) = ri−2(x) − Qi(x)ri−1(x) = ai(x)S(x) + bi(x)x2t
ai(x) = ai−2(x) − Qi(x)ai−1 (x) , bi(x) = bi−2(x) − Qi(x)bi−1 (x)
At some step i the remainder ri(x) has degree < t.1
The first such remainder is ri(x) = γΩ(x), where γ is the constant term of ai(x).
The error-locator polynomial Λ(x) = γ −1ai(x) is a polynomial of least degree such
that deg(S(x)Λ(x) mod x2t) < t.

1
Unless Si = 0 for i ≤ t , and not all Si = 0 , in which case an uncorrectable error has occurred.
EE 387 Notes #7, Page 57

Euclidean algorithm: pseudocode

1. Compute syndomes: Sj = r(αj ) , j = 1, . . . , 2t
2. Initialize:
2t 
X 1 0
s(x) ← x2t ; t(x) ← Sj xj−1 ; A(x) ← ;
0 1
j=1

3. While deg t(x) ≥ t

       
s(x) s(x) 0 1 s(x) 0 1
Q(x) ← ; ← ; A(x) ← A(x) ;
t(x) t(x) 1 −Q(x) t(x) 1 −Q(x)

4. Finalize:
∆ ← A22(0); Λ(x) ← ∆−1A22(x); Ω(x) ← ∆−1 t(x) ;

s(x) s(x)
   
The quotient is defined by s(x) = t(x) + r(x) , deg r(x) < deg t(x) .
t(x) t(x)

EE 387 Notes #7, Page 58

 Euclidean algorithm tableau
1 0 0 0 0 0 0 0 0 0 0 0 0 0

S S S S S S S S S S S S 1

q1 q0 q1 q0

q1 q0

q1 q0

q1 q0

q1 q0

q1 q0

Ω(x) Λ(x)

Usually the quotient qi(x) is linear. In this case

ri(x) = ri−2(x) − qi1xri−1(x) − qi0ri−1(x)
Coefficients of qi(x) can be found from first 2 coefficients of ri−2(x), ri−1(x).

EE 387 Notes #7, Page 59

Euclidean algorithm: example (1)

6EC Reed-Solomon code over GF(28):
One error:
ri(x) Qi(x) ai (x)
00 00 00 00 00 00 00 00 00 00 00 00 01 − 00
25 2E 12 A1 D5 D8 DF 95 C9 ED B2 05 − 01
29 CE A7 CE A7
Ω(x) = 29/CE = 25 , Λ(x) = (CE A7)/CE = 01 71
Op count: mul = 29 , div = 5
Three errors:
ri(x) Qi(x) ai (x)
00 00 00 00 00 00 00 00 00 00 00 00 01 −
10 1a cf dc 28 1d d2 52 5d 19 57 ec −
dd 9b 4a 2f f9 3f 05 34 04 76 66 1c 6d 1c 6d
b9 54 34 fa db eb a6 87 bc 4a 6e d8 5d 97 17
b1 47 69 ae e1 d3 f2 ad 2b
Ω(x) = 10 b3 f5 , Λ(x) = 01 5c d7 4f
Op count: mul = 91 , div = 13

EE 387 Notes #7, Page 60

 Euclidean algorithm: example (2)
6EC Reed-Solomon code over GF(28):
Six errors:
ri(x) Qi(x) ai(x)
00 00 00 00 00 00 00 00 00 00 00 00 01 − 00
04 19 50 23 BB AF AE F6 41 CB 0A AB − 01
A6 A4 36 F1 B0 C5 75 08 79 E9 6B A7 3C A7 3C
53 DA D8 39 2E 52 3D A6 DC 51 8B 71 DD 3C B3
B4 3E 51 46 82 BA 35 21 65 2D 5C 2D 23 06 23
70 2B 5F D7 ED F3 45 C8 0C 4F 1C 8C 5F 36 C4
94 33 CC 1F E2 84 07 69 5C 25 55 7C 53 6B D2
EC E2 0D 83 78 DB AD 47 3B EB 8C C9 FE 8E BA

Ω(x) = 04 F4 16 CC F2 BA , Λ(x) = 01 7C 95 B7 09 DA 82
Op count: mul = 169 , div = 25

EE 387 Notes #7, Page 61

Euclidean algorithm: computational cost

The Euclidean algorithm produces remainders such that deg ri(x) < deg ri−1(x).
• initial remainder S(x) has degree ≤ 2t − 1
• final remainder Ω(x) has degree ≤ t − 1
Therefore at most t major steps are needed.
Each major step is polynomial division followed by polynomial multiplication:
ri−2(x) = Qi(x)ri−1(x) + ri(x)
ai(x) = ai−2(x) − Qi(x)ai−1(x)
At step i approximately 2 · (2t − i) multiplications are used to find Qi(x) and 2i
multiplications to find ai(x). Total multiplications per step ≈ 4t.
Overall cost to find Λ(x) and Ω(x): 4t2 multiplications and t reciprocals.

Solving Mt [ Λt , . . . , Λ1 ]T = −[ St+1 , . . . , S2t ]T directly takes ≈ t3 /6 operations.

EE 387 Notes #7, Page 62

 Berlekamp decoding algorithm
Berlekamp (1967) invented an efficient iterative procedure for solving the linear
equations with coefficient matrices
 
S1 S2 S3 · · · Sµ
S S4 · · · Sµ+1 
 2 S3 
 
Mµ =  S3 S4 S5 · · · Sµ+2  ,
 . .. .. ... .. 
 . 
Sµ Sµ+1 Sµ+2 · · · S2µ−1
P
where Sj = νi=1 YiXij is a partial syndrome.
Each Mµ is found by using results of computations for some previous Mµ−ρ plus
an additional O(µ) operations.
Summing over µ from 1 to ν gives total cost O(ν 2) operations.
In Berlekamp’s original algorithm, a table with 2t rows stored intermediate results.

EE 387 Notes #7, Page 63

Massey decoding algorithm: shift register synthesis

Massey (1969) showed how finding the error-locator polynomial Λ(x) is equivalent
to a shift-register synthesis problem:
Given a sequence S1, S2, . . . , S2t , find the shortest sequence Λ1, Λ2, . . . , Λν that
generates Sν+1, . . . , S2t starting from S1, . . . , Sν in a shift-register of size ν .

Sν Sν−1 Sν−2 ... S2 S1

−1 Λ1 Λ2 Λ3 ... Λν

...

Recall that if the number of errors is ν then

Sj Λν + Sj+1Λν−1 + · · · + Sj+ν−1Λ1 = −Sj+ν
for j = 1, . . . , 2t − ν . The PGZ system of equations is a convolution S ∗ Λ.

EE 387 Notes #7, Page 64

 Berlekamp-Massey algorithm: overview
Partial syndromes S1, . . . , S2t are examined one at a time for k = 1, . . . , 2t.
At the end of the k-th step, Λ(k)(x) of degree L satisfies first k equations:
(k) (k)
Sk−i + Sk−i−1Λ1 + · · · + Sk−i−LΛL = 0 i = 0, . . . , k − L
If Λ(k−1)(x) satisfies k-th equation, then obviously
Λ(k)(x) = Λ(k−1)(x) .
The key and surprising idea: when Λ(k−1)(x) does not work (sum is ∆(k)(x) 6= 0),
update it as follows:
Λ(k)(x) = Λ(k−1)(x) − ∆(k)T (x) ,
1
where T (x) = ∆(r)
xk−r Λ(r)(x) is the last failing Λ(r)(x) shifted and scaled.
When the degree of Λ(x) has increased, we save Λ(k−1)(x) for future steps:
1
T (x) = (k)
xΛ(k−1)(x)
∆
∆(k) (x) is called the discrepancy at step k .
EE 387 Notes #7, Page 65

Berlekamp-Massey algorithm: pseudocode

Λ(x) = 1 ; /* "connection polynomial" */
L = 0; /* L always equals deg Λ(x) */
T (x) = x ; /* "correction polynomial" */
for ( k = 1 ; k ≤ 2t ; k ++) {
L
X
∆ = Λi Sk−i ; /* Sk + Λ1Sk−1 + · · · + ΛL Sk−L−1 */
i=0
if ( ∆ == 0 ) {
N (x) = Λ(x) ; /* keep same Λ(x) if ∆ == 0 */
} else {
N (x) = Λ(x) − ∆T (x) ; /* new Λ(x) has 0 discrepancy */
if ( L < k − L ) {
L = k − L;
T (x) = ∆−1Λ(x) ; /* new correction polynomial */
}
}
T (x) = xT (x) ; /* shift correction polynomial */
Λ(x) = N (x) ; /* possibly new value of Λ(x) */
}

EE 387 Notes #7, Page 66

 Berlekamp-Massey tableau
The following figure shows typical computation for 6EC BCH code.
k Λ(x) T (x)
0 1 0 1

1 1 Λ 0 T

2 1 Λ 0 T T

3 1 Λ Λ 0 T T

4 1 Λ Λ 0 T T T

5 1 Λ Λ Λ 0 T T T

6 1 Λ Λ Λ 0 T T T T

7 1 Λ Λ Λ Λ 0 T T T T

8 1 Λ Λ Λ Λ 0 T T T T T

9 1 Λ Λ Λ Λ Λ 0 T T T T T

10 1 Λ Λ Λ Λ Λ 0 T T T T T T

11 1 Λ Λ Λ Λ Λ Λ 0 T T T T T T

12 1 Λ Λ Λ Λ Λ Λ 0 T T T T T T T

EE 387 Notes #7, Page 67

Berlekamp-Massey example (1)

6EC Reed-Solomon code over GF(28). One error.
S = 6f 81 63 f9 74 6f 81 63 f9 74 6f 81
k Λ(k)(x) T (k) (x)
1 01 6F 00 32
2 01 0A 00 00 32
3 01 0A 00 00 00 32
4 01 0A 00 00 00 00 32
5 01 0A 00 00 00 00 00 32
6 01 0A 00 00 00 00 00 00 32
7 01 0A 00 00 00 00 00 00 00 32
8 01 0A 00 00 00 00 00 00 00 00 32
9 01 0A 00 00 00 00 00 00 00 00 00 32
10 01 0A 00 00 00 00 00 00 00 00 00 00 32
11 01 0A 00 00 00 00 00 00 00 00 00 00 00 32
12 01 0A 00 00 00 00 00 00 00 00 00 00 00 00 32

Op count: mul = 28 , div = 1

EE 387 Notes #7, Page 68

 Berlekamp-Massey example (2)
6EC Reed-Solomon code over GF(28). Two errors.
S = b0 91 cc d1 99 26 0a 8a 70 67 96 c9
k Λ(k)(x) T (k) (x)
1 01 B0 00 87
2 01 AB 00 00 87
3 01 AB A6 00 6F 16
4 01 44 87 00 00 6F 16
5 01 44 87 00 00 00 6F 16
6 01 44 87 00 00 00 00 6F 16
7 01 44 87 00 00 00 00 00 6F 16
8 01 44 87 00 00 00 00 00 00 6F 16
9 01 44 87 00 00 00 00 00 00 00 6F 16
10 01 44 87 00 00 00 00 00 00 00 00 6F 16
11 01 44 87 00 00 00 00 00 00 00 00 00 6F 16
12 01 44 87 00 00 00 00 00 00 00 00 00 00 6F 16

Op count: mul = 45 , div = 2

EE 387 Notes #7, Page 69

Berlekamp-Massey example (3)

6EC Reed-Solomon code over GF(28). 6 errors.
S = bc 30 bb 24 81 74 e5 a7 bd 2b 95 34
k Λ(k)(x) T (k) (x)
1 01 BC 00 95
2 01 F2 00 00 95
3 01 F2 7E 00 98 F4
4 01 D9 9D 00 00 98 F4
5 01 D9 89 74 00 AC 6F AD
6 01 88 05 58 00 00 AC 6F AD
7 01 88 88 CC 7A 00 C9 66 CA 3A
8 01 9A ED 96 23 00 00 C9 66 CA 3A
9 01 9A 06 2D 43 45 00 77 57 E6 09 DF
10 01 DF 87 96 D9 C2 00 00 77 57 E6 09 DF
11 01 DF BA 05 06 50 B4 00 5E E6 BB 6C 3F 9E
12 01 62 B4 E9 48 F7 57 00 00 5E E6 BB 6C 3F 9E

Op count: mul = 123 , div = 6

EE 387 Notes #7, Page 70

 Berlekamp-Massey example (4)
6EC Reed-Solomon code over GF(28). 7 errors.
S = f1 9f 5e 6e 5c 52 b2 46 02 99 b2 17
k Λ(k)(x) T (k) (x)
1 01 F1 00 E7
2 01 CC 00 00 E7
3 01 CC 24 00 CE 0B
4 01 9D D9 00 00 CE 0B
5 01 9D 0A A2 00 30 6F 33
6 01 04 1B 64 00 00 30 6F 33
7 01 04 9C A5 BD 00 4C 2D 3A B2
8 01 8F 8A 51 66 00 00 4C 2D 3A B2
9 01 8F 1E 3B A6 F3 00 F3 04 1C 6E 0D
10 01 0B D8 53 10 1B 00 00 F3 04 1C 6E 0D
11 01 0B 36 CA F8 B6 D7 00 57 7B 37 84 19 62
12 01 0F 1A 8D A9 F6 BB 00 00 57 7B 37 84 19 62

Op count: mul = 123 , div = 6

If there are 7 errors, the Berlekamp-Massey algorithm usually produces a polynomial Λ(x) of degree 6 . But Λ(x) has
6 zeroes in GF(2m) with probability 1/6! = the conditional probability of miscorrection.
EE 387 Notes #7, Page 71

Berlekamp-Massey algorithm: program flow

4 ν=4

3
↑
L 2

0
0 1 2 3 4 5 6 7 8

k →

4 ν=4

3 ν=3
↑
L 2

0
0 1 2 3 4 5 6 7 8

k →

EE 387 Notes #7, Page 72

 Berlekamp-Massey: computational cost
The Berlekamp-Massey algorithm keeps a current estimate of
• connection polynomial Λ(x)
• correction polynomial T (x).
When necessary Λ(x) and T (x) are updated by parallel assignment:
   
Λ(x) Λ(x) − ∆T (x)
←
T (x) ∆−1 xΛ(x)
Storage requirements: 2t decoder alphabet symbols, for Λ(x) and T (x).
Worst case running time (multiply/divide):
2 + 4 + · · · + 4t ≈ 4t2
The running time with a fixed number of multipliers is O(t2).
If t multipliers are available, the algorithm can be performed in O(t) steps.
Some authors refer to this as linear run time.

EE 387 Notes #7, Page 73

Solving error-locator polynomials: degree 2

Polynomials over GF(2m) of degree ≤ 4 can be factored using linear methods.
Consider an error-locator polynomial of degree 2:
Λ(x) = 1 + Λ1x + Λ2x2 .
Squaring is a linear transformation of GF(2m) over scalar field GF(2).
Therefore the equation Λ(x) = 0 can be rewritten as
x(Λ2S + Λ1I) = 1 ,
where x is the unknown m-tuple, S is the m × m matrix over GF(2) that
represents squaring, and 1 is the m-tuple (1, 0, . . . , 0).
If there are two distinct solutions, they are the zeroes of Λ(x).
The squaring matrix S can be precomputed, so the coefficients of the m × m
matrix A = Λ2S + Λ1I can be computed in O(m2) bit operations
Solving the system requires O(m3) bit operations or O(m2) word operations.

EE 387 Notes #7, Page 74

 Solving error-locator polynomials faster: degree 2
Λ1
Use the change of variables x = u. Then Λ(x) = 0 becomes
Λ2
Λ(x) = Λ2x2 + Λ1x + 1
 2  
Λ1 Λ1
= Λ2 u + Λ1 u +1
Λ2 Λ2
 
Λ21 2 Λ21 Λ21 2 Λ2
= u + u+1 = u +u+ 2
Λ2 Λ2 Λ2 Λ1
The simplified equation is of the form u2 + u + c = 0.
It can be solved using the precomputed pseudo-inverse of S + I .
Λ2 Λ
If U1 is a zero of u2 + u + 2
, then X1 = 1 U1 is a zero of Λ(x), as is
Λ1 Λ2

Λ1 Λ1
X2 = (U1 + 1) = X1 + .
Λ2 Λ2
If 2m is not too large, we can store a table of zeroes of u2 + u + c.

EE 387 Notes #7, Page 75

Erasure correction
Erasures are special received symbols used to represent uncertainty. Examples:
• Demodulator erases a symbol when signal quality is poor.
• Lower level decoder erases symbols of codeword that has an uncorrectable error.
Theorem: A block code can correct up to d∗ − 1 erasures.
Proof : If the number of erasures is less than d∗ , then there is only one codeword
that agrees with the received sequence.
c1
11111111
00000000
00000000
11111111
r 00000000
11111111
00000000
11111111
< d erasures
c2

Conversely, if two codewords differ in exactly d∗ symbols, the received sequence

obtained by erasing the differing symbols cannot be decoded.
Fact: A block code can correct t errors and ρ erasures iff d∗ ≥ 2t + ρ + 1 .

EE 387 Notes #7, Page 76

 Erasure correction for linear block codes
Erasures can be corrected for linear block codes by solving linear equations.
The equation cH T = 0 gives n − k equations for the ρ erasure values.
Any d∗ − 1 columns of H are linearly indepenent, so the equations can be solved
when ρ < d∗ ≤ n − k + 1.
Example: Let r = [ 0 0 ? ? 0 1 0 ] be received sequence for (7, 4) Hamming code.
 
1 0 0 1 0 1 1
H = 0  1 0 1 1 1 0 .
0 0 1 0 1 1 1
The parity-check matrix yields three equations for the erased bits x and y:
0 = 1·0 + 0·0 + 0·x + 1·y + 0·0 + 1·1 + 1·0 = 1 + y
0 = 0·0 + 1·0 + 0·x + 1·y + 1·0 + 1·1 + 0·0 = 1 + y
0 = 0·0 + 0·0 + 1·x + 0·y + 1·0 + 1·1 + 1·0 = 1 + x
Therefore x = 1, y = 1 and the decoded codeword is c = [ 0 0 1 1 0 1 0 ].

EE 387 Notes #7, Page 77

Erasure correction for BCH codes (1)

Consider a BCH code defined by parameters (α, n, b, d).
Suppose ρ < d erasures in locations j1, . . . , jρ and no errors.
Define the erasure locators
U l = α jl , l = 1, . . . , ρ .
The syndrome equations for the erasure magnitudes are
S1 = E1U1b + E2U2b + · · · + EρUρb
S2 = E1U1b+1 + E2U2b+1 + · · · + EρUρb+1
.. .
Sd−1 = E1U1b+d−2 + E2U2b+d−2 + · · · + EρUρb+d−2
This system of linear equations has a unique solution for E1, E2, . . . , Eρ because
the coefficient matrix is column-scaled Vandermonde.
The Forney algorithm provides a faster solution.

EE 387 Notes #7, Page 78

 Erasure correction for BCH codes (2)
The erasure locator polynomial is defined by
Qρ
Γ(x) = l=1 (1 − Ulx) = 1 + Γ1x + Γ2x2 + · · · + Γρxρ
Unlike the error locator polynomial, the values of Ul are known.
The coefficients of Γ(x) can be computed by polynomial multiplication.
Qi Q i−1
l=1 (1 − Ul x) = (1 − Ui x) l=1 (1 − Ulx)
1
For each i we use i − 1 multiply-accumulates. Total operations: 2 ρ(ρ − 1).
The Forney algorithm gives values of errors in erasure locations:
Ω(Ul−1)
El = − Ul1−b , l = 1, . . . , ρ .
Γ′(Ul−1)
where Ω(X) = S(x)Γ(x) mod x2t has degree ≤ ρ − 1.
Ω0 = S1, Ω1 = S2 + S1Γ1, . . . , Ωp−1 = Sρ + Sρ−1Γ1 + · · · + S1Γρ
Computing ρ error magnitudes takes ≈ 25 ρ2 multiply-accumulates.
EE 387 Notes #7, Page 79

Erasure correction example: wireless network

Random bit errors, large collision rate. Maximum packet size: 600 bytes
Encoding procedure for concatenated code:
• Divide data into three equal rows
• Create two check rows by (5,3) shortened Reed-Solomon code on columns
• Encode rows with shortened (255,239) 2EC BCH code on fragments of
≤ 29 data bytes
Example: 58-byte frame. Subframes have 20 bytes and 2 BCH check bytes.
column codeword row checks

subframe 1
subframe 2
111
000
subframe 3 000
111
000
111
checkframe 1
checkframe 2

EE 387 Notes #7, Page 80

 Decoding procedure for concatenated code
BCH code corrects 2 bit errors in ≤ 31 bytes, since
29 · 8 + 16 = 232 + 16 = 248 ≤ 255 = 28 − 1 .
A subframe with 200 bytes requrires ⌈200/29⌉ = 7 fragments.
Exercise: Find probability that a frame is lost because of random errors.
Row miscorrections and burst errors are corrected using (5, 3) column code. Up to
two lost subframes can be replaced.
Erasure correction procedure requires solving linear equations.


We precompute the inverses of coefficient matrices for the 52 = 10 possible
combinations of two lost subframes.
Each byte in missing subframe is computed using 3 Galois field multiplications.
Software correction takes 10 to 15 M68000 machine instructions per byte.
Trick to reduce time: store logarithms of precomputed matrix constants.

When only one subframe is lost, it can be replaced by XORing the other subframes.

EE 387 Notes #7, Page 81

Error and erasure decoding: binary case

If there are ρ erasures in a binary senseword r, then t = ⌊ 21 (d∗ − 1 − ρ)⌋ errors can
be corrected using an errors-only decoder:
1. Let c0 and c1 be the codewords obtained by decoding the n-tuples r0 and r1
obtained from r by replacing all erasures with zeroes and ones, respectively.
2. Compare c0 and c1 with r and let ĉ be the one that is closer to r.
(Either c0 or c1 or both might be undefined because of decoder failure.
An undefined ci is ignored.)
r0 0000 ...

c 0110 ... r ???? ...

r1 1111 ...
If number of errors is ≤ ⌊ 12 (d∗ − 1 − ρ)⌋ then
d (ĉ, r) ≤ ⌊ 1 ρ⌋ + ⌊ 1 (d∗ − 1 − ρ)⌋
H 2 2

≤ 12 ρ + 21 (d∗ − 1 − ρ) = 1 ∗
2 (d − 1) .
This shows that r is within the decoding sphere of ĉ.
EE 387 Notes #7, Page 82
 Error and erasure correction: Berlekamp-Massey
Qρ
1. Compute erasure locator polynomial Γ(x) = l=1 (1 − Ulx).
2. Compute partial syndrome polynomial S(x) using 0 for erased locations.
3. Compute modified syndrome polynomial Ξ(x) = S(x)Γ(x) mod x2t . Modified
syndromes are Ξ1, . . . , Ξ2t−ρ .
4. Run Berlekamp-Massey algorithm with the modified syndromes Ξ1, . . . , Ξ2t−ρ
to find the error-locator polynomial Λ(x) of degree ≤ 21 (2t − ρ).
5. Use the modified key equation to find error evaluator polynomial Ω(x):
Ω(x) = S(x)Λ(x)Γ(x) mod x2t = S(x)Ψ(x) mod x2t
where Ψ(x) = Λ(x)Γ(x) is the error-and-erasure locator polynomial.
6. Use modified Forney algorithm to compute error magnitudes:
Ω(Xi−1) Ω(Ul−1)
Yi = − Xi1−b , El = − Ul1−b
Ψ′(Xi−1) Ψ′(Ul−1)
for i = 1, . . . , ν and l = 1, . . . , ρ.
EE 387 Notes #7, Page 83

Erasure correction application: variable redundancy

Some communications systems use varying amounts of error protection:
• An ECC subsystem may be customized for specific application.
• Adaptive system may increase or decrease check symbols as needed.
Obvious approach: use different Reed-Solomon code generator polynomials:
gt(x) = (x + α)(x + α2) · · · (x + α2t) , t = 1, 2, . . . , T .
Problem: encoders for different generator polynomials require many scalers.
Clever solution: use generator polynomial for maximum error correction but
transmit only 2t check symbols, that is, delete ρ = 2T − 2t checks symbols.

information symbols checks deleted

Then use errors-and-erasures decoding, where missing check symbols are erased.

EE 387 Notes #7, Page 84

 Syndrome modification (1)
The modified syndrome polynomial for Reed-Solomon code is easy to find.
1. Deleted checks are considered to be in locations −1, −2, . . . , −ρ.
2. Compute modified syndrome using circuit below.
3. Use modified syndromes T1, . . . , T2t−ρ in Berlekamp-Massey algorithm.
4. Find zeroes of Λ(x).
5. Compute Ψ(x) = Γ(x)Λ(x) and Ω(x) = S(x)Γ(x)Λ(x) mod x2t .
6. Use Forney algorithm to find error magnitudes and erasure magnitudes.
Erasure correction can be used by an encoder to generate check symbols from
partial syndromes of the message symbols.
Partial syndromes may be easier to compute because the circuits are uncoupled,
hence fewer long wires are needed.

EE 387 Notes #7, Page 85

Syndrome modification (2)

S1 ρ
Y
α−1 Ξ(x) = S(x) (1 + α−ix)
S2 l=1
m
α−2 (decoder alphabet GF(2 ))
α−1
S3
α−2 α−3
α−1
S4
α−2 α−3 α−4
α−1
S5 T1
α−2 α−3 α−4
α−1
S6 T2
α−2 α−3 α−4
α−1
S7 T3
α−2 α−3 α−4
α−1
S8 T4

EE 387 Notes #7, Page 86