TE EXTC Digital Communication Sem - V

Module – 2
=============================================
Error Detection Codes:
The binary information is transferred from one location to another location through some
communication medium. The external noise can change bits from 1 to 0 or 0 to 1. This change
in values changes the meaning of the actual message and is called an error. For efficient data
transfer, there should be error detection and correction codes. An error detection code is a
binary code that detects digital errors during transmission. To detect errors in the received
message, we add some extra bits to the actual data.
Without the addition of redundant bits, it is not possible to detect errors in the received
message. There are 3 ways in which we can detect errors in the received message:
1. Parity Bit
2. Checksum
3. Cyclic Redundancy Check (CRC)
What is parity bit?
A parity bit is an extra bit that is added to the message bits or data-word bits on the sender
side. Data-word bits along with parity bits is called a codeword. The parity bit is added to the
message bits on the sender side, to help in error detection at the receiver side.
Parity Bit Method
We’ll be understanding the parity bit method in this article in depth:
A parity bit is an extra bit included in the binary message to make a total number of 1’s either
odd or even. Parity word denotes the number of 1’s in a binary string. There are two parity
systems – even and odd parity checks.
Even Parity
Total number of 1’s in the given data bit should be even. So if the total number of 1’s in the
data bit is odd then a single 1 will be appended to make total number of 1’s even else 0 will be
appended(if total number of 1’s are already even). Hence, if any error occurs, the parity check
circuit will detect it at the receiver’s end. Let’s understand this with example, see the below
diagram .

In the above image, as we can see the data bits are ‘1011000’ and since this is even parity check
that we’re talking about, 1 will be appended as the parity bit (highlighted in red) to make total
count of 1’s even in the data sent. So here, our parity bit is 1. If the total count of 1 in the
given data bits were already even, then 0 would’ve been appended.

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 1

 TE EXTC Digital Communication Sem - V

Odd Parity
In odd parity system, if the total number of 1’s in the given binary string (or data bits) are even
then 1 is appended to make the total count of 1’s as odd else 0 is appended. The receiver
knows that whether sender is an odd parity generator or even parity generator. Suppose if
sender is an odd parity generator then there must be an odd number of 1’s in received binary
string. If an error occurs to a single bit that is either bit is changed to 1 to 0 or 0 to 1, received
binary bit will have an even number of 1’s which will indicate an error.
Take reference from fig(1.1) and rather than appending the 1 as parity bit, append 0 because
total number of 1’s are already odd.

Example:

Figure – Error Detection with Odd Parity Bit

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 2

 TE EXTC Digital Communication Sem - V

Advantages of Parity Bit Method

 Parity bit method is a promising method to detect any odd bit error at the receiver side.
 Overhead in data transmission is low, as only one parity bit is added to the message bits at
sender side before transmission.
 Also, this is a simple method for odd bits error detection.
Disadvantages of Parity Bit Method
 The limitation of this method is that only error in a odd number of bits are identified and
we also cannot determine the exact location of error in the data bit, therefore, error
correction is not possible in this method.
 If the number of bits in even parity check increase or decrease (data changed) but remained
to be even then it won’t be able to detect error as the number of bits are still even and same
goes for odd parity check.
See the below image for more details :

In the above example, the the data bits has been changed but as we can see the total count of
1’s remain to be even, the error can’t be detected even though the message’s meaning has been
changed. You can visualize the same for odd parity check the number of 1’s will remain odd,
even if the data bits have been changed and the odd parity check won’t be able to detect error.

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 3

 TE EXTC Digital Communication Sem - V
Points to Remember
 In 1’s complement of signed number +0 and -0 has two different representation.
 The range of signed magnitude representation of an 8-bit number in which 1-bit is used as a
signed bit as follows -2 7 to +27.
 Floating point number is said to be normalized if most significant digit of mantissa is one.
For example, 6-bit binary number 001101 is normalized because of two leading 0’s.
 Booth algorithm that uses two n bit numbers for multiplication gives results in 2n bits.
 The booth algorithm uses 2’s complement representation of numbers and work for both
positive and negative numbers.
 If k-bits are used to represent exponent then bits number = (2 k-1) and range of exponent = –
(2k-1 -1) to (2k-1).
Conclusion
Parity bit method is a simple method which uses only one bit extra parity with the message
bits to make codeword at sender side. It is used to detect errors of odd number of bits at
receiver side. However, it can neither detect errors of even number of bits, nor can it correct
any detected error as the location of bits where error occurred can’t be identified in this
method.

