Timeline for How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 7, 2012 at 7:49 | comment | added | Jyrki Lahtonen | As this polynomial has an irreducible primitive factor of degree 15, we must impose a restriction $N<2^{15}-1$. | |
| Jul 7, 2012 at 7:45 | comment | added | Jyrki Lahtonen | This is, of course, correct. But for exactly this reason (any polynomial over $GF(2)$ is a factor of a binomial) all the CRC-polynomials come together with a maximum length for the data packet that you can protect it with. The range of interesting values of $N$ has an upper bound. I'm afraid I don't remember what it is for this particular CRC-polynomial. | |
| Jul 6, 2012 at 19:41 | comment | added | Douglas Zare | If $g$ is divisible by $x+1$ then there is a parity issue, but perhaps other than that the distribution could look roughly Gaussian near the center. In other words, perhaps the probability that a random polynomial of weight $k$ is divisible by $g$ is roughly constant. You can prove that there are many polynomials with weights close to $N/2$ which are divisible by $g$ since there are many multiples of $g$, and not so many polynomials with weights far from $N/2$. | |
| Jul 6, 2012 at 9:52 | comment | added | Alexander Chervov | @Douglas Zare thank you very much ! Indeed I was wrong. I added some guess about the distribtion. I would be happy if you comment on this. The guess is simple - distribution is the "same" as for g=x^16, for which it is obviously binomial coefficient (N-16,k) | |
| Jul 6, 2012 at 8:55 | history | answered | Douglas Zare | CC BY-SA 3.0 |