|dc.description.abstract||The fundamental problem that led to the development of the theory of error correcting
codes was that of having a reliable communication over unreliable channels. A commu-
nication channel can be as simple as the air between the voicebox of one adressing an
audience and the ears of the listeners. Copper wires connecting telephones or modems
can also be considered as channels. In the case of data storage, say in a magnetic tape or
disc, the magnetized eld in the magnetic tape or disc is the channel.
One property of these channels is their capacity to distort the information. For instance,
the copper wires connecting telephones may get heated resulting in background interrup-
tions. Magnetisation on the tape may re-align over time, or the head of the drive reading
the tape or disc may be ill positioned and the right magnetisation be misread! Such
distotortions to our good information will be referred to as noise.
There are two main ways of handling noise; physical means and system means. Under
physical means, one "targets" the cause of noise and seeks to eliminate it. For instance if
the drive head misreads the magnetisation, then a better drive is used as a replacement
for the "now faulty drive". As for system means, one "sandwiches" the channel between
two devices; an encoder and a decoder (see gure 0:1) so that any form of noise can be
detected and possibly corrected. The theory of error correcting codes is involved in this.
For our purpose we will consider an abstract communication channel called the Binary
Symmetric Channel (BSC). In BSC, information to be transmitted is encoded as a string
of 00s and 10s. An error is then considered as an interchange between the binary digits in
the sent and received information symbols||en