What is ARQ (Automatic Repeat Request)?

ARQ stands for Automatic Repeat Request also known as Automatic Repeat Query. ARQ is an error-
control strategy used in a two-way communication system. It is a group of error-control protocols to
achieve reliable data transmission over an unreliable source or service. These protocols reside in the
Transport Layer and Data Link Layer of the OSI(Open System Interconnection) model . These protocols
are responsible for the automatic retransmission of packets that are found to be corrupted or lost during
the transmission process.
Working Principle of Automatic Repeat Request
The main function of these protocols is, that the sender receives an acknowledgment from the receiver end
implying that the frame or packet is received correctly before a timeout occurs, timeout is a specific period
within which the acknowledgment has to be sent by the receiver to the sender. If a timeout occurs, then
the sender does not receive the acknowledgment before the specified time, it is implied that the frame or
packet has been corrupt or lost during the transmission. Accordingly, the sender retransmits the packet and
these protocols ensure that this process is repeated until the correct packet is transmitted.

Applications

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 4

 TE EXTC Digital Communication Sem - V
ARQ protocols have a wide range of applications as they provide reliable transmissions over unreliable
upper sources. These protocols are mainly functional on shortwave radio to ensure reliable delivery of
signals. For the same function of ARQ, there are various applications.
 Transmission Control Protocol (TCP)
 Specific Service Orientation Protocol: Error-correction of message signals in ATM networks.
 High-Level Data Link protocol .
 IBM Binary synchronous Communications Protocol.
 Xmodem: Modem file transfer protocol.

Types of ARQ
There are several types of ways in which these protocols function in the data link layer:

Stop And Wait ARQ

Stop and wait ARQ is also referred to as the alternating protocol is a method used in two-way
communication systems to send information between two connected devices (sender and a receiver). It is
referred to as stop and wait ARQ because the function of this protocol is to send one frame at a
time. After sending a frame or packet, the sender doesn’t send any further packets until it receives an
acknowledgement from the receiver. Moreover, the sender keeps a copy of the sent packet. After receiving
the desired frame, the receiver sends an acknowledgement. If the acknowledgement does not reach the
sender before the specified time, known as the timeout, the sender sends the same packet again. The
timeout is reset after each frame transmission. The above scenario depicts a Stop and wait situation, so
this control mechanism is termed as Stop and wait ARQ.

Go Back-N ARQ
Go-Back-N ARQ is a type of the ARQ protocol, in which the sending process continues to send several
frames or packets even without receiving an acknowledgement packet from the receiver . The
receiver process keeps track of the sequence number of the next packet it expects to receive and sends that
sequence number with every acknowledgement to the sender. The receiver will remove any packet that
does not have the desired sequence number it expects and will resend an acknowledgement for the last
correct frame. There are only two possibilities that a frame won’t match the sequence number: it is either a
duplicated frame of an existing frame or an out-of-order frame that needs to be sent later, the receiver
recognizes this scenario and sends an acknowledgement signal accordingly. Once the sender has sent all
of the frames in its window, it will identify that all of the frames since the first lost frame, and will go
back to the sequence number of the last acknowledgement signal that it received from the receiver pr
and continue the process over again. The only drawback of this type of system is that it results in sending
packets multiple times: if any frame was lost or found to be corrupted, then that frame and all following
frames in the send window will be re-transmitted. This protocol is more efficient than Stop and wait
ARQ as there is no waiting time.

Selective Repeat ARQ/Selective Reject ARQ

Selective Repeat ARQ/Selective Reject ARQ protocol mechanism is similar to the Go-Back-N protocol
mechanism but in Selective Repeat ARQ the sending process continues even after a frame is found to be
corrupt or lost. This is achieved with the receiver process keeps track of the sequence number of the
earliest frame it has not received and sends the respective sequence number with the acknowledgement
signal. If a frame is not received at the receiver end, the sender continues to send the succeeding frames
until it has emptied its window. once this error-correction process has been done, the process continues
where it left off. Unlike, Go back-N protocol this does not send a packet multiple times.

What is the Difference Between TCP and ARQ?

TCP (Transmission Control Protocol)

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 5

 TE EXTC Digital Communication Sem - V
