In data communications, Hamming code is an error detection code that is interspersed with the bits of each character. At the receiving station, the code is checked in order to detect missing bits, and one-bit errors can be corrected automatically.
Hamming is a code is used to detect and correct errors in individual bits of transmitted data. Most land-based communications are satisfied by relying on checksum or CRC methods to detect errors. CRC correction requires re-transmission of faulty messages. But let us take the case of a satellite transmitting visual data as binary streams of information around another planet say Jupiter. The time it takes those messages to arrive at an Earth station from the satellite is measured in hours. During this time the satellite has adjusted its orbit and is going across new territory and sending additional data. Correcting errors in these messages cannot be done by re-transmission. A request for that re-transmission takes as long to get to the satellite as the original message took to get to Earth. Then consider the time it would take to resent the message. First satellite would have to be found. During the time it looks to send the original message and get the request to resent it, the satellite has gathered billions of additional data. The memory needed to hold data long enough to assure that were sent properly is staggering. Instead, an error-correction method such as the Hamming code is used so that errors can be corrected as they are detected.
Hamming code provide a method for error correction. Error bits called
Hamming bits, are inserted into the message at the random locations. It is
believed that the randomness of their locations reduces the odds that these
Hamming bits themselves would be in error. This is based on a mathematical
assumption that because there are so many more message bits compared with
hamming bits, there is a greater chance for a message bit to be in error than
for a Hamming bit to be wrong. Determining the placement and binary value of
the Hamming bits can be implemented using hardware, but it is often more
practical to implement them using software. The number of bits in a message (M)
are counted and used to solve the following equation to determine the number of
Hamming bits (H) to be used.
2H
≥ H + M + 1
Once the number of hamming bits is
determined, the actual placements of bits into the message are performed. It is
important to note that despite the random nature of the hamming bit placements,
exact placements must be known and used by both the transmitter and receiver.
This is necessary so that the receiver can
remove the Hamming bits from the message and compare them with a similar set of
bits generated at the receiver. Once the hamming bits are inserted into their
positions, the numerical values of the bit positions of the logic 1 in the
original message are listed. The equivalent binary numbers of these values are
added and the sum produced is used as the sets of the Hamming bits in the message.
The numerical difference between the Hamming values transmitted and that
produced at the receiver indicates the bit position that contains a bad bit
which is then inverted to correct it.
We shall see the following example for sending the message Help!
When sending the message Help! using synchronous data, start and stop
bits as well as parity are not used. Each ASCII character contains 7 bits, for
a total of 35 bits. The number of hamming bits is computed using equation
2H ≥ H + M + 1
H = 6 is the smallest value that satisfies the equation.
64 > 35 + 6 + 1 > 42
For simplicity we will insert the Hamming bits, less randomly, at every
other bit position, starting with the least significant bit:
H e
l p !
100100011001011101100111000001H0H0H0H0H1H
To begin the process of determining the
states of each of the Hamming bits, list of numerical value of each bit
position whose state is a 1. Start with the least significant bit as 1 and
increase the count by 1 for each succeeding bit position. H bit must be
included in the counting (but not the listing) process. In our example, the
first bit position with a 1 in it is position 2. The following are all the bit
positions containing a 1 that is the positions 2, 12, 18, 19, 20, 23, 24, 26,
27, 28, 30, 33, 34, 38, and 41.
The next step is to list the number of vertically along with the binary
equivalent of each one. The value of the Hamming bits (H) is created by adding
each binary bit column in the list, ignoring any carry condition.
2
0 0 0 0 1 0
12
0 0 1 1 0 0
18
0 1 0 0 1 0
19
0 1 0 0 1 1
20
0 1 0 1 0 0
23
0 1 0 1 1 1
24
0 1 1 0 0 0
26
0 1 1 0 1 0
27
0 1 1 0 1 1
28
0 1 1 1 0 0
30
0 1 1 1 1 0
33 1
0 0 0 0 1
34
1 0 0 0 1 0
38
1 0 0 1 1 0
41
1 0 1 0 0 1
----------------------------------------------------------------
H = 0 1 1 0 1 1
These values are submitted for the
"H" bits in the message in the order shown. The receiver repeats the process,
again ignoring the Hamming bit positions in the list. If everything is all
right, a comparison of the H values sent and those generated by the receiver
produces zero. When the receiver does the Hamming process, number 23 is omitted
from the list. This causes the Hamming bits to have a value of 0 0 1 1 0 0
instead of 0 1 1 0 1 1. When the H bits computed at the receiver are compared
with the transmitted H bits the result is as follows :
H
sent 0 1 1 0
1 1 as shown above
H
computed at receiver 0 0 1 1 0 0 *
-------------------------------
comparison results: 0 1 0 1 1 1 = 23 decimal
* because 23rd 1 will be changed to zero so
the sum !
To correct the message the receiver would
invert bit 23.
The reason why the Hamming code works is as
follows:
The originally transmitted codes are formulated by adding binary bits
together, ignoring carries. The process of this addition is nothing more than
exclusive ORing these bits together. A similar process occurs at the receiver.
If a bit has changed state between being sent and received , it either will not be included in
the process or , in the case of changing from a 0 to a 1, will be added to the
process. By exclusive ORing the two Hamming codes, the process is reversed. The
errant bit appears as the difference between the transmitted and received
Hamming bit values.
No comments:
Post a Comment