Decoding Hermitian Codes with Sudan's Algorithm

摘要

We present an efficient implementation of Sudan's algorithm for list decoding Hermitian codes beyond half the minimum distance. The main ingredients are an explicit method to calculate so-called increasing zero bases, an efficient interpolation algorithm for finding the Q-polynomial, and a reduction of the problem of factoring the Q-polynomial to the problem of factoring a univariate polynomial over a large finite field.