Transcript Ch. 6

Ch. 6 Error Detection and
Correction
By William Stallings (Tenth Edition)
6.1 Types of Errors
• An error occurs when a bit is altered.
• A single bit error is an isolated error.
• Error Burst—a group of bits in which two
successive erroneous bits are always separated
by less than a given number x of correct bits.
• See Figure 6.1.
6.2 Error Detection
• Probabilities of Error Types
–
–
–
–
Pb: Probability of a single bit error (BER).
P1: A frame arrives with no bit errors
P2: A frame arrives with some undetected bit errors.
P3: A frame arrives with some detected bit errors.
• Assume that no parity is sent (P3=0):
– P1 = (1-Pb) ^F, where F is the frame size.
– P2 = 1 - P1
• Example: If Pb or F is "large" then P2 could
become a problem.
• Fig. 6.3--The error detection process.
6.3 Parity Checks
• Parity Check—See Figure 6.3
– The simplest scheme.
– Even number of errors is undetectable.
• Cyclic Redundancy Check (CRC)
– Very powerful and often used.
– Given k message bits, n "check" bits are
generated.
– k+n bits are transmitted together.
6.5 Cyclic Redundancy CheckCRC
• Modulo 2 Arithmetic
– Binary addition without carries (exclusive or
operation.)
• The simple view is to consider variable,
binary strings:
–
–
–
–
D-- data or message (k-bits)
F--frame check sequence (n-k bits)
P--pattern of n-k+1 bits
T--transmitted frame (n bits)
6.5 CRC (cont.)
• Consider the following three step process:
– STEP 1: Multiply D by 2n-k.
• n-k 0's will be shifted in, from the right.
– STEP 2: Divide by P
• This will produce a quotient and a remainder.
• The quotient (Q) will not be used, but the remainder (R)
is used as F.
– STEP 3: Add R to the shifted version of D to
produce T.
• R replaces the n 0's that were added to D.
• T will be transmitted.
6.5 CRC
• Why does this work?
– We are looking for something that is evenly
divisible by P.
– T/P =(D2n-k +R)/P = (D2n-k/P) + R/P
=Q+R/P+ R/P.
– But R/P + R/P =0, because of modulo 2
arithmetic.
– Hence T/P=Q which is evenly divisible by P
(remainder is 0).
– Example 6.6--page 195.
6.5 CRC(cont.)
• Suppose that bit errors are possible during
transmission.
– Model the error pattern (E) as a binary string with a
1 in the position of a bit that has been received
incorrectly.
– Received frame: Tr = T + E.
– Divide by P: Tr/P = T/P + E/P= Q + E/P
– If the remainder is 0, then assume E=0.
– If P is chosen properly, very few error patterns will
be evenly divisible by P (i.e. have a remainder of 0)
and very few undetected errors will occur.
6.5 CRC
• Polynomials (Example 6.7 and Fig. 6.5)
– The CRC process can be viewed as binary
polynomials of X.
– The coefficients of the polynomials correspond to
the previously defined bit-string variables.
– Arithmetic operations use modulo-2 (this makes
it an "algebra.")
• Generating Polynomials
– Carefully chosen polynomials can allow the
detection of many types of errors(p.193).
– Ex: CRC-12, CRC-16, CRC-CCITT, CRC-32.
6.5 CRC
• CRCs can be generated using hardware
(See Fig. 6.6 and 6.7 and Example 6.8).
– Basic components:
• D Type flip-flops (or J-K Equivalents)-- one
for each CRC bit.
• Exclusive OR gates (or equivalents)
– Operation:
• Flip-Flops are initialized to 0.
• Message bits are clocked into the circuit.
6.6 Error Correction
• Fig. 6.8 Error Correction Process
– k bits are “mapped” into n bit block.
– Result is called a codeword.
– Example 6.7--Forward Error Correction
– (n-k)/k is called the redundancy.
– k/n is called the code rate.
• Fig. 6.9 How Coding Improves System
Performance
Appendix G: Interfacing
(Fig.G.1)
th
• DTE--Data Terminal Equipment (not in 8
Edition)
– Equipment consisting of digital end instruments that
convert the user information into data signals for
transmission, or reconvert the received data signals into
user information.
• DCE--Data Circuit-terminating Equipment
– In a data station, the equipment that provides the signal
conversion and coding between the data terminal
equipment (DTE) and the line.
– DCE may be separate equipment or an integral part of the
DTE or intermediate equipment.
G.1 Interfacing (cont.)
• Interchange Circuits
– The connection between the DTE and DCE.
• Standards--Physical Layer of the OSI Model
– V.24/EIA-232-F (RS-232--1962)
– X.21--15 wire interface for public switched
network interfacing.
– ISDN Physical Interface (8 wire interface).
G.1 Four Characteristics
• Mechanical
– Pertain to the actual physical connection of the
DTE and DCE (the terminator plugs and sockets).
• Electrical
– The voltage levels and timing of voltage changes.
• Functional
– The functions performed by various interchange
circuits: data, control, timing and ground.
• Procedural
– The sequence of events for transmitting data.
G.1 EIA-232-F
• Mechanical (ISO 2110)
– DB-25 connector (a 25 pin connector)
– Fig. G.2.
• Electrical(V.28)
–
–
–
–
Digital signaling; up to 20 kbps; up to 15m.
Logic 1 and OFF : less than -3 volts
Logic 0 and ON : greater than +3 volts
And more (C, R, short circuit current, max
voltages, slew rate, etc.)
G.1 EIA-232-F (p.2)
• Functional (V.24)
– Table G-1--Interchange Circuits
• Procedural (V.24)
– Fig. G.4
G.1 Loopback Testing
• EIA-232-F control circuits assist in
loopback testing and fault isolation.
– Local loopback tests are used to check the
functioning of the local interface and the local
DCE.
– Remote loopback tests are used to check the
transmission channel and the remote DCE.
• Figure G.3 Local and remote loopback.
G.1 The Null Modem
• Used to connect two DTEs directly (no
DCEs used).
• It is not a real modem, but simply a cable
that rewires the circuits to trick the DTEs
into thinking that they are talking with
DCEs.
• Fig. G.5 illustrates the null modem wiring.
G.2 ISDN Physical Interface
• X.21--15 pin connection for digital interface
to public switched networks.
• ISDN--ISO 8877 specifies an 8 pin
connector.
• The reduction of interface circuits forced
greater complexity in the logic circuits at
each end of the cable, but integrated circuits
have become cheap whereas wire remains
relatively expensive.
• Fig. G.6 shows the ISDN Interface.