-1
$\begingroup$

"Let $G\left ( x \right )$ be the generator polynomial used for CRC checking.What is the condition that should be satisfied by $G\left ( x \right )$ to detect odd number of bits in error?
a) $G\left ( x \right )$ contains more than two terms
b) $G\left ( x \right )$ does not divide $1+x^{k}$ , for any $k$ not exceeding the frame length
c) $1 + x$ is a factor of $G\left ( x \right )$
d) $G\left ( x \right )$ has an odd number of terms."

While learning about CRCs in link layer error control,I came to know that the error detection power of a CRC depends on its Generator Polynomial and we should pick $G\left ( x \right )$ carefully.
but my intuitions about CRC are not strong enough to answer this question.
Could anybody please help me out here?

$\endgroup$
  • $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$ – D.W. Jan 14 '16 at 16:12
  • $\begingroup$ I am sorry for asking this question here, sir.I'll refrain myself from asking such questions in future. $\endgroup$ – Romy Jan 14 '16 at 16:54
  • $\begingroup$ Did you ever find out the correct answer? $\endgroup$ – AndyG Nov 15 '16 at 15:11
1
$\begingroup$

I'm no expert, but I dug into this a bit, so please correct any mistakes.

From Wikipedia:

A common misconception is that the "best" CRC polynomials are derived from either irreducible polynomials or irreducible polynomials times the factor 1 + x, which adds to the code the ability to detect all errors affecting an odd number of bits.

So you want your generator polynomial to be an irreducible one.

Also from Wikipedia:

An irreducible polynomial is, roughly speaking, a non-constant polynomial that cannot be factored into the product of two non-constant polynomials.

This rules out option a):

a) $G\left ( x \right )$ contains more than two terms

because plenty of 3 term polynomials are in fact not irreducible, for example (also from Wikipedia)

$p_1(x)=x^2+4x+4\,={(x+2)(x+2)}$

In fact, this also rules out option d), too:

d) $G\left(x\right)$ has an odd number of terms.

Which leaves us with either b) or c). Examining c):

c) $1 + x$ is a factor of $G\left ( x \right )$

Well, from http://www.cs.jhu.edu/~scheideler/courses/600.344_S02/CRC.html

Consider how the CRC behaves [if] $G\left(x\right)$ is $x^k +1$ for some $k$ larger than one. Obviously, this CRC will catch any error that changes an odd number of bits.

Implies that the most common way to create a generator polynomial to detect an odd number of bits is to use this technique, so my wager is that c) if the correct answer.

As for b). I cannot discern any significance from the statement (I'm not sure what its implications are)

$\endgroup$
-2
$\begingroup$

If there have been two isolated single-bit errors, $E(x) = x^i + x^j$, where $i > j$. Alternatively, this can be written as $E(x) = x^j(x^{i − j} + 1)$. If we assume that $G(x)$ is not divisible by $x$, a sufficient condition for all double errors to be detected is that $G(x)$ does not divide $x^k + 1$ for any $k$ up to the maximum value of $i − j$ (i.e., up to the maximum frame length). Simple, low-degree polynomials that give protection to long frames are known. For example, $x^{15} + x^{14} + 1$ will not divide $x^k + 1$ for any value of $k$ below $32,768$.

If there are an odd number of bits in error, $E(X)$ contains an odd number of terms (e.g., $x^5 + x^2 + 1$, but not $x^2 + 1$). Interestingly, no polynomial with an odd number of terms has $x + 1$ as a factor in the modulo $2$ system. By making $x + 1$ a factor of $G(x)$, we can catch all errors with an odd number of inverted bits.

Source: Computer Networks by A. Tanenbaum 5th edition, page number: 214

$\endgroup$
  • 2
    $\begingroup$ Thanks for contributing but, we're not really looking for copy-pastes from textbooks. $\endgroup$ – David Richerby Aug 28 '18 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.