Unit 4

Error Detection and Correction, Data

Communications Equipment
Types of Errors
• Whenever bits flow from one point to another, they are
subject to unpredictable changes because of interference.

• This interference can change the shape of the signal.

• Two types:
• Single-bit error
• Burst error
 Single bit error

• In a single-bit error, only 1 bit in the data unit has changed.

• Single-bit errors are the least likely type of error in serial data
transmission.
• Imagine data sent at 1 Mbps. This means that each bit lasts only
1/1,000,000 s, or 1 μs.
• For a single-bit error to occur, the noise must have a duration of
only 1 μs, which is very rare; noise normally lasts much longer
than this.
7.3
Burst Error
• A burst error means that 2 or more bits in the data unit have changed.
• A burst error is more likely to occur than a single-bit error.
• The duration of noise is normally longer than the duration of 1 bit, which
means that when noise affects data, it affects a set of bits.
• The number of bits affected depends on the data rate and duration of
noise.
Redundancy
• The central concept in detecting or correcting errors is
redundancy.
• To detect or correct errors, we need to send extra
(redundant) bits with data.
• These redundant bits are added by the sender and removed
by the receiver.
• Their presence allows the receiver to detect or correct
corrupted bits.
Detection Vs Correction
• The correction of errors is more difficult than the detection.
• In error detection, we are not even interested in the number of
errors. A single-bit error is the same for us as a burst error.
• In error correction, we need to know the exact number of bits
that are corrupted and more importantly, their location in the
message. The number of the errors and the size of the message
are important factors.
• If we need to correct one single error in an 8-bit data unit, we
need to consider eight possible error locations; if we need to
correct two errors in a data unit of the same size, we need to
consider 28 possibilities.
Forward Error Correction and Retransmission
• Two main methods of error correction:
1. Forward error correction (FEC):
The process in which the receiver tries to guess the
message by using redundant bits.

2. Retransmission:
A technique in which the receiver detects the occurrence
of an error and asks the sender to resend the message.
Note: Use FEC if the number of errors is small.
 Modular Arithmetic
• In modular arithmetic, we use only a limited range of integers.
We define an upper limit, called a modulus N. We then use
only the integers 0 to N - 1.
• For example, if the modulus is 12, we use only the integers 0 to
11.
• In a modulo-N system, if a number is greater than N, it is
divided by N and the remainder is the result.
• Addition and subtraction in modulo arithmetic are simple.
There is no carry when you add two digits in a column. There
is no carry when you subtract one digit from another in a
column
Modulo-2 Arithmetic
• In this arithmetic, the modulus N is 2. We can use only 0
and 1. The following shows how we can add or subtract 2
bits.

Adding: 0+0=0, 0+1=1, 1+0=1, 1+1=0

Subtracting: 0-0=0, 0-1=1, 1-0=1, 1-1=0

• XOR (exclusive OR) operation is used for both addition and

subtraction.
Coding
• Redundancy is achieved through various coding schemes.
• The sender adds redundant bits through a process that creates a
relationship between the redundant bits and the actual data
bits.
• The receiver checks the relationships between the two sets of
bits to detect or correct the errors.
• The ratio of redundant bits to the data bits and the robustness
of the process are important factors in any coding scheme.
• Divided into Two categories:
• Block Coding
• Convolution Coding (not there in the syllabus)
Block Coding
• In block coding, message is divided into blocks, each of k
bits, called datawords.
• Add r redundant bits to each block to make the length n = k
+ r. The resulting n-bit blocks are called codewords.
• With k bits, we can create a combination of 2k datawords;
with n bits, we can create a combination of 2n codewords.
• The block coding process is one-to-one; the same data
word is always encoded as the same codeword. This
means that we have 2n - 2k codewords that are not used.
Let k = 4 and n = 5. We have 2k = 16 datawords and 2n = 32
codewords. 16 out of 32 codewords are used for message transfer
and the rest are either used for other purposes or unused.
Process of error detection in block coding
• If the following two conditions are met, the receiver can
detect a change in the original codeword.

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

2. The original codeword has changed to an invalid one.
• Let us assume that k = 2 and n =
3. Table.1 shows the list of
datawords and codewords.
• Assume the sender encodes Datawords Codewords
the dataword 01 as 011 and 00 000
sends it to the receiver. 01 011
Consider the following cases: 10 101
11 110
1. The receiver receives 011. It is
a valid codeword. The receiver
extracts the dataword 01 from it.
2. The codeword is corrupted during transmission, and 111 is
received. This is not a valid codeword and is discarded (don’t exist
in table).

