ata Communication Networks (U19EC30

Session by
Dr/L.RAJA, ASP/ECE

1
cussion about the previous sessions

• Address Resolution Protocol

(ARP)
• Communication example
• Error Detection
• Error Correction

2
Agenda of the session

• Error Detection
• Parity Check
• Checksum
• Cyclic Redundancy check

3
Error Detection
If the following two conditions are met, receiver can detect a change
in original codeword.

1. The receiver has (or can find) a list of valid code words.

2. The original codeword has changed to an invalid one.

Types –
 Parity Check
 Checksum
 Cyclic Redundancy
Check(CRC)
4
 Parity Check

 Parity bit - Redundant bit – Added to every data unit

 Total number of 1’s in data unit becomes odd or even

 Two Dimensional Parity

 simple one dimensional parity - adding one extra bit to 7 bit

code to form a byte

A simple parity-check code is a single-bit error-

detecting 5
 Parity Check
 Parity computed for each row – vertical redundancy Check

 Parity computed for each column – Longitudinal redundancy Check

 Both redundancy check adds extra parity byte for entire frame in
addition to parity bit
for each computes
 Receiver byte row and column parities for data bits.

 If all parity bits and byte matches, frame is accepted else

discarded

 2D parity catches 1,2,3 bit and most 4 bit errors

6
Parity Check Code
 Familiar Error detecting code – simple parity

check code

 Linear Block code

 K bit data word changed to n bit code word (n

parity-check code with k = 4=k+1)

and n = 5

 Extra bit (parity bit) added to make total number

of 1’s even

7
ncoder and decoder for simple parity-check code

r0 = a3+ a2 + a1+ a0 (modulo-2)

If number of 1s is even, result

is 0;
If number of 1s is odd, result
is 1

 Encoder takes copy of data word (a0,a1,a2,a3) and generates

parity bit (r0)
 dataword bits and the parity bit create the 5-bit codeword
 parity bit is added, makes number of 1s in codeword as 8
ncoder and decoder for simple parity-check code

 Sender sends code words - during transmission, it may be

corrupted
 Receiver receives 5 bit word.
 Checker at receiver does same thing as sender with one
exception
 Addition is performed over all 5 bits called syndrome (one
bit)
 Syndrome - 0 -when received code word – even
 Syndrome – 1 – when received code word – odd
 Syndrome (s0) = b3+b2+b1+b0+q0 9
 Example
Look at some transmission scenarios. Assume the sender sends the data
word 1011. The codeword created from this data word is 10111, which is sent
to the receiver. Examine five cases:

10
 2D Parity Check
 Better Approach – Two dimensional parity check

 Here , data word – organized in a table (rows, columns)

 Five 7 bit bytes put in separate rows

 For each row and column one parity check bit is calculated

 Two dimensional parity check can detect upto three errors that occur
anywhere in table

 Arrow head pointing locations indicate non zero syndrome

 Errors affecting four bits may be detected

A simple parity-check code can detect an odd 11
number of errors
2D Parity Check

12
2D Parity Check

13
 Checksum
 Another error detection method is called checksum.

 checksum is used in Internet by several protocols although

not at DLL

 Checksum – based on concept of redundancy

Tendancy - Checksum is used to replace CRC

CRC is used in layers other than DLL

14
 Checksum -Example
Suppose our data is a list of five 4-bit numbers that we want to
send to a destination. In addition to sending these numbers,
send the sum of the numbers.
For example, if the set of numbers is (7, 11, 12, 0, 6)
send (7, 11, 12, 0, 6, 36), where 36 is the sum of the original
numbers.

 Receiver adds five numbers and compares the result with

sum.
 If the two are same, receiver assumes no error
 Accepts the five numbers, and discards the sum.
 Otherwise, there is an error somewhere and data are 15not
 Checksum
To make the job of the receiver easier, send the negative
(complement) of the sum, called the checksum. In this case,
send (7, 11, 12, 0, 6, −36). The receiver can add all the
numbers received (including the checksum).
If the result is 0, it assumes no error; otherwise, there is an
error.
Drawback of previous example

All data is represented as 4-bit word (<15) except

checksum

Solution – 1’s complement

16
 Checksum - Example
How can we represent the number 21 in one’s complement
arithmetic using only four bits?

Solution

The number 21 in binary is 10101 (it needs five bits).

 wrap the leftmost bit and add it to the four rightmost

bits.

 (0101 + 1) = 0110 or 6. 17
 Checksum - Example
How can we represent the number −6 in one’s complement
arithmetic using only four bits?
Solution
In one’s complement arithmetic, the negative or complement of a number
is found by inverting all bits. Positive 6 is 0110; negative 6 is 1001.

If we consider only unsigned numbers, this is 9.

In other words, the complement of 6 is 9.

Another way to find the complement of a number in one’s complement

arithmetic is to subtract the number from 2n − 1 (16 − 1 in this case). 15-
6=9
18
Checksum

19
 Checksum

Sender site :
1. The message is divided into 16-bit words.
2. The value of the checksum word is set to 0.
3. All words including the checksum are
added using one’s complement addition.
4. The sum is complemented and becomes the
checksum.
5. The checksum is sent with the data. 20
 Checksum
Receiver site:

1. The message (including checksum) is divided into 16-bit

words.

2. All words are added using one’s complement addition.

3. The sum is complemented and becomes the new

checksum.
21
 Cyclic Codes

 Cyclic codes are special linear block codes with one extra property.

 In a cyclic code, codeword is cyclically shifted (rotated), the result is

another codeword.

 For example, if 1011000 is a codeword

cyclically left-shift, then 0110001 is also a codeword.

22
Cyclic Redundancy Check

 Cyclic codes are used to correct errors.

 codes are used for error detection and encoding
 CRC is subset of cyclic codes used in networks such as
LANs and WANs.

23
 CRC- Encoder and Decoder
In the encoder,
 Dataword has k bits (4 here)
 Codeword has n bits (7 here)
 Size of dataword is
augmented by
adding n − k (3 here) 0s to
right-
hand side of the word.
 n-bit result is fed into
generator.
 Generator uses a divisor of
size
n − k + 1 (4 here),
predefined.
 Generator divides the
 Decoder receives codeword (possibly corrupted in transition). augmented
 A copy of all n bits is fed to checker, which is a replica of generator.dataword by the divisor
 Remainder produced by the checker is a syndrome of n − k (modulo-2 (3 here) bits, which is fed to
decision logic analyzer. division).
 Analyzer has a simple function. If the syndrome bits are all 0s, 4leftmost
Quotientbitsof
ofdivision is24
the codeword
Division in CRC encoder

25
vision in the CRC decoder for two cases

26
Cyclic Redundancy Check

27
Advantages - CRC

 cyclic codes have a very good performance in

detecting
 single-bit errors,
 double errors,
 odd number of errors,
 burst errors.
 Easily be implemented in hardware and software.
 They are especially fast when implemented in28
 Quiz/Activity/Q&A
How error detection and correction is The ________ of errors is more difficult than _____
done? A Correction, Detection
a) By passing it through equalizer B Detection, Correction
b) By passing it through filter C creation, correction
c) By amplifying it D creation, Detection
d) By adding redundancy bits

Which can detect two bit errors? A simple parity check code can detect
a) Parity check _____ errors
b) Cyclic redundancy check a.Even number of errors
c) Parity & Cyclic redundancy check b.Two
d) None of the mentioned c.Odd number of errors
d. no errors

29
Session Handler Details
(Dr. L.RAJA)
ASP/ECE
[email protected]

30