2
$\begingroup$

Reference Question from Forouzon Book Computer Network. Find the status of the following generator related to two isolated, single-bit errors. $$x^{15} + x^{14} + 1$$ Answer given : This polynomial cannot divide any error of type $x^t + 1$ if t is less than 32,768. This means that a codeword with two isolated errors that are next to each other or up to 32,768 bits apart can be detected by this generator. Can some one please help me why is this true...? Or even how should I have an in general approach to analyze such questions...? (Sorry if this is very silly, but I am unable to get a grasp of how the reason works...!)

$\endgroup$
2
$\begingroup$

Your polynomial is primitive, which means that the order of $x$ modulo your polynomial is exactly $2^{15}-1$. In particular, $x^a \not\equiv 1$ modulo your polynomial for all $1 \leq a \leq 2^{15}-2$, which means that your polynomial doesn't divide $x^a-1$ for this range of $a$.

(This also means that your polynomial should divide $x^{2^{15}-1}-1$, in contrast to what the question claims.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please explain it a bit more briefly I am trying to understand it but still stuck at how come a Database Management Course book taking me to primitive ..and plz also explain a bit more about how and why are these primitive polynomials coming to picture...(sorry if you find it silly) $\endgroup$ – Piyush Sawarkar Mar 11 at 18:47
  • $\begingroup$ The internet has an endless amount of material on primitive polynomials. $\endgroup$ – Yuval Filmus Mar 11 at 18:48
  • $\begingroup$ Okay so tell me one thing ..if I have $x^5+x^4+1$ then would this be also equivalent to $x^{2^5-1}-1$..? $\endgroup$ – Piyush Sawarkar Mar 11 at 18:51
  • $\begingroup$ I could look it up in a list of primitive polynomials, but so could you. $\endgroup$ – Yuval Filmus Mar 11 at 18:52
  • $\begingroup$ ok..now I got it thanks for help!! $\endgroup$ – Piyush Sawarkar Mar 14 at 14:48

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.