Introduction

ERROR
• Error is a condition when the output information does not match with
the input information.

• During transmission, digital signals suffer from noise that can

introduce errors in the binary bits travelling from one system to other.

• That means a 0 bit may change to 1 or a 1 bit may change to 0.

Error-Detecting codes
• Whenever a message is transmitted, it may get scrambled by noise or
data may get corrupted.

• To avoid this, we use error-detecting codes which are additional data

added to a given digital message to help us detect if an error occurred
during transmission of the message.

• A simple example of error-detecting code is parity check.

Error-Correcting codes
• Along with error-detecting code, we can also pass some data to figure
out the original message from the corrupt message that we received.

• This type of code is called an error-correcting code.

• Error-correcting codes also deploy the same strategy as error-

detecting codes but additionally, such codes also detect the exact
location of the corrupt bit.
• In error-correcting codes, parity check has a simple way to detect
errors along with a sophisticated mechanism to determine the
corrupt bit location.

• Once the corrupt bit is located, its value is reverted (from 0 to 1 or 1

to 0) to get the original message.
How to Detect and Correct Errors?
BLOCK CODING

• To detect and correct the errors, additional bits are added to the data
bits at the time of transmission.

• The additional bits are called parity bits. They allow detection or

correction of the errors.

• The data bits along with the parity bits form a code word.
Parity Checking of Error Detection
• It is the simplest technique for detecting and correcting errors.

• The MSB of an 8-bits word is used as the parity bit and the remaining
7 bits are used as data or message bits.

• The parity of 8-bits transmitted word can be either even parity or odd
parity.
• Even parity -- Even parity means the number of 1's in the given word
including the parity bit should be even (2,4,6,....).

• Odd parity -- Odd parity means the number of 1's in the given word including
the parity bit should be odd (1,3,5,....).

• The parity bit can be set to 0 and 1 depending on the type of the parity
required.

• For even parity, this bit is set to 1 or 0 such that the no. of "1 bits" in the
entire word is even. Shown in fig. (a).

• For odd parity, this bit is set to 1 or 0 such that the no. of "1 bits" in the entire
word is odd. Shown in fig. (b).
How Does Error Detection Take Place?
• Parity checking at the receiver can detect the presence of an error if
the parity of the receiver signal is different from the expected parity.

• That means, if it is known that the parity of the transmitted signal is

always going to be "even" and if the received signal has an odd parity,
then the receiver can conclude that the received signal is not correct.

• If an error is detected, then the receiver will ignore the received byte
and request for retransmission of the same byte to the transmitter.
• error detection and correction or error control are techniques that
enable reliable delivery of digital data over unreliable 
communication channels.

• Many communication channels are subject to channel noise, and thus

errors may be introduced during transmission from the source to a
receiver.

• Error detection techniques allow detecting such errors, while error

correction enables reconstruction of the original data in many cases.
Types of error correction
• Automatic repeat request (ARQ)
• Automatic Repeat reQuest (ARQ) is an error control method for data
transmission that makes use of error-detection codes, acknowledgment
and/or negative acknowledgment messages, and timeouts to achieve
reliable data transmission.

• An acknowledgment is a message sent by the receiver to indicate that it

has correctly received a data frame.

• Usually, when the transmitter does not receive the acknowledgment before
the timeout occurs (i.e., within a reasonable amount of time after sending
the data frame), it retransmits the frame until it is either correctly received
or the error persists beyond a predetermined number of retransmissions.
• Three types of ARQ protocols are Stop-and-wait ARQ, Go-Back-N ARQ,
and Selective Repeat ARQ.

• ARQ is appropriate if the communication channel has varying or unknown 

capacity, such as is the case on the Internet.

• However, ARQ requires the availability of a back channel, results in

possibly increased latency due to retransmissions, and requires the
maintenance of buffers and timers for retransmissions, which in the case
of network congestion can put a strain on the server and overall network
capacity.

• For example, ARQ is used on shortwave radio data links in the form of 
ARQ-E, or combined with multiplexing as ARQ-M.
• Forward error correction
• Forward error correction (FEC) is a process of adding redundant data such
as an error-correcting code (ECC) to a message so that it can be recovered
by a receiver even when a number of errors (up to the capability of the
code being used) were introduced, either during the process of
transmission, or on storage.

• Since the receiver does not have to ask the sender for retransmission of
the data, a backchannel is not required in forward error correction, and it
is therefore suitable for simplex communication such as broadcasting.

• Error-correcting codes are frequently used in lower-layer communication,

as well as for reliable storage in media such as CDs, DVDs, hard disks, and 
RAM.
• Error-correcting codes are usually distinguished between 
convolutional codes and block codes:

• Convolutional codes are processed on a bit-by-bit basis. They are

particularly suitable for implementation in hardware, and the 
Viterbi decoder allows optimal decoding.

• Block codes are processed on a block-by-block basis. Early examples of

block codes are repetition codes, Hamming codes and 
multidimensional parity-check codes.
• They were followed by a number of efficient codes, 
Reed–Solomon codes being the most notable due to their current
widespread use. Turbo codes and low-density parity-check codes
 (LDPC) are relatively new constructions that can provide almost 