3. The codeword is corrupted during transmission, and 000 is

received. This is a valid codeword. The receiver incorrectly extracts
the dataword 00. Two corrupted bits have made the error
undetectable.
Note

An error-detecting code can detect only the

types of errors for which it is; designed, other
types of errors may remain undetected.
Process of error correction in block coding
• In error detection, the
receiver needs to know
only that the received
codeword is invalid; in Datawords Codewords
error correction the
receiver needs to find the 00 00000
original codeword sent. 01 01011
10 10101
• Let us assume that k = 2 11 11110
and n = 5. Table.2 shows
the list of datawords and
codewords.
Assume the dataword is 01. The sender creates the codeword 01011. The
codeword is corrupted during transmission, and 01001 is received. First, the
receiver finds that the received codeword is not in the table. This means an
error has occurred. The receiver, assuming that there is only 1 bit corrupted,
uses the following strategy to guess the correct dataword.
1. Comparing the received codeword with the first codeword in the table
(01001 versus 00000), the receiver decides that the first codeword is not
the one that was sent because there are two different bits.
2. By the same reasoning, the original codeword cannotbe the third or
fourth one in the table.
3. The original codeword must be the second one in the table because this is
the only one that differs from the received codeword by 1 bit. The receiver
replaces 01001 with 01011 and consults the table to find the dataword 01.
Hamming Distance
• The Hamming distance between two words is the number of
differences between corresponding bits.
• The Hamming distance can easily be found if XOR operation
is applied on the two words and count the number of 1’s in
the result.
• Note that the Hamming distance is a value greater than zero.
• The Hamming distance d(000, 011) is 2 because
• The minimum Hamming distance is the smallest Hamming
distance between all possible pairs in a set of words denoted
as dmin
• Example 1: The dmin in this case is 2.

• Example 2: The dmin in this case is 3.

• Any coding scheme needs to have at least three parameters:
the codeword size n, the dataword size k, and the minimum
Hamming distance dmin.

• A coding scheme C is written as C(n, k) with a separate

expression for dmin.

• For example, we can call our first coding scheme C(3, 2) with
dmin =2 and our second coding scheme C(5, 2) with dmin = 3.
Hamming Distance and Error
• When a codeword is corrupted during transmission, the
Hamming distance between the sent and received codewords
is the number of bits affected by the error.
• For example, if the codeword 00000 is sent and 01101 is
received, 3 bits are in error and the Hamming distance
between the two is d(00000, 01101) =3.

Note
To guarantee the detection of up to s errors in all cases, the
minimum Hamming distance in a blockcode must be dmin = s + 1.
Linear Block Codes
• A linear block code is a code in which the exclusive OR (addition
modulo-2) of two valid codewords creates another valid
codeword.
• The minimum Hamming distance for a linear block code is the
number of 1’s in the nonzero valid codeword with the smallest
number of 1’s.
• There are mainly 4 types of linear block codes
• Simple Parity Check Code
• Hamming Code
• Cyclic Code
Simple Parity Check Code
• The most familiar error-detecting code is the simple parity-
check code.
• In this code, a k-bit dataword is changed to an n-bit
codeword where n = k + 1.
• The extra bit, called the parity bit, is selected to make the
total number of 1’s in the codeword even.

A simple parity-check code is a single-bit

error-detecting code in which n = k + 1 with
dmin = 2.
Encoder and decoder for simple parity-check code
Simple parity-check code C(5, 4)
• Assume the sender sends the dataword 1011. The codeword created from
this dataword is 10111, which is sent to the receiver. We examine five cases:
1. No error occurs; the received codeword is 10111. The syndrome is 0. The
dataword 1011 is created.
2. One single-bit error changes a1 . The received codeword is 10011. The
syndrome is 1. No dataword is created.
3. One single-bit error changes r0 . The received codeword is 10110. The
syndrome is 1. No dataword is created.
4. An error changes r0 and a second error changes a3 . The received
codeword is 00110. The syndrome is 0. The dataword 0011 is created at
the receiver. Note that here the dataword is wrongly created due to the
syndrome value.
5. Three bits— a3, a2, and a1—are changed by errors. The received
codeword is (01011). The syndrome is 1. The dataword is not created.
Two-dimensional parity-check code
Hamming Code

• Hamming code is an error-correcting code originally

