The Gateway to Computer Science Excellence
+3 votes

Consider the use of Cyclic Redundancy Code (CRC) with generator polynomial $G(x)$ for error detection. Recall that error detection with a CRC works by appending the CRC value to the bit sequence to make it a multiple of $G(x)$.

  1. Calculate the CRC value of the bit sequence $1 \: 1 \: 0 \: 0 \: 1 \: 1$, if $G(x) = x^4 + x^3 + 1$.
  2. A $\text{burst error}$ of length $k$ means that there are $k$ bits from the first to the last error positions in the frame, including both positions. Note that the intermediate bits may or may not be in error. For example, if $1 \: 0 \: 1 \: 1 \: 0 \: 0$ is transmitted and $1 \: 1 \: 0 \: 1 \: 1 \: 0$ is received, then we can say that a burst error of length $4$ has occurred. Construct a burst error of length $5$ in such a way that the error cannot be detected by the CRC with the $G(x)$ given above.
in Computer Networks by Veteran (106k points)
edited by | 807 views

4 Answers

+1 vote

CRC sent will be definitely 1100111001....its an easy approach appending 4 0's to bit sequence nd then dividing by generator that is a usual process.

the second question is more interesting..since it is asking to find the burst error of length 5 which cannot be detected by given generator.

according to rule in the burst error if the length of error equals to or greater than the degree of generator polynomial then it cannot detect that error.

so what we have to do is to make only an error of length 4 or more than that bcoz the degree of the generator is 4.

by Active (3.6k points)
0 votes
1) crc will be 001 becz g(x)= 11001 so ... we ll get 001 as crc
by (49 points)
crc will be 1001
Plz explain how to solve 2nd part
crc will be 1100111001   as crc is not only the remainder partbut when the message bits are appended with the remainder bits then it becomes cyclic redundancy checksum

if 1 0 1 1 0 0 is transmitted and 1 1 0 1 1 0 is received, then we can say that a burst error of length 4 has occurred

the above statement is wrong as mention i the question there are only 3 bit errors  

0 votes
the crc whould be 1100111001

for the second bit the answer whould be 1101010010
by Active (1.8k points)
For the second part the question is saying the length of the burst error has to be of length 5. But in your answer length is 7.

I think we can use 1010101001. Burst error starts from second bit from left and ends at 6th bit from left.

Please check this one.
What is the method of generating this erroneous code 1010101001 ?
0 votes

For the first part CRC will be 1001. So codeword will be 1100111001.

Now in CRC, If the generator is of degree d then it can detect all the burst error of length d, and all the burst error of length d+1 except one pattern.

so, in above bit sequence (1100111001) , burst error of length 5 can be generated like this:

0 _ _ _ 011001  .....(1)

(we can put either 0 or 1 in place of _ , as those bits may or may not be in error.)

 OR 10_ _ _ 01001 .....(2) 

OR  111_ _ _0001 ....(3) and more.

Now looking at the generator (11001), we can choose intermediate bits such that it becomes multiple of 11001.

so for Eq(1) we can choose M' as 0000011001

for Eq(2) 1010101001.

Please correct me if this is wrong.

by (323 points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,394 answers
105,446 users