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.

Improve this question
$\endgroup$
2
  • $\begingroup$ You can get the weight distribution of such words that enter the zero state of the trellis only at the beginning and at the end from a suitable generating function. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 25, 2012 at 6:40
  • $\begingroup$ Related question: math.stackexchange.com/questions/177465/… $\endgroup$
    – Alexander Chervov
    Commented Aug 1, 2012 at 10:28

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ah... Thank you very much ! I should think more before asking... Well, any way the bigger question behind is the following : can we generate some other examples of g1(x) g2(x), such that we can guarantee that norm of image is |g1|+|g2| ? How to describe all such g ? $\endgroup$
    – Alexander Chervov
    Commented Jul 24, 2012 at 13:35
  • $\begingroup$ Maybe you should post that as a new question. $\endgroup$
    – Gerry Myerson
    Commented Jul 25, 2012 at 5:55
  • $\begingroup$ Asked mathoverflow.net/questions/103196/… $\endgroup$
    – Alexander Chervov
    Commented Jul 26, 2012 at 13:56
  • $\begingroup$ Related question math.stackexchange.com/questions/177465/… $\endgroup$
    – Alexander Chervov
    Commented Aug 1, 2012 at 10:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .