Data Communication &

Computer Network

Lecture:17, 18,19, 20 & 21

Presented By
Dr. S.Kanungo
 Asynchronous and Synchronous Transmission
• Timing problems require a mechanism to synchronize
the transmitter and receiver
• Two solutions
➢ Asynchronous
➢ Synchronous
• Data transmission and modes
 Asynchronous
• Data transmitted one character at a time
• Also called start and stop transmission
• Synchronize without utilizing a clock
• Data flows in a Half Duplex mode
• We send 1 start bit (0) at the beginning and 1 or more stop bits
(1s) at the end of each byte. There may be a gap between each
byte.
• Asynchronous at the byte level; but the bits are still
synchronized; their durations are the same
• Synchronous
➢Used for sending huge amount of data
➢Allows connected devices to interact in real time
➢High data transfer speed
➢ Full Duplex transmission using frames or blocks
➢ More efficient (lower overhead) than asynchronous
➢ We send bits one after another without start or stop bits
or gaps. It is the responsibility of the receiver to group the
bits.

• Isochronous: synchronization between characters is not

enough; the entire stream of bits must be synchronized. It
guarantees that the data arrive at a fixed rate.
 Types of Error
• Categories: Content Error and Flow Integrity Error
• An error occurs when a bit is altered between
transmission and reception
• Single bit errors
– One bit altered
– Adjacent bits not affected
– White noise

• Burst errors
– Length B
– Contiguous sequence of B bits in which first, last and
any number of intermediate bits in error
– Impulse noise
– Fading in wireless
– Effect greater at higher data rates
Error Detection Process (Figure 6.2)
 Error Detection
• Additional bits added by transmitter for error
detection code
• Parity check
– Value of parity bit is such that character has even (even
parity – used for synchronous transmission) or odd
(odd parity – used for asynchronous transmission)
number of ones
– Even number of bit errors goes undetected

1The least significant bit of a character is transmitted first, and that the
parity bit is the most significant
• Two-dimensional Parity Check
- The string of data bits to be checked is arranged in a 2-D array
- It is more robust than the single parity bit
- Any odd number of bit errors detected
- The error can be determined to be at the intersection of
that row and column
- It is possible to not only detect the error but also correct the bit
error
• Example: A string of 20 data bits arranged in a 4×5 array
Fig. 6.3 2D Even Parity Scheme

➢ If an even number of errors occur in a row, the errors are detected by

the column parity bits. Similarly, if an even number of errors occur in a
column, the errors are detected by the row parity bits. However, any
pattern of four errors forming a rectangle, as shown in Figure 6.3d, is
undetectable. If the four circled bits change value, the corresponding
row and column parity bits do not change value.
• Internet Checksum
- An error detecting code used in many Internet standard
protocols, including IP, TCP, and UDP
- Calculation based on 1’s complement operation and 1’s
complement addition
- 1’s complement addition:
1. The two numbers are treated as unsigned binary integers and added.
2. If there is a carry out of the leftmost bit, add 1 to the sum. This is
called an end-around carry.
• It provides greater error-detection capability than a parity
bit or 2-D parity scheme but is considerably less effective
than Cyclic Redundancy Check (CRC)
• It is an efficient technique as it causes very little overhead
 Cyclic Redundancy Check (CRC)
• One of the most common, and one of the most powerful, error-detecting codes
• Given a k-bit block of bits, or message, the transmitter generates an (n - k)-bit
sequence, known as a frame check sequence (FCS), such that the resulting frame,
consisting of n bits, is exactly divisible by some predetermined number. The
receiver then divides the incoming frame by that number and, if there is no
remainder, assumes there was no error.
• This procedure is slightly different from that of Figure 6.2.
• Modulo 2 Arithmetic
➢ It uses binary addition with no carries, which is just the exclusive-OR (XOR)
operation. Binary subtraction with no carries is also interpreted as the XOR
operation: For example:

