ELG 5372 Error
Control Coding
Lecture 17: Berlekamp-Massey
Algorithm for Binary BCH
Codes
Chien Search
• If Λ(βi) = 0, then rn-i is in error.
• This means that Λ(βi)+1 = 1.
• X(βi) = Λ1βi + Λ2β2i+…Λvβvi.
• If X(βi) = 1, cn-i = rn-i+1, else cn-i = rn-i.
• If the Chien Search fails to find v roots of a
error locator polynomial of degree v, then the
error pattern is an uncorrectable error pattern.
Chien Search 2
r0 r1 r2 … rn-1 +
X If X = 1
+ Y=1, else Y=0
Λ1 Λ2 … Λv
β β2 βv
Berlekamp-Massey Algorithm
• Peterson’s method involves straightforward linear algebra, but it
is computationally complex to implement.
• Should A be singular, the last two rows and columns are deleted
and the determinant of the new A must be computed again.
• Thus, the Peterson method starts with a big problem and works
it down to a small problem (thus if it is a small problem to begin
with, the most computationally complex step is done for
nothing).
• The Berlekamp-Massey algorithm starts with a small problem
and works up to a large problem.
• Complexity of Peterson algorithm is proportional to v3, while that
of Berlekamp-Massey algorithm is proportional to v2.
Berlekamp-Massey Algorithm 2
• It was observed from Newton’s identities that
v
S j = −∑ Λ i S j −i , j = v + 1, v + 2,...,2t (*)
i =1
• (*) describes the output of a linear feedback shift
register with coefficients Λ1, Λ2, …, Λv.
• Given a sequence S1, S2, …, S2t, we can
determine the LFSR coefficients.
Berlekamp-Massey Algorithm 3
• In the Berlekamp-Massey algorithm, we build the LFSR that
produces the entire sequence by successively modifying an
existing LFSR to produce increasingly longer sequences.
• We start with a LFSR that can produce S1, then we check to see
if that LFSR can produce {S1,S2}.
– If so, no modification is necessary.
– If not, then we need to modify the current LFSR to produce a
new one that can produce the sequence.
• We repeat until we have a LFSR that produces the sequence
{S1, S2, … S2t}.
Berlekamp-Massey Algorithm 4
• Let k be the iteration index of the algorithm and let Lk
be the length of the LFSR on iteration k.
• Let Λ(k)(x) be the error locator polynomial at iteration
k.
Λ( k ) ( x) = 1 + Λ(1k ) x + Λ(2k ) x 2 + ... + Λ(Lk ) x Li
i
• At iteration k, we have a LFSR capable of producing
sequence {S1, S2, …, Sk}.
Lk
S j = −∑ Λ(ik ) S j −i , j = Lk + 1,..., k
i =1
Berlekamp-Massey Algorithm 5
• Suppose after k-1 iterations, we have Λ(k-1)(x). On
iteration k, we compute:
Lk −1
Sˆ k = − ∑ Λ(ik −1) S k −i (**)
i =1
• If this is equal to Sk, then the error locator polynomial
is good to produce the sequence {S1, S2, …, Sk} and
no changes are needed. Therefore Λ(k)(x) = Λ(k-1)(x).
• If (**) is not equal to Sk, then the polynomial needs to
be modified. Lk −1
• This discrepancy is d k = S k − Sˆ k = S k + ∑ Λ i S k −i
( k −1)
i =1
Berlekamp-Massey Algorithm 6
Lk −1
d k = S k − Sˆ k = ∑ i S k −i
Λ( k −1)
i =0
Let us produce a new polynomial Λ(k)(x) = Λ(k-1)(x)+AxlΛ(m-1)(x),
where A is some element in the field, l is an integer and
Λ(m-1)(x) is one of the prior error locator polynomials associated
with an non-zero discrepancy dm.
Let us compute the new discrepancy using this new polynomial.
Lk −1 Lm−1
d 'k = ∑ Λ(ik −1) S k −i + A ∑ Λ(im −1) S k −i −l = d k + Ad m if we select l = k − m
i =0 i =0
By choosing A = -dm-1dk, d’k = 0. Thus, new polynomial produces
{S1, S2, …, Sk}. Proof in text to show that this algorithm produces
shortest LFSR.
Example
• Consider the two error correcting binary (15,7) BCH
code. The generator polynomial has roots α, α2, α3
and α4.
• Let r(x) = x2+x5.
• S1 = α, S2 = α2, S3 = α13 and S4 = α4.
Example Cont’d
k Sk dk c(x) L p(x) dm
0 0 1 1 0 1 1
1 α α 1+αx 0 1 1
2 α2 0 1+αx 1 1 α
3 α13 α13+α3 = 1+αx+x(3- 2 1+αx α
α8. 1)α8α14 =
1+αx+α7x2.
4 α4 α4+α14+ 1+αx+α7x2. 2 1+αx α8
α9 = 0
Simplification for binary codes
• Since S2k is not independent of Sk, every even
iteration of the Berlekamp-Massey algorithm will
result in dk = 0. Thus, we can skip every even
iteration.