Categories
Binary Code

Example 2: Hamming code and Parity bit

Eg.  Now form a hamming code for 5-bit information bits 10110 with odd parity

m=5 and we have to follow         2p >= m + p + 1

The value of p as 4 to satisfy 24 (16) >= 5 + 4 + 1 but p=3 doesn’t satisfy as 23 (8) >= 5 + 3 + 1

So p=4 and hence a total of 9 bits

Parity bit positions are 1, 2, 4, 8

And hence hamming code composition is as follow

0001       0010      0011      0100       0101       0110       0111       1000       1001 

1              2              3              4              5              6              7              8              9

P1                P2             M1             P3              M2            M3               M4               P4             M5

Now if we see Phas 1 at LSB so message bits with this parity bit are M1 M2 M4 M5

Similarly we see P2 checks M1 M3 M4

Similarly we see P3 checks M2 M3 M4

Similarly we see P4 checks M5

Or we can also put it as

Pchecks code bits 1, 3, 5, 7, 9

Pchecks code bits 2, 3, 6, 7

Pchecks code bits 4, 5, 6, 7

Pchecks code bits 8, 9

For message 10110 we hamming code

Bit positions  

1              2              3              4              5              6              7              8              9 

P1               P2               1 P3             0 1 1 P4              0

We see P1=1 to make no. of 1’s to 3 i.e. odd

We see P2=0 to make no. of 1’s to 3 i.e. odd

We see P3=1 to make no. of 1’s to 3 i.e. odd

We see P4=1 to make no. of 1’s to 1 i.e. odd

So we get the hamming code as 101101110

Categories
Binary Code

Example 1: Hamming code & parity bit

Eg. So let’s form hamming code using 4-bit message bits 1101 with parity bits as even parity bit and check how it is able to detect and correct error.

As we have already decided parity bit positions and their corresponding message bits for a 4-bit message

For the moment we have hamming code as P1    P2    1 P1 0 1

As we have already seen              PChecks bit number 1,3,5,7

So P1 = 1 to make number of 1’s to 4 i.e. even in positions 1,3,5,7

 PChecks bit number 2,3,6,7

So P2 = 0 to make number of 1’s to 2 i.e. even in positions 2,3,6,7

PChecks bit number 4,5,6,7

So P3 = 0 to make number of 1’s to 2 i.e. even in positions 4,5,6,7

Hence we have the hamming code as 1010101

As we have already mentioned that hamming code can only detect and correct only single error. So we have error at 5th position which means bit changes from 1 to 0 so we have data changed from 1010101 to 1010001

Now let’s start checking all 3 parity bits starting from P1

PChecks bit number 1,3,5,7 and we see we have number 1’s in these bits is 3 i.e. odd which is wrong as it should have been even so put a 1

PChecks bit number 2,3,6,7 and we see we have number 1’s in these bits is 2 i.e. even which is right so put a 0

PChecks bit number 4,5,6,7 and we see we have number 1’s in these bits is 1 i.e. odd which is wrong as it should have been even so put a 1

Now we collect all the bits recorded with bit from Pas LSB

So we get 101 hence we get bit 5 with

So as P1  and P3 give wrong results so now we find which code bit position is common but not found in code bit position of parity bit Pand we see that we 5 and 7 common for P1  and P3 but 7 is also present in P2 so we are left with code position 5.

RULE TO FIND POSITION OF ERROR: We start from Pand start checking whether bit is correct or wrong and if it is wrong then we put a 1 and put a zero if it is correct. And while we reach end we collect all those bits taking bit from Pas LSB. The decimal equivalent we get from the bits collected is the bit position of error

Hence we have the bit change in position 5 so re-change it to get the correct value.  Hence we change 5th bit of received message which is 1010001, we get 1010101 which is correct one.

So we see hamming code is able to detect and correct single error.

Categories
Binary Code

Parity bit relation with message bits

E.g.  Consider the parity bit Pand we have to find the position of message bits which we’ll cover with this parity bit.

Firstly write the binary equivalents of positions of message bit

Bit1        bit2       bit3        bit4        bit5        bit6        bit7

Parity    parity                    parity

P1                  P2             M1                P3           M2               M3          M4

 001          010         011          100         101         110         111

