How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)

Question

Let us consider polynoms over $F_2$. Consider the linear SUBSPACE of polynoms divisible by $x^{16}+x^{12}+x^5 +1$ and of degree less or equal $N$ (e.g. 40).

Question: How many k-nomials belong to this subspace ?

By k-nomials I mean polynom containing only $k$ monomials, e.g. x^2+x - is 2-nomial.

---

Motivation and more general question

$g = x^{16}+x^{12}+x^5 +1$ is generating polynom for the CRC-16-CCITT error-correcting code. I am intersting about the Hamming weight distribution for the code-words, it is important characteristics of the code.

Question More generally we can take other "generating polynoms" and ask a similar questions, what is known about it ?

---

Examples

k =1 , answer = 0, rather obviously for all N.

k = 2 , answer = 0, (Wrong as Douglas Zare pointed in his answer)

k= 3 , answer = 0 , AFAIU (=as far as I understand)

k= 4 , answer N-15 , AFAIU (Wrong as Douglas Zare pointed in his answer)

Some guess based on numerical experiments

it seems the distribution is Gaussian like near its maximum - it seems that it does not depend much on polynomial (only tails depends), so we can take polynomial to be just g=x^16, for which the answer is obviusly binomial coefficient (N-16, k), which behaves like Gaussian by central limit theorem.

Questions Is this guess reasonable ? It is is correct what is the deviation of real distribution and gaussian ? What happens with tails ?

Answer 1

Your examples are wrong for large $N$. For large $N$, you can classify and count the polynomials with few terms divisible by $g$ by considering the powers of $x$ in $F_2[x]/g$. By the pigeonhole principle, some $x^a \equiv x^b \mod \langle g,2 \rangle$, which implies there are binomials divisible by $g$ for any $g$. In particular, $(x^{16}+x^{12}+x^5+1) ~|~ x^{32767} + 1 = x^{2^{15}-1}+1$. If the polynomial is chosen well, then $x$ may be primitive in $F_2[x]/g$, which would mean that the only binomials would be ones where $(2^{\deg g}-1) | (a-b)$.

Since $x^{16}+x^{12}+x^5+1$ has an even number of terms it is divisible by $x+1$, which can't divide any trinomial or other polynomial with an odd number of terms, so $x^{16}+x^{12}+x^5+1$ can't either. If $g$ were irreducible with $x$ primitive in $F_2[x]/g$, then for any $0 \le a \lt b \lt 2^{\deg g}-1$, there is a unique $0 \le c \lt 2^{\deg g}-1$ so that $x^a + x^b + x^c$ is divisible by $g$, and $c$ can't equal $a$ or $b$. It is possible when $x$ is not primitive that there don't have to be any trinomials divisible by $g$, e.g., $g = x^4 + x^3 + x^2 + x + 1$ does not divide any trinomials.

Similarly, if $g$ is irreducible and $x$ is primitive in $F_2[x]/g$ then $4$-nomials divisible by $g$ of degree up to $2^{\deg g}-1$ correspond to sums $\vec{v_1} + \vec{v_2}+\vec{v_3}+\vec{v_4} = 0$ where the $\vec{v_i}$ are distinct nonzero vectors in a $(\deg g)$-dimensional vector space over $F_2$, and these can be counted by inclusion-exclusion.

Your $g = (x+1)g_{15}$, where $g_{15} = x^{15}+x^{14}+x^{13}+x^{12}+x^4+x^3+x^2+x+1$ is an irreducible degree $15$ polynomial so that $x$ is primitive in $f_2[x]/g_{15}$. So, there are many $4$-nomials which are divisible by $g_{15}$ hence by $g$ which are not just $x^n \times g$. For example, $x^{16}+x^{12}+x^5+1 ~|~ x^{12496} + x^2 + x + 1$.

Answer 2

As noted by Douglas Zare, $x^{16} + x^{12} + x^5 + 1 = (x+1)g_{15}(x)$, where $g_{15}(x) := x^{15}+x^{14}+x^{13}+x^{12}+x^4+x^3+x^2+x+1$.

Let $Q:=\mathbb{F}_2[x]/\langle g_{15}(x)\rangle$ be the factor-ring of polynomials over $\mathbb{F}_2$ modulo $g_{15}(x)$. (Since $g_{15}$ is irreducible, $Q$ is isomorphic to $GF(2^{15})$ and thus has $2^{15}$ elements).

For any nonnegative integers $N,k$ and any $q(x)\in Q$, let $h_k(N,q)$ be the number of $k$-nomials $f(x)$ of degree $\leq N$ such that $f(x)\equiv q(x)\pmod{g_{15}(x)}$.

Clearly, $h_0(N,q(x)) = 0$ unless $q(x)= \mathbf{0}$, and $h_0(N,\mathbf{0}) = 1$.

For $k\geq 1$, we have $$h_k(N,q(x)) = \sum_{j=1}^N h_{k-1}(j-1,q(x)-x^j \bmod g_{15}(x)),$$ which allows to recursively compute $h_k(N,q(x))$. The answer to the first question for even $k$ is given by $h_k(N,\mathbf{0})$. Using dynamic programming, this computation will take $O(kn^2)$ arithmetic operations.