topcn

NETAJI SUBHASH ENGINEERING COLLEGE
TOPIC-With a given example explain Hamming Code
method for error detection and correction.
NAME - SANDIP HALDER

CLASS ROLL - 113 DEPT. -IT(B)
UNIV. ROLL - 10900221120
SUBJECT - COMPUTER NETWORK
CODE- PCC-CS602
Introduction to Hamming Code
Hamming Code is the set of error-correction codes that are used to detect the
error in the transmitted data and to correct the error. It can be applied to data
units of any length.
Hamming code is generally used for detecting as well as correcting single-bit

errors. Generally, the source encodes the message by adding a few redundant bits
during the transmission.
These redundant bits are generated and inserted at certain positions in the
message. They are mostly used for error detection and correction process.
Redundant Bits
So let's get into detail about the implementation of Hamming Code.
Implementation of Hamming code uses redundant bits. Firstly what is a
redundant bit? Redundant bits are the extra bits that are added by the sender and
removed(decoded) by the receiver.
They are generated by following the below algorithm. These extra redundant bit
help not only in error detection but also in error correction by indicating at which
bit the error occurred.
The number of redundant bits required can be calculated using the

below formula below:
2�≥�+�+12R≥M+R+1
where, R = Number of redundant bits,
M = Number of data bits
Determining the Position of Redundant Bits
For instance, if data bits are 4 then the number of redundant bits can be
calculated as 23>=4+3+123>=4+3+1 where 3 is the required number of
redundant data bits so that no data is lost during the transmission.
Parity Bits
Parity bits are nothing but redundant bits that are added to oversee that no data is
being lost during transmission. These extra bits are basically used for error
detection at the receiver point. There are two types of parity bits, which are:
Odd Parity bit:
• To find the value of a parity bit we need to check the number of ones in the
data.
• So, the number of ones is counted, if the count is even then the odd parity
bit's value is set to 1 and vice-versa if the count is odd, i.e parity bit's value
is set to 0.
Even parity bit:

• In the same way as in the Odd parity bit, we first need to count the number
of ones present in the given data. And then accordingly we need to assign
the value.
• If the count is even then even parity bit's value is assigned as 0.
• If the count is odd then the even parity bit's value is assigned as 1.
Determining the Parity Bits
Now, let's discuss about the position of parity bits:
Parity bits are placed at the bit position which is the power of 2 i.e, ( 2^0^ , 2^1^,
2^2^, 2^3^, 2^4^ ,.... so on) which are (1,2,4,8,... so on ). So for example, in the
7-bit data transfer we will be having 4 parity bits which are (1,2,4,8).
Example of Hamming Code

For an example of 4 data bits, we need to determine the number of redundant bits
required and the position of each redundant bits: We know that the redundancy
bits are placed at positions that are a power of 2 i.e, 1,2,4,8,16,..so on. Let's
consider an example:
Number of data bits to be transmitted = 4 Number of redundant bits required for

According the formula:
2�≥�+�+12R≥M+R+1
where, R = Number of redundant bits, M = Number of data bits
23>=4+3+123>=4+3+1
Therefore the number of redundant bits for lossless of data during transmission
is 3 Therefore the total number of bits obtained are(redundant bits + data bits)
3+4=73+4=7
The redundant bits are placed at positions corresponding to the power of 2 i.e (1,
2, 4, 8, 16...etc)
The below image explains it more clearly about it:
Where D represents data bit and R represents parity bit. Let's suppose the data to
be transmitted is 1110 the bit will be placed as follows:
The third step includes determining the value of parity bits:
1. To find the value of R1: Follow this- check 1 bit, then skip 1 bit, check 1
bit and then skip 1 bit, and so on. R1 bits: 1, 3, 5, 7, 9, 11.. so on, Since the
total number of bits is 7. So, R1 bits are: 1, 3, 5, 7. This is clearly explained
using the image:
This image is just an example but the value in the bits should be like in the next
image attached here(same for all below cases)
Mathematically: R1 = even parity(1, 3, 5, 7) = 0 For the value of redundant bit
R1, we check for even parity. Since the total number of 1’s in all the bit positions
corresponding to R1 is an even number the value of R1 (parity bit’s value) = 0
2. To find the value of R2: Follow this- check 2 bits, then skip 2 bits, check 2
bits and then skip 2 bits, and so on. R2: bits 2, 3, 6, 7
Mathematically: R2 = even parity(2, 3, 6, 7) = 0 For the value of

