Berlekamp–Massey algorithm: Difference between revisions

Revision as of 21:58, 24 September 2019

Revision as of 00:35, 25 September 2019

Line 24:

|authorlink= James Massey

|title= Shift-register synthesis and BCH decoding

|journal= IEEE Trans.Transations Inf.on Information Theory

|volume= IT-15

|issue= 1

|yeardate= January 1969

|pages= 122–127

|url= http://crypto.stanford.edu/~mironov/cs359/massey.pdf
|doi= 10.1109/TIT.1969.1054260

}}</ref><ref>{{Citation

|last= Ben Atti

Line 38 ⟶ 39:

|first3= Henri

|title= The Berlekamp–Massey Algorithm revisited

|journal= Applicable Algebra in Engineering, Communication and Computing

|dateApril 2006 |volume=17 |issue=1 |pages=75–82

|citeseerx=10.1.1.96.2743

|url= http://hlombardi.free.fr/publis/ABMAvar.html

|doi= }}</ref> Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm),<ref>{{Harvnb|Massey|1969|p=124}}</ref> but it is now known as the Berlekamp–Massey algorithm.

|doi= 10.1007/s00200-005-0190-z

|doi= }}</ref> Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm),<ref>{{Harvnb|Massey|1969|p=124}}</ref> but it is now known as the Berlekamp–Massey algorithm.

==Description of algorithm==

Line 48 ⟶ 53:

In the code examples below, ''C''(''x'') is a potential instance of ''Λ''(''x''). The error locator polynomial ''C''(''x'') for ''L'' errors is defined as:

:<math> C(x) = C_L \ x^L + C_{L-1} \ x^{L-1} + \cdots + C_2 \ x^2 + C_1 \ x + 1 </math>

or reversed:

:<math> C(x) = 1 + C_1 \ x + C_2 \ x^2 + \cdots + C_{L-1} \ x^{L-1} + C_L \ x^L. </math>

The goal of the algorithm is to determine the minimal degree ''L'' and ''C''(''x'') which results in all [[Decoding methods#Syndrome decoding|syndromes]]

:<math> S_n + C_1 \ S_{n-1} + \cdots + C_L \ S_{n-L}</math>

being equal to 0:

:<math> S_n + C_1 \ S_{n-1} + \cdots + C_L \ S_{n-L} = 0,\qquad L\le n\le N-1.</math>

Algorithm:

Line 64 ⟶ 69:

Each iteration of the algorithm calculates a discrepancy ''d''. At iteration ''k'' this would be:

:<math> d \gets S_k + C_1 \ S_{k-1} + \cdots + C_L \ S_{k-L}.</math>

If ''d'' is zero, the algorithm assumes that ''C''(''x'') and ''L'' are correct for the moment, increments ''m'', and continues.

Line 70 ⟶ 75:

If ''d'' is not zero, the algorithm adjusts ''C''(''x'') so that a recalculation of ''d'' would be zero:

:<math>C(x) \gets C(x) \ - \ (d / b) \ x^m \ B(x).</math>

The ''x^m'' term ''shifts'' B(x) so it follows the syndromes corresponding to ''b''. If the previous update of ''L'' occurred on iteration ''j'', then ''m'' = ''k'' − ''j'', and a recalculated discrepancy would be:

:<math> d \gets S_k + C_1 \ S_{k-1} + \cdots - (d/b) (S_j + B_1 \ S_{j-1} + \cdots ).</math>

This would change a recalculated discrepancy to:

Line 106 ⟶ 111:

/* steps 2. and 6. */

for (n = 0; n < N; n++) {

{

/* step 2. calculate discrepancy */

field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i};

if (d == 0) {

{

/* step 3. discrepancy is zero; annihilation continues */

m = m + 1;

} else }if (2 * L <= n) {

else if (2 * L <= n)

{

/* step 5. */

/* temporary copy of C(x) */

Line 127 ⟶ 128:

b = d;

m = 1;

} else }{

else

{

/* step 4. */

C(x) = C(x) - d b^{-1} x^m B(x);