is like a super careful friend. When they get your note, they check every word and send a thumbs-up if
everything looks good. If part of the note is missing or smudged, they ask you to resend that part until it’s
perfect.
ARQ (Automatic Repeat Request)
is like a friend who just asks you to resend the note if they can’t read it. They don’t check every word as
carefully as TCP, but they will ask for another copy if something doesn’t make sense.
ARQ (Automatic Repeat
Aspect TCP (Transmission Control Protocol) Request)

Transport Layer and Data Link

Layer Transport Layer
Layer

Comprehensive protocol including error

Primarily focuses on error detection
Functionality detection, correction, flow control, and
and correction
congestion control

Uses a combination of ARQ mechanisms

Uses specific ARQ mechanisms
(Stop and Wait, Go-Back-N, Selective
Mechanism such as Stop and Wait, Go-Back-N,
Repeat) along with flow and congestion
and Selective Repeat
control

Incorporates flow control mechanisms to

Does not inherently include flow
Flow Control prevent sender from overwhelming the
control mechanisms
receiver

Congestion Includes congestion control algorithms to Does not inherently include

Control manage network traffic and avoid congestion congestion control

Sequence numbers are used in

Sequence Uses sequence numbers for packets to ensure
ARQ protocols to keep track of
Numbering correct order and detect duplicates
frames and retransmissions

Ensures reliable delivery of data through Ensures reliable delivery through

Reliability acknowledgments, retransmissions, and retransmissions upon detecting
sequence numbering errors or losses

Uses checksums, sequence numbers, and Uses acknowledgments and

Error
acknowledgments for error detection and timeouts to detect errors and
Handling
correction retransmit corrupted or lost frames

Widely used in internet communications, Used in various communication

Use Cases such as web browsing, email, and file systems, including shortwave radio
transfers and modem protocols

Advantages of ARQ
 The Error-detection and correction mechanisms are quite simple compared to the other techniques.
 A much simpler decoding equipment can be put to use compared to the other techniques.
Disadvantages of ARQ

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 6

 TE EXTC Digital Communication Sem - V
 A medium or a channel with a high error rate might cause too much transmission of the frames or
packets of information.
 The high error rate in the channel might also lead to loss of information, therefore reducing the
efficiency or the productivity of the system.
Conclusion
Whether you’re testing a program or sending messages, it’s important to make sure everything works just
right. Test doubles like stubs and mocks help programmers test parts of their code, while protocols like
TCP and ARQ help ensure that messages get through without mistakes. Knowing when to use these tools
can make things run smoothly.
DEFINITION

forward error correction (FEC)

What is forward error correction (FEC)?

Forward error correction (FEC) is a method for obtaining error control in data transmission in which the
source (transmitter) sends redundant data and the destination (receiver) recognizes only the portion of the
data that contains no apparent errors. When FEC is used in data transmissions, the receiver can detect and
correct a limited number of errors. If there are too many errors, the sender must retransmit the packets that
contain the errors.
FEC does not require handshaking between the source and the destination, which means that the two
systems do not need to establish a connection before data can be transmitted. This makes it possible to
broadcast data to multiple destinations simultaneously from a single source. In addition, FEC's ability to
correct errors means that less data needs to be retransmitted, reducing bandwidth and power consumption.

Because of its error-correcting capabilities, FEC is commonly implemented when transmitting data
over noisy or unreliable communication channels, making it suitable for both wired and wireless
communications. For example, FEC provides an efficient solution for streaming video content or supporting
cellular networks. It can also be used by modems and routers, support cable and optic communications, and
facilitate one-way data transmissions.

How does forward error correction work?

In the simplest form of FEC, the transmitter sends each character multiple times to provide a safeguard
against lost or corrupted data. The receiver compares the character instances and, if there are discrepancies,
uses a "majority rules" system to recover the data. For example, the transmitted data might include the
capital letter W, which has a binary value of 01010111. If the transmitter were to send the W byte three
times, the receiver would compare the bits in each byte instance to determine which bits are accurate, as
shown in

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 7

 TE EXTC Digital Communication Sem - V

In this case, there are two errors in the data when it arrives at the receiver. The fifth bit in the second
character instance is different from the other two bits in that position, and the second bit in the third instance
is different from the other two in its position. For each bit position, the receiver compares the bits. If all
three are the same, that value is considered the correct bit. If one value is different from the other two, the
two majority values are considered the correct bit.

The exact process used for FEC-based communications varies from one system to the next. At a
high level, however, they generally follow a similar approach. The transmitter uses some type
of encoder to add the necessary parity data to the original data, and the receiver uses some type
of decoder to extract the original data from the transmitted data while correcting errors in the
process. Figure 2 provides a simplified overview of how this works.

