Module 3

10.1 INTRODUCTION

10.2 BLOCK CODING

10.3 CYCLIC CODES

10.4 CHECKSUM
 Chapter 10: Objective

❑ The first section introduces types of errors, the concept of

redundancy, and distinguishes between error detection and
correction.

❑ The second section discusses block coding. It shows how error

can be detected using block coding and also introduces the
concept of Hamming distance.

❑ The third section discusses cyclic codes. It discusses a subset of

cyclic code, CRC, that is very common in the data-link layer. Also
shows how CRC can be easily implemented in hardware and
represented by polynomials.
 Chapter 10: Objective (continued)

❑ The fourth section discusses checksums. It shows how a

checksum is calculated for a set of data words. It also gives some
other approaches to traditional checksum.
 10-1 INTRODUCTION

•TCP/IP protocol does not define any protocol in DLL

or PL.
•These two layers are territories of networks that when
connected make up the Internet.
•These networks (wired/wireless), provide services to
upper three layers of TCP/IP suite.

•Networks must be able to transfer data from one

device to another with acceptable accuracy.
•For most of the applications, system must guarantee
that data received are identical to the one transmitted .
 INTRODUCTION

•In transmission, there are possibilities that any time

message gets corrupted.
•Many factors alter one or more bits of a message.
•Some applications require a mechanism for detecting
and correcting errors.
•Some applications can tolerate some errors.
Eg: A/V (random errors )
but transfer of text, expect high level of accuracy.
•Discuss some issues related, directly or indirectly, to
error detection and correction.
 Types of Errors
•Whenever bits flow from one point to another, they are
subject to unpredictable changes because of interference.

•This interference can change the shape of the signal.

• The term single-bit error means that only 1 bit of a given data
unit (such as a byte, character, or packet) is changed from 1 to
0 or from 0 to 1.

• The term burst error means that 2 or more bits in the data unit
have changed from 1 to 0 or from 0 to 1. Figure below shows
the effect of a single-bit and a burst error on a data unit.
Single-bit and burst error
 Types of Errors

• Burst error is more likely to occur than single bit error.

• Reason is duration of noise signal is longer than the duration

of a bit.

• When noise affects data, it affects set of bits.

• Number of bits affected depends on the duration of the noise

and data rate.

Eg: If we send 1 kbps of data, a noise 1/100 s can affect 10 bits.

If 1 Mbps data rate, noise can affect 10,000 bits.
 Redundancy
•The central concept in detecting or correcting errors
is redundancy.

•To be able to detect or correct errors, need to send

some extra bits with our data.

•These redundant bits are added by the sender and

removed by the receiver.

•Presence of redundant bits allows the receiver to

detect or correct corrupted bits.
 Detection versus Correction
•The correction of errors is more difficult than the
detection.

• In error detection, check if any error has occurred.

The answer is a simple yes or no.Not interested in the
number of corrupted bits.

•A single-bit error is the same for us as a burst error.

•In error correction,

Need to know the exact number of bits that are
corrupted and, more importantly, their location in the
message.
 Coding
•Redundancy is achieved through various coding schemes.

•The sender adds redundant bits through a process that creates

a relationship between the redundant bits and the actual data
bits.

•The receiver checks the relationships between the two sets of

bits to detect errors.

•The ratio of redundant bits to data bits and the robustness of

the process are important factors in any coding scheme.
 Coding
■Two coding schemes are
i) Block coding ii) Convolution coding
■Concentrate on block codes.
■In modulo-N arithmetic, the integers in the range 0 to
N −1inclusive is used,
 10-2 BLOCK CODING

•In block coding, message is divided into

blocks, each of k bits, called data words.
•Add r redundant bits to each block to make the
length n = k + r.
•The resulting n-bit blocks are called code
words.
 BLOCK CODING

•In block coding, we have set of data words,

each of size k, code words, each of size n.
•Since n>k, the possible number of code words
are larger than the data words.
•Block coding process is one-to-one, same data
word is encoded as code word.
•2n - 2K code words are not used.
•If receiver receives invalid codeword, it
indicates data is corrupted during transmission.
 Error Detection

•How can errors be detected by using block coding?

•If the following two conditions are met, the receiver

can detect a change in the original codeword.

a. The receiver has (or can find) a list of valid

code words.

b. The original codeword has changed to an invalid

one.
Process of error detection in block coding
 Example 10.1
Let us assume that k = 2 and n = 3. Table below shows the
list of data words and code words.

A code for error detection

 Hamming distance (HD)
