SUMMER 2009 - NSERC USRA REPORT
ERROR-CORRECTING CODES AND THEIR APPLICATIONS
AL-HASAN AL-AZZAWI
Information media, such as communication systems and storage devices of data, are not
absolutely reliable in practice because of noise or other forms of introduced interference. One
of the tasks in coding theory is to detect, or even correct, errors. One of the most important
applications of Coding Theory is the Compact Disk (CD). It is not an exaggeration to say
that without error-correcting codes, the Compact Disk system would not be technically
feasible. Under the supervision of Dr. Hamid Usefi, I undertook the task of studying and
implementing the theories of this topic. In this project I had the opportunity to learn Maple
and C++ more in depth.
Consider the source encoding of four fruits, apple, banana, cherry, grape, as follows:
apple → 00, banana → 01, cherry → 10, grape → 11. Suppose the message apple, which is
encoded as 00, is transmitted over a noisy channel. The message may become distorted and
may be received as 01. The receiver may not realize that the message was corrupted. This
communication fails. How can we store the information so that all is not lost? On thing we
can do is to encode the message by repeating every bit 3 times to create a codeword. Then
to decode: in every triple of bits in the received word, we take a majority vote to determine
the bit of the message, see the figure below. This is however a naive way of encoding. With
the help of Coding theory, we can use much more efficient ways to encode and decode that
would add little redundancy while achieving better error-correcting ability.
I began my research by studying topics in number theory such as finite fields and minimal
polynomials since Coding Theory requires this background. Then with the guidance of Dr.
Usefi, I studied several types of codes, ranging from the general and basic types such as linear
codes to more complicated ones such as Reed-Solomon codes. I have implemented several
programs in both Maple and C++, including the implementation of the Reed-Solomon code
with parameters [255, 251, 5].
The Reed-Solomon code [255, 251, 5] was first implemented successfully using a high
level programming language Maple. This code is can correct up to 2 errors if used on its
own, it was chosen because of the fact that it is the exact same one used in Compact Discs.
The error locator polynomial in the program was determined using the Euclidean algorithm
Date: Aug, 26 2009.
1
2 AL-HASAN AL-AZZAWI
method. Dr. Usefi suggested using Shoup’s NTL library blah for c++ to implement the
decoding as NTL is known for having one of the fastest polynomial arithmetic. Although
not very user-friendly, it proved to be of better performance as the decoding was almost
twice as fast as the one done with maple.
After deeply learning Reed-Solomon codes, I conducted a research on their application
in the Compact Disk and how the CDs are actually encoded and decoded. Encouraged by
Dr. Usefi, I have written a report that summarizes the error-correcting codes I have studied
and their applications in various science disciplines.I also indulged in more advanced topics
such as list-decoding of Reed-Solomon [?] and studied some recent papers [?]. I am currently
working on a program that list decodes Reed-Solomon Codes.