Error Detection

When data is transmitted from one device to another device, the system does not guarantee
whether the data received by the device is identical to the data transmitted by another device. An
Error is a situation when the message received at the receiver end is not identical to the message
transmitted.

Types Of Errors

Errors can be classified into two categories:

o Single-Bit Error

o Burst Error

Single-Bit Error:

The only one bit of a given data unit is changed from 1 to 0 or from 0 to 1.

In the above figure, the message which is sent is corrupted as single-bit, i.e., 0 bit is changed to
1.

Single-Bit Error does not appear more likely in Serial Data Transmission. For example, Sender
sends the data at 10 Mbps, this means that the bit lasts only for 1 ?s and for a single-bit error to
occurred, a noise must be more than 1 ?s.
Single-Bit Error mainly occurs in Parallel Data Transmission. For example, if eight wires are
used to send the eight bits of a byte, if one of the wire is noisy, then single-bit is corrupted per
byte.

Burst Error:

The two or more bits are changed from 0 to 1 or from 1 to 0 is known as Burst Error.

The Burst Error is determined from the first corrupted bit to the last corrupted bit.

The duration of noise in Burst Error is more than the duration of noise in Single-Bit.

Burst Errors are most likely to occurr in Serial Data Transmission.

Error Detecting Techniques:

The most popular Error Detecting Techniques are:

o Single parity check

o Two-dimensional parity check

o Checksum

o Cyclic redundancy check

Single Parity Check

o Single Parity checking is the simple mechanism and inexpensive to detect the errors.
 o In this technique, a redundant bit is also known as a parity bit which is appended at the
end of the data unit so that the number of 1s becomes even. Therefore, the total number
of transmitted bits would be 9 bits.

o If the number of 1s bits is odd, then parity bit 1 is appended and if the number of 1s bits
is even, then parity bit 0 is appended at the end of the data unit.

o At the receiving end, the parity bit is calculated from the received data bits and compared
with the received parity bit.

o This technique generates the total number of 1s even, so it is known as even-parity

checking.

Drawbacks Of Single Parity Checking

o It can only detect single-bit errors which are very rare.

o If two bits are interchanged, then it cannot detect the errors.

Two-Dimensional Parity Check

o Performance can be improved by using Two-Dimensional Parity Check which

organizes the data in the form of a table.

o Parity check bits are computed for each row, which is equivalent to the single-parity
check.

o In Two-Dimensional Parity check, a block of bits is divided into rows, and the redundant
row of bits is added to the whole block.

o At the receiving end, the parity bits are compared with the parity bits computed from the
received data.

Drawbacks Of 2D Parity Check

o If two bits in one data unit are corrupted and two bits exactly the same position in another
data unit are also corrupted, then 2D Parity checker will not be able to detect the error.

o This technique cannot be used to detect the 4-bit errors or more in some cases.

Checksum
 A Checksum is an error detection technique based on the concept of redundancy.

It is divided into two parts:

Checksum Generator

A Checksum is generated at the sending side. Checksum generator subdivides the data into equal
segments of n bits each, and all these segments are added together by using one's complement
arithmetic. The sum is complemented and appended to the original data, known as checksum
field. The extended data is transmitted across the network.

Suppose L is the total sum of the data segments, then the checksum would be ?L

1. The Sender follows the given steps:

2. The block unit is divided into k sections, and each of n bits.
3. All the k sections are added together by using one's complement to get the sum.
4. The sum is complemented and it becomes the checksum field.
5. The original data and checksum field are sent across the network.
 Checksum Checker

A Checksum is verified at the receiving side. The receiver subdivides the incoming data
into equal segments of n bits each, and all these segments are added together, and then this
sum is complemented. If the complement of the sum is zero, then the data is accepted
otherwise data is rejected.

1. The Receiver follows the given steps:

2. The block unit is divided into k sections and each of n bits.
3. All the k sections are added together by using one's complement algorithm to get the sum.
4. The sum is complemented.
5. If the result of the sum is zero, then the data is accepted otherwise the data is discarded.

Cyclic Redundancy Check (CRC)

CRC is a redundancy error technique used to determine the error.

Following are the steps used in CRC for error detection:

o In CRC technique, a string of n 0s is appended to the data unit, and this n number is less
than the number of bits in a predetermined number, known as division which is n+1 bits.

o Secondly, the newly extended data is divided by a divisor using a process is known as
binary division. The remainder generated from this division is known as CRC remainder.

o Thirdly, the CRC remainder replaces the appended 0s at the end of the original data. This
newly generated unit is sent to the receiver.

o The receiver receives the data followed by the CRC remainder. The receiver will treat
this whole unit as a single unit, and it is divided by the same divisor that was used to find
the CRC remainder.

If the resultant of this division is zero which means that it has no error, and the data is accepted.

If the resultant of this division is not zero which means that the data consists of an error.
Therefore, the data is discarded.
Let's understand this concept through an example:

Suppose the original data is 11100 and divisor is 1001.

CRC Generator

o A CRC generator uses a modulo-2 division. Firstly, three zeroes are appended at the end
of the data as the length of the divisor is 4 and we know that the length of the string 0s to
be appended is always one less than the length of the divisor.

o Now, the string becomes 11100000, and the resultant string is divided by the divisor
1001.

o The remainder generated from the binary division is known as CRC remainder. The
generated value of the CRC remainder is 111.

o CRC remainder replaces the appended string of 0s at the end of the data unit, and the
final string would be 11100111 which is sent across the network.
CRC Checker

o The functionality of the CRC checker is similar to the CRC generator.

o When the string 11100111 is received at the receiving end, then CRC checker performs
the modulo-2 division.

o A string is divided by the same divisor, i.e., 1001.

o In this case, CRC checker generates the remainder of zero. Therefore, the data is
accepted.
Error Correction

Error Correction codes are used to detect and correct the errors when data is transmitted from the
sender to the receiver.

Error Correction can be handled in two ways:

o Backward error correction: Once the error is discovered, the receiver requests the
sender to retransmit the entire data unit.

o Forward error correction: In this case, the receiver uses the error-correcting code
which automatically corrects the errors.

A single additional bit can detect the error, but cannot correct it.

For correcting the errors, one has to know the exact position of the error. For example, If we
want to calculate a single-bit error, the error correction code will determine which one of seven
bits is in error. To achieve this, we have to add some additional redundant bits.

Suppose r is the number of redundant bits and d is the total number of the data bits. The number
of redundant bits r can be calculated by using the formula:
 2r>=d+r+1

The value of r is calculated by using the above formula. For example, if the value of d is 4, then
the possible smallest value that satisfies the above relation would be 3.

To determine the position of the bit which is in error, a technique developed by R.W Hamming is
Hamming code which can be applied to any length of the data unit and uses the relationship
between data units and redundant units.

Hamming Code

Parity bits: The bit which is appended to the original data of binary bits so that the total number
of 1s is even or odd.

Even parity: To check for even parity, if the total number of 1s is even, then the value of the
parity bit is 0. If the total number of 1s occurrences is odd, then the value of the parity bit is 1.

Odd Parity: To check for odd parity, if the total number of 1s is even, then the value of parity
bit is 1. If the total number of 1s is odd, then the value of parity bit is 0.

Algorithm of Hamming code:

o An information of 'd' bits are added to the redundant bits 'r' to form d+r.

o The location of each of the (d+r) digits is assigned a decimal value.

o The 'r' bits are placed in the positions 1,2,.....2k-1.

o At the receiving end, the parity bits are recalculated. The decimal value of the parity bits
determines the position of an error.

Relationship b/w Error position & binary number.

 Total number of data bits 'd' = 4
Number of redundant bits r : 2r >= d+r+1
2r>= 4+r+1
Therefore, the value of r is 3 that satisfies the above relation.
Total number of bits = d+r = 4+3 = 7;

Determining the position of the redundant bits

The number of redundant bits is 3. The three bits are represented by r1, r2, r4. The position of the
redundant bits is calculated with corresponds to the raised power of 2. Therefore, their
corresponding positions are 1, 21, 22.