■The Hamming distance between two words(of same
size) is the number of differences between
corresponding bits. (total number of 1’s).
■Why HD in Error detection????
■HD between the sent code word & received codeword
is the number of bits that got corrupted during
transmission.
Eg: Let us find the Hamming distance between two
pairs of words.
 Hamming Distance
■The Hamming distance d(000, 011) is 2.
■The Hamming distance d(10101, 11110) is 3
because

■ If the HD between sent & received code word is not zero,

then code word has been corrupted during transmission.
■ The minimum Hamming distance is the smallest
Hamming distance between all possible pairs in a set of
words.
 Hamming distance
■Find the minimum Hamming distance of the
coding scheme in

We first find all Hamming distances

The dmin in this case is 2

 Example 10.2
Let us find the Hamming distance between two pairs of
words.
 Example 10.3
The minimum Hamming distance for our first code scheme
(Table 10.1) is 2.

This code guarantees detection of only a single error. For

example, if the third code word (101) is sent and one error
occurs, the received code word does not match any valid
code word.

If two errors occur, however, the received code word may

match a valid code word and the errors are not detected.
 Example 10.6
In our first code (Table 10.1), the numbers of 1s in the
nonzero codewords are 2, 2, and 2. So the minimum
Hamming distance is dmin = 2.
 LINEAR BLOCK CODES

■Almost all block codes used today belong to a

subset called linear block codes.
■ A linear block code is a code in which the
exclusive OR (addition modulo-2) of two valid
code words creates another valid codeword.
Table : Simple parity-check code C(5, 4)
 Example
■ Let us see if the two codes defined in Tables above,
belong to the class of linear block codes.

1. The scheme in the above Table is a linear block code

because the result of XORing any codeword with any
other codeword is a valid codeword.
So the minimum Hamming distance is dmin = 2.

2. The scheme in Table second is also a linear block code.

We can create all four codewords by XORing two
other codewords.
■ So the minimum hamming distance is dmin = 3.
 Simple Parity check code
■ A simple parity-check code is a single-bit error-
detecting code in which n = k + 1 with dmin = 2.
■The extra bit called parity bit is selected to make
number of 1’s in the code word even.
■The code is single-bit error detecting code.
■It cannot correct any error.
■In the fig. encoder takes a copy of 4 bit data
word(a0,a1,a2,a3 ) and generates a parity bit r0.
■Parity bit creates the 5-bit code word.
Encoder and decoder for simple parity-check
code
 Simple Parity check code
■The parity bit that is added makes the number of 1’s
in the codeword even. i.e
r0 = a0 +a1 +a2 +a3 (modulo-2)
■If number of 1s is even, the result is 0.
■If number of 1s is odd, the result is 1.
🡪 The sender sends the code word which is corrupted
during transmission.
🡪 The receiver receives 5 bit code word.
🡪 The checker performs modulo-2 of all the bits
received. The result is called syndrome.
s0 = b0 +b1 +b2 +b3 + q0 (modulo-2)
 Continued..
■If number of 1s in the codeword is even, the
syndrome is 0.
■If number of 1s in the codeword is odd, the
syndrome is 1.
■The syndrome is passed to decision logic
analyzer. If Syndrome is 0, no error in the code
word received, data portion is extracted.
■If syndrome is 1, error in the received
codeword and discarded.
 Example 10.7
Let us look at some transmission scenarios. Assume the
sender sends the data word 1011. The codeword created
from this data word is 10111, which is sent to the receiver.
Five cases can be examined:
 10-3 CYCLIC CODES

•Cyclic codes are special linear block codes

with one extra property.
•In a cyclic code, if a codeword is cyclically
shifted (rotated), the result is another codeword.

Eg:1011000 is a codeword and if it is cyclically

left-shifted, then 0110001 is also a codeword.

We can shift the bits using

b1=a0,b2=a1, b3=a2, b4=a3, b5=a4, b6=a5, b0=a6
 Cyclic Redundancy Check

• Cyclic codes are created to correct errors.

•Discuss a subset of cyclic codes called the cyclic

redundancy check (CRC), which is used in networks
such as LANs and WANs.
A CRC code with C(7, 4)
CRC encoder and decoder
 CRC

■In the encoder, the data word has k bits(4 bits),

code word has n bits(7 here).
■The data word is augmented by adding n-k 0s to
the right hand side of the word.
■The n-bit result is fed to the generator.
■The generator uses a divisor of size
n-k+1which is predefined and agreed upon.
■ The generator divides the augmented dataword
 CRC