Forward Error Correction (FEC) vs Automatic

Repeat Request (ARQ)
Forward Error Correction (FEC)
FEC is a method of obtaining error control in data transmission where the source (transmitter) sends
redundant data and the destination (receiver) recognizes only the portion of the data that contains no
apparent errors.
Key characteristics of FEC include:
 Error detection and correction: FEC can both detect and correct errors without needing a reverse channel to request
retransmission of data.
 Redundancy: FEC adds redundancy to the transmitted information using an algorithm.
 No retransmission: FEC does not require retransmission of data, which makes it suitable for real-time applications or
systems where retransmissions are costly.
Automatic Repeat Request (ARQ)

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 8

 TE EXTC Digital Communication Sem - V
ARQ, on the other hand, is a protocol for error control in data transmission. When the receiver detects an
error in a packet, it automatically requests the transmitter to resend the packet.
Key characteristics of ARQ include:
 Error detection: ARQ can detect errors, but it cannot correct them.
 Retransmission: If an error is detected, ARQ requests retransmission of the data.
 Acknowledgement: ARQ uses acknowledgements (ACKs) and timeouts to ensure data delivery.

Key Difference
The key difference between FEC and ARQ lies in how they handle errors:
 FEC corrects errors by using the redundant data that was transmitted along with the original data. It does not require
retransmission of data.
 ARQ, however, does not correct errors. Instead, it detects errors and requests retransmission of the erroneous data.
Here is a comparison table for a quick overview:
Forward Error Correction (FEC)Automatic Repeat Request (ARQ)

Error Correction Yes No

Error Detection Yes Yes

Retransmission No Yes

Use of Redundancy Yes No

Use of
No Yes
Acknowledgement

In conclusion, the choice between FEC and ARQ depends on the specific requirements of your
communication system, such as the acceptable error rate, the availability of a reverse channel, and the cost
of retransmissions.

Vertical Redundancy Check (VRC) or Parity Check

Vertical Redundancy Check is also known as Parity Check. In this method, a redundant bit also called
parity bit is added to each data unit. This method includes even parity and odd parity. Even parity means
the total number of 1s in data is to be even and odd parity means the total number of 1s in data is to be
odd. Example - If the source wants to transmit data unit 1100111 using even parity to the destination. The
source will have to pass through Even Parity Generator.

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 9

 TE EXTC Digital Communication Sem - V
Parity generator will count number of 1s in data unit and will add parity bit. In the above example, number
of 1s in data unit is 5, parity generator appends a parity bit 1 to this data unit making the total number of
1s even i.e 6 which is clear from above figure. Data along with parity bit is then transmitted across the
network. In this case, 11001111 will be transmitted. At the destination, This data is passed to parity
checker at the destination. The number of 1s in data is counted by parity checker. If the number of 1s
count out to be odd, e.g. 5 or 7 then destination will come to know that there is some error in the data. The
receiver then rejects such an erroneous data unit.
Advantages :
 VRC can detect all single bit error.
 It can also detect burst errors but only in those cases where number of bits changed is odd, i.e. 1, 3, 5,
7, .......etc.
 VRC is simple to implement and can be easily incorporated into different communication protocols
and systems.
 It is efficient in terms of computational complexity and memory requirements.
 VRC can help improve the reliability of data transmission and reduce the likelihood of data corruption
or loss due to errors.
 VRC can be combined with other error detection and correction techniques to improve the overall
error handling capabilities of a system.
Disadvantages :
 The major disadvantage of using this method for error detection is that it is not able to detect burst
error if the number of bits changed is even, i.e. 2, 4, 6, 8, .......etc.
 Example - If the original data is 1100111. After adding VRC, data unit that will be transmitted is
11001111. Suppose on the way 2 bits are 01011111. When this data will reach the destination, parity
checker will count number of 1s in data and that comes out to be even i.e. 8. So, in this case, parity is
not changed, it is still even. Destination will assume that there is no error in data even though data is
erroneous.
 VRC is not capable of correcting errors, only detecting them. This means that it can identify errors, but
it cannot fix them.
 VRC is not suitable for applications that require high levels of error detection and correction, such as
mission-critical systems or safety-critical applications.
 VRC is limited in its ability to detect and correct errors in large blocks of data, as the probability of
errors increases with the size of the data block.
 VRC requires additional overhead bits to be added to the data stream, which can increase the
