ECE4253 Digital Communications | |
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada | |
If more bits are included with a message, and if those bits can be arranged such that different errored bits produce different error results, then bad bits could be identified. In a 7-bit message, there are seven possible single bit errors, so three error control bits could potentially specify not only that an error occured but also which bit caused the error.
Similarly, if a family of codewords is chosen such that the minimum distance between valid codewords is at least 3, then single bit error correction is possible. This distance approach is geometric while the above error-bit argument is algebraic.
Either of the above arguments serves to introduce the Hamming Code, a binary block code allowing correction of single bit errors.
Three even parity bits (P) are computed on different subsets of the four message bits (D) as shown below.
7 | 6 | 5 | 4 | 3 | 2 | 1 |   |
D | D | D | P | D | P | P | 7-BIT CODEWORD |
D | - | D | - | D | - | P | (EVEN PARITY) |
D | D | - | - | D | P | - | (EVEN PARITY) |
D | D | D | P | - | - | - | (EVEN PARITY) |
The three parity bits (1,2,4) are related to the data bits (3,5,6,7) as shown at right. In this diagram, each overlapping circle corresponds to one parity bit; each circle encompasses a different group of four bits and each circle is to have even parity. For example, parity bit 2 is computed so that its circle including data bits (3,6,7) is even parity. Given four data bits, the three parity bits can easily be chosen to ensure this condition. It can be observed that changing any one bit numbered 1..7 uniquely affects the three parity bits. Changing bit 7 affects all three parity bits, while an error in bit 6 affects only parity bits 2 and 4, and an error in a parity bit affects only that bit. The location of any single bit error can be established by rechecking the three parity circles.
|
For example, the message 1101 would be sent as 1100110, since:
When these seven bits are entered into the parity circles, it can be confirmed that the choice of these three parity bits ensures that the parity within each circle is even, as shown here. |
It may now be observed that if an error occurs in any of the seven bits, that error will affect different combinations of the three parity bits depending on the bit position.
For example, suppose the above message 1100110 is sent and a single bit error occurs such that the codeword 1110110 is received:
transmitted message received message 1 1 0 0 1 1 0 ------------> 1 1 1 0 1 1 0 BIT: 7 6 5 4 3 2 1 BIT: 7 6 5 4 3 2 1
The above error (in bit 5) can be corrected by examining which of the three parity bits was affected by the bad bit:
7 | 6 | 5 | 4 | 3 | 2 | 1 | |||
1 | 1 | 1 | 0 | 1 | 1 | 0 | 7-BIT CODEWORD | ||
1 | - | 1 | - | 1 | - | 0 | (EVEN PARITY) | NOT! | 1 |
1 | 1 | - | - | 1 | 1 | - | (EVEN PARITY) | OK! | 0 |
1 | 1 | 1 | 0 | - | - | - | (EVEN PARITY) | NOT! | 1 |
In fact, the bad parity bits labelled 101 point directly to the bad bit since 101 binary equals 5. Examination of the 'parity circles' confirms that any single bit error could be corrected in this way.
The value of the (7,4) Hamming code for error correction can be summarized:
The ability to correct single bit errors comes at a cost which is less than sending the entire message twice. (Recall that simply sending a message twice does not allow error correction.)
  | 7 6 5 4 3 2 1 |
Hamming Code Generator - This circuit generates the (7,4) codewords at left from the four inputs bits (7,6,5,3) at the top. The XOR gates accomplish modulus 2 addition to determine the parity bits (4,2,1). |
0 | 0 0 0 0 0 0 0 | |
1 | 0 0 0 0 1 1 1 | |
2 | 0 0 1 1 0 0 1 | |
3 | 0 0 1 1 1 1 0 | |
4 | 0 1 0 1 0 1 0 | |
5 | 0 1 0 1 1 0 1 | |
6 | 0 1 1 0 0 1 1 | |
7 | 0 1 1 0 1 0 0 | |
8 | 1 0 0 1 0 1 1 | |
9 | 1 0 0 1 1 0 0 | |
A | 1 0 1 0 0 1 0 | |
B | 1 0 1 0 1 0 1 | |
C | 1 1 0 0 0 0 1 | |
D | 1 1 0 0 1 1 0 | |
E | 1 1 1 1 0 0 0 | |
F | 1 1 1 1 1 1 1 |
The Hamming code is an example of a linear code because if any two of the above codewords are added together, the sum is another codeword.
Looking again at the Venn diagram (at right) it can be observed that a change in any of the data bits (3,5,6,7) necessary changes at least two other bits in the codeword. For example, given a valid Hamming codeword, a change in bit 3 changes three bits (1,2,3) such that the new codeword is a distance (d=3) from the initial word. The clever arrangement of the Hamming codewords ensures that this is the case for every valid codeword in the set. Having distance (d=3) allows correction of single bit errors OR detection of 2-bit errors (because the two cases cannot be distinguished). |
If a 2-bit error occurs, the (7,4) Hamming code will interpret the event as an apparent single-bit error to be corrected. If an additional parity bit (P) is appended to the Hamming code as shown in the diagram at right, the resulting (8,4) codewords in the Extended Hamming Code will have distance (d=4). The new check bit (P) is computed as the even parity of the entire 7-bit Hamming code and improves the performance of the Hamming code whenever two bit errors occur. Having distance (d=4) allows correction of single bit errors and detection of 2-bit errors. Specifically, if a 1 bit error occurs, parity check (P) fails, while a 2-bit error is distinguished by the fact that parity check (P) passes. |
There is no unique set of codewords with L=7 and D=3. The Hamming code shown here (L=7,D=3) is useful because it is easy to generate and to check this particular set of codewords by hand using the Venn diagram. The distance D=3 would still be achieved if two columns were swapped in the codewords or if the bits in any column were complemented, but the codewords would look very different (and the Venn diagrams could not be used).
Practical applications of the Hamming code use matrix methods to create codewords and to check for errors. See Hamming Code with Matrices
To examine sets of codewords with various distance properties, Online Codeword Generating Tool
The value of carefully choosing error control schemes is demonstrated by the (7,4) Hamming Code where set of codewords separated by a minimum distance D=3 allow for single-bit error correction.
Fri Apr 26 05:58:51 ADT 2024
Last Updated: 26 JAN 2016 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |