TCN Lec-4

Lecture-4 (TCN TC-316)
Error Detection and Correction

(DLL Layer Function) (Continued)
By
Dr. Rizwan Aslam Butt
Assistant Professor
Department of Electronic Engineering
NED University of Engineering and
Technology
TCN TC-421 NED University of Engineering and Technology
CYCLIC CODES (CRC)
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.
Example of a CRC code with C(7, 4)
10.2
 Encoding using CRC
 The communicating parties agrees upon the size of

message block and the CRC divisor.
 For example, the block chosen may be CRC (7, 4),
where 7 is the total length of the block and 4 is the
number of bits in the data segment. The divisor
chosen may be 1011.
 The sender performs binary division of the data
segment by the divisor.
 It then appends the remainder called CRC bits to the
end of data segment. This makes the resulting data
unit exactly divisible by the divisor.
Decoding Using CRC
 The receiver divides the incoming data unit by the divisor.
 If there is no remainder, the data unit is assumed to be correct and

is accepted.
 Otherwise, it is understood that the data is corrupted and is

therefore rejected. The receiver may then send an erroneous
acknowledgement back to the sender for retransmission
10.4
Algorithm for Encoding using CRC
 The communicating parties agrees upon the size

of message, M(x) and the generator
polynomial, G(x).
 If r is the order of G(x),r, bits are appended to the
low order end of M(x). This makes the block size
bits, the value of which is xrM(x).
 The block xrM(x) is divided by G(x) using modulo
2 division.
 The remainder after division is added
to xrM(x) using modulo 2 addition. The result is the
frame to be transmitted, T(x). The encoding
procedure makes exactly divisible by G(x).
10.5
Algorithm for Decoding using CRC
 The receiver divides the incoming data frame T(x)

unit by G(x) using modulo 2 division.
Mathematically, if E(x) is the error, then modulo 2
division of [M(x) + E(x)] by G(x) is done.
 If there is no remainder, then it implies that E(x).
The data frame is accepted.
 A remainder indicates a non-zero value of E(x), or
in other words presence of an error. So the data
frame is rejected. The receiver may then send an
erroneous acknowledgment back to the sender
for retransmission.
10.6
Figure 10.14 CRC encoder and decoder
10.7
Figure 10.15 Division in CRC encoder
10.8
Figure 10.16 Division in the CRC decoder for two cases
10.9
Example -1
Data word to be sent - 100100 Key -
1101 [ Or generator polynomial x3 + Receiver Side: Code word received at the
x2 + 1] Sender Side: receiver side 100100001
Therefore, the remainder is 001 and

Therefore, the remainder is all zeros.
hence the encoded data sent is
Hence, the data received has no error.
100100001.
10.10
Example -2
Data word to be sent - 100100 Key
Receiver Side Let there be error in
- 1101 Sender Side:
transmission media Code word received at
the receiver side - 100000001
Therefore, the remainder is 001 and

hence the code word sent is Since the remainder is not all zeroes,
100100001. the error is detected at the receiver
10.11 side.
Figure 10.18 Simulation of division in CRC encoder
10.12
Figure 10.21 A polynomial to represent a binary word
10.13
Note
The divisor in a cyclic code is normally

called the generator polynomial
or simply the generator.
10.14
In a cyclic code,
If s(x) ≠ 0, one or more bits is corrupted.
If s(x) = 0, either
a. No bit is corrupted. or
b. Some bits are corrupted, but the
decoder failed to detect them.
In a cyclic code, those e(x) errors that are

divisible by g(x) are not caught.
10.15
If the generator has more than one term
and the coefficient of x0 is 1,
all single errors can be caught.
10.16
Example 10.15
Which of the following g(x) values guarantees that a

single-bit error is caught? For each case, what is the
error that cannot be caught?
a. x + 1 b. x3 c. 1
Solution
a. No xi can be divisible by x + 1. Any single-bit error can
be caught.
b. If i is equal to or greater than 3, xi is divisible by g(x).
All single-bit errors in positions 1 to 3 are caught.
c. All values of i make xi divisible by g(x). No single-bit
error can be caught. This g(x) is useless.
10.17
Note
❏ All burst errors with L ≤ r will be

detected.
❏ All burst errors with L = r + 1 will be
detected with probability 1 – (1/2)r–1.
❏ All burst errors with L > r + 1 will be
detected with probability 1 – (1/2)r.
10.18
Example 10.17
Find the suitability of the following generators in relation

to burst errors of different lengths.
a. x6 + 1 b. x18 + x7 + x + 1 c. x32 + x23 + x7 + 1
Solution
a. This generator can detect all burst errors with a length
less than or equal to 6 bits;
b. This generator can detect all burst errors with a length
c. This generator can detect all burst errors with a length

10.19
Example 10.17 (continued)
b. This generator can detect all burst errors with a length

less than or equal to 18 bits; 8 out of 1 million burst
errors with length 19 will slip by; 4 out of 1 million
burst errors of length 20 or more will slip by.
c. This generator can detect all burst errors with a length

less than or equal to 32 bits; 5 out of 10 billion burst
errors with length 33 will slip by; 3 out of 10 billion
burst errors of length 34 or more will slip by.
10.20
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.
10.21
Table 10.7 Standard polynomials
10.22
10-5 CHECKSUM
The last error detection method we discuss here is