bandwidth and storage requirements of the system.

Longitudinal Redundancy Check (LRC)/2-D Parity Check

Longitudinal Redundancy Check (LRC) is also known as 2-D parity check. In this method, data which the
user want to send is organised into tables of rows and columns. A block of bit is divided into table or
matrix of rows and columns. In order to detect an error, a redundant bit is added to the whole block and
this block is transmitted to receiver. The receiver uses this redundant row to detect error. After checking
the data for errors, receiver accepts the data and discards the redundant row of bits. Example : If a block
By Gauri Joshi VPM’s MPCOE, Velneshwar Page 10
 TE EXTC Digital Communication Sem - V
of 32 bits is to be transmitted, it is divided into matrix of four rows and eight columns which as shown in
the following figure :

Figure: LRC
In this matrix of bits, a parity bit (odd or even) is calculated for each column. It means 32 bits data plus 8
redundant bits are transmitted to receiver. Whenever data reaches at the destination, receiver uses LRC to
detect error in data. Advantage : LRC is used to detect burst errors. Example : Suppose 32 bit data plus
LRC that was being transmitted is hit by a burst error of length 5 and some bits are corrupted as shown in
the following figure :

Figure : Burst error & LRC

The LRC received by the destination does not match with newly corrupted LRC. The destination comes to
know that the data is erroneous, so it discards the data. Disadvantage : The main problem with LRC is
that, it is not able to detect error if two bits in a data unit are damaged and two bits in exactly the same
position in other data unit are also damaged. Example : If data 110011 010101 is changed to
010010110100.

Figure : Two bits at same bit position damaged in 2 data units

In this example 1st and 6th bit in one data unit is changed . Also the 1st and 6th bit in second unit is
changed.

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 11

 TE EXTC Digital Communication Sem - V

Error Detection Code – Checksum

Checksum is the error detection method used by upper-layer protocols and is considered to be more
reliable than Longitudinal Redundancy Check (LRC), Vertical Redundancy Check (VRC), and Cyclic
Redundancy Check (CRC). This method uses a Checksum Generator on the sender side and
a Checksum Checker on the receiver side.
It is a unique number generated from data to verify its integrity. When data is created, a checksum is
calculated and sent or saved with it. Later, when accessing the data, the checksum is recalculated. If the
two checksums match, the data is likely error free. In this article we will see checksum error detection
method in detail.
How Checksum Works?
On the Sender side, the data is divided into equal subunits of n bit length by the checksum generator. This
bit is generally of 16-bit length. These subunits are then added together using one’s complement method.
This sum is of n bits. The resultant bit is then complemented. This complemented sum which is called
checksum is appended to the end of the original data unit and is then transmitted to the receiver.

The Receiver after receiving data + checksum passes it to checksum checker. Checksum checker divides
this data unit into various subunits of equal length and adds all these subunits. These subunits also contain
checksum as one of the subunits. The resultant bit is then complemented. If the complemented result is
zero, it means the data is error-free. If the result is non-zero it means the data contains an error and
Receiver rejects it.
What are the Factors that Cause Inconsistent Checksum Number?
Whenever checksum values doesn’t matches, it seems that some disturbance happened in the data during
transmission. There are several factors which can create disturbance are mentioned below:
 Interruption in the network connection can create inconsistent checksum number.
 Issue in the storage space or hard drives can also lead to problem in checksum.
 Corrupted Disk and Corrupted FIle can lead to error in Checksum.
 If a third party inferns while transferring the data, it can also lead to checksum.
Example – If the data unit to be transmitted is 10101001 00111001, the following procedure is used
at Sender site and Receiver site.
Sender Site:
10101001 subunit 1
00111001 subunit 2
11100010 sum (using 1s complement)
00011101 checksum (complement of sum)
Data transmitted to Receiver is:

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 12

 TE EXTC Digital Communication Sem - V

Checksum – Example

Receiver Site:
10101001 subunit 1
00111001 subunit 2
00011101 checksum
11111111 sum
00000000 sum's complement

Result is zero, it means no error.

Example – If the data transmitted along with checksum is 10101001 00111001 00011101. But the
data received at destination is 00101001 10111001 00011101.
Receiver Site:
00101001 1st bit of subunit 1 is damaged
10111001 1st bit of subunit 2 is damaged
00011101 checksum
11111111 sum
00000000 Ok 1's complement
Although data is corrupted, the error is undetected.
Advantages of Checksum
 Error Detection: It helps detect data corruption during transmission or storage, ensuring the data
