Semester III

BCA312 Computer Networks

(Unit-4)
 Error Detection and Correction Codes

• What is an Error
– 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:
– Single-Bit Error
– 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 given figure, the message which is sent is corrupted as single-bit, i.e., 0 bit is
changed to 1.
– 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 occur in Serial Data
Transmission.
– The number of affected bits depends on the duration of
the noise and data rate.
 Error Detection and Correction codes

• Error detection and correction code plays an important role in

the transmission of data from one source to another. The
noise also gets added into the data when it transmits from
one system to another, which causes errors in the received
binary data at other systems. The bits of the data may
change(either 0 to 1 or 1 to 0) during transmission.
• It is impossible to avoid the interference of noise, but it is
possible to get back the original data. For this purpose, we
first need to detect either an error is present or not using
error detection codes. If the error is present in the code, then
we will correct it with the help of error correction codes.
 Error Detecting Codes

• The error detection codes are the code used for detecting the
error in the received data bit stream. In these codes, some
bits are included appended to the original bit stream.
• Error detecting codes encode the message before sending it
over the noisy channels. The encoding scheme is performed in
such a way that the decoder at the receiving can find the
errors easily in the receiving data with a higher chance of
success. Error detecting codes are:
– Single parity check
– Two-dimensional parity check
– Checksum
– Cyclic redundancy check
 Single Parity Check
• Single Parity checking is the simple mechanism and
inexpensive to detect the errors.
• 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.
• 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.
• At the receiving end, the parity bit is calculated from the
received data bits and compared with the received parity bit.
• This technique generates the total number of 1s even, so it is
known as even-parity checking.
 Two-Dimensional Parity Check
• Performance can be improved by using Two-Dimensional
Parity Check which organizes the data in the form of a table.
• Parity check bits are computed for each row, which is
equivalent to the single-parity check.
• 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.
• At the receiving end, the parity bits are compared with the
parity bits computed from the received data.
• Checksum
Error detection using checksum method involves the following
steps-
Step-01:
At sender side,
• If m bit checksum is used, the data unit to be transmitted is
divided into segments of m bits.
• All the m bit segments are added.
• The result of the sum is then complemented using 1’s
complement arithmetic.
• The value so obtained is called as checksum.
 Step-02:
• The data along with the checksum value is transmitted
to the receiver.
Step-03:
At receiver side,
• If m bit checksum is being used, the received data unit
is divided into segments of m bits.
• All the m bit segments are added along with the
checksum value.
• The value so obtained is complemented and the result
is checked.
• Then, following two cases are possible-
Case-01: Result = 0
• If the result is zero,
• Receiver assumes that no error occurred in the data during
the transmission.
• Receiver accepts the data.
Case-02: Result ≠ 0
• If the result is non-zero,
• Receiver assumes that error occurred in the data during the
transmission.
• Receiver discards the data and asks the sender for
retransmission.
• Checksum Example-

Consider the data unit to be transmitted is-

10011001111000100010010010000100

Consider 8 bit checksum is used.

Step-01:
At sender side,
The given data unit is divided into segments of 8 bits as-
• Now, all the segments are added and the result is obtained as-
 Cyclic Redundancy Check
• CRC is based on binary division.
• In CRC, a sequence of redundant bits, called cyclic redundancy
check bits, are appended to the end of data unit so that the
resulting data unit becomes exactly divisible by a second,
predetermined binary number.
• At the destination, the incoming data unit is divided by the
same number. If at this step there is no remainder, the data
unit is assumed to be correct and is therefore accepted.
• A remainder indicates that the data unit has been damaged in
transit and therefore must be rejected.
Example:
Suppose the original data is 11100 and divisor is 1001.
CRC Generator
• 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.
• Now, the string becomes 11100000, and the resultant string is
divided by the divisor 1001.
• The remainder generated from the binary division is known as CRC
remainder. The generated value of the CRC remainder is 111.
• 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
• The functionality of the CRC checker is similar to the CRC
generator.
• When the string 11100111 is received at the receiving end,
then CRC checker performs the modulo-2 division.
• A string is divided by the same divisor, i.e., 1001.
• In this case, CRC checker generates the remainder of zero.
Therefore, the data is accepted.
 Error correction code

• Error correction codes are generated by using the specific

algorithm used for removing and detecting errors from the
message transmitted over the noisy channels. The error-
correcting codes find the correct number of corrupted bits
and their positions in the message.

• One way of detecting and correcting error is Hamming Codes.

