Error Control Codes

Course Code: CSC 3116 Course Title: Computer Networks

Dept. of Computer Science

Faculty of Science and Technology

Lecturer No: 11 Week No: 12 Semester:

Lecture Outline

1. Cyclic redundancy check

2. Linear block code
 Cyclic Redundancy Check
Introduction

 What if the transmitted bits get altered on the way?

 Is there any technique to detect the error?
Yes, using Cyclic Redundancy Check (CRC)

 CRC
 In CRC, some redundant bits are sent in addition to the
message bits.
 The purpose of the redundant bits is to facilitate detecting
error.
How bits
 The redundant is FCS generated?
are called frame check sequence (FCS)
Cyclic Redundancy Check….
Introduction….

• Strength of the CRC depends on the number of redundant bits (that is,
FCS length)
• Longer FCS length results in better accuracy in detecting error

 Required two sequence

 Message sequence, M
 The desired data to be sent
 Can be of any length
 Pattern sequence, P
 Known to both sender and receiver
 If we want to use K bits FCS, we need a pattern bit sequence, P, of
length K+1 bits.
Cyclic Redundancy Check….
Generation of FCS

1. Decide how many FCS bits, K, you are going to use.

2. Append K zeros at the end of the message bits to generate M+K
bits long sequence S.
3. Select a K+1 bits long pattern sequence, P.
4. Divide the sequence S by the pattern sequence P to find the K bits
of the remainder, R.
5. Remove the appended zeros from S and append the calculated
remainder R Thus, the N bits message bits and K bits remainder
constitutes the transmitting sequence, T.
Cyclic Redundancy Check….
Error detection at the receiver

1. At the destination, the received sequence, , is divided by the same

patter sequence, P.
2. If at this step there is no remainder, the data unit is assumed to be
correct and is therefore accepted.
3. A remainder indicates that the data unit has been damaged on the
way and therefore must be rejected.
 Cyclic Redundancy Check….
Example 1

 Generate FCS if the message polynomial and generator polynomial

are And , respectively.
Let M(x) be the message polynomial
Let P(x) be the generator polynomial/Pattern sequence
Let P(x) = 1011
Let M(x) = 1101

1. Consider the case where M=1101 and P=1011.

2. Since P consists of 4 bits, append K=3 bits zeros ( 000) at the end of
M, S=1101000
3. Divide S by P to get 3 bits remainder.
Cyclic Redundancy Check….
Example 1

At sender
P S

Transmit sequence or codeword

T=1101001

R
Cyclic Redundancy Check….
Example 1

At Receiver
1011 1 1 0 1 0 0 1
1011
1100
1011
1110
1011
1011
1011
0000

Since the remainder is zero, there is no error in the received sequence

 Cyclic Redundancy Check….
Example 1

What if any bit gets altered in the channel?

Suppose that the second bit (red) has altered from 1 to 0.
1011 1 0 0 1 0 0 1
1011
1000
1011
111

The nonzero remainder indicates an erroneous reception.

The frame will not be acknowledged.
The sender will resend the frame.
Cyclic Redundancy Check….
Example 2

• Message M = 1010001101
• Pattern P = 110101
• Length of P=6
• Append K=6-1=5 zeros at the end of M
• S=101000110100000
• Now divide S by P to find 5 bits remainder
[1].
 
Cyclic Redundancy Check….
Example 2

• Transmitted sequence, T=101000110101110

• At the receiving end, T is divided by P to see if the remainder is
zero. The zero remainder indicates error free reception.
Cyclic Redundancy Check….
Example 1

Because there is no remainder, it is assumed that there have been no errors.

Homework

1. Detect whether the received sequence 101110101 is error

free if the pattern sequence is 1010.
 Linear Block Code
Generator Matrix

Linear Block Code: A code in which addition of any two codewords gives another
codeword [2].
Message, M: k bits long
Redundant bits, Q: q bits long
Codeword length, N: k+q bits long

[ ]
Generator matrix, 𝐺=[ 𝑃 𝑘 ×𝑞 𝐼 𝑘 ] 1 1 0
𝑃 3 ×3 = 0 1 1
For 𝑘=3 and q , 1 0 1

[ ]
1 1 0 1 0 0

[ ]
𝐺= 0 1 1 0 1 0 1 0 0
1 0 1 0 0 1 𝐼 3= 0 1 0
0 0 1
Then, it is a (n, k) =(6, 3) block code
 Linear Block Code….