received is correct.
 Simple and Fast: Easy to implement with quick calculations, making it ideal for real-time
applications like network transfers.
 Less Resources: Requires minimal computing resources, so it doesn’t slow down the system.
Disadvantages of Checksum
 Limited Detection: It may miss certain types of errors, such as bit rearrangements or specific patterns
of corruption.
 No Error Correction: It can only detect errors but cannot fix or recover corrupted data.
 Not Secure: Checksum algorithms are not designed for security and can be easily manipulated by
attackers.

Cyclic Redundancy Check and Modulo-2 Division

Cyclic Redundancy Check or CRC is a method of detecting accidental changes/errors in the
communication channel. CRC uses Generator Polynomial which is available on both sender and receiver
side.
An example generator polynomial is of the form like x3 + x + 1. This generator polynomial represents key
1011. Another example is x2 + 1 that represents key 101.
There are two primary variables in CRC:
 n: Number of bits in data to be sent from sender side
 k: Number of bits in the key obtained from generator polynomial.
Encoded Data Generation from Generator Polynomial (Sender Side)
 The binary data is first augmented by adding k-1 zeros in the end of the data.
 Then, modulo - 2 binary division is used to divide binary data by the key and remainder of division is
stored.
 At last the the remainder is appended at the end of the data to form the encoded data which is later
sent.
Checking Error in Transmission (Receiver Side)
 After receiving the data, to check if the data is error free, perform the modulo-2 division again.

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 13

 TE EXTC Digital Communication Sem - V
 If the remainder is 0, then there are not errors, otherwise, the data is faulty and contain transmission
errors.
Modulo 2 Division
The process of modulo-2 binary division is the same as the familiar division process we use for decimal
numbers. Just that instead of subtraction, we use XOR here.
 In each step, a copy of the divisor (or data) is XORed with the k bits of the dividend (or key).
 The result of the XOR operation (remainder) is (n-1) bits, which is used for the next step after 1 extra
bit is pulled down to make it n bits long.
 When there are no bits left to pull down, we have a result. The (n-1)-bit remainder which is appended
at the sender side.
Examples:
Case 1: No error in transmission
Data = 100100, Generator Polynomial (Key) = x3 + x2 + 1 (1101)
Sender Side

The remainder is 001. Thus the data sent is 100100001.

Receiver Side
Code word received at the receiver side 100100001

The remainder is 0, hence the data received has no errors.

CRC Implementation - O(n) Time and O(n) Space
Case 2: Error in Transmission
Data = 100100, Generator Polynomial (Key) = x3 + x2 + 1 (1101)

Sender Side

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 14

 TE EXTC Digital Communication Sem - V

The remainder is 001. Thus the data sent is 100100001.

Receiver Side
Let there be an error and code word received at the receiver side 100000001.

As the remainder is not 0, hence there is some error detected in the receiver side.
Implementation of Cyclic Redundancy Check
The idea is to firstly generate the encoded data by appending the remainder of modulo - 2 division of data
and key in the given data. Then, repeat the same process for the data received, and if the decoded data
contains any '1', then there is some error in transmission, otherwise the correct data is received.
Follow the below given step-by-step process:
 Start by appending n-1 zeroes to data to form a new string str, where n is the length of key.
 Compute the remainder by calling mod2div with dividend set to str and divisor set to key. In mod2div,
first slice dividend to the length of divisor, then repeatedly perform the following:
o If the first character of the current slice (tmp) is '1', call findXor with divisor and tmp;
otherwise, call findXor with a string of pick zeroes and tmp.
o Append the next bit of dividend to the result and increment pick.
 The function findXor calculates the XOR of two strings a and b by traversing from index 1 to the end:
if corresponding bits are the same, it appends "0" to result, otherwise "1".
 After processing the entire dividend, mod2div returns the final remainder. Append this remainder to
data to form the encoded codeword.
 At the receiver side, extract the first n bits of code and perform mod2div with key to obtain curXor.
Then, while cur is not equal to code.size, if curXor’s length is not equal to key’s length, append the
next bit from code; otherwise, update curXor by performing mod2div on it.
 Finally, if curXor’s length equals key’s length, perform a final mod2div. If curXor contains any '1', the
data is incorrect; otherwise, the data is correct.

By Gauri Joshi VPM’s MPCOE, Velneshwar Page 15