Berlekamp-Massey algorithm

The Berlekamp-Massey algorithm is used to find the shortest, linear feedback shift register that will output a given sequence of symbols. The symbols can come from any body . The process was developed from 1968 to 1969 by Elwyn Berlekamp and James Massey . Applications are in the area of efficient decoding of BCH codes and subgroups such as the Reed-Solomon codes .

Preliminary remarks

In the case of a linearly fed back shift register of length, the first output symbols match the initial contents of the memory cells. The following output symbols are caused by the recursion ${\ displaystyle L}$ ${\ displaystyle L}$ ${\ displaystyle L}$

{\ displaystyle s_ {j} = - \ sum _ {k = 1} ^ {L} c_ {k} \ cdot s_ {jk}}

certainly. The feedback coefficients denote the shift register. If the designation D is introduced for a delay, the feedback shift register can also use the polynomial ${\ displaystyle c_ {k}}$

{\ displaystyle C (D) = 1 + \ sum _ {k = 1} ^ {L} c_ {k} \ cdot D ^ {k}}

to be discribed.

The aim of the Berlekamp-Massey algorithm is therefore to find the feedback polynomial and the length of the generating shift register for a given sequence of symbols . ${\ displaystyle \ left (s_ {0}, s_ {1}, \ ldots, s_ {n-1} \ right)}$ ${\ displaystyle C (D)}$ ${\ displaystyle L}$

Simple example

For simplicity, we consider the binary case, that a body with only two elements: . The addition is defined as follows: and and can be implemented with an XOR gate. For the multiplication applies and , which corresponds to a logical AND operation . ${\ displaystyle \ mathbb {F} _ {2} = \ {0,1 \}}$ ${\ displaystyle 1 \ oplus 0 = 0 \ oplus 1 = 1}$ ${\ displaystyle 0 \ oplus 0 = 1 \ oplus 1 = 0}$ ${\ displaystyle 0 \ otimes 0 = 0 \ otimes 1 = 1 \ otimes 0 = 0}$ ${\ displaystyle 1 \ otimes 1 = 1}$

The Berlekamp-Massey algorithm determines the shortest, linear feedback shift register for the symbol sequence (0 0 1 1 0 1 1), which outputs this sequence:

The feedback polynomial is for this example and the length of the shift register is . ${\ displaystyle C (D) = 1 + D + D ^ {2}}$ ${\ displaystyle L = 3}$

algorithm

The following variables are introduced to describe the algorithm:

symbol	meaning
${\ displaystyle i}$	Index of the symbol that is currently being processed
${\ displaystyle C (D)}$	current feedback polynomial of the shift register
${\ displaystyle L}$	current length of the shift register
${\ displaystyle d}$	current discrepancy, i.e. difference between the current symbol and the symbol that is generated by the current shift register ${\ displaystyle s_ {i}}$
${\ displaystyle C_ {l} (D)}$	Feedback polynomial of the shift register when the length was last changed
${\ displaystyle l}$	Index indicating the step in which the length was last changed
${\ displaystyle d_ {l}}$	The value of the discrepancy when the length was last changed
${\ displaystyle T (D)}$	Temporary storage for the feedback polynomial ${\ displaystyle C (D)}$

This results in the following algorithm

Berlekamp-Massey algorithm

The principle of the algorithm is easy to understand: It starts with a shift register of length 0, which generates an output sequence of all zeros. In each iteration step it is checked whether the current shift register outputs the desired output symbol. If so, the shift register is retained and the iteration continues with the next symbol in the given sequence. However, if a discrepancy is found, the shift register is adjusted. Whether the length of the shift register has to be increased depends on the current length of the shift register and the number of symbols processed. In case of discrepancy applies to the new length: . ${\ displaystyle L_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle L_ {i + 1} = {\ text {max}} (L_ {i}, i + 1-L_ {i})}$

For the binary case, the algorithm can be simplified significantly. In this case, the input symbols , the feedback coefficients and the discrepancy come from the set . So it immediately follows from and . ${\ displaystyle s_ {i}}$ ${\ displaystyle c_ {k}}$ ${\ displaystyle d}$ ${\ displaystyle \ {0.1 \}}$ ${\ displaystyle d \ neq 0}$ ${\ displaystyle d = 1}$ ${\ displaystyle d ^ {- 1} = 1}$

Applications

The Berlekamp-Massey algorithm can be used to decode the Reed-Solomon code . A Reed-Solomon code has the property that 2 · t values of the discrete Fourier transform of the error pattern can be determined from the received symbols. The entire Fourier transformation can be reconstructed from these 2 · t support values with the aid of the Berlekamp-Massey algorithm, provided that at most t symbols of the code word are incorrect.

With the help of the Berlekamp-Massey algorithm, it is possible to efficiently determine what is the shortest, linearly feedback shift register that generates a given sequence. The length of this shift register is called the linear complexity of the sequence. In cryptography in particular , it is of interest to know the linear complexity of a sequence.

literature

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography . CRC Press, Boca Raton FL et al. 1996, ISBN 0-8493-8523-7 ( CRC Press series on discrete mathematics and its applications ).
Elwyn R. Berlekamp: Algebraic Coding Theory . 2nd Edition. Aegean Park Press, 1984, ISBN 0-89412-063-8 (1st edition, published by McGraw-Hill in 1968).

Individual evidence

↑ Elwyn R. Berlekamp: Nonbinary BCH decoding . In: IEEE transactions on information theory . tape 14 , 1968, ISSN 0018-9448 , pp. 242 .
↑ James L. Massey: Shift-Register Synthesis and BCH Decoding . In: IEEE transactions on information theory . tape 15 , no. 1 , 1969, ISSN 0018-9448 , p. 122-127 .

Web links

Applet for the Berlekamp-Massey algorithm

[berle1-1] Elwyn R. Berlekamp: Nonbinary BCH decoding . In: IEEE transactions on information theory . tape 14 , 1968, ISSN 0018-9448 , pp. 242 .

[masse1-2] James L. Massey: Shift-Register Synthesis and BCH Decoding . In: IEEE transactions on information theory . tape 15 , no. 1 , 1969, ISSN 0018-9448 , p. 122-127 .