Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
