Experiment No.
: - 03
TITLE: -
Write a program for error detection and correction for 7/8 bits ASCII codes using
Hamming Codes or CRC.
PROBLEM STATEMENT: -
Demonstrate the packets captured traces using Wireshark Packet Analyzer Tool for
peer-to-peer mode. Write a program for error detection and correction for 7/8 bits
ASCII codes using Hamming Codes or CRC.
OBJECTIVES: -
1. Implement and Test Error Detection/Correction.
2. Simulate and Correct Errors.
3. Analyse Network Traffic.
THEORY: -
Hamming Code :
Hamming code is 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.
Cyclic Redundancy Check (CRC)
An error detection mechanism in which a special number is appended to a block of
data in order to detect any changes introduced during storage (or transmission). The
CRe is recalculated on retrieval (or reception) and compared to the value originally
transmitted, which can reveal certain types of error. For example, a single corrupted
bit in the data results in a one-bit change in the calculated CRC, but multiple corrupt
bits may cancel each other out.
A CRC is derived using a more complex algorithm than the simple CHECKSUM,
involving MODULO ARITHMETIC (hence the 'cyclic' name) and treating each
input word as a set of coefficients for a polynomial.
● CRC is more powerful than VRC and LRC in detecting errors.
● It is not based on binary addition like VRC and LRC. Rather it is based
on binary
division.
● At the sender side, the data unit to be transmitted IS divided by a
predetermined divisor
(binary number) in order to obtain the remainder. This remainder is called
CRC.
● The CRC has one bit less than the divisor. It means that if CRC is of n bits,
divisor is of
n+ 1 bit.
● The sender appends this CRC to the end of data unit such that the
resulting data unit
becomes exactly divisible by predetermined divisor i.e. remainder becomes
zero.
● At the destination, the incoming data unit i.e. data + CRC is divided by the
same number
(predetermined binary divisor).
● If the remainder after division is zero then there is no error in the data unit
& receiver
accepts it.
● If remainder after division is not zero, it indicates that the data unit has been
damaged in
transit and therefore it is rejected.
● This technique is more powerful than the parity check and checksum error
detection.
● CRC is based on binary division. A sequence of redundant bits called
CRC or CRC remainder is appended at the end of a data unit such as byte.
Requirements of CRC :
A CRC will be valid if and only if it satisfies the following requirements:
1. It should have exactly one less bit than divisor.
2. Appending the CRC to the end of the data unit should result in the bit
sequence which is exactly divisible by the divisor.
CRC Generator
The various steps followed in the CRC method are
1. A string of n as is appended to the data unit. The length of predetermined
divisor is n+ 1.
2. The newly formed data unit i.e. original data + string of n as are divided by
the divisor
using binary division and remainder is obtained. This remainder is called
CRC.
3. Now, string of n Os appended to data unit is replaced by the CRC
remainder (which is
also of n bit).
4. The data unit + CRC is then transmitted to receiver.
5. The receiver on receiving it divides data unit + CRC by the same divisor &
checks the
remainder.
6. If the remainder of division is zero, receiver assumes that there is no error in
data and it
accepts it.
7. If remainder is non-zero then there is an error in data and receiver rejects it.
• For example, if data to be transmitted is 1001 and predetermined divisor is 1011.
The procedure given below is used:
String of 3 zeroes is appended to 1011 as divisor is of 4 bits. Now newly formed
data is 1011000
CRC Checker
1. Data unit 1011000 is divided by 1011.
2. During this process of division, whenever the leftmost bit of dividend or
remainder is 0,
we use a string of Os of same length as divisor. Thus in this case divisor 1011
is replaced by 0000.
3. At the receiver side, data received is 1001110.
4. This data is again divided by a divisor 1011.
5. The remainder obtained is 000; it means there is no error.
Conclusion:
Successfully implemented the hamming code error detection and correction &
implemented the program for CRC generator and CRC checker.
