List Decoding of Algebraic Codes

Research output: Book/ReportPh.D. thesisResearch

794 Downloads (Pure)


We investigate three paradigms for polynomial-time decoding of Reed–Solomon codes beyond half the minimum distance: the Guruswami–Sudan algorithm, Power decoding and the Wu algorithm. The main results concern shaping the computational core of all three methods to a problem solvable by module minimisation; by applying the fastest known algorithms for this general problem, we then obtain realisations of each paradigm which are as fast or faster than all previously known methods. An element of this is the “2D key equation”, a heavily generalised form of the classical key equation, and we show how to solve such using module minimisation, or using our new Demand–Driven algorithm which is also based on module minimisation.

The decoding paradigms are all derived and analysed in a self-contained manner, often in new ways or examined in greater depth than previously. Among a number of new results, we give: a fast maximum-likelihood list decoder based on the Guruswami–Sudan algorithm; a new variant of Power decoding, Power Gao, along with some new insights into Power decoding; and a new, module based method for performing rational interpolation for theWu algorithm. We also show how to decode Hermitian codes using Guruswami–Sudan or Power decoding faster than previously known, and we show how to Wu list decode binary Goppa codes.
Original languageEnglish
Place of PublicationKgs. Lyngby
PublisherTechnical University of Denmark
Number of pages178
Publication statusPublished - 2013
SeriesDTU Compute PHD-2013


Construction and decoding of algebraic codes

Rosenkilde, J. S. H., Beelen, P., Geil, H. O., Augot, D., Bossert, M. & Høholdt, T.

Technical University of Denmark


Project: PhD

Cite this

Nielsen, J. S. R. (2013). List Decoding of Algebraic Codes. Technical University of Denmark. DTU Compute PHD-2013, No. 309