Skip to main content
4 of 4
completely rewritten
Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209

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?)

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 ?

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.

Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209