Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Given the sequence 0010001111 (or any other, not homework, but exam practice), how do you use the Berlekamp-Massey algorithm to construct a minimal LFSR?

I have read several definitions of how Berlekamp-Massey works, but I'm missing some simple example that actually demonstrates the algorithm in use.

Trying to use the following http://en.wikipedia.org/wiki/Berlekamp-Massey#The_algorithm_for_the_binary_field this is how far (or short) I get:

  1. Let $s_0, s_1, \dots, s_9$ be the bits 0,0,1,0,0,0,1,1,1,1.

  2. Let the arrays b and c, each of length 10, be: b = {1,0,0,0,0,0,0,0,0,0}, c = {1,0,0,0,0,0,0,0,0,0}

  3. Let L = 0, m = -1

  4. Iterate 10 times:

Iteration 0:

$$d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9}$$

Already at this first iteration (0) I run into problems. What are these negative subscript s variables?

I'm using the formula on Wikipedia, which is:

$$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$

Is there a fault in this formula? Earlier at step 3, the algorithm states L = 0, hence the final term with:

$$c_Ls_{N-L}$$

makes no intuitive sense if it is taken literally? I assume that the subscript of this s variable should keep decreasing and for c it should keep increasing? If taken as the formula states it, these would be just 0?

But regardless, there is this problem with the negative s variables.

share|improve this question
    
Perhaps the explanation in this answer might help, even though it uses slightly different notation. –  Dilip Sarwate May 17 at 3:26

1 Answer 1

up vote 1 down vote accepted

There are no issues with negative indices, even the first (or zero-th depending on how you want to count them) iteration.

The quantity $d$ is called the discrepancy. During the $N$-th iteration, $d$ is the difference between $s_N$, the $N$-th bit of the given sequence for which you are finding the LFSR, and the bit computed by the LFSR that you have synthesized thus far. If $d=0$, the bit produced by the LFSR is the same as the bit in the given sequence and so the current LFSR, which is guaranteed to produce $s_0, s_1, \ldots, s_{N-1}$, need not be changed: it is producing $s_N$ also. On the other hand, if $d \neq 0$, then the current LFSR needs to be updated, that is, you need to find the shortest LFSR that produces not just $s_0, s_1, \ldots, s_{N-1}$ but also $s_N$. How to go about doing this is the crux of the Berlekamp-Massey algorithm. Note that it is easy to find an LFSR that will produce $s_0, s_1, \ldots, s_{N}$: the trick lies in finding the shortest LFSR that will do so.

With that as background, and the further information that $L$ is an upper bound on the number of stages in the current LFSR, consider the discrepancy calculation $$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$ which really ought to be expressed as $$d = c_0s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$ but the simpler version works because $c_0 = 1$ always (see the initialization). Now, we begin with $c_0 = 1$ and all other $c_i = 0$, that is, a trivial LFSR with no stages that will produce $0$s for all eternity if you ask it to. In the very first calculation when $L=0$ and $N=0$, we have $$d = c_0 s_0 = s_0.$$ If you want to use the full-fledged form $$d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9}$$ that is fine, as long as you remember that $c_1=c_2=\cdots=c_9 = 0$, and the values you choose to ascribe to $s_{-1}, s_{-2}, \ldots, s_{-9}$ don't affect the computation at all. But more realistically, you should note that $L=0$ and $N=0$, and so the term $c_Ls_{N-L}$ that makes no sense to you is just $c_0s_{0-0}=c_0s_0=s_0$, just it ought to be.

In the form $$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$ correctly interpreted, you never run out of bits because $c_{L+1}, c_{L+2}, \ldots$ are all guaranteed to be $0$ and $L$ is upper bounded by $N$ and so $s_{N-L}$ can reach down to $s_0$, the leading bit of the given sequence, but no farther.

There are no negative subscripts on $s$ (or $c$) that we ever need to worry about.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.