Now let’s see in the binary equivalent of position of parity bit Pthat at which position we have 1and we see 1 is at LSB so we select the message bits which have positions with 1 at LSB which are M1, Mand M4 So Pbit would check the parity for M1, Mand M4

E.g.  Consider the parity bit Pand we have to find the position of message bits which we’ll cover with this parity bit

We have 1 at second position from left so we choose message bits which have 1 at 2nd position n their position’s binary equivalent. Hence we get message bits MM3 and M4. So Pchecks parity for message bits of MM3 and M4

Similarly we have 1 at 3rd position of Pmessage bits with 1 at 3rd position are  M2MM4

So we now have

PChecks bit number 1,3,5,7

PChecks bit number 2,3,6,7

PChecks bit number 4,5,6,7

These parity bits can be either even or odd parity bits but all  parity bits must be same i.e. all odd or all even

Categories
Binary Code

Hamming code

This code is used for single error correction i.e. using this code we can detect only single error. In parity bit method we used only single extra bit but in this method number of extra bits (which also are parity bits) vary with the number of bits of the message.

Suppose we have the number of information bits as m=4 then we have to determine number of parity bits using above relation

2p >= 4 + p + 1

2p >= 5 + p

From this we can check for values of p, which one satisfies

For p=1                                 2 >= 6 doesn’t satisfy

For p=2                                 4>= 7 doesn’t satisfy

For p=3                                 8>=8 satisfies hence we have p=3

So now we have 4 information bits and 3 parity bits so total of 7 bits. In the parity bit method, we placed the parity bit at rightmost position. But here we don’t place the extra bits consecutively but the positions are fixed by following rule:

As we need only three positions so we have to pick first 3 which are 1, 2, and 4.

So we have the composition of hamming code as follow:

Bit1        bit2       bit3        bit4        bit5        bit6        bit7

Parity    parity                    parity

P1                  P2                  M1               P3                  M2               M3               M4

Now we have to decide positions in the hamming code which would be covered by the parity bit i.e. the positions considering which value of parity bit would be decided. We’ll be using following rule for this:

Categories
Binary Code

Parity Bit questions

Q1. Find out the parity bit (odd) for message 1100

As 1100 has 2 i.e. even number of 1’s so we take parity bit (odd) as 1 to make odd number of 1’s out of 5 bits

So message we send is 11001 (5th is the parity bit)

Q2. Find out the parity bit (even) for message 1100

As we have 2 i.e. even number of 1’s so we take parity bit (even) as 0 so that number of 1’s remain even. Hence the message is 11000 (5th is the parity bit)

Q3. Find out the parity bit (even) for message 1000

As we have 1 i.e. odd number of 1’s so we take parity bit (even) as 1 so that number of 1’s as even. Hence the message is 10001 (5th is the parity bit)

Categories
Binary Code

Error detection by Parity bit

Eg. Find out the parity bit (odd) for message 1101 and show us how it helps in detecting errors

As 1101 has 3 i.e. odd number of 1’s so P=0 so that we still have the odd number of 1’s in the combination of 5 bits(message(4 bits) and parity bit(1 bit))

So message we send with parity is 11010 (5th bit from left is parity bit)

Let’s now see the effect of errors on this message

1 error: Suppose we have error in 3rd bit from left so bit at 3rd position would change from 0 to 1. Hence message received would be 11110 instead of 11010 and at the receiver we check the parity of message and we see message has even number 1’s in the received signal which should have been odd so we have detected the error although we are not sure about the position of the error. So as error is detected we can make a request for another send of the same message.

2 errors: Suppose we have error at positions 1 and 4 from left so we have a bit change from 1 to 0 at 1st and 1 to 0 at 2nd position. We messaged received is 01000 and we have odd number of 1’s in received message which is also the parity status of sent message so no detection of errors so we can see this method is unable to detect even number of errors

3 errors: Suppose we have error in 2nd , 3rd and 4th bit from left so bit change at 2nd position is 1 to 0, at 3rd position would from 0 to 1 and at 4th from 1 to 0. Hence message received would be 10100 instead of 11010 and at the receiver we check the parity of message and we see message has even number 1’s in the received signal which should have been odd so we have detected the error although we are not sure about the positions of the error. So as error is detected we can make a request for another send of the same message.

So from here one can easily conclude that PARITY BIT method can detect only odd number of errors independent on whether we have odd parity message or even parity message.

Categories
Binary Code

Parity bit

A parity bit is an extra bit that is attached to the information that is being sent from one position to the other. This bit is attached just to detect the error if any in the information during the transmission.  This bit is used to make number of 1’s in the message or information either even or odd. So if there is any change in any bit during transmission then there would be change in number of 1’s hence error would change the number of 1’s from odd to even or even to odd which can be detected. This way parity bit helps to detects errors.  So whenever we need to send information we’ll pass the information firstly through PARITY GENERATOR CIRCUIT and then send. Also at the receiver end information received is passed trough the PARITY CHECK CIRCUIT and if parity matches, only then we use the information. If we make number of 1’s even then it is called even parity and if number of 1’s is made odd then it is called odd parity.

But there are few drawbacks attached with this method:

  1. This system can detect only odd combinations of error, not even combinations. That means if there is 2 or 4 or 6 etc number of then it would go undetected while it can easily detect 1, 3, 5 etc number of errors.
  2. We can not check the position of error even if we are able to detect it.
Categories
Binary Code

M out of N coding scheme And its efficiency

In this coding scheme we have N total number of bits and fixed M of those bits are 1s and N – M bits are 0s. Hence this scheme is called M out of N coding scheme. It is a type of Error-Detecting coding scheme as if during transmission we have any error in the message we can see that if number of 1s in the message is same. If they are not same then there is an error during transmission. Hence error is detected. 2 out of 5 codes is such an example

Biquinary code (2 out of 7) with weights as 5043210 is such an example.

5           0             4             3              2              1              0           Decimal equivalent

0              1              0              0              0              0            1                  0

0              1              0              0              0              1          0                  1

0              1              0              0              1              0             0                  2

0              1              0              1              0              0              0                  3

0              1              1              0              0              0              0                  4             

1              1              0              0              0              0              0                  5             

1              0              0              0              0              1              0                  6             

1              0              0              0              1              0              0                  7             

1              0              0              1              0              0              0                  8             

1              0              1              0              0              0              0                  9

Efficiency:           As we can represent only 10 digits using 7 bits while in binary representation we can represent 27 numbers. Hence

Efficiency = (10/ 128)*100 = 8% (approx.)

Categories
Binary Code

Gray Code

This is also called unit distance code or reflected code. This coding system has a property that there is only one bit change between consecutive gray codes. The following table would show gray codes of decimal values.

Binary to gray conversion:

Starting from right to left

  1. If it is MSB then place it as it is
  2. Otherwise, Add the bit to the previous bit and place the sum in GRAY, ignoring any carry
  3. Repeat step 2 till end

Eg.  Convert 1011 to gray

Gray to Binary conversion:

Starting from right to left  

  1. If it is MSB then place it as it is
  2. Otherwise, Add the bit to the previous than corresponding bit of GRAY code and place the sum in GRAY, ignoring any carry
  3. Repeat step 2 till end

Eg.  Convert 1110 to gray

Categories
Binary Code

Excess-3 Code

It is also known as XS-3. We add 310 or 1102 to the each 4-bit combination of BCD codes to get excess-3 codes. We can see the corresponding Excess-3 codes of each BCD number:

 Decimal Binary                   BCD                                        Excess-3

0          0000                       0000                                       0011

  1.         0001                       0001                                       0100
  2.         0010                       0010                                       0101
  3.         0011                       0011                                       0110
  4.         0100                       0100                                       0111
  5.         0101                       0101                                       1000
  6.         0110                       0110                                       1001
  7.         0111                       0111                                       1010
  8.         1000                       1000                                       1011
  9.         1001                       1001                                       1100
  10.         1010                       0001 0000                            0001 0011
  11.         1011                       0001 0001                            0001 0100
  12.         1100                       0001 0010                            0001 0101
  13.         1101                       0001 0011                            0001 0110
  14.         1110                       0001 0100                            0001 0111
  15.         1111                       0001 0101                            0001 1000