3 ms·
After graduating with my BSEE and getting my first professional job, one of my very first tasks was to implement this algorithm on a PDP 11, in assembly. I firs
by sizzzzlerz 3y ago
After graduating with my BSEE and getting my first professional job, one of my very first tasks was to implement this algorithm on a PDP 11, in assembly. I first implemented it in Fortran (C had just come out and I didn't know it yet) to run on a VAX 11/780. Once it was working, it was amazing to see how powerful it was in correcting noisy data, even using rate 1/2 coding and short constraint lengths. Consider that the Voyager spacecraft, now nearly 24 billion miles from earth, uses it and it is still possible to decode it's data. In my mind, Viterbi's algorithm is equal in importance in communications with the FFT.
- aDfbrtVt 3y agoI would argue the FFT algorithm is much more important in communication systems than the Viterbi algorithm. There are plenty of powerful Forward Error Correction schemes that do not use Convolutional codes (and thus cannot use Viterbi algorithms). However, every single system with a reasonably long channel equalizer makes use of a real time FFT algorithm.
- pacaro 3y agoVoyager also uses Golay codes which are pretty neat too. The original paper is just one page. https://www.lama.univ-savoie.fr/pagesmembres/hyvernat/Enseignement/2223/info602/TP-Golay/golay_paper.pdf https://www.lama.univ-savoie.fr/pagesmembres/hyvernat/Enseig...
- aDfbrtVt 3y agoFun fact, Golay codes are the only perfect code outside of Hamming codes. Perfect codes are interesting in that the Hamming bound becomes an equality, effectively saying that the distance between all valid codewords is exactly the minimum distance "d".
- akhayam 3y agoIndeed, Hamming and Golay codes are an absolute thing of beauty. For folks that wanna read more about Hamming Bound, Kevin Boone does a good job in starting from the basics and explaining the intuition behind the proof: https://kevinboone.me/hamming_bound.html?i=1 https://kevinboone.me/hamming_bound.html?i=1
- pacaro 3y agoAnother fun fact, you could use one of the Roman dodecahedrons mentioned in another of today's articles to encode or decode Golay codes by hand...