Berlekamp–Massey algorithm

The Berlekamp -Massey algorithm is used to find the shortest linear feedback shift register that outputs a given sequence of symbols. The icons can be from any body. The procedure was developed 1968-1969 by Elwyn Berlekamp and James Massey. Applications are in the area of ​​efficient decoding of BCH codes and sub-groups such as the Reed -Solomon codes.

Preliminary remarks

With a linear feedback shift register of the length, the first output symbols correspond to the initial content of the memory cells. The following output symbols are defined by the recursion

Determined. In this case, refer to the coefficients of the feedback shift register. If we introduce the term D is a delay, then the feedback shift register also by the polynomial

Are described.

The aim of the Berlekamp -Massey algorithm, then, is to find a sequence of symbols given the feedback polynomial and the length of the generating shift register.

Simple Example

For simplicity, we consider the binary case, that a body having only two elements. The addition is defined as follows: and and can be implemented with an XOR gate. Applies and for the multiplication, which corresponds to a logical AND operation.

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

The feedback polynomial is for this example and the length of the shift register.

Algorithm

For the description of the algorithm, the following variables are introduced:

This results in the following algorithm

The principle of the algorithm is easy to understand: You start 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 icon. If this is the case, then the shift register is maintained and the iteration continues to the next symbol of the given sequence. If, however, constitute an discrepancy, the shift register is adjusted. Whether the length of the shift register needs to be increased, dependent on the current length of the shift register and the number of processed symbols. In the event of a discrepancy applies to the new length.

For the binary case, the algorithm can be significantly simplified. In this case, the input symbols, the feedback coefficients and the discrepancy from the set derived. Therefore follows from immediately.

Applications

The Berlekamp -Massey algorithm can be used for decoding the Reed-Solomon code. A Reed- Solomon code having the property that, for the two received symbols xt values ​​of the discrete Fourier transform of the error pattern may be determined. From these basic values ​​2 × t, the total Fourier transform to be reconstructed by means of the Berlekamp -Massey algorithm, as long as more than t symbols of the codeword are in error.

Using the Berlekamp -Massey algorithm can be efficiently determined, what is the shortest linear feedback shift register which generates a given sequence. The length of this shift register is called linear complexity of the sequence. In particular in the cryptography, it is of interest to know the linear complexity of a sequence.