• Hamming Codes
– Hamming code is used to detect and correct the error in
the transmitted data. So, it is an error detection and
correction code. It was originally invented by Richard W.
Hamming in the year 1950. Hamming codes detect 1-bit
and 2-bit errors.
– While transmitting the message, it is encoded with the
redundant bits. The redundant bits are the extra bits that
are placed at certain locations of the data bits to detect
the error. At the receiver end, the code is decoded to
detect errors and the original message is received.
– So before transmitting, the sender has to encode the
message with the redundant bits. It involves three steps,
as described below:
1. Selecting the number of redundant bits:
– The hamming code uses the number of redundant bits
depending on the number of information bits in the
message.
– Let n be the number of information or data bits, then the
number of redundant bits P is determined from the
formula: 2P ≥ n + P + 1
– For example, if 4-bit information is to be transmitted, then
n=4. The number of redundant bits is determined by the
trial and error [Link] P=2, we get 22≥ 4 + 2 + 1
– The above equation implies 4 not greater than or equal to
7. So let’s choose another value of P=3.
23≥ 4 + 3 + 1
– Now, the equation satisfies the condition. So number of
redundant bits, P=3.
– In this way, the number of redundant bits is selected for
the number of information bits to be transmitted.
2. Choosing the location of redundant bits
– For the above example, the number of data bits n=4, and
the number of redundant bits P=3. So the message
consists of 7 bits in total that are to be coded. Let the
rightmost bit be designated as bit 1, the next successive bit
as bit 2 and so on.
– The seven bits are bit 7, bit 6, bit 5, bit 4, bit 3, bit 2, bit 1.
– In this, the redundant bits are placed at the positions that
are numbered corresponding to the power of 2, i.e., 1, 2,
4, 8,… Thus the locations of data bit and redundant bit
are D4, D3, D2, P3, D1, P2, P1.
3. Assigning the values to redundant bits
– Now it is time to assign bit value to the redundant bits in
the formed hamming code group. The assigned bits are
called a parity bit.

– Each parity bit will check certain other bits in the total
code group. It is one with the bit location table, as shown
here:
 – Parity bit P1 covers all data bits in positions whose binary
representation has 1 in the least significant position(001, 011, 101,
111, etc.). Thus P1 checks the bit in locations 1, 3, 5, 7, 9, 11, etc..
– Parity bit P2 covers all data bits in positions whose binary
representation has 1 in the second least significant position(010, 011,
110, 111, etc.). Thus P2 checks the bit in locations 2, 3, 6, 7, etc.
•
Bit Location 7 6 5 4 3 2 1
Bit designation D4 D3 D2 P3 D1 P2 P1
Binary
111 110 101 100 011 010 001
representation
Information /
D4 D3 D2 D1
Data bits
Parity bits P3 P2 P1
– Parity bit P3 covers all data bits in positions whose binary
representation has 1 in the third least significant
position(100, 101, 110, 111, etc.). Thus P3 checks the bit in
locations 4, 5, 6, 7, etc.

– Each parity bit checks the corresponding bit locations and

assign the bit value as 1 or 0, so as to make the number of
1s as even for even parity and odd for odd parity.
• Example:
Encode a binary word 11001 into the even parity hamming
code.
Given, number of data bits, n =5.
• To find the number of redundant bits:
Let us try P=4. 24 ≥ 5 + 4 + 1
– The equation is satisfied and so 4 redundant bits are
selected.
– So, total code bit = n+P = 9
– The redundant bits are placed at bit positions 1, 2, 4 and 8.
• Construct the bit location table:

Bit
Locati 9 8 7 6 5 4 3 2 1
on

Bit
design D5 P4 D4 D3 D2 P3 D1 P2 P1
ation
Binary
repres
1001 1000 0111 0110 0101 0100 0011 0010 0001
entati
on
Inform
ation 1 1 0 0 1
bits
Parity
1 1 0 1
bits
• To determine the parity bits
– For P1: Bit locations 3, 5, 7 and 9 have three 1s. To have
even parity, P1 must be 1.
– For P2: Bit locations 3, 6, 7 have two 1s. To have even
parity, P2 must be 0.
– For P3: Bit locations 5, 6, 7 have one 1s. To have even
parity, P3 must be 1.
– For P4: Bit locations 8, 9 have one 1s. To have even parity,
P4 must be 1.
– Thus the encoded 9-bit hamming code is 111001101.
• After receiving the encoded message, each parity bit along
with its corresponding group of bits are checked for proper
parity. While checking, the correct result of individual parity is
marked as 0 and the wrong result is marked as 1.
• After checking all the parity bits, a binary word is formed
taking the result bits for P1 as LSB. So formed binary word
gives the bit location, where there is an error.
• If the formed binary word has 0 bits, then there is no error in
the message.
• Let us assume the even parity hamming code from the above
example (111001101) is transmitted and the received code is
(110001101). Now from the received code, let us detect and
correct the error.