designed with dmin = 3, which means that it can detect up to
two errors or correct one single error.
• We need to choose an integer r >= 3. The values of n and k are
then calculated from r as n =2r- 1 and k =n - r.
• Note: some Hamming codes that can correct more than one
error, our discussion focuses on the single-bit error-
correcting code.
Hamming code C(7, 4)

ro= a2+a1+a0 (Modulo-2 addition)

r1= a3+a2+a1 (Modulo-2 addition)
r2= a3+a1+a0 (Modulo-2 addition)
Logical decision made by the correction logic analyzer
We need a dataword of at least 7 bits. Calculate values of k
and n that satisfy this requirement.
Solution:
We need to make k = n − r greater than or equal to 7.

1. If we set r = 3, the result is n=23-1=7 and k = 7 − 3, or 4,

which is not acceptable.
2. If we set r = 4, then n = 24− 1 = 15 and k = 15 − 4 = 11, which
satisfies the condition. So the code is
C(15, 11)
Cyclic Codes

• In a cyclic code, if a codeword is cyclically shifted (rotated),

the result is another codeword.

• Cyclic codes are created to correct errors.

• A category of cyclic codes called the Cyclic Redundancy

Check (CRC) is used in networks such as LANs and WANs.
A CRC code with C(7, 4)
Division in CRC encoder
• A better way to understand cyclic codes and how they can be
analyzed is to represent them as polynomials.
• A pattern of 0’s and 1’s can be represented as a polynomial
with coefficients of 0 and 1.
• The power of each term shows the position of the bit; the
coefficient shows the value of the bit.
Checksum
• The checksum is used in the Internet by several protocols although not
at the data link layer.

• 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, we send the sum
of the numbers.

• For example, if the set of numbers is (7, 11, 12, 0, 6), we send (7, 11, 12,
0, 6, 36), where 36 is the sum of the original numbers. The receiver
adds the five numbers and compares the result with the sum. If the two
are the same, the receiver assumes no error, accepts the five numbers,
and discards the sum. Otherwise, there is an error somewhere and the
data are not accepted.
• We can make the job of the receiver easier if we send the
negative (complement) of the sum, called the checksum. In
this case, we 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.
• The sender initializes the checksum to 0 and adds all data
items and the checksum.
• The result is 36. However, 36 cannot be expressed in 4 bits.
• The extra two bits are wrapped and added with the sum to
create the wrapped sum value 6.
• The sum is then complemented, resulting in the checksum
value 9 (15 − 6 = 9).
• The sender now sends six data items to the receiver
including the checksum 9.
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.

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.
4. If the value of checksum is 0, the message is accepted; otherwise, it
is rejected.
Data Communication Equipment
• Digital service units (DSUs) and channel service units (CSUs)
are customer premise equipment (CPE) used to terminate a
digital circuit at a subscriber’s location and allow the
subscriber to connect to a local central telephone office.
Digital Service Unit (DSU)
• At the transmit end, a digital service unit (DSU) converts unipolar digital
signals from a local area network’s digital terminal equipment into self
clocking bipolar digital signals that are capable of being transmitted more
efficiently over a telecommunications line.

• At the receive end, a DSU removes any special codes inserted by the
transmitting DSU and converts the bipolar digital signals back to unipolar.

• A DSU may also provide timing (clock) recovery, control signaling, and
synchronous sampling.
Channel Service Unit (CSU)
• A channel service unit (CSU) serves as the demarcation point between
the digital Station equipment and the telecommunications line.
• A CSU physically terminates the telecommunications line, performs
signal regeneration and reshaping, performs zero substitution, and
converts digital signals to a format more suitable for transmission
over the digital transmission facility.
• CSUs may also perform other functions, such as channel multiplexing
and line conditioning (equalization); execute certain carrier-controlled
tests, such as local and remote loop backs; and provide performance
measurement capabilities and statistical compilations.
Voice-band Data Communication Modems
• The most common type of data communications equipment (DCE) is the data
communications modem.

• The word modem is a contraction derived from the words modulator and
demodulator.

• Data communications modems designed to operate over the limited bandwidth of

the public telephone network are called voice-band modems.

• Because digital information cannot be transported directly over analog

transmission media, the primary purpose of a data communications modem is to
interface computers, computer networks, and other digital terminal equipment to
analog communications facilities.
• In the transmitter section of a modem, digital signals are encoded onto
an analog carrier signal. The digital signals modulate the carrier,
producing digitally modulated analog signals that are capable of being
transported through the analog communications media. Therefore, the
output of a modem is an analog signal that is carrying digital information.

• In the receiver section of a modem, digitally modulated analog signals