by divisor (modulo-2 division).
■The quotient of the division is discarded.
■The remainder r2r1 r0 is appended to the data
word to create the codeword.
■The decoder receives the corrupted codeword.
■A copy of all n bits are fed to the checker.
■The remainder produced by checker is a
syndrome of n-k bits, which is fed to the decision
logic analyzer.
■ If syndrome bits are 0, the 4 left most bits of the
code word are accepted as a data word.
Division in CRC encoder
 CRC-Encoder

■Encoder takes data word and augments it with

n-k number of 0s.
■It then divides the augmented data word by a
divisor.
■Modulo-2 binary division is used. For Addition and
subtraction, XOR operations is used.
■In each step, copy of the divisor is XOR ed
with 4 bits of dividend. The result of XOR
operation is 3 bits.
 CRC-Decoder

■Code word can change during transmission.

■The decoder same thing as encoder and
remainder of the division id the syndrome.
■If syndrome is all 0s, no error, data word is
separated from the code word and accepted.
■Otherwise , everything is discarded.
■Question is how divisor 1011 is chosen??
Division in the CRC decoder for two cases
 Polynomials

■A better way to understand cyclic codes, and

how they can be analyzed is to represent them
as polynomials.
■A pattern of 0s and 1s can be represented as
polynomial with coefficient of 0 and 1.
■The power of each term shows the position of
the bit.
■The coefficient shows the value of the bit.
A polynomial to represent a binary word
 Degree of Polynomials

■Is the highest power of the polynomial.

Eg: Degree of x6 + x+1 is 6.
■Degree of polynomial is one less than that the
number of bits in the pattern.
■Addition and subtraction of polynomials is
done by adding and subtracting the coefficient
terms with the same power.
■Coefficients are only 0 and 1, and adding is in
modulo-2
Adding and subtracting of polynomials

■Addition and subtraction is done by

combining terms and deleting pair of identical
terms.
■Eg: x5 + x4+x2
x6 +x4+x2
-------------------------------

x6 + x 5
 Multiplication and Division of
polynomials
■Multiplication is adding powers.
Eg: x4 * x 2 = x 6
■Division, subtract the power of second term
from the first term.
Eg: x5 / x 2 = x 3
■Multiplication of two polynomials
(x5 + x3 + x2 ) (x2 + x + 1)= x7 + x6 + x5 + x5 + x4 + x3 + x4+ x3

+ x2
🡪
x7 + x6 + x2
 Shifting of polynomials

■A binary pattern is shifted left or right by

number of bits.
■Shifting to the left means adding extra 0s as
right most bits.
■ Shifting to the right means deleting some
right most bits.
■Shifting to the left is accomplished by
multiplying each term of the polynomial by xm
where m is the number of shifted bits
 Continued..

■Shifting to the right is accomplished by

dividing each term of the polynomial by xm
where m is the number of shifted bits.

■Shift left by 3 bits :10011 becomes 10011000

x4+x +1 becomes x7 + x4+x3
■Shift right by 3 bits: 10011 becomes 10
x4+x +1 becomes x
CRC division using polynomials
Cyclic code analysis using
polynomials
■In a polynomial representation, divisor is
normally referred to as generator polynomial
t(x).
■f(x) is the polynomial with binary coefficients
data word d(x), code word c(x), Generator g(x)
syndrome s(x) and error e(x).
🡪 Is s(x) is not zero, one or more bits are
corrupted. If s(x) is zero, either no error or
decoder failed to detect any error.
 Cyclic Code Analysis

•Analyze a cyclic code to find its capabilities by using

polynomials.

• Define the following, where f(x) is a polynomial

with binary coefficients.
 Example 10.8
Which of the following g(x) values guarantees that a single-
bit error is caught? x + 1, x3 and 1

Solution
Representation of isolated single-bit errors
 Example 10.9
Find the suitability of the following generators in relation to
burst errors of different lengths: x 6 + 1, x18 + x7 + x + 1, and
x32 + x23 + x7 + 10.
Solution
 Example 10.10
Find the status of the following generators related to two
isolated, single-bit errors: x + 1, x 4 + 1, x7 + x6 + 1, and
x15 + x14 + 1

Solution
 Summary

■A good polynomial generator needs to have

the following characteristics:
1. It should have at least two terms.
2. The coefficient of the term x0 should
be 1.
3. It should not divide xt + 1, for t
between 2 and n − 1.
4. It should have the factor x + 1.
Table :Standard polynomials
 Advantages of Cyclic Codes

