Error Control ,

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:

How many pairs bits are added if the total number of bits in a message is $m$ ?
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.

0Comment

thumbs up down