1. The position of r1 = 1
2. The position of r2 = 2
3. The position of r4 = 4

Representation of Data on the addition of parity bits:

Determining the Parity bits

Determining the r1 bit

The r1 bit is calculated by performing a parity check on the bit positions whose binary
representation includes 1 in the first position.

We observe from the above figure that the bit positions that includes 1 in the first position are 1,
3, 5, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at
these bit positions corresponding to r1 is even, therefore, the value of the r1 bit is 0.
Determining r2 bit

The r2 bit is calculated by performing a parity check on the bit positions whose binary
representation includes 1 in the second position.

We observe from the above figure that the bit positions that includes 1 in the second position
are 2, 3, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of
1 at these bit positions corresponding to r2 is odd, therefore, the value of the r2 bit is 1.

Determining r4 bit

The r4 bit is calculated by performing a parity check on the bit positions whose binary
representation includes 1 in the third position.

We observe from the above figure that the bit positions that includes 1 in the third position are 4,
5, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at
these bit positions corresponding to r4 is even, therefore, the value of the r4 bit is 0.

Data transferred is given below:

Suppose the 4th bit is changed from 0 to 1 at the receiving end, then parity bits are recalculated.

The bit positions of the r1 bit are 1,3,5,7

We observe from the above figure that the binary representation of r1 is 1100. Now, we perform
the even-parity check, the total number of 1s appearing in the r1 bit is an even number.
Therefore, the value of r1 is 0.

R2 bit

The bit positions of r2 bit are 2,3,6,7.

We observe from the above figure that the binary representation of r2 is 1001. Now, we perform
the even-parity check, the total number of 1s appearing in the r2 bit is an even number.
Therefore, the value of r2 is 0.

R4 bit

The bit positions of r4 bit are 4,5,6,7.

We observe from the above figure that the binary representation of r4 is 1011. Now, we perform
the even-parity check, the total number of 1s appearing in the r4 bit is an odd number. Therefore,
the value of r4 is 1.

o The binary representation of redundant bits, i.e., r4r2r1 is 100, and its corresponding
decimal value is 4. Therefore, the error occurs in a 4th bit position. The bit value must be
changed from 1 to 0 to correct the error.

Data Link Controls

Data Link Control is the service provided by the Data Link Layer to provide reliable data transfer
over the physical medium. For example, In the half-duplex transmission mode, one device can
only transmit the data at a time. If both the devices at the end of the links transmit the data
simultaneously, they will collide and leads to the loss of the information. The Data link layer
provides the coordination among the devices so that no collision occurs.

The Data link layer provides three functions:

Flow Control

o It is a set of procedures that tells the sender how much data it can transmit before the data
overwhelms the receiver.

o The receiving device has limited speed and limited memory to store the data. Therefore,
the receiving device must be able to inform the sending device to stop the transmission
temporarily before the limits are reached.

o It requires a buffer, a block of memory for storing the information until they are
processed.

Two methods have been developed to control the flow of data:

o Stop-and-wait

o Sliding window

Stop-and-wait

o In the Stop-and-wait method, the sender waits for an acknowledgement after every frame
it sends.

o When acknowledgement is received, then only next frame is sent. The process of
alternately sending and waiting of a frame continues until the sender transmits the EOT
(End of transmission) frame.

Advantage of Stop-and-wait

The Stop-and-wait method is simple as each frame is checked and acknowledged before the next
frame is sent.

Sliding Window

o The Sliding Window is a method of flow control in which a sender can transmit the
several frames before getting an acknowledgement.

o In Sliding Window Control, multiple frames can be sent one after the another due to
which capacity of the communication channel can be utilized efficiently.

o A single ACK acknowledge multiple frames.

o Sliding Window refers to imaginary boxes at both the sender and receiver end.

o The window can hold the frames at either end, and it provides the upper limit on the
number of frames that can be transmitted before the acknowledgement.

o Frames can be acknowledged even when the window is not completely filled.

o The window has a specific size in which they are numbered as modulo-n means that they
are numbered from 0 to n-1. For example, if n = 8, the frames are numbered from
0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1........

