Fix polynoms g1(x), g2(x) over F\_2[x].


**Question:** How to find minimum over polynoms p(x) of the:


*HammingWeight(p(x) g1(x) ) + HammingWeight(p(x) g2(x) )* ? 


By HammingWeight of polynom I mean number of non-zero monoms, let me denote by || \*||


Trivial estimate: minimum <= || g1(x)|| + || g2(x)||. Proof just put p(x) =1.


Numerical observation: apparently there are polynoms g1,g2 where this estimate is exact.
Can this be true ?




---


**Modified question 1** If I put restriction deg(p(x)) < N with N>> deg(gi) will it change minimum ? if yes what can be said about it ? 


**Modified question 2** If I put restriction deg(p(x)) < N and moreover
will consider multiplication in the factor F\_2[x]/ (x^N-1) will it change minimum ? if yes what can be said about it ? 




---


**Error-correcting codes formulation** 
The question is how to calculate minimal distance of [non-recursive convolutional code](http://en.wikipedia.org/wiki/Convolutional_code#Recursive_and_non-recursive_codes) ?


If I put restriction deg(p) < N this corresponds to various truncations of them.
In particular working with F\_2[x]/ (x^N-1) corresponds to "tail-biting".




---


PS


This is completely rewritten version of the previous 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?)
Presumably you forgot to add the condition $\gcd(g\_1(x),g\_2(x))=1$ for otherwise you would allow catastrophic encoders (a finite number of channel errors may cause an infinite number of
errorneously interpreted input bits).


The minimum distance of a convolutional code can be calculated by a slightly modified Viterbi algorithm. Calculate the least possible Hamming distance to the all-zero path. All you need to is to snip the first edge going from the zero state to the zero state to force the first input to be non-zero. Then keep running Viterbi until the minimum penalty surviving path is at the zero state. The penalty of that survivor is the minimum distance.


Letting $N$ grow without bound will obviously not change this after you have reached that point.


I don't know what happens with the tailbiting version. Some modifications to the above algorithm probably exist, but pseudocodewords will disturb it.


