Error Correcting Codes
Simplified Hamming Codes
Error correcting codes operate under the assumption about the probability
of error. The code scheme described below assumes that at most one in
every eight bits is changed during transmission. Actual data is combine
with error correcting data by making use of parity with groups of
bits. The error correcting data is added to give each group of bits odd
parity (an odd number of 1 (on, true) bits).
The eight transmitted bits are referred to as bit [0] through bit
[7]. Four bits of live data are transmitted with four bits of error
correcting data as follows:
-
The four bits of live data are placed in bits [3], [5], [6],
and [7]
-
These four bits are corresponded to the four areas indicated in the Venn
diagram
-
Bits [1], [2], and [4] are selected to create odd
parity in the three circles, indicated as A, B, and C.
-
Bit [0] is selected to produce odd parity in the entire diagram
To illustrate, consider the as an example the transmission of the four
bits 1 0 1 0. These four bits are placed in positions [3],
[5], [6], and [7], respectively, in the array, and
are considered to be in the corresponding four positions in the Venn diagram.
Next, zeros and ones are placed into areas [1], [2], and
[4] so that each of the four circles has odd parity. This is achieved
by placing a 0 in [1], a 1 in [2], and
a 0 in [4]. Finally, a zero or one is placed in area [0]
to give the entire Venn diagram odd parity. In this example, this is achieved
by placing a 0 in area [0].
This result provide us with the four error correcting bits that are included
in the eight bits that will be transmitted. Set theory can be used to determine
if the bits received are correct, or need to be corrected, or, if two bits
are changed that there is an error.
To illustrate the error correction process, assume bit [3] was
changed in transmission, and the string
was received. This information is placed into the Venn diagram. The following
observations can be made about the sets A, B, and C,
and the entire Venn diagram, indicated by U, 
-
A does not have parity, therefore the error is in
A.
-
B does not have parity, therefore the error is in
B.
-
C has parity, therefore the error is not in C,
so the error is in C compliment, ~C.
-
U does not have parity, therefore the error is in
U.
Form the intersection of these four sets, A and
B and ~C and U which
equals area [3], which is the desired result. By flipping the bit
in area [3], parity is achieved in Venn diagram and the string of
bits,
If no bits are changed, the parity is achieved in all the sets and there
is no need to perform a correction. If two bits are changed, then one or
more of the sets A, B, and C do not have parity, but
U does. In this case, an error is detected, but the error cannot
be corrected.
Practice problems In each case below determine is there is an error.
If there is, determine whether it can be corrected. If it can, make the
correction.