redundant bit R2, we check for even parity. Since the total number of
1’s in all the bit positions corresponding to R2 is an even number the
value of R1 (parity bit’s value) = 0
3. To find the value of R4: Follow this check 4 bits, then skip 4 bits,
check 4 bits and then skip 4 bits, and so on. R4: bits 4, 5, 6, 7
Mathematically: R4 = even parity(4, 5, 6, 7) = 1 For the value of redundant bit
R4, we check for even parity. Since the total number of 1’s in all the bit positions
corresponding to R4 is odd number the value of R1 (parity bit’s value) = 1
Thus the data which will be transferred is:
Error Detection and Correction using Hamming Code:

Suppose in the below example if the 10^th^ bit is changed from 0 to 1 during
data transmission due to several external and internal factors, then it changes
the parity values in the binary number which is formed:
• So to calculate the position of error we make use of values present in
redundant bits/parity bits. These bits give the binary number representation
as 1010 whose decimal value is 10.
• To calculate the binary representation as 1010, we need to do the parity
check for positions of bits like we do for calculating the value of all
redundant bits, i.e for R1, R2, R4, R8.
• And each bit in 1010 is values obtained by :
o Bit 1(from right hand side): parity(1, 3, 5, 7, 9, 11) = 1 (observe from
the image)
o Bit 2(from right hand side): parity(2, 3, 6, 7, 10, 11) = 0
o Bit 3(from right hand side): parity(4, 5, 6, 7) = 1
o Bit 4(from right hand side): parity(8, 9, 10, 11) =0
o Mathematically, 1010 is the binary representation of the error bit.
• Therefore, we can conclude that bit 10 contains an error. To correct the
error the 10th bit is (toggled) i.e, changed from 0 to 1.
Advantages of Hamming Code

In this section, we will discuss the advantages of Hamming Code:
• Hamming codes are considered to be ideal for computer memory

and single-error correction.
• Hamming code not only detects errors but also helps in the identification of
bits on which error has occurred so that they can be corrected by the error
detection procedure explained above.
• It is considered more efficient where the data streams are delivered
for single-bit mistakes.
Disadvantages of Hamming Code

Despite having advantages Hamming Code also has a disadvantage:
• Hamming code is considered to be ideal for single-bit error correction but

what if there are multiple bits where an error occurred? Hamming Code
doesn't come handy during this issue(not efficient).
Conclusion
• Hamming code is a technique that was developed by R.W.Hamming to
detect errors and correct them.
• Data can be transmitted during communication without any corruption.
• Hamming code is a set of liner code that is useful for error detection up to
two immediate bit errors.
• It is also capable of single-bit errors.
• Few applications of using Hamming code are Modems, Satellites,
Embedded Processor, Computer Memory, etc.
• With the use of Hamming Code, we can encrypt and decode the data while
transmitting and after transmitting.

topcn

Uploaded by

Copyright:

Available Formats

topcn

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

topcn

Uploaded by

Copyright:

Available Formats

NETAJI SUBHASH ENGINEERING COLLEGE

TOPIC-With a given example explain Hamming Code

method for error detection and correction.

NAME - SANDIP HALDER

Hamming code is generally used for detecting as well as correcting single-bit

The number of redundant bits required can be calculated using the

where, R = Number of redundant bits,

M = Number of data bits

Determining the Position of Redundant Bits

Even parity bit:

Determining the Parity Bits

Now, let's discuss about the position of parity bits:

Example of Hamming Code

Number of data bits to be transmitted = 4 Number of redundant bits required for

where, R = Number of redundant bits, M = Number of data bits

The below image explains it more clearly about it:

The third step includes determining the value of parity bits:

Mathematically: R2 = even parity(2, 3, 6, 7) = 0 For the value of

Thus the data which will be transferred is:

Error Detection and Correction using Hamming Code:

Advantages of Hamming Code

• Hamming codes are considered to be ideal for computer memory

Disadvantages of Hamming Code

• Hamming code is considered to be ideal for single-bit error correction but

You might also like