• To detect the error, let us construct the bit location table.

Bit
Locati 9 8 7 6 5 4 3 2 1
on
Bit
design D5 P4 D4 D3 D2 P3 D1 P2 P1
ation
Binary
repres
1001 1000 0111 0110 0101 0100 0011 0010 0001
entati
on
Receiv
ed 1 1 0 0 0 1 1 0 1
code
• Checking the parity bits
• For P1 : Check the locations 1, 3, 5, 7, 9. There is three 1s in
this group, which is wrong for even parity. Hence the bit value
for P1 is 1.
• For P2 : Check the locations 2, 3, 6, 7. There is one 1 in this
group, which is wrong for even parity. Hence the bit value for
P2 is 1.
• For P3 : Check the locations 4, 5, 6, 7. There is one 1 in this
group, which is wrong for even parity. Hence the bit value for
P3 is 1.
• For P4 : Check the locations 8, 9. There are two 1s in this
group, which is correct for even parity. Hence the bit value for
P4 is 0.
• The resultant binary word is 0111. It corresponds to the bit
location 7 in the above table. The error is detected in the data
bit D4. The error is 0 and it should be changed to 1. Thus the
corrected code is 111001101.
Cryptography
Cryptography is the technique of securing information by converting it into an unreadable form (ciphertext) so that only authorized users can access it.
What is Cipher?
A cipher is a technique that is used in transforming the readable data (plaintext) into coded data (ciphertext)
and the other way round. The first step in converting regular text into an unrecognizable form is encryption and
the process of converting the encoded text back into regular text is decryption. Ciphers are able to perform
these transformation using keys; specific pieces of information. It guarantees that only the right person can get
to the primary data.

Cipher working

Primary Terminologies
 Cipher: A method or a set of rules for performing encryption or decryption of information – a step by step
process.
 Encryption: The transformation of plaintext to the ciphertext through the use of a cipher.
 Decryption: The act of moving from the encrypted text to the original text.
 Plaintext: The source or plain data or text that has to be converted into cipher text before sending it over a
channel.
 Ciphertext: The coded message that cannot be comprehended in its original form without the usage of
decryption.
 Key: An item of data that a cipher employs to engage in the conversion of plaintext into ciphertext and vice
versa.
How Ciphers Work?
Ciphers work by rearranging readable information (plaintext) in another form of information called ciphertext by
use of a process that is known as encryption and this involves use of a certain key. Shifting of the plaintext is
controlled by this key which operates like a password. Decryption is the process of recuperating the initial text
from the cipher-text, which can be done only having the right key. This entitles the information to be secured
and released to the right personnel only. Various ciphers like substitution ciphers, transposition ciphers and
the modern algorithms employed in the contemporary AES and RSA modes, employ these methods to
perform the above transformation to improve security depending on the complexity of the key and the
algorithm in use.
What are Ciphers Used for?
Ciphers have a wide range of applications across various fields to ensure the security and integrity of
information:
 Secure Communications: Encryption of emails, instant messages, and VoIP convert messages to codes
that cannot be understandable to an unauthorized person and thus allow only the target receiver to be able
to read the message.
 Protect Financial Transactions: Secure Internet connection, which is applied in online banking and e-
commerce, uses encryption to safeguard consumers’ private data and, in particular, their credit card
numbers and other personal data, against scammers.
 Safeguard Data Storage: Encryption is applied for safeguard of data which is stored in devices, servers
and even in cloud. This guarantees that even in cases where the disks on which data is stored are lost or
mobile phone is stolen, the content of it cannot be accessed without the Decryption Key.
 Ensure Authentication: The authentication protocols entail the use of encryption to be able to identify the
user and or devices. It also assist in avoiding fraudulent communications and transaction, thereby securing
the communications from unauthorized access.
 Enable Secure Digital Signatures: Digital signals are implemented using encryption to reduce the
reliability of documents and messages that are transmitted electronically. This makes sure that it has not
been interfered with and that it is original from the source that has the information.
Types of Ciphers
Ciphers can be broadly classified into three categories: Among the types of ciphers there are substitution
ciphers, transposition ciphers, and modern ciphers.

