enter image description here

I'm trying to find a way to understand the process of the Berlekamp-Massey Algorithm. But I'm struggling in understanding the fourth step of the process, which is $B^{(r+1)}(x) = A^{(r)}/\delta^{(r)}$. I found this algorithm from this paper, "VLSI Architectures for Reed-Solomon Codes: Classic, Nested, Coupled, and Beyond". However, I don't know what this step is doing. Can anyone explain to me the purpose of having this step?


1 Answer 1


Too long for a comment.

The Berlekamp Massey algorithm is a tour de force. It has the names of two Shannon award (top information/coding theory award for lifetime contributions) recipients attached and it is quite subtle.

The step you point to is a way of correcting the discrepancy between the sequence the current polynomial would generate and the actual sequence by modifying the polynomial.

Dilip Sarwate has a nice answer on this with somewhat different notation.

Berlekamp-Massey to construct minimal LFSR

The textbooks by Richard Blahut also explain the BM algorithm. The one called “Fast algorithms..” may be the most detailed.

  • $\begingroup$ The explanation is based on the wikepedia derivation. That part i understand. However, this algorithm seems to correct the discrepancy in the future iteration. This part I'm confused. $\endgroup$
    – ytj_banana
    Commented Feb 6, 2021 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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