close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Error
DETECTION
&
CORRECTION
Detection in oral communication
No, UCLA
won today
Receiver
Sender
No, you see
LA won today
In verbal communication we use the most likely
interpretation and only question when there seem
to be ambiguities or inconsistencies.
Detection in data communication
Program
Sender
Receiver
Even a single bit in error can result in
•loading from the wrong address
•storing in the wrong address
•executing the wrong op code
•using the wrong data value
“All” Errors must be detected
• Detection is probabilistic.
• We’ll never detect ALL errors, only
optimize the likelihood of detecting it.
• Our focus is on techniques which detect
communications-type errors with the
highest probability.
• Correction will follow. Focus on detection.
Parity
Databits
___
1 ___
0 ___
1 ___
0 ___
0 ___
0 ___
1 ___
0
Parity
___
•Count the number of 1s.
•For EVEN (ODD) parity, set the parity bit to either
1 or 0 to have the total number of 1s EVEN
(ODD).E.g. for EVEN parity:
___
1 ___
0 ___
1 ___
0 ___
0 ___
0 ___
1 ___
0
___
1
___
1 ___
0 ___
1 ___
1 ___
1 ___
1 ___
1 ___
0
___
0
Detection with parity
___
1 ___
0 ___
1 ___
0 ___
0 ___
0 ___
1 ___
0
___
1
Sender
transmits
___
1
Receiver
gets
Error Occurs
___
1 ___
0 ___
0 ___
0 ___
0 ___
0 ___
1 ___
0
Receiver calculates parity. Should be 0! Is 1! … ERROR
No method to determine WHICH bit is in error.
But ONLY NEED TO DETECT.
Double Errors with parity
___
1 ___
0 ___
1 ___
0 ___
0 ___
0 ___
1 ___
0
___
1
Sender
transmits
___
1
Receiver
gets
Error Occurs
___
1 ___
0 ___
0 ___
0 ___
0 ___
0 ___
1 ___
1
Receiver calculates parity. Should be 1! Is 1! …
ERROR NOT DETETED.
This is a PROBLEM!
So is parity useful?
• Probability
– If two events (E1, E2) are independent of one
another, probability of simultaneous occurrence
is P(E1) * P(E2).
– P(single bit error) = P(S) = 10-6,
• P(two bits in error)= P(S)*P(S) = 10-12
• If two bit errors are independent.
• Parity is useful when bit errors are not
independent.
A PROBLEM!
• This is NOT typically true in
communications environments.
One more important concern!
• Communications errors are BURSTY.
• This means that neighboring bits are
affected by each other and the independence
assumption is invalid.
___
1 ___
0 ___
1 ___
0 ___
0 ___
0 ___
1 ___
0
___
1
___
1 ___
0 ___
1 ___
1 ___
1 ___
1 ___
1 ___
0
___
1
A similar approach
1 0
1
0
0
0
1
0
1
1
1
1
0
1
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
1
0
1
0 1
1
0
0
0
0
0
0
Vertical Parity
Catches MORE errors but still misses this one.
CRC Codes
•
•
•
•
•
More complicated to calculate.
Good at detecting bursty errors.
Not intuitive.
Standard and well-known codes.
Uses a “binary” arithmetic technique
Representing a polynomial
in binary
x  x  x 1
6
4
IS
1x  0 x  1x  0 x  0 x  1x  1x
6
5
4
3
2
1
WHICH CAN BE VIEWED AS
1
0
1
0
0
1
1
0
A few new operations
ADDITION
(No carry)
same as subtraction
1101010
1001000
0100010
Division
(Will it divide?)
0100010
0100011
YES
1100010
0100011
NO
1100010
YES
1100011
easy
easy
not easy
Will divide if the same length!
Put together for division
1000010
100010
100011000000
100010
100000
100010
Remainder
0000100
Relating this to CRC
• A special polynomial named the
GENERATOR is used as the divisor.
• The message appended parity bits are the
dividend
• Initially the parity bits are all zero.
• After calculating the remainder(CRC), replace
the parity bits with the remainder.
Example message
Generator
100010
Message
1000110
PARITY
00000
Parity will be replaced
with remainder.
Remainder always ONE
less that length of Generator.
(initially)
100010
Remainder
100011000000
…...
…...
100
(same problem)
100011000100
Message Transmitted
OldMessage+NewParity
Receiver checks CRC
1000010
100010
100011000100
100010
100010
100010
Remainder
0
0 remainder indicates no error detected.
Message is extracted and forwarded!
Received message
1000110
Summary
Use generator and message to determine CRC
Generator
Message
Zeros
…….
…….
Remainder
Append Remainder(CRC) to message and transmit.
Message
Remainder
Receiver calculates remainder. Expects 0.
Generator
Message
Remainder
0
ACCEPT
IF 0
CRC detection of errors
• Remember that CRC finds bursty (and other
types of) errors with high probability.
• Although it is not obvious, this is also easy
to calculate. … IMPORTANT not to slow
the communication process.
• We’ll see how to CORRECT later.
1/--страниц
Пожаловаться на содержимое документа