Math and Computer Science Honors Theses

Decoding Algorithms for Reed-Solomon Codes

Date of Creation

5-16-2011

Document Type

Departmental Honors Thesis - Restricted Access

Department

Mathematics

First Advisor

John B. Little

Abstract

Reed-Solomon codes are a class of error-correcting codes whose construction and properties depend on the algebra of finite fields. They have been used in applications such as communication with deep space probes and the Compact Disc audio system. This paper will discuss the error correction capacity of these codes and one of the t raditional unique decoding methods based on solving the so-called key equation. These methods are limited in a sense because they often fail when a received word contains too many errors. Most recent work on the decoding problem for Reed-Solomon codes has focused on alternative approaches which output a list of possible decodings (codewords within some specified distance of the received word) instead of a unique closest codeword. We will discuss two such methods, one proposed recently by Lee and O'Sullivan, and a second based on the FGLM Grabner basis conversion algorithm. We will compare the efficiency of these two approaches and present experimental results.

Comments

Reader: Cristina Ballantine

This document is currently not available here.

Share

COinS