Discrepancy $δ$ in the Berlekamp-Massey Algorithm

Question

I have a question regarding to the Berlekamp–Massey algorithm. Can someone guide me to understand the idea/intuition of this algorithm?

According to the explanation in Wikepedia, in each iteration, the algorithm is trying to calculate the discrepancy $δ$.

If $δ≠0$, the algorithm will update the error locator polynomial using an update polynomial $B(x)$. However, at this point, I know that the resulted error locator polynomial will make the $δ$ in current iteration become zero. But, how about all the $δ$ in previous iterations? It is very hard to visualize that the algorithm actually makes all previous $δ=0$.

Answer 1

Actually, BMA is a recursive algorithm and the discrepancy $$d_{n+1}=\hat{s}_{n+1}-s_{n+1}$$is the difference between

• What the current polynomial $C^{\{n\}}$ determined by BMA based on the sequence $(s_0,\cdots,s_n)$ predicts as the next symbol $\hat{s}_{n+1}$, and
• The actual symbol $s_{n+1}$.

This is what is used to update the polynomial if necessary. By induction, all discrepancies are then zero.

Answer 2

The Berlekamp-Massey algorithm is a procedure for LFSR synthesis; it. finds the shortest LFSR that will produce the given sequence $s_0, s_1, s_2, \cdots$. The algorithm is iterative (not recursive since it doesn't call itself) in that it examines the sequence one symbol at a time until it has processed the entire given sequence. At the end of the $i$-th iteration, the algorithm has examined $s_0, s_1, \cdots, s_{i-1}$ (examination of $s_i, s_{i+1}, \cdots$ is yet to come) and has synthesized the shortest LFSR that will generate $s_0, s_1, \cdots, s_{i-1}$. Then, at the beginning of the $(i+1)$-th iteration, the algorithm determines whether $s_i$ will be generated by the LFSR it has just found by computing what the next output $\hat{s}_i$ would be from the just-synthesized LFSR, and comparing it to what we want the LFSR to generate, namely, the given $s_i$. The difference is called the discrepancy $\delta_i$ and if $\delta_i$ happens to be nonzero, the previously-synthesized LFSR is updated so that the updated LFSR will compute $s_0, s_1, \cdots, s_{i-1}, {\mathbf s_i}$ (emphasis added). This update might increase the LFSR length and also change the feedback taps, or just change the feedback taps. It can be proven that if an iteration resulted in an increase in LFSR length and changing the taps, then on the very next iteration, only the feedback taps might change; the LFSR cannot increase in length.

In short, there is no need to worry about what happens to previous discrepancies; the current LFSR is guaranteed to generate all of the sequence examined thus far without any discrepancies creeping in during the generation process.