Timeline for 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?)
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2012 at 7:22 | vote | accept | Alexander Chervov | ||
| Jul 24, 2012 at 7:21 | comment | added | Alexander Chervov | @Jyrki Lahtonen Thank you very much ! My e-mail is al.mylastname at gmail . com please e-mail me yours lecture notes | |
| Jul 20, 2012 at 12:06 | comment | added | Jyrki Lahtonen | (cont.) The Griesmer bound in particular turned out to be very useful in such exercises. If you are interested, I can e-mail you those lecture notes. the previous comment (and this one up to this point) were thought out before I saw the question about Goppa codes. Yes $F_2((D))$ is the proper algebraic playground. I don't think there are any good families of convolutional codes other than the Wyner-Ash codes. I have asked this from a few researchers in the area, and they say that non are known. Joachim Rosenthal has some, but the alphabet was larger. | |
| Jul 20, 2012 at 12:00 | comment | added | Jyrki Lahtonen | Probably something can be said, but as the trellis may contain several edges labelled with the all-zero vector, it is not straightforward to tell how much. I don't have enough experience with this to tell. I just checked the lecture notes of a course on convolutional codes that I wrote 14 years ago. In all the examples/exercises that I had, testing a candidate pair $(g_1(D),g_2(D))$ against at most quadratic inputs (i.e. $\deg p(x)\le 2$) was enough. The reason is that one can use known bounds on the minimum Hamming distance of binary linear codes to rule out many possibilities. | |
| Jul 20, 2012 at 11:32 | comment | added | Alexander Chervov | I would prefer to speak F_2((D)) otherwise you indeed should say "multiply by D^k". Am I right - that no problem to substitute by F_2((D)) yours F_2[[D]] ? Some analogy comes in my mind - in my "previous life" I studied algebraic curves and the following construction was important: take curve "C", point z, local coordinate "D" around this point. Consider subspace "L" in F_2((D)) which is generated by rational functions on the curve "C" which may have pole only at "x". I wonder will this generate somewhat like a code ? May be it is something like Goppa code ? | |
| Jul 20, 2012 at 11:25 | comment | added | Alexander Chervov | You write: "Then keep running Viterbi until the minimum penalty surviving path is at the zero state. " Can algebra help us to estimate the time of running ? | |
| Jul 20, 2012 at 8:32 | comment | added | Jyrki Lahtonen | Either just the power series, or (going to the field of fractions) allow polynomials of $D^{-1}$ also. So only a pole of finite order is ever allowed. The practical convolutional encoders must have generators in $F_2[[D]]\cap F_2(D)$, i.e. rational functions that have causal power series representations, for if the denominator is divisible by $D$, then the encoder will need to know input bits from the future, breaking causality :-). Multiplying everything by a power of $D$ amounts to just translating the origin of the time axis, so does not really change anything. | |
| Jul 20, 2012 at 8:11 | comment | added | Alexander Chervov | Do you mean F_2[[D]] i.e. D^k k>=0 or F_2((D)) - Laurent power series with D^k k>-Inf ? | |
| Jul 20, 2012 at 8:03 | comment | added | Alexander Chervov | Thanks very much ! I do not mean "simple" answer - I mean some answer in terms of algebra (may be complicated - Galois orbitrs whatever), not Viterbi which at first look is not algebra. For example if we consider just 1 polynom i.e. coderate =1, at least algebra can give answer that for big length the distance will be equal to 2 - since we can find x^n-1 divisible by any g. Can we see it from Viterbi ? | |
| Jul 19, 2012 at 19:33 | comment | added | Jyrki Lahtonen | (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. | |
| Jul 19, 2012 at 19:25 | comment | added | Jyrki Lahtonen | @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. | |
| Jul 19, 2012 at 19:13 | comment | added | Alexander Chervov | 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 ? | |
| Jul 19, 2012 at 19:05 | comment | added | Alexander Chervov | 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. | |
| Jul 19, 2012 at 17:20 | comment | added | Alexander Chervov | Can the answer be expressed in terms of polynoms? | |
| Jul 19, 2012 at 14:36 | history | answered | Jyrki Lahtonen | CC BY-SA 3.0 |