optimal efficiency.
• Hybrid schemes
• Hybrid ARQ is a combination of ARQ and forward error correction.
There are two basic approaches:

• Messages are always transmitted with FEC parity data (and error-
detection redundancy). A receiver decodes a message using the parity
information, and requests retransmission using ARQ only if the parity
data was not sufficient for successful decoding (identified through a
failed integrity check).

• Messages are transmitted without parity data (only with error-

detection information). If a receiver detects an error, it requests FEC
information from the transmitter using ARQ, and uses it to
reconstruct the original message.
Error detection schemes
• Error detection is most commonly realized using a suitable 
hash function.

• A hash function adds a fixed-length tag to a message, which enables

receivers to verify the delivered message by recomputing the tag and
comparing it with the one provided.

• There exists a vast variety of different hash function designs.

• Minimum distance coding

• A random-error-correcting code based on minimum distance coding can

provide a strict guarantee on the number of detectable errors, but it may
not protect against a preimage attack.

• Parity bit

• A parity bit is a bit that is added to a group of source bits to ensure that
the number of set bits (i.e., bits with value 1) in the outcome is even or
odd.

• It is a very simple scheme that can be used to detect single or any other
odd number (i.e., three, five, etc.) of errors in the output.
• An even number of flipped bits will make the parity bit appear correct
even though the data is erroneous.

• Extensions and variations on the parity bit mechanism are 

longitudinal redundancy checks, transverse redundancy checks, and
similar bit-grouping techniques.
• Repetition code
• A repetition code is a coding scheme that repeats the bits across a
channel to achieve error-free communication.

• Given a stream of data to be transmitted, the data are divided into

blocks of bits.

• Each block is transmitted some predetermined number of times. For

example, to send the bit pattern "1011", the four-bit block can be
repeated three times, thus producing "1011 1011 1011".

• If this twelve-bit pattern was received as "1010 1011 1011" – where the
first block is unlike the other two – an error has occurred.
• A repetition code is very inefficient, and can be susceptible to
problems if the error occurs in exactly the same place for each group
(e.g., "1010 1010 1010" in the previous example would be detected as
correct).

• The advantage of repetition codes is that they are extremely simple.

• Checksum

• A checksum of a message is a modular arithmetic sum of message code

words of a fixed word length (e.g., byte values).

• The sum may be negated by means of a ones'-complement operation

prior to transmission to detect unintentional all-zero messages.

• Checksum schemes include parity bits, check digits, and 

longitudinal redundancy checks.

• Some checksum schemes, such as the Damm algorithm, the Luhn

algorithm, and the Verhoeff algorithm, are specifically designed to
detect errors commonly introduced by humans in writing down or
remembering identification numbers.
• Cyclic redundancy check

• A cyclic redundancy check (CRC) is a non-secure hash function designed

to detect accidental changes to digital data in computer networks.

• It is not suitable for detecting maliciously introduced errors.

• It is characterized by specification of a generator polynomial, which is

used as the divisor in a polynomial long division over a finite field,
taking the input data as the dividend.

• The remainder becomes the result.

• A CRC has properties that make it well suited for detecting 
burst errors.

• CRCs are particularly easy to implement in hardware and are

therefore commonly used in computer networks and storage devices
such as hard disk drives.

• The parity bit can be seen as a special-case 1-bit CRC.

• Cryptographic hash function

• The output of a cryptographic hash function, also known as

a message digest, can provide strong assurances about data integrity,
whether changes of the data are accidental (e.g., due to transmission
errors) or maliciously introduced.

• Any modification to the data will likely be detected through a

mismatching hash value.

• Furthermore, given some hash value, it is typically infeasible to find

some input data (other than the one given) that will yield the same
hash value.
• If an attacker can change not only the message but also the hash
value, then a keyed hash or message authentication code (MAC) can
be used for additional security.

• Without knowing the key, it is not possible for the attacker to easily
or conveniently calculate the correct keyed hash value for a modified
message.
Checksum
• This is a block code method where a checksum is created based on
the data values in the data blocks to be transmitted using some
algorithm and appended to the data.

• When the receiver gets this data, a new checksum is calculated and
compared with the existing checksum.

• A non-match indicates an error.

• Error Detection by Checksums

• For error detection by checksums, data is divided into fixed sized

frames or segments.

• Sender’s End − The sender adds the segments using 1’s complement
arithmetic to get the sum. It then complements the sum to get the
checksum and sends it along with the data frames.

• Receiver’s End − The receiver adds the incoming segments along with
the checksum using 1’s complement arithmetic to get the sum and
then complements it.
• If the result is zero, the received frames are accepted; otherwise they
are discarded.
• Suppose that the sender wants to send 4 frames each of 8 bits, where
the frames are 11001100, 10101010, 11110000 and 11000011.

• The sender adds the bits using 1s complement arithmetic. While

adding two numbers using 1s complement arithmetic, if there is a
carry over, it is added to the sum.

• After adding all the 4 frames, the sender complements the sum to get
the checksum, 11010011, and sends it along with the data frames.

• The receiver performs 1s complement arithmetic sum of all the frames

including the checksum. The result is complemented and found to be
0. Hence, the receiver assumes that no error has occurred.
• RC or Cyclic Redundancy Check 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.