1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Forgot to write p(x) is NON zero. Otherwise we get zero Hamming weight immediately. $\endgroup$
    – Alexander Chervov
    Jul 19, 2012 at 19:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Can the answer be expressed in terms of polynoms? $\endgroup$
    – Alexander Chervov
    Jul 19, 2012 at 17:20
  • $\begingroup$ about gcd =1, thanks that it is interesting remark, but it seems to me I am allowed to ask this question for any polynoms - question is well defined as well as trivial estimate works. $\endgroup$
    – Alexander Chervov
    Jul 19, 2012 at 19:05
  • $\begingroup$ Thanks very much for Viterbi, it seems I understand what you mean if have time will try to check. But still, I am puzzled can the answer be expressed in terms of polynoms - the question seems quite belong to the realm of algebra, while Viterbi is something outside. Or may be Viterbi have some interpretation in terms of algebra ? $\endgroup$
    – Alexander Chervov
    Jul 19, 2012 at 19:13
  • $\begingroup$ @Alexander: I don't think that this question has a very simple answer in terms of the polynomials $g_1(x), g_2(x)$. Hamming weight is a relatively non-algebraic quantity. The reason, why I had to exclude the case $\gcd(g_1(x),g_2(x))\neq1$ is seen in the following example. Let $g_1$ be irreducible, and $g_2(x)=g_1(x)(1+x)$. Now, if your input sequence is the (truncated) Taylor series of $1/g_1(x)$, then the output will look more and more like the vector $(1,1+x)$ of Hamming weight 3, but the algorithm I proposed never terminates. $\endgroup$
    – Jyrki Lahtonen
    Jul 19, 2012 at 19:25
  • $\begingroup$ (cont') Many authors (at least McEliece, my favorite) define a $(n,k)$ convolutional code as rank $k$ free submodule $C$ of a free module $R^n$, where $R=F_2[[D]]$ is the ring of formal power series, such that the module $C$ has a basis with all components in $F_2(D)$, or rational functions. In other words the inputs might (in theory) continue indefinitely into the future, but must begin at some point in the past. The rationality of the components of generators guarantees that some set of inputs will terminate the code. $\endgroup$
    – Jyrki Lahtonen
    Jul 19, 2012 at 19:33

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.