➢ Define:
T = n-bit frame to be transmitted; D = k-bit block of data, or message, the first k bits of T
F = (n - k)-bit FCS, the last (n - k) bits of T; P = pattern of n - k + 1 bits; this is the
predetermined divisor; We would like T/P to have no remainder:
Coding for detection and correction of content errors
• Coding is the process of adding check bits
• The block of data bits to which check bits are added is
called a Data Word
• Code Word: The bigger block containing check bits
• Hamming Distance: Distance between two code words
is the number of disagreement between them.
• If data word has length l, and r number of check bits
are added to each data word to generate code
words of length n=l+r, we have 2l combinations of
data words to be mapped to code words from 2l+r
possible combinations.
• If we want to detect up to E errors, then all the
valid code words should be at least E+1 distance
apart.
• Error Correction Approaches
➢ Reverse Error Correction (REC)
- The receiver requests for retransmission of the
code word whenever it detects an error. If there
is no error, the receiver returns an ACK for the
correctly received code words
➢ Forward Error Correction (FEC)
- The code is so designed that it is possible for
the receiver to detect and correct the error
- The FEC decoder has 4 possible outcomes:
▪ No errors: If there are no bit errors, the input to the
FEC decoder is identical to the original codeword, and
the decoder produces the original data block as output.
• Detectable, correctable errors: For certain error
patterns, it is possible for the decoder to detect and
correct those errors. Thus, even though the incoming
data block differs from the transmitted codeword, the
FEC decoder is able to map this block into the original
data block.
• Detectable, not correctable errors: For certain error
patterns, the decoder can detect but not correct the
errors. In this case, the decoder simply reports an
uncorrectable error.
• Undetectable errors: For certain, typically rare, error
patterns, the decoder does not detect the error and
maps the incoming n-bit data block into a k-bit block
that differs from the original k-bit block.
• Block Code Principles
➢ The Hamming distance d(v1, v2) between two n-bit binary
sequences v1 and v2 is the number of bits in which v1 and v2
disagree. For example, if
v1 = 011011, v2 = 110001
then
d (v1, v2) = 3
➢ Suppose we wish to transmit blocks of data of length k bits.
Instead of transmitting each block as k bits, we map each k-
bit sequence into a unique n-bit codeword.
• Perfect Error Correcting Code
- No. of check bits required (r) to correct error for data word
length (l) ?
- For single bit errors
- we need to address this problem from two angles
(i) The no. of check bits should be sufficient to ensure
that single-bit errors do not generate another valid code
word.
(ii) The no. of check bits should be sufficient to point to
location of the bit in error if there is an error.
- A perfect error correcting code is the one in which no. of
check bits is equal to the minimum integer value of r that
satisfies the inequality 2r ≥ n +1. (for e.g., if n = 7, the
perfect code will require 3 check bits for coding 4-bit data
word.)
• Forward Error Correction Methods
- Block Parity
- Hamming Code
- Interleaved Code
- Convolutional Code
• Block Parity
- The data block is arranged in a rectangular matrix form
and two sets of parity bits are generated namely:
- Longitudinal Redundancy Check (LRC)
- Vertical Redundancy Check (VRC)
- VRC is the parity bit associated with the character code
and LRC is generated over the rows of the bits.
- Single bit errors in the block result in failure of LRC in
one of the rows and VRC in one of the columns.
- The bit which is at intersection of the row and the column is in
error.
• Hamming Code
- It consists of code words of length n each having r parity bits,
where r is the smallest integer satisfying the condition 2r ≥ n +1.
- The check bits are generated using even or odd parity for a
defined set of data bits.
- The location of error is pointed out by error syndrome, which is
calculated based on the parity checks. (for e.g., if the 6th bit is in
error, error syndrome will take binary value 110.)
- For correction of single bit errors in data word (4 bit), 3 check
bits are required.
- For a 7-bit hamming code, syndrome can take values from 001
to 111.
- LSB of the syndrome is 1 for the bit positions 1,3, 5 and 7 (first
parity). These positions are grouped together. The error in these
positions is detected by keeping a parity bit at any one of these 4
positions. Whenever any of these bit positions is in error, the LSB
of the syndrome is made 1.
• Middle bit of syndrome is 1 for bit positions 2,3,6 and 7(second
parity). Third parity bit is kept at any one of the positions 4,5,6
or 7
• Bit positions 1,2,4,8 … of the code word are reserved for the
parity bits. The other bit positions are for the data bits.
P1 P2 D P4 D D D P8 D D D

• Here, P: Parity bit; D: Data bit

• Example Question:
Detect and correct the single error in the received Hamming
code word 10110010111. Assume even parity.
Ans: 9th bit position is in error. Correct code word is
101100110011
• Asynchronous Data Error Methods(Low-speed asynchronous
transmission)
- The most common and oldest method of error detection is the
use of parity.
 - Parity Error detection
- Parity generation (use Ex-OR)
- Parity checker
- ARQ (Automatic Request for Retransmission OR Automatic
Repeat Request): Request that the message containing error be
retransmitted (error correction)
- VRC and LRC for single bit error correction
• Synchronous Data Error Methods
- For transmission at higher data rates
- Cyclic Redundancy Check (CRC)
- Checksum Error Detection
- Hamming Code
• Reverse Error Correction (REC)
- Stop and Wait
- Go-Back-N
- Selective Retransmission
 Error Testing Equipment
• Bit-Error Tester (BERT)
- Bit-Error Rate(Measure of the occurrences of an incorrect bit
in a stream of data) = (No. of bad bits/Total no. of bits) × 100%
- It can test a data link for several different types of error
occurrences i.e., bit-error rate, parity and framing-error testing.
- It cab used by tapping into the line between the terminal and
the modem.
• Error-Free Seconds
- It is used as a measure of error occurrences for data
transmission from 2.4 kbps to 2.5 mbps.
- It is a measure of the number of seconds of transmission time
that contain at least one error.
- An error-free second percentage is computed as:
error-free seconds = 100 % - (seconds with an error/total
transmission seconds) × 100%
- Used in the same manner as BERT
 Line Configuration