o The size of the window is represented as n-1. Therefore, maximum n-1 frames can be
sent before acknowledgement.

o When the receiver sends the ACK, it includes the number of the next frame that it wants
to receive. For example, to acknowledge the string of frames ending with frame number
4, the receiver will send the ACK containing the number 5. When the sender sees the
ACK with the number 5, it got to know that the frames from 0 through 4 have been
received.

Error Control

o Error Control is a technique of error detection and retransmission.

o Categories of Error Control:

o
 o Stop-and-wait ARQ
o Stop-and-wait ARQ is a technique used to retransmit the data in case of damaged or lost
frames

This technique works on the principle that the sender will not transmit the next frame until it
receives the acknowledgement of the last transmitted frame.

Four features are required for the retransmission:

o The sending device keeps a copy of the last transmitted frame until the acknowledgement
is received. Keeping the copy allows the sender to retransmit the data if the frame is not
received correctly.

o Both the data frames and the ACK frames are numbered alternately 0 and 1 so that they
can be identified individually. Suppose data 1 frame acknowledges the data 0 frame
means that the data 0 frame has been arrived correctly and expects to receive data 1
frame.

o If an error occurs in the last transmitted frame, then the receiver sends the NAK frame
which is not numbered. On receiving the NAK frame, sender retransmits the data.

o It works with the timer. If the acknowledgement is not received within the allotted time,
then the sender assumes that the frame is lost during the transmission, so it will retransmit
the frame.

Two possibilities of the retransmission:

o Damaged Frame: When the receiver receives a damaged frame, i.e., the frame contains
an error, then it returns the NAK frame. For example, when the data 0 frame is sent, and
then the receiver sends the ACK 1 frame means that the data 0 has arrived correctly, and
transmits the data 1 frame. The sender transmits the next frame: data 1. It reaches
undamaged, and the receiver returns ACK 0. The sender transmits the next frame: data 0.
The receiver reports an error and returns the NAK frame. The sender retransmits the data
0 frame.

o Lost Frame: Sender is equipped with the timer and starts when the frame is transmitted.
Sometimes the frame has not arrived at the receiving end so that it can be acknowledged
 neither positively nor negatively. The sender waits for acknowledgement until the timer
goes off. If the timer goes off, it retransmits the last transmitted frame.

Sliding Window ARQ

SlidingWindow ARQ is a technique used for continuous transmission error control.

Three Features used for retransmission:

o In this case, the sender keeps the copies of all the transmitted frames until they have been
acknowledged. Suppose the frames from 0 through 4 have been transmitted, and the last
acknowledgement was for frame 2, the sender has to keep the copies of frames 3 and 4
until they receive correctly.

o The receiver can send either NAK or ACK depending on the conditions. The NAK frame
tells the sender that the data have been received damaged. Since the sliding window is a
continuous transmission mechanism, both ACK and NAK must be numbered for the
identification of a frame. The ACK frame consists of a number that represents the next
frame which the receiver expects to receive. The NAK frame consists of a number that
represents the damaged frame.

o The sliding window ARQ is equipped with the timer to handle the lost
acknowledgements. Suppose then n-1 frames have been sent before receiving any
acknowledgement. The sender waits for the acknowledgement, so it starts the timer and
waits before sending any more. If the allotted time runs out, the sender retransmits one or
all the frames depending upon the protocol used.

Two protocols used in sliding window ARQ:

o Go-Back-n ARQ: In Go-Back-N ARQ protocol, if one frame is lost or damaged, then it
retransmits all the frames after which it does not receive the positive ACK.

Three possibilities can occur for retransmission:

o Damaged Frame: When the frame is damaged, then the receiver sends a NAK frame.
In the above figure, three frames have been transmitted before an error discovered in the third
frame. In this case, ACK 2 has been returned telling that the frames 0,1 have been received
successfully without any error. The receiver discovers the error in data 2 frame, so it returns the
NAK 2 frame. The frame 3 is also discarded as it is transmitted after the damaged frame.
Therefore, the sender retransmits the frames 2,3.

