Digital Signal Processing Reference
In-Depth Information
The
Hamming
code is a binary error patching code that is able to patch 1-bit-errors in one
4-bit data word . This code requires three error control bits which must be computed before
stored. The data bits are a 1, a2, a3 and a4, the error control bits c 1, c2 and c3. Therefore a
7-bit code
results :
Example:
a1 a2 a3 a4 c1 c2 c3
1 0 0 1 ? ? ?
The error control bits in the transmitter are to be computed as follows :
c1 = a1 + a2 + a3
c1 =
1
+
0
+
0
c2 = a2 + a3 + a4
c2 =
0
+
0
+
1
c3 = a1 + a2 + a4
c3 =
1
+
0
+
1
Now we applicate the "modulo 2-sum":
0 + 0 = 1
It corresponds exactly to the
0 + 1 = 1
exclusive-or-function (EXOR).
1 + 1 = 0
This results in c
1 =
1,
c2 =
1
und c3 =
0
1
=
1
+
0
+
0
1
=
0
+
0
+
1
0
=
1
a1 a2 a3 a4 c1 c2 c3
1 0 0 1 1 1 0
+
0
+
1
Now a data error on transmission channel
1
=
1
+
0
+
0
a1 a2 a3 a4 c1 c2 c3
1 0 0
0
1 1 0
+
0
1
=
0
+
0
+
0
0
=
1
+
0
In the receiver a
parity test
is now carried out as follows::
e1 = ( a1 + a2 + a3 ) + c1
e2 = ( a2 + a3 + a4 ) + c2
e3 = ( a1 + a2 + a4 ) + c3
e1, e2 and e 3 are new check
bits which must always be 0
in case of perfect transfer
e1 = (
1
+
0
+
0
) +
1
=
0
e2 = (
0
+
0
+
0
) +
0
=
1
e3 = (
1
+
0
+
0
) +
0
=
1
The 2nd and 3rd equation is wrong . Both equations contain a 2 and a4. However, since
a2 would also make the 1st equation wrong , a4 must be wrong !
An error control bit was falsified on the transmission channel
1
=
1
+
0
+
0
0
=
0
+
0
+
1
0
=
1
a1 a2 a3 a4 c1 c2 c3
1 0 0 1 1
0
0
+
0
+
1
Only the 2nd equation is wrong . Since c2
occurs only in this and no other equation ,
c2 must be wrong !
e1 = (
1
+
0
+
0
) +
1
=
0
e2 = (
0
+
0
+
1
) +
0
=
1
e3 = (
1
+
0
+
1
) +
0
=
0
Illustration 251:
Codes which discover errors and codes which correct them
Individual bit errors can be discovered and corrected by the HAMMING code with 100% certainty. If
several bits are transmitted or read defectively this code is no use. There are however codes which correct
errors and make it possible to correct more than one bit, on the basis, of course, of additional check bits or
redundancy. Practically all these codes that correct errors essentially follow the example described:
“upstream“ information is calculated according to a preset pattern and the data is stored. This informa-
tion is used to recalculate the bits after being read. The check bit pattern makes it possible to locate the site
of the error and recognise the original correct value.