• Two characteristics that distinguish various data link
configurations are topology and whether the link is half
duplex or full duplex
• Topology
– Physical arrangement of stations on medium
– Point to point
– Multi point
• Computer and terminals, local area network
• Half duplex (two-way alternate)
– Only one station may transmit at a time
– Requires one data path
• Full duplex (two way simultaneous)
- Simultaneous transmission and reception between two stations
- Requires two data paths
• Echo Cancelation: A technique to transmit digital signals in both
directions simultaneously on a single transmission line
Traditional Configurations
 Interfacing
• Data processing devices (or data terminal
equipment, DTE) do not (usually) include data
transmission facilities
• Need an interface called data circuit terminating
equipment (DCE)
– e.g., modem, NIC
• DCE transmits bits on medium
• DCE communicates data and control info with DTE
– Done over interchange circuits
– Clear interface standards required
Data Communications Interfacing
 Characteristics of Interface
• Mechanical
– Connection plugs
• Electrical
– Voltage, timing, encoding
• Functional
– Data, control, timing, grounding
• Procedural
– Sequence of events
 V.24/EIA-232-F
• ITU-T v.24
• Only specifies functional and procedural
– References other standards for electrical and
mechanical
• EIA-232-F (USA)
– RS-232
– Mechanical ISO 2110
– Electrical v.28
– Functional v.24
– Procedural v.24
Mechanical Specification
 Electrical Specification
• Digital signals
• Values interpreted as data or control, depending on circuit
• More than -3v is binary 1, more than +3v is binary 0 (NRZ-L)
• Signal rate < 20kbps
• Distance <15m
• For control, more than-3v is off, +3v is on
Functional Specification
• Circuits grouped in categories
(i) Data (ii) Control (iii) Timing (iv) Ground
• One circuit in each direction
– Full duplex
• Two secondary data circuits
– Allow halt or flow control in half duplex operation
Local and Remote Loopback
 Procedural Specification
• E.g. Asynchronous private line modem
• When turned on and ready, modem (DCE) asserts DCE
ready
• When DTE ready to send data, it asserts Request to Send
– Also inhibits receive mode in half duplex
• Modem responds when ready by asserting Clear to send
• DTE sends data
• When data arrives, local modem asserts Receive Line
Signal Detector and delivers data
 Data Link Control Protocols
• What are the requirements and objectives for effective data
communication?
 Flow Control
• Ensuring the sending entity does not overwhelm
the receiving entity
– Preventing buffer overflow
• Transmission time
– Time taken to emit all bits into medium
• Propagation time
– Time for a bit to traverse the link
Model of Frame Transmission
 Stop and Wait
• It is the simplest form of flow control
• Source transmits frame
• Destination receives frame and replies with
acknowledgement
• Source waits for ACK before sending next frame
• Destination can stop flow by not sending ACK
• Works well for a few large frames
• Why a source break up large block of data into smaller blocks?
➢ The buffer size of the receiver may be limited.
➢The longer the transmission, the more likely that there will be an
error, necessitating retransmission of the entire frame. With smaller
frames, errors are detected sooner, and a smaller amount of data needs
to be retransmitted.
➢ On a shared medium, such as a LAN, it is usually desirable not to
permit one station to occupy the medium for an extended period, thus
causing long delays at the other sending stations.
 Fragmentation
• Large block of data may be split into small
frames
– Limited buffer size
– Errors detected sooner (when whole frame
received)
– On error, retransmission of smaller frames is
needed
– Prevents one station occupying medium for
long periods
• Stop and wait becomes inadequate (only
one frame at a time can be in transit)
• The bit length of a link is defined as:
• When a is less than 1, the propagation time is less
than the transmission time. In this case, the frame
is sufficiently long that the first bits of the frame
have arrived at the destination before the source
has completed the transmission of the frame.
• When a is greater than 1, the propagation time is
greater than the transmission time. In this case,
the sender completes transmission of the entire
frame before the leading bits of that frame arrive at
the receiver.
• For a > 1, the line is always underutilized and even
for a <1, the line is inefficiently utilized.
• For very high data rates, for very long distances
between sender and receiver, stop-and-wait flow
control provides inefficient line utilization.
 Sliding Windows Flow Control
• Allow multiple frames to be in transit
• Receiver allocates buffer for W frames
• Transmitter can send up to W frames without waiting for
any ACK
• Each frame is numbered
• ACK includes number of next frame expected
• This scheme can also be used to acknowledge multiple
frames
• The sender maintains a list of sequence numbers that it is
allowed to send, and the receiver maintains a list of
sequence numbers that it is prepared to receive.
• Lists can be thought of as a window of frames
• Sequence number bounded by size of field (k)
– Frames are numbered modulo 2k
Sliding Window Diagram
Example Sliding Window
 Sliding Window Enhancements
• Receiver can acknowledge frames without
permitting further transmission (Receive Not
Ready)
• Must send a normal acknowledge to resume
• If duplex, use piggybacking
– If no data to send, use acknowledgement frame
– If data but no acknowledgement to send, send
last acknowledgement number again, or have
ACK valid flag (TCP)