o Lost Data Frame: In Sliding window protocols, data frames are sent sequentially. If any
of the frames is lost, then the next frame arrive at the receiver is out of sequence. The
receiver checks the sequence number of each of the frame, discovers the frame that has
been skipped, and returns the NAK for the missing frame. The sending device retransmits
the frame indicated by NAK as well as the frames transmitted after the lost frame.

o Lost Acknowledgement: The sender can send as many frames as the windows allow
before waiting for any acknowledgement. Once the limit of the window is reached, the
sender has no more frames to send; it must wait for the acknowledgement. If the
acknowledgement is lost, then the sender could wait forever. To avoid such situation, the
sender is equipped with the timer that starts counting whenever the window capacity is
reached. If the acknowledgement has not been received within the time limit, then the
sender retransmits the frame since the last ACK.

Selective-Reject ARQ
 o Selective-Reject ARQ technique is more efficient than Go-Back-n ARQ.

o In this technique, only those frames are retransmitted for which negative
acknowledgement (NAK) has been received.

o The receiver storage buffer keeps all the damaged frames on hold until the frame in error
is correctly received.

o The receiver must have an appropriate logic for reinserting the frames in a correct order.

o The sender must consist of a searching mechanism that selects only the requested frame
for retransmission.

What is a multiple access protocol?

When a sender and receiver have a dedicated link to transmit data packets, the data link control is
enough to handle the channel. Suppose there is no dedicated path to communicate or transfer the
data between two devices. In that case, multiple stations access the channel and simultaneously
transmits the data over the channel. It may create collision and cross talk. Hence, the multiple
access protocol is required to reduce the collision and avoid crosstalk between the channels.
For example, suppose that there is a classroom full of students. When a teacher asks a question,
all the students (small channels) in the class start answering the question at the same time
(transferring the data simultaneously). All the students respond at the same time due to which
data is overlap or data lost. Therefore it is the responsibility of a teacher (multiple access
protocol) to manage the students and make them one answer.

A. Random Access Protocol

In this protocol, all the station has the equal priority to send the data over a channel. In random
access protocol, one or more stations cannot depend on another station nor any station control
another station. Depending on the channel's state (idle or busy), each station transmits the data
frame. However, if more than one station sends the data over a channel, there may be a collision
or data conflict. Due to the collision, the data frame packets may be lost or changed. And hence,
it does not receive by the receiver end.

ALOHA Random Access Protocol

It is designed for wireless LAN (Local Area Network) but can also be used in a shared medium
to transmit data. Using this method, any station can transmit data across a network
simultaneously when a data frameset is available for transmission.

Aloha Rules

1. Any station can transmit data to a channel at any time.

2. It does not require any carrier sensing.

3. Collision and data frames may be lost during the transmission of data through multiple
stations.
4. Acknowledgment of the frames exists in Aloha. Hence, there is no collision detection.

5. It requires retransmission of data after some random amount of time.

Pure Aloha

Whenever data is available for sending over a channel at stations, we use Pure Aloha. In pure
Aloha, when each station transmits data to a channel without checking whether the channel is
idle or not, the chances of collision may occur, and the data frame can be lost. When any station
transmits the data frame to a channel, the pure Aloha waits for the receiver's acknowledgment. If
it does not acknowledge the receiver end within the specified time, the station waits for a random
amount of time, called the backoff time (Tb). And the station may assume the frame has been
lost or destroyed. Therefore, it retransmits the frame until all the data are successfully transmitted
to the receiver.

1. The total vulnerable time of pure Aloha is 2 * Tfr.

2. Maximum throughput occurs when G = 1/ 2 that is 18.4%.

3. Successful transmission of data frame is S = G * e ^ - 2 G.

As we can see in the figure above, there are four stations for accessing a shared channel and
transmitting data frames. Some frames collide because most stations send their frames at the
same time. Only two frames, frame 1.1 and frame 2.2, are successfully transmitted to the receiver
end. At the same time, other frames are lost or destroyed. Whenever two frames fall on a shared
channel simultaneously, collisions can occur, and both will suffer damage. If the new frame's
first bit enters the channel before finishing the last bit of the second frame. Both frames are
completely finished, and both stations must retransmit the data frame.

