Error Detection and Correction

1
transmission For reliable

Data can be corrupted during transmission.
communication, errors must be detected and corrected.
Types of errors :
Single
g Bit Error : onlyy one bit of a g
given data unit ((such as
byte, character, data unit, or packet) is
changed from 1 to 0 or from 0 to 1.
example
Data sent
00000010
ASCII STX
Received
00001010
The bit error is

very rare in
serial
transmission
ASCII LF
2
Burst Error : two or more bits in the data unit have change
from 1 to 0 or from 0 to 1.
Example
Sent
Length of
burst
b t
error (5
bits)
0100010001000011
0101110101000011
Received
The length of burst is measured from the first to the last

corrupted bit.
Burs error is most likely to occur in a serial transmission
transmission.
The duration of noise normally longer than the duration of
one bit.
Detection
Error detection is the first step in the error correction
process.
Redundancy
One error detection mechanism would be to send every
data unit twice.
The receiving device would be then be able to do a bitfor-bit comparison between the two version of the data.
A
Any discrepancy
di
would
ld iindicate
di t an error, and
d an
appropriate correction mechanism could be set in place
Redundancy
Error detection uses the concept of redundancy, which
means adding extra bits for detecting errors at the
destination.
Three types of redundancy cheeks are common in

data communications :
Detection Methods
Parity check
CRC
Checksum
Parity Check
This is the most common and least expensive mechanism
for error detection.
detection
Simple Parity Check
Two
T
dimensional
di
i
lP
Parity
it Ch
Check
k
A redundant bit is added to every data unit so that the total
number of 1in
1 in the unit (including the parity bit) becomes
even (or add).
A parity bit
Simple Parity Check
(even-parity)
8
Example :
Suppose the sender wants to send the word WORLD. In ASCII
the five character are coded as :
1110111 1101111 1110010 1101100 1100100
W
Each of the first four character has an even number of 1s, so

th parity
the
it bit iis a 0
0. Th
The llastt character
h
t (d)
(d), h
however h
has th
three
1s (an odd number), so the parity bit is a 1 to make the total
number of 1s even. The following shows the actual bit sent (the
parity
it bit
bits are underlined).
d li d)
11101110 11011110 11100100 11011000 11001001
9
Performance :
Simple parity check can detect all single-bit errors.

It can detect burst errors only if the total number in each
data unit is odd.
10
Two-Dimensional Parity Check

In two-dimensional parity check, a block of bits is divided into
rows and a redundant row of bits is added to the whole block.
11
Example :
Suppose the following block is sent :
10101001 00111001 11011101 11100111 10101010
However, it is hit by a burst noise of length 8, and some bit are
corrupted.
10100011 10001001 11011101 11100111 10101010
When the receiver checks the parity bits, some of the bits do not
follow the even-parity rule and the whole block is discarded (the
nonmatching
t hi bit
bits are shown
h
iin b
bold
ld
10100011 10001001 11011101 11100111 10101010
parity bit
12
Performance :
Two dimension parity check increase the likelihood of detecting
burst errors.
A burst error of more than n bits is also detected by this method
with a very high probability.
If 2 bits in one data unit are damaged and two bits in exactly the
same positions in another data unit are also damaged, the
checker will not detect the error. For example, if two data units :
11110000 and 11000011. If the receiver receive 01110001 and
01000010, the error cannot be detected.
13
Cyclic Redundancy Check (CRC)

Invented by Peterson [1961].
y field theory.
y
It is a p
powerful method backed by
Each code is considered as a polynomial with coefficients 0
or 1.
Example: 10011010 is M(x)=x7+x4+x3+x1
Select a k-bit code and a divisor polynomial
Example k=3, code 111, C(x)= x3+x2+x1
The
Th idea
id iis tto always
l
ttransmit
it a polynomial
l
i l P(
P(x)) which
hi h iis exactly
tl
divisible by C(x).
On the receiving end P(x)+E(x); (E(x) is error will be received and
di id d b
divided
by C(
C(x).
)
The result will be zero if there is no error or the error E(x) is also
divisible by C(x).
14
Problems :
How
to compute P(x) from M(x)

and C(x)?
How to make sure that E(x) is not
divisible by C(X)?
15
How to Compute P(x)?

HowtoComputeP(x)?
Usethesimplemathematics.
MultiplyM(X)by100(kbitshift)getN(x).
M l i l M(X)b (k bi hif ) N( )
DividethemultipliedvalueN(x)byC(x).
Computereminder.SubtractthereminderfromN(x).
Computereminder SubtractthereminderfromN(x)
Forapolynomialwith,1/0coefficientstheaddition
Forapolynomialwith,1/0coefficientstheaddition
andsubtractionisjustEXORoperation.
Multiplicationissimplyleftshift.
16
Example
P(x)
P( ) ?
?
C(x) ?
( ) ?
N(X)
17
Example(divide)
18
Example (divide)
19
Final Code
Reminder: 1110
20
Tugas : Dikerjakan Kelompok di kumpulkan hari ini Rabu, 30 4

2014 di administrasi Jurusan TE.
A. PelajariSlidediatasdandiskusikandengankelompoknya,
berikancatatanpertanyaan
berikancatatanpertanyaanpertanyaanbilaadabagian
pertanyaanbilaadabagian
yangtidakdipahami!
B. Kerjakansoalsoalberikut:
1.
2.
3.
4.
Dapatkanderetanbityangdihasilkan,apabiladeretanbit
01001001 diprosespadapengkodeanevenparitycheck!
DapatkanderetanbitoutputdariprosespengkodeanTwo
DimensionalParityCheckbiladeretanbitinputnyaadalah:
0011010100100110101100101001
SebuahpengkodeanCRCdenganGenerator10110,bilainformasi
yangdiinputkanpadasistemadalah1101001100,dapatkanderetan
bitoutputdarisistemCRCtersebut!
ApakahkelebihandankekuranganantaraPengkodeanEvenParity
Check,TwoDimensionalParityCheckdanCRC?
21

Error Detection and Correction

Uploaded by

Copyright:

Available Formats

Error Detection and Correction

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Error Detection and Correction

Uploaded by

Copyright:

Available Formats

1

transmission For reliable

The bit error is

The length of burst is measured from the first to the last

Three types of redundancy cheeks are common in

Each of the first four character has an even number of 1s, so

Simple parity check can detect all single-bit errors.

Two-Dimensional Parity Check

Cyclic Redundancy Check (CRC)

to compute P(x) from M(x)

How to Compute P(x)?

Tugas : Dikerjakan Kelompok di kumpulkan hari ini Rabu, 30 4

You might also like