1. Substitution Ciphers

Substitution ciphers involve replacing each member of the plaintext with another member which can be of the
same set. One of the early examples of the substitution technique is the Caesar cipher that got its name from
Julius Caesar, who allegedly employed it in his secret letters.
Caesar Cipher
The Caesar cipher is a substitution cipher where each letter in the plaintext is replaced by another letter
shifted a fixed number of positions down the alphabet.

2. Transposition Ciphers

Transposition ciphers are those forms of ciphers that work on the principle of shifting the positions of the
characters of the plaintext to create the ciphertext. While in substitution ciphers the actual letters are replaced,
in transposition ciphers the letters’ positions are changed instead.
Rail Fence Cipher
In the Rail Fence Cipher, the plaintext is arranged in a manner of a zigzag pattern on the number of ‘rails’ and
then read row-wise.
Columnar Transposition Cipher
In Columnar Transposition Cipher, the plaintext is written into rows under a certain key. The columns are then
arranged in order of the key names by using the sort function.

Caesar cipher
The Caesar cipher is a simple encryption technique that was used by Julius Caesar to send secret messages to
his allies. It works by shifting the letters in the plaintext message by a certain number of positions, known as the
"shift" or "key". The Caesar Cipher technique is one of the earliest and simplest methods of encryption techniques.
It's simply a type of substitution cipher, i.e., each letter of a given text is replaced by a letter with a fixed number of
positions down the alphabet. For example with a shift of 1, A would be replaced by B, B would become C, and so
on. The method is apparently named after Julius Caesar, who apparently used it to communicate with his officials.

Cryptography Algorithm For the Caesar Cipher

 Thus to cipher a given text we need an integer value, known as a shift which indicates the number of positions
each letter of the text has been moved down.
The encryption can be represented using modular arithmetic by first transforming the letters into numbers,
according to the scheme, A = 0, B = 1,..., Z = 25. Encryption of a letter by a shift n can be described
mathematically as.
 For example, if the shift is 3, then the letter A would be replaced by the letter D, B would become E, C would
become F, and so on. The alphabet is wrapped around so that after Z, it starts back at A.
 Here is an example of how to use the Caesar cipher to encrypt the message "HELLO" with a shift of 3:
1. Write down the plaintext message: HELLO
2. Choose a shift value. In this case, we will use a shift of 3.
3. Replace each letter in the plaintext message with the letter that is three positions to the right in the alphabet.
H becomes K (shift 3 from H)
E becomes H (shift 3 from E)
L becomes O (shift 3 from L)
L becomes O (shift 3 from L)
O becomes R (shift 3 from O)
[Link] encrypted message is now "KHOOR".
 To decrypt the message, you simply need to shift each letter back by the same number of positions. In this
case, you would shift each letter in "KHOOR" back by 3 positions to get the original message, "HELLO".

En(x)=(x+n)mod 26 En(x)=(x+n)mod 26
(Encryption Phase with shift n)
Dn(x)=(x−n)mod 26 Dn(x)=(x−n)mod 26
(Decryption Phase with shift n)
Examples :
Text : ABCDEFGHIJKLMNOPQRSTUVWXYZ
Shift: 23
Cipher: XYZABCDEFGHIJKLMNOPQRSTUVW

Text : ATTACKATONCE
Shift: 4
Cipher: EXXEGOEXSRGI

Advantages

 Easy to implement and use thus, making suitable for beginners to learn about encryption.
 Can be physically implemented, such as with a set of rotating disks or a set of cards, known as a scytale, which
can be useful in certain situations.
 Requires only a small set of pre-shared information.
 Can be modified easily to create a more secure variant, such as by using a multiple shift values or keywords.

Disadvantages

 It is not secure against modern decryption methods.

 Vulnerable to known-plaintext attacks, where an attacker has access to both the encrypted and unencrypted
versions of the same messages.
 The small number of possible keys means that an attacker can easily try all possible keys until the correct one
is found, making it vulnerable to a brute force attack.
 It is not suitable for long text encryption as it would be easy to crack.
 It is not suitable for secure communication as it is easily broken.
 Does not provide confidentiality, integrity, and authenticity in a message.