Codeword calculation

Modulo-2 summation
The codeword for the message [ 0 1 1] is 0 ×1 1× 0 1× 1=1
𝐶= 𝑀 × 𝐺 0 ×1 1× 1 1 ×0=1

[ ] 0 × 0 1 ×1 1× 1=0
1 1 0 1 0 0
𝐶= [ 0 1 1] × 0
1
1
0
1
1
0
0
1
0
0
1
0 ×1 1× 0 1× 0=0
0 × 0 1 ×1 1× 0=1
𝐶= [ 1 1 0 0 1 1 ] 0 × 0 1 × 0 1 ×1=1
𝑄 𝑀
Linear Block Code….
Error-detection

[ ]
Receiving end 1 1 0
𝑃 3 ×3 = 0 1 1
1 0 1
Parity check matrix, H = [ 𝐼𝑞 𝑃 𝑇
𝑘 ×𝑞 ]

[ ]
1 0 1
H = [ 𝐼3 𝑃 3 × 3 ]
𝑇 𝑇
𝑃 3 ×3 = 1 1 0
0 1 1

[ ]
1 0 0 1 0 1
H= 0 1 0 1 1 0
0 0 1 0 1 1 is the transpose of
 Linear Block Code….
Error-detection….

Suppose that there is no error in the received sequence.

Hence the received sequence, , is the same as the transmit sequence, .
𝑟 =𝐶

[ ]
1 0 0 1 0 1
𝑟 =[ 1¿1¿0¿ 0¿1¿1] H= 0 1 0 1 1 0
Syndrome, 𝑠=𝑟 𝐻 𝑇 0 0 1 0 1 1

[ ]
1 0 0
0 1 0
𝑇 0 0 1
𝐻 =
1 1 0
𝑠= [ 0 0 0 ] 0 1 1
1 0 1
The all-zero syndrome indicates a correct reception !
 Linear Block Code….
Error-detection….

Suppose that there is an error in the received sequence.

The second bit (from left side) has altered from 1 to 0
𝑟 =[ 1¿0¿ 0¿0 ¿1¿1]

Syndrome, 𝑠=𝑟 𝐻 𝑇

𝑠= [ 0 1 0 ]

The non-zero syndrome indicates an erroneous reception !

 Linear Block Code….
Error-correction

[ ]
1 0 0
How to correct the error? 0 1 0
𝐻𝑇 = 0 0 1
1 1 0
1. Syndrome ,𝑠= [ 0 1 0 ] 0 1 1
1 0 1
2. Locate the syndrome in
3. It is in second row
4. So, the second element in the received sequence,
is erroneous.
4. Alter the second bit from 0 to 1.
5. So the correct received sequence is [ 1 1 0 0 1 1].
Note: The given generator matrix enables correction of at most 1 bits.

It is possible to correct more bits , but it requires quite a lot work! No Free Lunch!
 Homework

 Consider a (7, 4) code whose generator matrix is given by

[ ]
1 1 1 1 0 0 0
0 1 1 0 1 0 0
𝐺=
1 1 0 0 0 1 0
1 0 1 0 0 0 1

(a) Find all the codewords of the code

(b)Find the parity-check matrix
(c) Find the syndrome for the received vector [ 1 1 0 1 0 1 0]. Is it a valid codewor
References

[1] W. Stallings, Data and Computer Communication, 10th ed., Pearson

Education, Inc., 2014, USA, pp. 194 - 196.
[2] B. Sklar, Digital Communications, 2nd ed., Prentice Hall. 2017, USA, pp. 328 - 345.
Recommended Books

1. Data Communications and Networking, B. A. Forouzan, McGraw-Hill, Inc., Fourth

Edition, 2007, USA.
2. Computer Networking: A Top-Down Approach, J. F., Kurose, K. W. Ross, Pearson
Education, Inc., Sixth Edition, USA.
3. Official Cert Guide CCNA 200-301 , vol. 1, W. Odom, Cisco Press, First Edition, 2019,
USA.
4. CCNA Routing and Switching, T. Lammle, John Wily & Sons, Second Edition, 2016,
USA.
5. TCP/IP Protocol Suite, B. A. Forouzan, McGraw-Hill, Inc., Fourth Edition, 2009, USA.
6. Data and Computer Communication, W. Stallings, Pearson Education, Inc., Tenth
Education, 2013, USA.