Creating and implementing efficient decoding algorithms is an important study in Coding Theory. This thesis focuses on the decoding algorithms for Reed-Solomon Codes and Hermitian Codes, specifically the Berlekamp-Massey Algorithm and the Berlekamp-Massey- Sakata Algorithm. The Berlekamp-Massey-Sakata Algorithm alone is not enough to decode up to the minimum distance bound so Feng and Rao's technique of Majority Voting is included to allow decoding up to the minimum distance bound and even beyond for some high rate codes. An implementation for each of these decoding algorithms using the programming language Sage was created with the goal that these could be made available to the community of Sage users.

A divide-and-conquer approach to perform the bivariate polynomial interpolation procedure is discussed in Chapter 3. This method can potentially reduce the interpolation complexity of algebraic soft-decision decoding of Reed-Solomon code.

How can one exchange information e?ectively when the medium of com- nication introduces errors? This question has been investigated extensively starting with the seminal works of Shannon (1948) and Hamming (1950), and has led to the rich theory of “error-correcting codes”. This theory has traditionally gone hand in hand with the algorithmic theory of “decoding” that tackles the problem of recovering from the errors e?ciently. This thesis presents some spectacular new results in the area of decoding algorithms for error-correctingcodes. Speci?cally,itshowshowthenotionof“list-decoding” can be applied to recover from far more errors, for a wide variety of err- correcting codes, than achievable before. A brief bit of background: error-correcting codes are combinatorial str- tures that show how to represent (or “encode”) information so that it is - silient to a moderate number of errors. Speci?cally, an error-correcting code takes a short binary string, called the message, and shows how to transform it into a longer binary string, called the codeword, so that if a small number of bits of the codewordare ?ipped, the resulting string does not look like any other codeword. The maximum number of errorsthat the code is guaranteed to detect, denoted d, is a central parameter in its design. A basic property of such a code is that if the number of errors that occur is known to be smaller than d/2, the message is determined uniquely. This poses a computational problem,calledthedecodingproblem:computethemessagefromacorrupted codeword, when the number of errors is less than d/2.