Section 9.2 Coding Theory
715
As an analogy, consider voice transmission over a poor-quality cell phone
connection. The speaker says the black hat but the receiver hears the black cat.
Because the received message makes sense and could have been the transmitted
message, there is no way to detect that an error has occurred. An alternative is to
encode the message to be transmitted by repeating it. Thus the code word for the
black hat would be the black hat the black hat, and the code word for the black cat
would be the black cat the black cat. A received message of the black hat the black
cat would alert the receiver that an error has occurred in transmission. However,
the received message is equally close to either of the two code words, so there is no
way to guess the correct code word. Note that two errors could still go undetected.
Now let’s make the code word three copies of the message: the black hat the
black hat the black hat and the black cat the black cat the black cat. A received
message of the black hat the black cat the black hat would signal that either one or
two errors has occurred. If we assume it to be more likely that only one error has
occurred, we decode the message to the closest code word, the black hat the black
hat the black hat. This process is called maximum likelihood decoding and gives
us the correct code word for a received message where no more than one error has
occurred. Because we can detect up to two errors and correct the effects of one
error, we have designed a double-error detecting, single-error correcting code.
Here we’ve seen three ideas central to coding theory: redundancy in coding,
maximum-likelihood decoding, and distance between code words. Redundancy
uses additional bandwidth or storage space, and it also increases exposure to errors. Yet, as we’ve seen from our little example, it also increases the capability for
detecting and perhaps correcting such errors. You are probably familiar with the
idea of a parity bit, where at the end of a binary string one extra bit is added so
that the total number of 1s in the string, including the parity bit, is even (an even
parity bit scheme). A single bit error is detectable because it would result in an odd
number of 1s. But there’s no way to tell which bit is in error. An even number of
errors is undetectable, and any odd number of errors is indistinguishable from a
single error. This code is single-error detecting.
The codes we will examine are generalizations of the parity-bit code.
A parity-bit code adds one bit to the end of an m-tuple message to turn it into an
n-tuple code word where n = m + 1. Our code words will add additional bits to
the end of an m-tuple message to create an n-tuple code word where the additional
n − m bits are all special sorts of parity bits. These codes also rely on further
results from group theory (indeed they are called group codes), so we need some
additional background first.
Background: homomorphisms and Cosets
According to the definition, for f to be an isomorphism it must be both a bijection
and a homomorphism.
example 17
Consider the following functions from Z to Z:
f (x) = 0
g(x) = x + 1
The function f is a homomorphism from the group 3Z, + 4 to the group 3Z, + 4
because f (x + y) = 0 = 0 + 0 = f (x) + f ( y). However, f is not a bijection,
715
As an analogy, consider voice transmission over a poor-quality cell phone
connection. The speaker says the black hat but the receiver hears the black cat.
Because the received message makes sense and could have been the transmitted
message, there is no way to detect that an error has occurred. An alternative is to
encode the message to be transmitted by repeating it. Thus the code word for the
black hat would be the black hat the black hat, and the code word for the black cat
would be the black cat the black cat. A received message of the black hat the black
cat would alert the receiver that an error has occurred in transmission. However,
the received message is equally close to either of the two code words, so there is no
way to guess the correct code word. Note that two errors could still go undetected.
Now let’s make the code word three copies of the message: the black hat the
black hat the black hat and the black cat the black cat the black cat. A received
message of the black hat the black cat the black hat would signal that either one or
two errors has occurred. If we assume it to be more likely that only one error has
occurred, we decode the message to the closest code word, the black hat the black
hat the black hat. This process is called maximum likelihood decoding and gives
us the correct code word for a received message where no more than one error has
occurred. Because we can detect up to two errors and correct the effects of one
error, we have designed a double-error detecting, single-error correcting code.
Here we’ve seen three ideas central to coding theory: redundancy in coding,
maximum-likelihood decoding, and distance between code words. Redundancy
uses additional bandwidth or storage space, and it also increases exposure to errors. Yet, as we’ve seen from our little example, it also increases the capability for
detecting and perhaps correcting such errors. You are probably familiar with the
idea of a parity bit, where at the end of a binary string one extra bit is added so
that the total number of 1s in the string, including the parity bit, is even (an even
parity bit scheme). A single bit error is detectable because it would result in an odd
number of 1s. But there’s no way to tell which bit is in error. An even number of
errors is undetectable, and any odd number of errors is indistinguishable from a
single error. This code is single-error detecting.
The codes we will examine are generalizations of the parity-bit code.
A parity-bit code adds one bit to the end of an m-tuple message to turn it into an
n-tuple code word where n = m + 1. Our code words will add additional bits to
the end of an m-tuple message to create an n-tuple code word where the additional
n − m bits are all special sorts of parity bits. These codes also rely on further
results from group theory (indeed they are called group codes), so we need some
additional background first.
Background: homomorphisms and Cosets
According to the definition, for f to be an isomorphism it must be both a bijection
and a homomorphism.
example 17
Consider the following functions from Z to Z:
f (x) = 0
g(x) = x + 1
The function f is a homomorphism from the group 3Z, + 4 to the group 3Z, + 4
because f (x + y) = 0 = 0 + 0 = f (x) + f ( y). However, f is not a bijection,