Description
Objective
Write a program for error detection and correction for ASCII codes using Hamming
Codes. Demonstrate the packets captured traces using Wireshark Packet Analyzer Tool
for peer to peer mode.
Theory
Hamming Code :
Hamming code is a technique developed by R.W. Hamming for error correction.
Hamming code is a set of error-correction codes that can be used to detect and correct
bit errors that can occur when computer data is moved or stored. Like other
error-correction code, Hamming code makes use of the concept of parity and parity bit
s, which are bits that are added to data so that the validity of the data can be checked
when it is read or after it has been received in a data transmission. Using more than one
parity bit, an error-correction code can not only identify a single bit error in the data unit,
but also its location in the data unit.
Computing parity involves counting the number of ones in a unit of data, and
adding either a zero or a one (called a parity bit ) to make the count odd (for odd parity)
or even (for even parity). For example, 1001 is a 4-bit data unit containing two one bits;
since that is an even number, a zero would be added to maintain even parity, or, if odd
parity was being maintained, another one would be added. To calculate even parity, the
XOR operator is used; to calculate odd parity, the XNOR operator is used. Single bit
errors are detected when the parity count indicates that the number of ones is incorrect,
indicating that a data bit has been flipped by noise in the line. Hamming codes detect
two bit errors by using more than one parity bit, each of which is computed on different
combinations of bits in the data.
Explanation :
Hamming Codes fall under the category of linear Block codes of Forward Error
Correcting (FEC) codes. To understand how it can be constructed, consider the
simplest (7,4) hamming code. The notation(7,4) indicates that the codewords are of
length 7 bits. Out of
these 7 bits, 4 bits are the original message and remaining 3 bits are added for
detecting and correcting errors. These remaining 3 bits are called redundant bits.
The structure can be indicated as follows:
4 message bits + 3 redundant bits 7 bit Hamming code. ⇒
Generally the linear block codes can be represented in two forms. One is called
Systematic form and other is called non-Systematic form. In Systematic Coding, the
redundant bits are calculated from the message bits and both are concatenated side by
side. Just by looking at the codeword you can identify the message portion and the
redundant portion.
Construction of Hamming codes :
Consider transmitting 4 data bits and these data bits are represented by letter D. We
are going to find the 3 redundant bits (represented by letter P) using Hamming code
algorithm and form the 7 bit Hamming code. The codewords made in this way is called
(7,4)
Hamming code which is a very basic code.
Let the codeword bits be represented by D7,D6,D5,P4,D3,P2,P1.
Here D7,D6,D5 and D3 are the message bits and P4,P2,P1 are the parity or redundant
bits. The parity bits are calculated using the following equations. Here + sign indicates
modulo-2 addition or XOR operation.
The following table illustrates how to calculate parity bits for the above coding scheme.
Find the Hamming code for the message bits 1101. The message 1101 will be sent as
1100110 using Hamming coding algorithm as follows. Here the data bits and the parity
bits in the codeword are mixed in position and so it is a non-systematic code.
The 4-bit message is converted into 7 bit codeword. This means, out of 128
combinations (27=128) only 16 combinations are valid codewords. At the decoder side,
if we receive these valid codewords then there is no error. If any of the other
combinations (apart from the valid codewords) are received then it is an error. The
minimum Hamming distance of the given Hamming code is 3, this indicates that the
Hamming code can detect 2 bit errors or it can correct single bit error.
Error Correction :
Consider that the codeword generated as before was transmitted and instead of
receiving 1100110, we received 1110110. A one bit error has occurred during the
reception of the codeword. Let’s see how the decoding algorithm corrects this single bit
error. The equation for the detecting the position of the error is given by
If there is an error then ABC will be the binary representation of the subscript or the
position of the erroneous bit.
Calculating A,B and C for the received codeword 1110110 gives A=1,B=0,C=1. Thus
ABC is 101 in binary, which is 5 in decimal. This indicates that the fifth bit (D5) bit is
corrupted and the decoder flips the bit at this position and restores the original
message.
