0
$\begingroup$

Everything over F_2. Let us define Hamming norm of polynom |p(x)| = number of non-zero monoms.

Respectivly for a pair of polynoms |[p ; g]| = |p| +|g|.

Consider linear map $F_2[x] \to F_2[x] \oplus F_2[x] $ given by $p(x) \mapsto [ p(x)(x^2+1) ; p(x) (x^2+x+1)] $.

Question Is it true that minimal Hamming norm in the image of the map above equal to 5 ? Of course, delete [0; 0] from the image.

It is clearly not more than 5, since take p(x)=1, then $1 \mapsto [ x^2+1; x^2+x+1] $. and $|x^2+1| =2$ $x^2+x+1 = 3$ , So 2+3 =5.

By brute force search for p(x): deg p <16 the answer is 5.

On the other hand it is clearly more than 4. Since when multiply any two non-monoms we will get non-monom and hence norm of each product is not less than 2.


However if I take x+1, x^2+x+1 the corresponding answer will be 4, because take p(x)= x+1, we will get:

[(x+1)(x+1); (x+1) (x^2+x+1)] = [x^2 + 1; x^3+1] - only 4 monoms so norm is 4.


This is toy model for convolutional error correcting codes.

See the question Given g1(x), g2(x) minimize over p(x) Hamming weight of [p(x)g1; p(x)g2(x) ] ? (Or how to find minimal distance of convolutional code?)


PS

The answer can be obtained by Viterbi algorithm as Jyrki Lahtonen suggests. However the question is so much down-to earth that probably some simple reason may exist

PSPS

Here is distribution of Hamming weights of image for p(x) deg p(x)<17

0, 0, 0, 0, 17, 31, 56, 100, 176, 409, 850, 1627, 2888, 4713, 7202, 10109, 13080, 15442, 16232, 15514, 13673, 10729, 7664, 5230, 2992, 1309, 630, 315, 70, 7, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0,

It is like Gaussian.

$\endgroup$
2

1 Answer 1

6
$\begingroup$

Yes. Without loss of generality, we can assume $p(x)$ is not divisible by $x$. Then $p(x)(x^2+1)$ and $p(x)(x^2+x+1)$ both have constant term $1$, so the combined Hamming weight is at least $4$ from the constant and leading terms. The only way it could be $4$ is if they were $x^n+1$ and $x^m+1$ for some $n$ and $m$. However, $p(x)(x^2+1)$ and $p(x)(x^2+x+1)$ have the same degree and are not equal to each other, so this cannot be the case.

$\endgroup$
4

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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