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)$.

- Calculate the CRC value of the bit sequence $1 \: 1 \: 0 \: 0 \: 1 \: 1$, if $G(x) = x^4 + x^3 + 1$.
- 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.

+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.

0 votes

0 votes

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** _ _ _ **0**11001 .....(1)

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

OR 1**0**_ _ _ **0**1001 .....(2)

OR 11**1**_ _ _**0**001 ....(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 **00000**11001

for Eq(2) 1**01010**1001.

Please correct me if this is wrong.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,394 answers

198,594 comments

105,446 users