called the checksum. The checksum is used in the
Internet by several protocols although not at the data
link layer. However, we briefly discuss it here to
complete our discussion on error checking
10.23
Example 10.18
Suppose our data 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. For example,
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
data are not accepted.
10.24
Example 10.19
We can make the job of the receiver easier if we send the

negative (complement) of the sum, called the checksum.
In this case, we send (7, 11, 12, 0, 6, −36). The receiver
can add all the numbers received (including the
checksum). If the result is 0, it assumes no error;
otherwise, there is an error.
10.25
Example 10.20
How can we represent the number 21 in one’s

complement arithmetic using only four bits?
Solution
The number 21 in binary is 10101 (it needs five bits). We
can wrap the leftmost bit and add it to the four rightmost
bits. We have (0101 + 1) = 0110 or 6.
10.26
Example 10.21
How can we represent the number −6 in one’s

complement arithmetic using only four bits?
Solution
In one’s complement arithmetic, the negative or
complement of a number is found by inverting all bits.
Positive 6 is 0110; negative 6 is 1001. If we consider only
unsigned numbers, this is 9 (Modulo-10 system).
In other words, the complement of 6 is 9. Another way to
find the complement of a number in one’s complement
arithmetic is to subtract the number from 2n − 1 (16 − 1
in this case).
10.27
Example 10.22
Let us redo Exercise 10.19 using one’s complement

arithmetic. Figure 10.24 shows the process at the sender
and at the receiver. The sender initializes the checksum
to 0 and adds all data items and the checksum (the
checksum is considered as one data item and is shown in
color). The result is 36. However, 36 cannot be expressed
in 4 bits. The extra two bits are wrapped and added with
the sum to create the wrapped sum value 6. In the figure,
we have shown the details in binary. The sum is then
complemented, resulting in the checksum value 9 (15 − 6
= 9). The sender now sends six data items to the receiver
including the checksum 9.
10.28
Example 10.22 (continued)
The receiver follows the same procedure as the sender. It

adds all data items (including the checksum); the result
is 45. The sum is wrapped and becomes 15. The wrapped
sum is complemented and becomes 0. Since the value of
the checksum is 0, this means that the data is not
corrupted. The receiver drops the checksum and keeps
the other data items. If the checksum is not zero, the
entire packet is dropped.
10.29
Figure 10.24 Example 10.22
36=00100100
= 0100+ 10=
0110
(Wrapped
Sum
45= 00101101=1101+10 = 1111 = 15

10.30
Note
Sender site:
1. The message is divided into 16-bit words.
2. The value of the checksum word is set to 0.
3. All words including the checksum are
added using one’s complement addition.
4. The sum is complemented and becomes the
checksum.
5. The checksum is sent with the data.
10.31
Note
Receiver site:
1. The message (including checksum) is
divided into 16-bit words.
2. All words are added using one’s
complement addition.
3. The sum is complemented and becomes the
new checksum.
4. If the value of checksum is 0, the message
is accepted; otherwise, it is rejected.
10.32
Example 10.23
Let us calculate the checksum for a text of 8 characters
(“Forouzan”). The text needs to be divided into 2-byte
(16-bit) words. We use ASCII (see Appendix A) to change
each byte to a 2-digit hexadecimal number.
For example, F is represented as 0x46 and o is
represented as 0x6F. Figure 10.25 shows how the
checksum is calculated at the sender and receiver sites. In
part a of the figure, the value of partial sum for the first
column is 0x36. We keep the rightmost digit (6) and insert
the leftmost digit (3) as the carry in the second column.
The process is repeated for each column. Note that if
there is any corruption, the checksum recalculated by the
receiver is not all 0s. We leave this an exercise.
10.33
Figure 10.25 Example 10.23
10.34
Appendix A
10.35
Assignment Question
Read the paper titled “Cyclic Redundancy

Code (CRC) Polynomial Selection For
Embedded Networks“
At following link and make a 1 page
summary
of this research paper;
http://users.ece.cmu.edu/~koopman/rose
s/dsn04/koopman04_crc_poly_embedde
d.pdf
10.36

TCN Lec-4

Uploaded by

Copyright:

Available Formats

TCN Lec-4

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

TCN Lec-4

Uploaded by

Copyright:

Available Formats

Lecture-4 (TCN TC-316)

Error Detection and Correction

 The communicating parties agrees upon the size of

 The receiver divides the incoming data unit by the divisor.

 If there is no remainder, the data unit is assumed to be correct and

 Otherwise, it is understood that the data is corrupted and is

 The communicating parties agrees upon the size

 The receiver divides the incoming data frame T(x)

Therefore, the remainder is 001 and

Therefore, the remainder is 001 and

The divisor in a cyclic code is normally

In a cyclic code, those e(x) errors that are

Which of the following g(x) values guarantees that a

❏ All burst errors with L ≤ r will be

Find the suitability of the following generators in relation

c. This generator can detect all burst errors with a length

b. This generator can detect all burst errors with a length

c. This generator can detect all burst errors with a length

The last error detection method we discuss here is

Suppose our data is a list of five 4-bit numbers that we

The receiver adds the five numbers and compares the

We can make the job of the receiver easier if we send the

How can we represent the number 21 in one’s

How can we represent the number −6 in one’s

Let us redo Exercise 10.19 using one’s complement

The receiver follows the same procedure as the sender. It

45= 00101101=1101+10 = 1111 = 15

Read the paper titled “Cyclic Redundancy

You might also like