Advisor:  Dr. Maegan Bos

SLU Festival of Science 2001 Oral Presentation

 

Description of Project:

Coding theory is the field of mathematics that describes how to retrieve a message transmitted through a channel.  In particular, it emphasizes how to design a code so that one can detect and correct errors created by noise in the channel.  Noise is any disturbance that distorts the message being sent.  Additionally, coding theory has practical applications.  For example, the Pathfinder that was sent to Mars transmitted digital images back to Earth.  Each image was broken down into a grid of pixels, and each pixel color was encoded as strings of zeroes and ones.  Other applications include ensuring telephone conversations do not have interference and making sure that scratches on compact discs do not distort the information on the CD.

There are several assumptions we will make in coding theory.  First, the codes are binary codes; they are composed of zeroes and ones known as bits.  Another main assumption is that the probability that a bit is sent correctly is greater than the probability that it is sent incorrectly.  Thus, although this assumption allows errors to be made, it makes it possible to detect and correct those errors.  A third assumption is that every channel used is a binary symmetric channel; thus, the chances that a certain bit is received is independent of whether that bit is a zero or a one.  Another important idea in coding theory is that the code is a block code.  Block codes consist of several codewords made up of the same number of bits; so, codewords are all of the same length.  Finally, there is an assumption made when one corrects errors.  If one has the set of codewords, and the word received is not in that set, then one decodes the word received to the “closest match” among the codewords.  There are several ways of doing this.  Finding the error pattern of the code is one way while using an algorithm such as maximum likelihood decoding is a method that works better for larger codes.  Each different code has an associated method of detecting and correcting errors.

There are different types of codes in coding theory.  One category of codes is linear codes.  One manipulates these codes via the theorems and methods of linear algebra.  Two other codes worth noting are Hamming codes and Golay codes.  Hamming codes are designed to correct any single error, while Golay codes corrects three or fewer errors.  The Golay code was used to encode pictures from Jupiter and Saturn.

For my oral presentation, I will discuss the basics of coding theory as well as several codes and their implementation.  I will work through an example of a linear code that covers these basic principles of coding theory.