Introduction to Hamming Code and Parity Bits

 

  •  To detect d bit error we need d+1  bits. 
  • To Correct d bit error, we need 2d+1 bits.

Hamming code:

A Hamming code detects and corrects only one-bit error.

Parity bits: Along with message bits sender sends some extra bits which are helpful in error detection and correction. Those extra added bits are called Parity bits

There are two types of parity bits in Hamming code:

1. Even parity: If the total number of 1's including parity bits in a message is even, then that is called even parity. 

Example: let a sender sends a packet (message bits + parity bits) = 1010101000, Number of 1's is 4, So it is even parity.

2. Odd parity: If the total number of 1's including parity bits in a message is odd, then that is called odd parity. 

Example: let a sender sends a packet (message bits + parity bits) = 110010001001, Number of 1's is 5, So it is odd parity.

 

Deciding Parity Bits:-

let me ask you some questions:

  1. How many pairs bits are added if the total number of bits in a message is  m ?
  2. How the Receiver will know whether the error has happened or not?

Calculating Number of  parity bits:

let the number of message bits = m and

number of the parity bits            = p

then p should be satisfying g this easy condition:  \large {\color{Red} 2^p\geq m+p +1}

Example :

1. let the number of message bits = 4

Then

1. The number of parity bits \large p :

            \large 2^p= m+p +1

            \large 2^p= 4+p +1

            \large 2^p= 5+p 

Now the minimum value of \large p satisfying this equation is 3 So the total number of parity bits = \large 3

2. Total number of bits in Message(to be send)  =   parity bits + original message bits

                                                                                                     =      \large 3+4 =7

 

2. let's take  another example:

number of message bits = 7

So parity bit (p) = ???

       \large 2^p= m+p +1

      \large 2^p= 7+1+p= 8+p 

if \large p=4 

     \large 2^4\geqslant 8+4= 16\geq 12 

Yes, the equation is satisfied.

So the number of parity bit (p) =\large 4

Total number of bits in Message(to be send)  =   parity bits + original message bits

                                                                                                =    \large 11   

 

Each parity bits have some special functionality depending on their location and parity bits are added only  at location  \large 2^n:  where n= 0,1,2,3..........n

It means we can have parity bits at location 1, 2, 4, 8, 16.......

depending on the location of parity bits  we can write them like this

\large p_{1} = parity bit at location 1

\large p_{2} = parity bit at location 2

\large p_{4}= parity bit at location 4 ..... 

Remember \large p_{4} doesn't mean that it is number 4 So, it means it is used at location  number 4.

For example : let's say our message bit is like 

\large M= m_{1}m_{2}m_{3}m_{4} there are 4 bits so we need 3 parity bits and they are: \large p_{1}, p_{2}, p_{4}

So a total of 7 bits are needed to be sent: 

Location:      1       2      3       4      5      6       7  

Bits:                {\color{Red} p_{1}}    {\color{Red} p_{2}}   {\color{Blue} m_{1}}  {\color{Red} p_{4}}    {\color{Blue} m_{2}}   {\color{Blue} m_{3}}    {\color{Blue} m_{4}}

Each parity bit is going to take care of another bit depending on the location of the parity bit. Example:

{\color{Red} p_{1}=} {\color{Blue} 1,3,5,7,9,11}

{\color{Red} p_{2}=} {\color{Blue} 2,3,6,7,10,11....}

{\color{Red} p_{4}=} {\color{Blue} 4,5,6,7,12,13.14.15....} and so on.

How to remember this:

let's talk about {\color{Red} p_{4}=} {\color{Blue} 4,5,6,7,12,13.14.15....} {\color{Red} p_{4}} has a subtext 4 that's why it starts with 4 and read four continuous value 4,5,6,7 then it makes a gap for four number(8,9,10,11). Now it will read the next four value 12,13,14,15 and again a gap of four continuous numbers(16,17, 18, 19) and so on...

Now we are done with basics. Let's move forward to implement all this stuffs.

 

 

 

 

Contributor's Info

Created:
0Comment
Error Control

Error Control:
 The error made in bits during transmission from source to destination machines must be detected and corrected.
 Many error detecting and error correcting codes are available.
 Both sending and receiving ends must agree to use any one code.
 

Contributor's Info

Created:
0Comment