are demodulated. Modem receivers (demodulators) simply extract digital
information from digitally modulated analog carriers.
• The most common (and simplest) modems available are those intended
to be used to interface DTEs through a serial interface to standard
voice-band telephone lines and provide reliable data transmission rates
between 300 bps to 56 kbps.
Bell Systems Compatible Voice-band Modems
• Bell system modems were virtually the only modems in existence at a
particular time.
• Non-Bell companies were allowed equipment manufacturing from
1968.
• The operating parameters for Bell system modems are the models
from which the international standards specified by the ITU-T
evolved.
• Bell system modem specifications apply only to voice-band modems
that existed in 1968; therefore, their specifications pertain only to
modems operating at data transmission rate of 9600 bps or less.
Voice-band modem block diagram
Serial interface circuit:
• This interfaces the modem transmitter and receiver to the serial
interface.
• The transmit section accepts digital information from the serial
interface, converts it to the appropriate voltage levels, and then
directs the information to the modulator.
• The receive section receives digital information from the
demodulator circuit, converts it to the appropriate voltage levels,
and then directs the information to the serial interface.
• In addition, the serial interface circuit manages the flow of control,
timing, and data information transferred between the DTE and the
modem, which includes handshaking signals and clocking
information.
Modulator circuit
• This receives digital information from the serial interface circuit.

• The digital information modulates an analog carrier producing a

digitally modulated analog signal.

• In essence, the modulator converts digital changes in the

information to analog changes in the carrier.

• The output from the modulator is directed to the transmit band-

pass filter and equalizer circuit.
Band pass filter and equalizer circuit:
• There are band pass filter and equalizer circuits in both the
transmitter and the receiver sections of the modem.
• The transmit band pass filter limits the bandwidth of the digitally
modulated analog signals to a bandwidth appropriate for
transmission over a standard telephone circuit.
• The receive band pass filter limits the bandwidth of the signals
allowed to reach the demodulator circuit, thus reducing noise and
improving system performance.
• Equalizer circuits compensate for bandwidth and gain
imperfections typically experienced on voice-band telephone lines.
Telco interface circuit:
• The primary functions of the Telco interface circuit match the
impedance of the modem to the impedance of the telephone line
and regulate amplitude of the transmit signal.
• The interface also provides electrical isolation and protection and
serves as the demarcation (separation) point between subscriber
equipment and Telephone Company provided equipment.
• The Telco line can be two wire or four wire, and the modem can
operate half or full duplex. When the telephone line is two wire,
the Telco interface circuit would have to perform four-wire-to-two-
wire and two-wire-to-four-wire conversions.
Carrier and clock generation circuit
• The carrier generation circuit produces the analog carriers
necessary for the modulation and demodulation processes.
The clock generation circuit generates the appropriate clock
and timing signals required for performing transmit and
receive functions in an orderly and timely fashion.

Demodulator circuit
• This receives modulated signals from the band pass filter and
equalizer circuit and converts the digitally modulated analog
signals to digital signals. The output from the demodulator is
directed to the serial interface circuit, where it is passed on
to the serial interface.
Voice-band Modem Classification
• Generally classified as Synchronous or Asynchronous and use one of the
following digital modulation schemes:
• Amplitude Shift Keying (ASK)
• Frequency Shift Keying (FSK)
• Phase Shift Keying (PSK)
• Quadrature Amplitude Modulation (QAM)

• There are several other ways of classification depending on the

