# The Berlekamp-Massey Algorithm

This tutorial introduces linear feedback shift registers (LFSR) and explains the Berlekamp - Massey algorithm to find the shortest LFSR for a given binary output sequence. An implementation of the algorithm in C++ is provided as well.

## Feedback Shift Registers

Feedback shift registers, or FSRs, for short, were probably first invented by Solomon Golomb and Robert Tausworthe. This tutorial is but a brief introduction to the theory of FSRs. We will learn, however, how to find the shortest linear FSR for a given binary output sequence.

An FSR of length **feedback function**. Let

The first **start value**, or the **seed**, of the FSR and the **key expansion** transforms the short sequence

The simplest and best understood FSRs are the so-called **linear-feedback shift register**, or LFSRs. The feedback function of LSFRs is a linear map.

## Linear Maps

A boolean function **linear form**, if its degree is

It is easy to see that there are exactly

Boolean linear functions are actual linear mappings in the sense of linear algebra, that is, a boolean linear function

Using a linear map, the iteration of the shift registers takes the following form:

## Fibonacci LFSRs

The Fibonacci LFSR only feeds a few bits back into the feedback function. Those bits that actually affect the next state are called **taps**. The taps are then XORed, which is equivalent to the addition in

The LFSR is said to be of maximal length, if, and only if, the corresponding feedback polynomial is primitive. The above polynomial is indeed primitive.

The following C++-code creates a

The code is rather self-explanatory. The first actual line of code, inside the „do-while“ loop, simply takes the bits that are tapped, as defined by the feedback polynomial, and computes their sum by XORing them. The second line then „outputs“ the rightmost bit, by shifting everything to the right, and then replaces the last bit of the LSFR by the output of the feedback function just calculated in the first step. Note that by invoking the LSFR with a negative number for „steps“, the LFSR will continue to output bits until it has reached the end of its cycle, whose length it will return.

As an example, let us create a LFSR with the polynomial from above:

And here is the output:

## Matrix Form

Binary LFSRs can be expressed by matrices in

Let further

thus the Frobenius matrix completely determines the behaviour of the LFSR. Using matrix notation, it is straightforward to generalize LFSR to arbitrary fields.

## Applications and Weakness

LFSRs can be implemented in hardware, which makes them very useful for on-the-field deployment, as they generate pseudo-random sequences very quickly, and this makes them useful in applications that require very fast generation of a pseudo-random sequence, such as direct-sequence spread spectrum (DSSS) radios, for example. One example of a DSSS is the IEEE 802. 11b specification used in wireless networks.

LFSRs have also been used for generating an approximation of white noise in various programmable sound generators.

LFSRs have long been used as pseudo-random number generators for use in stream ciphers, especially in the military, due to the ease of construction from simple electromechanical or electronic circuits. Unfortunately, with their linearity comes a huge weakness. Even just a small piece of the output stream is enough to reconstruct an identical LSFR using the Berlekamp - Massey algorithm. Obviously, once the LFSR is known, the entire output stream is known.

Important LFSR-based stream ciphers still in use nowadays include the A5/1 and the A5/2 ciphers used in GSM cell phones, or the E0 cipher used in Bluetooth. The A5/2 cipher has been broken and both A5/1 and E0 have serious weaknesses.

## The Berlekamp - Massey Algorithm

Now that we know how to construct a LSFR, let us learn how to reconstruct one from knowing an output bit string. The first idea that comes to mind, obviously, is to abuse the linearity of the LFSR. Assume, further, that the length of the LSFR is known, then it is clear that a simple matrix inversion is enough to reconstruct the feedback polynomial. The difficulty then is to find the length

Enter the Berlekamp — Massey algorithm. Basically speaking, this algorithm starts with the assumption that the length of the LSFR is

To solve a set of linear equations of the form

With each iteration, the algorithm calculates the discrepancy

Now all that is left to do is to increase

In what follows, we will derive and implement the Berlekamp — Massey algorithm over the finite field with two elements.

## Berlekamp - Massey over

There are a few natural simplifications to the above algorithm when working over the finite field of characteristic

- Compute the discrepancy
. **If** , then is a polynomial which annihilates the stream from to .**Else**:- Copy
into a new array . - Set
, , …, . **If** , set , and .**Else**: do nothing.

- Copy

Without further ado, behold the C++ implementation of the above algorithm:

Now let us test the algorithm with the output from the linear feedback shift register from above:

And here is the output:

Happy coding!

## References

- Wikipedia