NUnullc·Apr 11, 2019
Some months ago a colleague of mine and I were working on coming up with an intuitive lay explanation of the Berlekamp–Massey algorithm as part of a greater explanation of some of our work that uses it ( https://github.com/sipa/minisketch/ ).
It isn't terribly difficult to work through the algorithm mechanically and see that it solves the equations that it's intended to solve, but that is a long way from a good intuitive understanding of it. We spent some time going back through the original literature describing it and related contemporary work, but what we found also focused on a rather procedural description that didn't really strike the insight we were looking for.
At one point, I quipped that I should reach out to Berlekamp and inquire if this work really weren't the product of reverse engineering instruments found in a 1967 UFO cra
Read the rest
sh-- given what a remarkable advance it was. :)
I'm sad to hear that the world will never know for sure now.
Although Berlekamp's work has already been important to the world-- impacting most of the communications and storage devices we interact with--, I expect that its importance will increase in the future.
Many advances in computer science and related fields have their utility gated or multiplied by the power and pervasiveness of computing technology. I am always struck when I read older papers-- even ones as late as the 90s-- and find them discussing problem sizes at the limits of their computer technology which my laptop is solving thousands of times per second as part of my application (or just as part of my research). So I find that my recent work using the berlekamp-massey algorithm casually applies to problem sizes that would have probably been unthinkable in the 80s, even using Cyclotomic's expensive specialized hardware. The increasing power and decreasing cost of general purpose computing increases the importance and broadens the applicability of the algorithms we run on it.