(Again, I’m not going to prove this if you’re interested, see Massey’s paper.) Sing Along with \( H_(x) \) is the unique polynomial of smallest degree that can be used in an LFSR to generate the set of output bits. Theorems! Bah! Those are so 17th-century. You can try reading James Massey’s original paper for the rest, but it’s heavy on the abstract algebra, at least for an amateur mathematician. It’s not so easy to explain why it works. That is, the Berlekamp-Massey algorithm is very simple to implement. There’s a very simple algorithm called the Berlekamp-Massey algorithm, that will do this. ![]() This time we’re tackling something different: how to determine the characteristic polynomial \( p(x) \) from the LFSR’s output. If we consider \( S \) as a polynomial bit vector such that \( S = x^k \bmod p(x) \), then this is equivalent to the task of figuring out \( k \) from \( S \) and \( p(x) \). ![]() The last two articles were on discrete logarithms in finite fields - in practical terms, how to take the state \( S \) of an LFSR and its characteristic polynomial \( p(x) \) and figure out how many shift steps are required to go from the state 000.001 to \( S \).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |