Data Communication

ERROR Detection
 ERROR Detection

 Error Detection
Error in bits during transmission from source to destination
 Solution
 Error detection using Parity Check, CRC and Checksum
 Correction using Hamming techniques and data flow
Introduction

 There are many reasons such as noise, cross-talk etc., which

may help data to get corrupted during transmission.

 Data-link layer uses some error control mechanism to ensure

that frames (data bit streams) are transmitted with certain
level of accuracy.
Types of errors may occurs

Single bit error one bit of data change from 1 to zero or zero to one

Multiple bit error: 2 or more non-consecutive bits of data changed

from 1 to zero or zero to one
Burst Error
Frame contains more than1 consecutive bits corrupted
Error Detection

Errors in the received frames are detected by some popular techniques for
error detection which are:

1. Simple Parity check

2. Two-dimensional Parity check
3. Checksum
4. Cyclic redundancy check

If the counter-check at receiver’ end fails, the bits are considered corrupted.
 Parity Check
One extra bit is sent along with the original bits to make number of 1s
either even in case of even parity, or odd in case of odd parity.
The sender while creating a frame counts the number of 1s in it.

For example, if even parity is used and number of 1s is even then one bit
with value 0 is added. This way number of 1s remains even. If the
number of 1s is odd, to make it even a bit with value 1 is added.
The receiver simply counts the number of 1s in a frame. If the count of 1s is
even and even parity is used, the frame is considered to be not-corrupted
and is accepted. If the count of 1s is odd and odd parity is used, the frame is
still not corrupted. The figure bellow makes the total number of 1’s even,
that is why it is called even parity checking
Two-dimensional Parity check

Parity check bits are calculated for each row, which is equivalent to a
simple parity check bit. Parity check bits are also calculated for all
columns, then both are sent along with the data. At the receiving end
these are compared with the parity bits calculated on the received data.
Checksum

 In checksum error detection scheme, the data is divided into k segments

each of m bits.
 In the sender’s end the segments are added using 1’s complement arithmetic
to get the sum. The sum is complemented to get the checksum.
 The checksum segment is sent along with the data segments.
 At the receiver’s end, all received segments are added using 1’s complement
arithmetic to get the sum. The sum is complemented.
 If the result is zero, the received data is accepted; otherwise discarded.
 Use checksum to validate at the receiver the data
10011001 11100010 00100100 10000100
 Use checksum to validate the word ”test”
 Checksum value of 1001001110010011 and 1001100001001101 of 16 bit
segment
 Hamming code for detect and
correct bit errors 2

15
 General Algorithm of Hamming code

The Hamming Code is simply the use of extra parity bits to allow the identification of an error.
 Write the bit positions starting from 1 2 3 4 6 7 … etc.
 All the bit positions that are a power of 2 are marked as parity bits 20 21 22 23 24 (1, 2, 4, 8, etc).
 All the other bit positions are marked as data bits.
 Each data bit is included in a unique set of parity bits, as determined its bit position in binary form.
a. Parity bit 1 covers all the bits positions whose binary representation includes a 1 in the least
significant position (‫( )اول رقم يمين‬1, (3, 5, 7, 9, 11, etc).
b. Parity bit 2 covers all the bits positions whose binary representation includes a 1 in the second
position from the least significant bit ( 1 ‫(الرقم التانى من اليمين يكون‬2, (3, 6, 7, 10, 11, etc).
c. Parity bit 4 covers all the bits positions whose binary representation includes a 1 in the third
position from the least significant bit (4,(5–7, 12–15, 20–23, etc).
d. Parity bit 8 covers all the bits positions whose binary representation includes a 1 in the fourth
position from the least significant bit bits (8(9–15, 24–31, 40–47,etc)
 Since we check for even parity,
 set a parity bit to 1 if the total number of ones in the positions it checks is odd.
 Set a parity bit to 0 if the total number of ones in the positions it checks is even
 Example

 These redundancy bits are placed at the positions which correspond to the
power of 2.
As in the example:
 The number of data bits = 7 n number of bits, p number of parity bit
 2p>=n+p+1
 The number of parity bits = 4 not 3 because if 3 the bit 8 not examined
 The total number of bits = 11
 Suppose the data to be transmitted is 1011001, the bits will be placed as follows:
 Determining the Parity bits

R1 bit is calculated using parity check at all the bits positions whose binary
representation includes a 1 in the least significant position.
R1(p1): bits 1, (3, 5, 7, 9, 11)

Then bit R1 = 0 , Since the total number of 1’s in all the bit positions corresponding to R1 is an even
 R2 bit is calculated using parity check at all the bits positions whose binary representation
includes a 1 in the second position from the least significant bit.R2: bits 2,(3,6,7,10,11)

Since the total number of 1’s in all the bit positions corresponding to R2 is an odd number the value of
R2(parity bit’s value)=1
 R4 bit is calculated using parity check at all the bits positions whose binary representation
includes a 1 in the third position from the least significant bit.R4: bits 4, (5, 6, 7)

Since the total number of 1’s in all the bit positions corresponding to R4 is an odd number the value of
R4(parity bit’s value) = 1
R8 bit is calculated using parity check at all the bits positions whose binary representation includes a
1 in the fourth position from the least significant bit.R8: bit 8,(9,10,11)

Since the total number of 1’s in all the bit positions corresponding to R8 is an even number the
value of R8(parity bit’s value)=0.
Thus, the data transferred is:
Example of Hamming Code
 Error detection and correction using 7 bits
hamming code

Eample 2 : 7 bits hamming code (3 parity bits + 4 data bits) d7 d6 d5 p4 d3 P2 P1

Solu: data is received (word 1011011) 1 0 1 1 0 1 1
1010 data
Which bits are parity bits 20 21 22 which are 1,2,4
Example: data is received (word 1011011)
p1 check one scape one , then it responsible for 1,3,5,7 (p1,d3,d5,d7) 1011 the number of 1s is odd
then p1= 1, it means error exist
p2 check 2 which are 2,3 and scape two 4,5 check 6,7 then it responsible for 2,3,6,7( d3,d6,d7 ) 1001 the
number of 1s is even then p2= 0 (no error)
p4 responsible for d5,d6,d7 1101 odd parity then p4 = 1 (error exist)
To correct errors: p4 p2 p1 is 101 convert to decimal = 5 then the bit position 5th is the error bit then it replaced
from 1 to 0
Then the correct word is 1001011