Fast Decoding Of Alternant Codes Using A Divison-Free Analog Of An Accelerated Berlekamp-Massey Algorithm

Abstract: – We present division-free analogs of the accelerated Berlekamp-Massey (BM) algorithms of R. Blahut based on an algorithm by G. Norton. Due to their similar structures, the computational complexity of Blahut’s algorithms and ours are essentially the same. However, the division-free operation of our algorithms make them attractive, particularly for hardware implementations. We further show how our algorithms may be used for fast decoding of alternant codes. In particular, we show that our algorithms simultaneously compute both an error locator and error evaluator polynomial. Although this is achievable with the accelerated BM algorithms as well, explicit details have not been given. Finally, due to the frequent occurence of minimal polynomials in other areas besides coding theory, such as cryptography and systems theory, we expect our algorithms to have many useful applications in related areas