FT Lecture 11 Error Control Codes Fall22

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: Summer 19-20

Lecturer: Md. Sakir Hossain, Email: [email protected]
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.
➢ The redundant bits are called frame check sequence (FCS)
How is FCS generated?
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.
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.
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.
Error detection at the receiver
Example 1
❑ Generate FCS if the message polynomial and generator polynomial

are 𝑋 3 + 𝑋 2 + 1 And 𝑋 3 + 𝑋 + 1, respectively.
Let M(x) be the message polynomial
Let P(x) be the generator polynomial/Pattern sequence
Let P(x) = 𝑋 3 + 𝑋 + 1 1011
Let M(x) = 𝑋 3 + 𝑋 2 + 1 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.
Example 1
At sender
P S
Transmit sequence or codeword

T=1101001
R
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

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.
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].

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.
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= 3 , 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0 × 11 × 1 = 1
𝐶 =𝑀×𝐺 0 × 11 × 11 × 0 = 1
1 1 0 1 0 0 0 × 01 × 11 × 1 = 0
𝐶= 0 1 1 × 0 1 1 0 1 0 0 × 11 × 01 × 0 = 0
1 0 1 0 0 1 0 × 01 × 11 × 0 = 1
𝐶= 1 1 0 0 1 1 0 × 01 × 01 × 1 = 1
𝑄 𝑀
Error-detection
Receiving end 1 1 0
𝑃3×3 = 0 1 1
Parity check matrix, 𝑇 1 0 1
H = 𝐼𝑞 𝑃𝑘×𝑞
1 0 1
𝑇
H= 𝐼3 𝑃3×3 𝑇
𝑃3×3 = 1 1 0
1 0 0 1 0 1 0 1 1
H= 0 1 0 1 1 0 𝑇
𝑃3×3 is the transpose of 𝑃3×3
0 0 1 0 1 1
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 1 0 0
0 0 1 0 1 0
𝑠 = [1 1 0 0 1 1]
1 1 0 0 0 1
0 1 1 𝐻𝑇 =
𝑠= 0 0 0 1 1 0
1 0 1 0 1 1
1 0 1
The all-zero syndrome indicates a correct reception !
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, 𝑠 = 𝑟𝐻𝑇
1 0 0
0 1 0
0 0 1
𝑠 = [1 0 0 0 1 1]
1 1 0
0 1 1
𝑠= 0 1 0 1 0 1
The non-zero syndrome indicates an erroneous reception !

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
2. Locate the syndrome in 𝐻𝑇 1 0 1
3. It is in second row
4. So, the second element in the received sequence, 𝑟 = [1 0 0 0 1 1]
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 codeword?
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.

FT Lecture 11 Error Control Codes Fall22

Uploaded by

Copyright:

Available Formats

FT Lecture 11 Error Control Codes Fall22

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

FT Lecture 11 Error Control Codes Fall22

Uploaded by

Copyright:

Available Formats

Error Control Codes

Course Code: CSC 3116 Course Title: Computer Networks

Dept. of Computer Science

Lecturer No: 11 Week No: 12 Semester: Summer 19-20

1. Cyclic redundancy check

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

❑ Required two sequence

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

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

❑ Generate FCS if the message polynomial and generator polynomial

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

Transmit sequence or codeword

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

What if any bit gets altered in the channel?

The nonzero remainder indicates an erroneous reception.

• Transmitted sequence, T=101000110101110

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

1. Detect whether the received sequence 101110101 is error free

Generator matrix, 𝐺 = 𝑃𝑘×𝑞 𝐼𝑘 1 1 0

Suppose that there is no error in the received sequence.

Suppose that there is an error in the received sequence.

The non-zero syndrome indicates an erroneous reception !

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

(a) Find all the codewords of the code

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

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

You might also like