Abstract:
In 2007 Wu published a new list decoder for Reed-Solomon codes. It has similarities with the famous Guruswami-Sudan algorithm, most notably the decoding radius, but works in a significantly different manner. Importantly, for high-rate codes the Wu list-decoder has lower complexity than the Guruswami-Sudan.
At the core, it is an extension of the minimum-distance decoder using the Berlekamp-Massey algorithm (BMA). The derivation, however, is somewhat involved and requires extensive arguments on the precise workings on the BMA.
I will describe how the Wu list-decoder works, but using the Extended Euclidean algorithm as its main engine. This reveals more clearly the algebra underlying the decoder.