• Cyclic codes have a very good performance in

detecting single-bit errors, double errors, an odd
number of errors, and burst errors.

•They can easily be implemented in hardware and

software.

•They are especially fast when implemented in

hardware which has made cyclic codes a good
candidate for many networks.
 Other Cyclic Codes

•The cyclic codes we have discussed are very simple.

• The check bits and syndromes can be calculated by

simple algebra.

•There are, however, more powerful polynomials that

are based on abstract algebra involving Galois fields.

•One of the most interesting of these codes is the

Reed-Solomon code used today for both detection and
correction.
 10-4 CHECKSUM

•Checksum is an error-detecting technique that

can be applied to a message of any length.

• In the Internet, the checksum technique is

mostly used at the network and transport layer
rather than the data-link layer.
•At source,
⮚ Message is divided into m-bit units.
⮚Generator then creates an extra m-bit unit
called checksum, which is sent with message.
 CHECKSUM

•At Destination,
⮚Checker creates a new checksum from
combination of the message and the sent
checksum.
⮚If new checksum is all 0’s, the message is
accepted else discarded.
Checksum
 Concept
•The idea of the traditional checksum is simple.
Show this using a simple example.
Suppose the message is a list of five 4-bit numbers that we
want to send to a destination.
In addition to sending these numbers, we send the sum of the
numbers.
Eg: if the set of numbers is (7, 11, 12, 0, 6), we send (7, 11, 12,
0, 6, 36), where 36 is the sum of the original numbers. The
receiver adds the five numbers and compares the result with
the sum.
If the two are the same, the receiver assumes no error, accepts
the five numbers, and discards the sum.
Otherwise, there is an error somewhere and the message not
accepted.
 Ones compliment Addition
•Each number can be written as a 4 bit word except
sum.
•This drawback we can over come using ones
compliment arithmetic.
•Represent unsigned numbers between 0 and 2m -1
Using only m bits.
•If the number has more than m bits, the extra
leftmost bits need to be added to the m rightmost bits.
 Example 10.12
In the previous example, the decimal number 36 in binary is
(100100)2. To change it to a 4-bit number we add the extra
leftmost bit to the right four bits as shown below.

Instead of sending 36 as the sum, we can send 6 as the sum

(7, 11, 12, 0, 6, 6).
The receiver can add the first five numbers in one’s
complement arithmetic.
If the result is 6, the numbers are accepted; otherwise, they
are rejected.
 Example 10.13
Let us use the idea of the checksum in Example 10.12. The
sender adds all five numbers in one’s complement to get the
sum = 6.
The sender then complements the result to get the checksum
= 9, which is 15 − 6.
⮚Note that 6 = (0110)2 and 9 = (1001)2;they are
complements of each other.
⮚The sender sends the five data numbers and the checksum
(7, 11, 12, 0, 6, 9).
⮚If there is no corruption in transmission, the receiver
receives (7, 11, 12, 0, 6, 9) and adds them in one’s
complement to get 15.
Example 10.13
Table : Procedure to calculate the traditional
checksum
Algorithm to calculate a traditional checksum
 Other Approaches
• One major problem with the traditional checksum
calculation.
• If two 16-bit items are transposed in transmission,
the checksum cannot catch this error.
•The reason is that the traditional checksum is not
weighted: it treats each data item equally.
•In other words, the order of data items is immaterial
to the calculation.
•Several approaches have been used to prevent this
problem.
•Two of them are: Fletcher and Adler.
 Fletcher Checksum
■ Was devised to weight each data item according to its position.
■ Two algorithms i) 8-bit ii) 16-bit.
■ In 8 bit Fletcher, calculation is done on 8-bit data and creates
16 bit checksum.
■ Calculation is done using modulo256(28 )i.e intermediate
results are divided by 256 and remainder is kept.
■ Algorithm uses two accumulators L & R
■ First simply adds data items together,
■ Second adds weights to the calculation.
■ In 16 bit Fletecher, calculation is done on 16-bit data and
creates 32 bit checksum.
Algorithm to calculate an 8-bit Fletcher
checksum
 Adler Checksum
■ Is a 32 bit checksum.
■ Similar to Fletcher.
■ 3 Major differences
i) Calculation is done on single byte instead of 2 bytes at a time
ii) Modulus is a prime number(65,521)instead of 65,536.
iii) L is initialized to 1 instead of 0
Algorithm to calculate an Adler checksum