Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Jyrki Lahtonen Jul 25 '12 at 6:40
    
Related question: math.stackexchange.com/questions/177465/… –  Alexander Chervov Aug 1 '12 at 10:28

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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 ? –  Alexander Chervov Jul 24 '12 at 13:35
    
Maybe you should post that as a new question. –  Gerry Myerson Jul 25 '12 at 5:55
    
    
Related question math.stackexchange.com/questions/177465/… –  Alexander Chervov Aug 1 '12 at 10:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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