Features of Caesar Cipher
1. Substitution cipher: The Caesar cipher is a type of substitution cipher, where each letter in the plaintext is
replaced by a letter some fixed number of positions down the alphabet.
2. Fixed key: The Caesar cipher uses a fixed key, which is the number of positions by which the letters are
shifted. This key is known to both the sender and the receiver.
3. Symmetric encryption: The Caesar cipher is a symmetric encryption technique, meaning that the same key is
used for both encryption and decryption.
4. Limited keyspace: The Caesar cipher has a very limited keyspace of only 26 possible keys, as there are only
26 letters in the English alphabet.
5. Vulnerable to brute force attacks: The Caesar cipher is vulnerable to brute force attacks, as there are only 26
possible keys to try.
6. Easy to implement: The Caesar cipher is very easy to implement and requires only simple arithmetic
operations, making it a popular choice for simple encryption tasks.
Rules for the Caesar Cipher
1. Choose a number between 1 and 25. This will be your "shift" value.
2. Write down the letters of the alphabet in order, from A to Z.
3. Shift each letter of the alphabet by the "shift" value. For example, if the shift value is 3, A would become D, B
would become E, C would become F, and so on.
4. Encrypt your message by replacing each letter with the corresponding shifted letter. For example, if the shift
value is 3, the word "hello" would become "khoor".
5. To decrypt the message, simply reverse the process by shifting each letter back by the same amount. For
example, if the shift value is 3, the encrypted message "khoor" would become "hello".
Algorithm for Caesar Cipher
Input:
1. Choose a shift value between 1 and 25.
2. Write down the alphabet in order from A to Z.
3. Create a new alphabet by shifting each letter of the original alphabet by the shift value. For example, if the shift
value is 3, the new alphabet would be:
4. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
DEFGHIJKLMNOPQRSTUVWXYZABC
5. Replace each letter of the message with the corresponding letter from the new alphabet. For example, if the
shift value is 3, the word "hello" would become "khoor".
6. To decrypt the message, shift each letter back by the same amount. For example, if the shift value is 3, the
encrypted message "khoor" would become "hello".

Transposition Cipher
The Transposition Cipher Technique is an encryption method used to encrypt a message or information. This
encryption method is done by playing with the position of letters of the plain text. The positions of the characters
present in the plaintext are rearranged or shifted to form the ciphertext. It makes use of some kind of permutation
function to achieve the encryption purpose. It is very easy to use and so simple to implement.

Types of Transposition Cipher Techniques

There are three types of transposition cipher techniques
 Rail Fence Transposition Cipher
 Block (Single Columnar) Transposition Cipher
 Double Columnar Transposition Cipher
Rail Fence Transposition Cipher
Rail Fence Transposition cipher technique is the simplest transposition cipher its. It is also termed as a zigzag
cipher. It gets its name from the way through which it performs encryption of plain text. The steps to get cipher text
with the help of the Rail Fence Transposition cipher technique are as follow-
Technique of Rail Fence Transposition Cipher

Example: The plain text is "Hello Krishna"

Now, we will write this plain text in the diagonal form:

Rail Fence Transposition Cipher

Now, following the second step we get our cipher text.
Cipher Text = "rsnelkiha"

Block (Single Columnar) Transposition Cipher

Block Transposition Cipher is another form of Transposition Cipher which was used to encrypt the message or
information. In this technique, first, we write the message or plaintext in rows. After that, we read the message
column by column. In this technique, we use a keyword to determine the no of rows.
 Step 1: First we write the message in the form of rows and columns, and read the message column by column.
 Step 2: Given a keyword, which we will use to fix the number of rows.
 Step 3: If any space is spared, it is filled with null or left blank or in by (_).
 Step 4: The message is read in the order as specified by the keyword.
Block Columnar Transposition Cipher

For example: The plaintext is "KRISHNA RANJAN"

Now we will write the plaintext in the form of row and column.
Cipher Text = IAN_RNANS_J_KHRA

Double Columnar Transposition Cipher

Double Columnar Transposition Cipher is another form of Transposition Cipher Technique. The main objective of
using a Double Columnar Transposition Cipher is to encrypt the message twice. It makes use of the Single
Columnar Transposition technique but uses two times. It can use the same or different secret keys. The output
obtained from the first encryption will be the input to the second encryption.
 Step 1: Write the plaintext row-wise in a matrix using the first keyword length as columns
 Step 2: Assign column numbers based on alphabetical order of the first keyword

Double Columnar Transposition Cipher

 Step 3: Read columns in that order to get the first ciphertext

Now applying keyword 2:
 Step 4: Write this ciphertext again row-wise using the second keyword
Now apply step 3:
 Step 5: Assign column order based on the second keyword.
 Step 6: Read columns accordingly to obtain the final ciphertext
Double Columnar Transposition Cipher