The Research Of List Decoding Algorithm For Derivative Codes

In 1997, Sudan presented the list-decoding algorithm for RS codes which provides error recovery capability beyond the error-correction bound of (1-R)/2. Since then, list-decoding algorithm has been explored to decode RS codes and their variants, and error-correction radius has been improved. In 2008, Guruswami and Rudra presented an algorithm based on multivariate polynomial interpolation to list decode folded RS Codes. The error-correction radius can approach the list decoding capacity value 1-R. In 2011, Guruswammi and Wang introduced the derivative codes which is closely related to the folded RS codes. They simplified the interpolation polynomial. The error-correction radius can still be made to exceed 1-R-ε for any ε> 0.Inspired by the work of Guruswami and Wang, in this thesis we utilized the property of formal derivative, changed the interpolation polynomial of their work and reduced the degree parameter. For every in order to correcting a fraction 1-R-ε of errors. At last, we evaluated that the tim complexity of our algorithm is...