HAMMING CODING TECHNIQUE FOR ERROR CORRECTION
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