Some Results on the Sudan Algorithm
Weishi Feng, Richard E. Blahut, Ece Dept · 1998
Sudan published a new algorithm that can decode low rate Reed-Solomon codes beyond their packing radii; he also gave an expression for the error-correcting capability and an upper bound on the number of outputs. we shall give a simpler deriva- tion which leads to simpler expressions for the error- correcting capability and a bound on the number of outputs of the algorithm. We also observe that the Sudan algorithm provides some information on the distance structure of low-rate Reed-Solomon codes at distance larger than the packing radii. Furthermore, our approach is more intuitive, for example, our ex- and it will output at most (r - 1) codewords, that is