Chapter – Error Detection and Correction

Error Detection and Correction

 Errors are inevitable (unavoidable)
 Interference
 Corruption as a result of transmission
 Reliable communication is dependent on being
able to detect and correct errors
 How will we know an error occurred?
 Do we retransmit or correct?

2
Types of Errors

 Single-bit error
 Burst error

3
Single-bit Errors
 Only one bit is changed: 0 changed to 1, or a 1 to a 0
 Least likely type of error since noise usually lasts longer
than the time to send one bit
 More likely in parallel transmission

4
Burst Errors
 Two or more bits in data unit are in error, not necessarily
consecutive in order
 Most likely in serial transmission
 Number of bits affected depend on data rate and noise
duration

5
Detection

 Need to detect before message is processed

 Redundancy may be used to add additional bits
to a message for error control
 Process must be handled by destination

6
Redundancy

7
Detection Methods

 Parity Check
 Cyclical Redundancy Check (CRC)
 Checksum
 Parity and CRC are performed by data link layer;
checksum performed by higher-layer protocols

8
Parity Check

 Most common and least expensive

 In even-parity, a redundant bit (parity bit) is
appended to every data unit so total number of 1
bits is even; odd-parity – total should be odd

9
Even-parity Check

10
Example 1
Suppose the sender wants to send the word world. In
ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000 11001001

11
Example 2
Now suppose the word world in Example 1 is received by
the receiver without being corrupted in transmission.
11101110 11011110 11100100 11011000
11001001
The receiver counts the 1s in each character and comes up
with even numbers (6, 6, 4, 4, 4). The data are accepted.

12
Example 3
Now suppose the word world in Example 1 is corrupted
during transmission.
11111110 11011110 11101100 11011000
11001001
The receiver counts the 1s in each character and comes up
with even and odd numbers (7, 6, 5, 4, 4). The receiver
knows that the data are corrupted, discards them, and asks
for retransmission.

13
Simple Parity Performance

 Can detect all single-bit errors

 May detect all burst errors as long as total
number of bits changed is odd
 Cannot detect errors when total number of bits
changed is even since parity check will pass even
though errors had occurred

14
Two-Dimensional Parity Check

 Data unit is divided into rows and columns;

parity checks are performed on
corresponding bits of each column

15
Two-Dimensional Parity

16
Two-Dimensional Parity Performance
 Increases likelihood of detecting burst errors

 Block parity character is also known as the

“Longitudinal Redundancy Check” (LRC)
character.LRC of n bits can easily detect a burst
error of n bits

 Cannot detect errors when two bits in one data

unit are damaged and two bits in exactly the
same positions in another data unit are damaged
17
Cyclic Redundancy Check (CRC)

 Parity checks based on addition; CRC based on

binary division
 A sequence of redundant bits (a CRC or CRC
remainder) is appended to the end of the data
unit
 These bits are later used in calculations to detect
whether or not an error had occurred

18
CRC Steps
 On sender’s end, data unit is divided by a
predetermined divisor; remainder is the CRC
 When appended to the data unit, it should be
exactly divisible by a second predetermined
binary number
 At receiver’s end, data stream is divided by same
number
 If no remainder, data unit is assumed to be error-
free

19
Deriving the CRC

 A string of 0s is appended to the data unit; n is

one less than number of bits in predetermined
divisor
 New data unit is divided by the divisor using
binary division; remainder is CRC
 CRC of n bits replaces appended 0s at end of
data unit

20
CRC Generator and Checker

21
CRC Generator
 Uses modulo-2 division
 Resulting remainder is the
CRC

22
CRC Checker
 Performed by receiver
 Data is appended with
CRC
 Same modulo-2 division
 If remainder is 0, data are
accepted
 Otherwise, an error has
occurred

23
Polynomials
 Used to represent CRC generator
 Cost effective method for performing calculations quickly

24
CRC Performance

 Can detect all burst errors affecting an odd

number of bits
 Can detect all burst errors of length less than or
equal to degree of polynomial

25
Checksum

 Performed by higher-layer protocols

 Also based on concept of redundancy

26
Checksum Generator

 At sender, checksum generator subdivides data

unit into k equal segments of n bits
 Segments are added together using one’s
complement arithmetic to get the sum
 Sum is complemented and becomes the
checksum, appended to the end of the data

27
Checksum

28
Checksum Checker

 Receiver subdivides data unit in k sections of n

bits
 Sections are added together using one’s
complement to get the sum
 Sum is complemented
 If result is zero, data are accepted; otherwise,
rejected

29
Performance

 Detects all errors involving odd number of bits,

most errors involving even number of bits
 Since checksum retains all carries, errors
affecting an even number of bits would still
change the value of the next higher column and
the error would be detected
 If a bit inversion is balanced by an opposite bit
inversion, the error is invisible

30
10.3 Error Correction

 Requires more redundancy bits; must know not

only that an error had occurred, but where the
error occurred in order to correct it
 Correction simply involves flipping the bit
 Hamming code may be applied to identify
location where error occurred by strategically
placed redundancy bits

31
Redundancy Bits

32
Example Hamming Code

 For a seven-bit data sequence

r1: bits 1, 3, 5, 7, 9, 11
r2: bits 2, 3, 6, 7, 10, 11
r3: bits 4, 5, 6, 7
r4: bits 8, 9, 10, 11

33
Example Hamming Code

34
Error Detection using Hamming Code

35
Burst Error Correction

 By rearranging the order of bit transmission of the

data units, the Hamming code can correct burst
errors
 Organize N units in a column and send first bit of
each, followed by second bit of each, and so on
 Hamming scheme then allows us to correct
corrupted bit in each unit

36
Burst Error Correction Example

37
Coming Up… Chapter 11
 Data Link Control and Protocols
 Flow Control
 Error Control
 Protocols

38
Credits

 All figures obtained from publisher-provided

instructor downloads
Data Communications and Networking, 3rd edition by
Behrouz A. Forouzan. McGraw Hill Publishing, 2004

39