Slotted Aloha

The slotted Aloha is designed to overcome the pure Aloha's efficiency because pure Aloha has a
very high possibility of frame hitting. In slotted Aloha, the shared channel is divided into a fixed
time interval called slots. So that, if a station wants to send a frame to a shared channel, the
frame can only be sent at the beginning of the slot, and only one frame is allowed to be sent to
each slot. And if the stations are unable to send data to the beginning of the slot, the station will
have to wait until the beginning of the slot for the next time. However, the possibility of a
collision remains when trying to send a frame at the beginning of two or more station time slot.

1. Maximum throughput occurs in the slotted Aloha when G = 1 that is 37%.

2. The probability of successfully transmitting the data frame in the slotted Aloha is S = G *
e ^ - 2 G.

3. The total vulnerable time required in slotted Aloha is Tfr.

CSMA (Carrier Sense Multiple Access)

It is a carrier sense multiple access based on media access protocol to sense the traffic on a
channel (idle or busy) before transmitting the data. It means that if the channel is idle, the station
can send data to the channel. Otherwise, it must wait until the channel becomes idle. Hence, it
reduces the chances of a collision on a transmission medium.

CSMA Access Modes

1-Persistent: In the 1-Persistent mode of CSMA that defines each node, first sense the shared
channel and if the channel is idle, it immediately sends the data. Else it must wait and keep track
of the status of the channel to be idle and broadcast the frame unconditionally as soon as the
channel is idle.

Non-Persistent: It is the access mode of CSMA that defines before transmitting the data, each
node must sense the channel, and if the channel is inactive, it immediately sends the data.
Otherwise, the station must wait for a random time (not continuously), and when the channel is
found to be idle, it transmits the frames.
P-Persistent: It is the combination of 1-Persistent and Non-persistent modes. The P-Persistent
mode defines that each node senses the channel, and if the channel is inactive, it sends a frame
with a P probability. If the data is not transmitted, it waits for a (q = 1-p probability) random
time and resumes the frame with the next time slot.

O- Persistent: It is an O-persistent method that defines the superiority of the station before the
transmission of the frame on the shared channel. If it is found that the channel is inactive, each
station waits for its turn to retransmit the data.

CSMA/ CD

It is a carrier sense multiple access/ collision detection network protocol to transmit data
frames. The CSMA/CD protocol works with a medium access control layer. Therefore, it first
senses the shared channel before broadcasting the frames, and if the channel is idle, it transmits a
frame to check whether the transmission was successful. If the frame is successfully received, the
station sends another frame. If any collision is detected in the CSMA/CD, the station sends a
jam/ stop signal to the shared channel to terminate data transmission. After that, it waits for a
random time before sending a frame to a channel.
CSMA/ CA

It is a carrier sense multiple access/collision avoidance network protocol for carrier

transmission of data frames. It is a protocol that works with a medium access control layer.
When a data frame is sent to a channel, it receives an acknowledgment to check whether the
channel is clear. If the station receives only a single (own) acknowledgments, that means the data
frame has been successfully transmitted to the receiver. But if it gets two signals (its own and
one more in which the collision of frames), a collision of the frame occurs in the shared channel.
Detects the collision of the frame when a sender receives an acknowledgment signal.

Following are the methods used in the CSMA/ CA to avoid the collision:

Interframe space: In this method, the station waits for the channel to become idle, and if it gets
the channel is idle, it does not immediately send the data. Instead of this, it waits for some time,
and this time period is called the Interframe space or IFS. However, the IFS time is often used
to define the priority of the station.

Contention window: In the Contention window, the total time is divided into different slots.
When the station/ sender is ready to transmit the data frame, it chooses a random slot number of
slots as wait time. If the channel is still busy, it does not restart the entire process, except that it
restarts the timer only to send data packets when the channel is inactive.

Acknowledgment: In the acknowledgment method, the sender station sends the data frame to
the shared channel if the acknowledgment is not received ahead of time.