distinguished features or capabilities, such as:
• Internal or External
• Low, Medium, High or very high speed
• Wideband or Voice band
• Personal or Commercial
• All modems share a common goal ,to convert digital pulses to analog
signals in the transmitter and analog signals to digital pulses in the
receiver
• Some Common features are:
• Automatic dialling, answering and redialling
• Error control (Detection and correction)
• Caller ID recognition
• Self-test capabilities
• Fax capabilities
• Data compression and expansion
• Telephone directory
• Adaptive transmit and receive data rates (300bps to 56kbps)
• Automatic equalization
• Synchronous and Asynchronous operation
Asynchronous Voice-band Modems
• Asynchronous voice band modems can be generally classified as low-
speed voice band modems, as they are typically used to transport
asynchronous data (i.e., data framed with start and stop bits).
• Synchronous data is sometimes used with an asynchronous modem;
however, it is not particularly practical or economical. Synchronous
data transported by asynchronous modems is called isochronous
transmission.
• Asynchronous modems use relatively simple modulation schemes,
such as ASK or FSK, and are restricted to relatively low-speed
applications (generally less than 2400 bps), such as telemetry and
caller ID.
• In the transmitter, serial data received from the DTE is applied directly to
the FSK modulator.
• Clocking information is not required because FSK modulators are typically
voltage controlled oscillators, which react to voltage levels independent of
any timing reference.
• The voltage for a binary 1 produces a mark frequency, and the voltage for a
binary 0 produces a space frequency. Thus, FSK modulators use single-bit
encoding, which means that each input bit modulates the carrier
independent of any other data bits.
• Single-bit encoding produces an output frequency that is changing
(shifting) at the same rate as the input data. The rate of change of the
digital input data is called the bit rate and the rate of change of output
analog signal is called baud (or baud rate).
• With FSK, the output frequency changes at the same rate as the input data
rate; therefore, with FSK the bit rate is equal to the baud.
• The minimum bandwidth necessary to propagate an FSK signal is
dependent on the mark and space frequencies and the bit rate.
• The modulated FSK signal is band-limited and pre-equalized and then
outputted onto the telephone line.
• Asynchronous receivers use noncoherent demodulation, which
means that the carrier and clocking information is not recovered in
the receiver.
• There are several standard asynchronous voice-band modems
designed for low-speed data applications using the switched public
telephone network.
• To operate full duplex with a two-wire dial-up circuit, it is necessary to
divide the usable bandwidth of a voice-band circuit in half, creating
two equal-capacity data channels.
Synchronous Voice-band Modems
• Synchronous modems use PSK or QAM to transport synchronous data
at transmission rates between 2400bps and 56K bps over standard
voice-grade telephone lines.
• The modulated carrier is transmitted to he distant modem, where
coherent carrier is recovered and used to demodulate the data.
• The transmit clock is recovered from the data and used to clock the
received data into the DTE.
• Because of the addition of clock and carrier recovery circuits,
synchronous modems are complicated and, thus more expensive than
Asynchronous modems.
Modem Synchronization
• During the RTS/CTS delay, a transmit modem outputs a special, internally
generated bit pattern called a training sequence. This bit pattern is used to
synchronize (train) the receive modem at the distant end of the
communications channel.
• Depending on the type of modulation, transmission bit rate, and modem
complexity, the training sequence accomplishes one or more of the following
functions:
1. Initializes the communications channel, which includes disabling echo and
establishing the gain of automatic gain control (AGC) devices
2. Verifies continuity (activates RLSD in the receive modem)
3. Initializes descrambler circuits in the receive modem
4. Initializes automatic equalizers in the receive modem
5. Synchronizes the receive modem’s carrier to the transmit modem’s carrier
6. Synchronizes the receive modem’s clock to the transmit modem’s clock
56K Modems
• V.90 allows modem downstream data rates up to 56kbps and
upstream data rates up to 33.6kbps. The reason for this restriction is
to reduce crosstalk on telephone feeder cables.
• Later in 2000, V.92 is approved offering more improvements over V.90
• Upstream rate of 48kbps accomplished through improved
signaling and compression techniques.
• Faster call setup capabilities because V.92 modems remember
information from previous calls to the same destination.
• Data call on-hold for up to 16 min when voice calls are received.
Cable Modems
• Cable modems are similar to standard voice-band modems, except cable
modems operate at higher frequencies, operate at higher bit rates, use
more sophisticated modulation and demodulation schemes, and require
more bandwidth than conventional voice-band modems.
• Cable modems connect subscribers to cable TV (CATV) facilities, such as
coaxial cables and optical fibers, and provide high-speed Internet access
and video services. A single CATV channel can support multiple individual
subscribers or a local area network using a shared network protocol
capable of supporting many users, such as Ethernet.
• Cable modems are broad band modems, which simply means that they
require wider bandwidths than standard voice-band modems.
• Subscribers are connected through a cable modem over a TV cable to
a CATV network headend, which is the originating point for the CATV
audio, video, and data signals.
• With cable modems, the upstream (subscriber to headend) and
downstream (headend to subscriber) frequency spectrums and
transmission rates are not the same (asymmetrical transmission).
• The bandwidths are considerably wider and transmission rates
considerably higher on the downstream connection.
• Cable modem frequency assignments and transmission rates are the
following:
Upstream:
Carrier frequency: 5 MHz to 40 MHz
Transmission rate: 19.2 kbps to 3 Mbps
Downstream:
Carrier frequency: 250 MHz to 850 MHz
Transmission rate: 10 Mbps to 30 Mbps