User jyrki lahtonen - MathOverflow

Answer by Jyrki Lahtonen for What are "best" polynoms f(x) g(x) of degree n ? I.e. ideal generated by them is as far from zero as possible ? (Best convolutional codes.)

2012-07-30T11:01:21Z

The following simple (suboptimal) bound will get you started. It is easier to give a lower bound for the degree $n$ of the polynomials in terms of the minimum distance $d$, so I will do that. Feel free to turn this into an upper bound on $d$ :-)

From the theory of biinary linear block codes we recall the so called Griesmer bound. It states that if a binary linear code has dimension $k$, minimum distance $d$ and length $N$, then we have the inequality $$ N\ge\sum_{j=0}^{k-1}\lceil\frac{d}{2^j}\rceil. $$

We apply this to convolutional codes of the type that you describe as follows. Consider the subspace gotten by restricting the multiplier $p(x)$ to be of degree $\le m$. The dimension of this subspace is $k=m+1$. The degrees of $pf$ and $pg$ are both at most $n+m$, so the pairs $(pf,pg)$ have $N=2(n+m+1)$ coefficients. Thus Griesmer bound gives us the inequality $$ 2(n+m+1)\ge\sum_{j=0}^m\lceil\frac{d}{2^j}\rceil. $$

How to select $m$? When we increase $m\to m+1$, the l.h.s. increases by two, and the r.h.s. increases by $\lceil d2^{-m-1}\rceil$. Therefore we get the tightest bound on $n$, when $m$ is the largest natural number with the property $d>2^{m+1}$, because this is the largest $m$ such that all the terms on the r.h.s. are larger than two.

As examples consider $d=5$. Then we select $m=1$, and get the bound $$ 2(n+2)\ge 5+3\implies n\ge 2. $$ This bound is attained with the well known pair $f(x)=1+x^2$, $g(x)=1+x+x^2$. If we used $d=6$ instead, we would get $n\ge3$, so we can conclude that $d=5$ is the best we can do with quadratic $(f,g)$.

If we want $d=9$, then we can select $m=2$, and $$ 2(n+3)\ge 9+5+3=17\implies n\ge 6 $$ (bearing in mind that $n$ is an integer). We see that $d=10$ also gives $n\ge 6$, but $d=11$ would give $n\ge 7$. This implies that with sextic $(f,g)$ the best we can hope for is $d=10$. This bound is actually achieved by the pair $$ f(x)=1+x+x^3+x^4+x^6,\qquad g(x)=1+x^3+x^4+x^5+x^6. $$ IIRC this code was used during the Voyager mission to transmit data (e.g. the pretty images) back to Earth.

The above bound is not always accurate. There are several reasons for this. When $k$ increases, the Griesmer bound is no longer tight. Also, there is no reason to think that the type of binary linear codes by limiting the degree of $p$ would be optimal binary linear codes. Bounds like this will give you an idea, what to expect, and then you can start developing a search heuristic. If there is a precise answer to your question, then it will need to use some new machinery.

Answer by Jyrki Lahtonen for A combinatorial question

2012-07-27T15:00:32Z

Unless I made mistake a counterexample is formed by the binary $m$-sequence of length 7 $s=(1,0,0,1,0,1,1)$ and its reversal $\tilde{s}=(1,1,0,1,0,0,1)$ that is not a cyclic shift of $s$. Both lead to the sequence of generating functions $1+2a+2b+2ab$, $2a+b+a^2+2ab+a^2b$, $a+a^2+2ab+a^3+2a^2b$, $a^2+ab+2a^3+2a^2b+a^3b$, $2a^3+2a^2b+a^4+2a^3b$ and $3a^4+4a^3b$.

The $m$-sequences are examples of de Bruijn -sequences. That is binary sequences of length $2^n-1$ such that every sequence of $n$ bits (with the exception of $n$ zeros) occurs exactly once in the cycle. This is, of course, then a natural source for an eventual counterexample as the condition is automatically satisfied for $A_j, j\lt n.$ Length 7 is the shortest, where not all de Bruijn sequences are cyclic shifts of each other.

An $m$-sequence is generated by a linear feedback shift register that has a primitive polynomial of degree $n$ from the ring $\mathbb{F}_2[x]$ as a feedback polynomial. If you decimate an $m$-sequence with a decimation exponent $d$, $\gcd(d, 2^n-1)=1,$ by cyclically taking every $d^{th}$ member, you get another $m$-sequence. Therefore for larger $n$ the number of non-cyclically equivalent $m$-sequences increases. For example, the sequence $s$ is generated by the feedback polynomial $x^3+x^2+1$, or equivalently by the given first 3 bits and the recurrence relation $$s_n=s_{n-3}+s_{n-2}\pmod2$$ with subscript arithmetic done modulo seven. The reversed sequence $\tilde{s}$ is similarly generated by the reciprocal polynomial $x^3+x+1$.

I dare not guess yet, whether all $m$-sequences of a given length give rise to the same sequence of multisets.

Answer by Jyrki Lahtonen for Structure of F_p[G], for finite group G ?

2012-07-21T19:51:15Z

Adding a few words from the coding theory side. Abelian groups without $p$-torsion are somewhat more natural in coding theory, because then we get the machinery of discrete Fourier transform (which is, of course, just representation theory) to play with. Dihedral groups have been used as symmetry groups of cyclic codes (add order reversal symmetry), but for the most part symmetries of codes just aid proving things about their properties.

When the group has $p$-torsion, the theory is less clean. Nevertheless, the topic has been studied. Check out papers by Karl-Heinz Zimmermann (http://www.tu-harburg.de/ti6/mitarbeiter/khz/pub.html). In his papers from the 90s a lot of representation theoretical concepts appear. I don't know, if they are very hot from the point of view of constructing new and better codes, though.

Answer by Jyrki Lahtonen for What is matrix A such that Hamming weight of [x, Ax] is maximal ? (Min distance of 1/2 block code?)

2012-07-19T14:42:00Z

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

Asymptotically the best bound is usually the linear programming bound due to McEliec-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.

An interesting simple general existence proof is described in van Lint's book (Springer GTM series). Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where $x\in S(i), y\in S(j), i+j\lt d$. The number of disallowed elements $a$ is thus at most $$ N(d)=\sum_{0\lt i,j\lt d; i+j\lt d}{n\choose i}{n\choose j}. $$ If $N(d)\lt 2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.

Answer by Jyrki Lahtonen 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?)

2012-07-19T14:36:51Z

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.

Answer by Jyrki Lahtonen for Good codes in practice for correcting combination of errors and erasures

2012-07-15T06:42:08Z

The answer depends on several things.

If your channel (or receiver) produces erasures and errors, then the relevant metric is the Hamming metric, as a code with minimum distance $d$ can correct a combination of $t$ errors and $e$ erasures, iff $d>2t+e$. Therefore a code with good Hamming distance may be the way to go (if an efficient decoding algorithm is known for it). I say "may", because other considerations may be more pressing. For example, you may want to use longer blocks (often a good idea, because the errors are then averaged out better).

If the errors/erasures affect individual bits more or less independently, then you need a binary code. If OTOH the errors/erasure come in lumps (or "bursts"), then it is better to view them as byte-errors (or symbol errors, pick a symbol size that gives the best results), and RS-codes are your friend, because RS-decoders don't care how many bits in a symbol are incorrect. This may also be the case, when the input to your decoder is the output of another code (think: the microcode in CD-ROM that tries to interpret a single byte from the disk). If RS-codes have too short block lengths for your purposes, you can try an algebraic-geometry code instead, but sadly I have never seen an application, where the savings would have been significant.

A generic erasure decoding algorithm for a binary linear code that has an error-correcting-algorithm is to do two error-correction attempts: one with all erasures replaced with ones, and another with all erasures replaced with zeros. At least one of those decoding attempts will succeed, if the inequality $2t+e\lt d$ holds. If both succeed, then you need to compare the two outputs to find the better match. This does not work with byte-errors, but the RS-codes (as well as the AG-codes) have errors-and-erasures decoding algorithms.

If your channel (and receiver) actually produce soft errors (= full continuum of likelihoods for a given bit to be 0 or 1), then you should try either a convolutional code, a turbo code, or an LDPC-code depending on the block length. If your blocks are long (over 10000 bits or thereabouts) I would try using an LDPC-code anyway, but I don't have any experience using an LDPC-code with errors-and-erasures only. Surely somebody has tried it, and can give rules of thumb on "how to treat the output of a hard decision receiver in a belief propagation algorithm".

Answer by Jyrki Lahtonen for Error correcting codes obtained as superposition of two codes e.g. CRC+Convolutional

2012-07-10T08:22:58Z

You do know how to calculate the minimum distance (=free distance?) of a convolutional code? Cut the first edge from the zero state to the zero state (to disallow the all zeros word), and run Viterbi (but counting the weight, or distance to the all zero word) to the point, where all the states have surviving minimal path of weight at least the weight of the surviving path back to the zero state. I guess this can be tweaked to cover your simplest case of a single parity check bit. Essentially now the "legal" inputs to the convolutional encoder are all the even weight sequences. So in the above algorithm we need to double the state complexity as follows. For each state we maintain two penalties: one for paths of an odd input weight and another for even input weights. Then when you run an iteration of Viterbi algorithm you match the parities according to the value of the new input bit. The stopping condition now applies to both variants of the penalty function, but comparisons are to be made only to the penalty of even input weight paths leading to the zero state.

It should be possible to also enumerate words corresponding to even input weights by a suitable variant of the transfer function or some such generating function.

How to decode? The first possibility that comes to mind is to replace the usual Viterbi algorithm with soft-output Viterbi algorithm (aka SOVA) that outputs, not the most likely path, but instead probabilities for each individual bits (often written as log-likelihood-ratios $LLR_i=\ln (P(b_i=0)/P(b_i=1))$, but that may not be needed here). Then if the sequence of bit values corresponding to the more likely choice has an even weight, you accept that. If that sequence has an odd weight, you flip the least reliable bit.

[Edit:] Arrgh! I only noticed after rereading that you were interested in tailbiting codes. The above method for calculating the minimum Hamming weight no longer works. There may be too many pseudocodewords. I'm sure that some algorithms have been developed to attack this, but cannot describe one. The decoding, surprisingly, may not be affected too much by tailbiting. I would begin by studying the sections on tailbiting convolutional codes in Johannesson & Zigangirov's book.

Answer by Jyrki Lahtonen for Will "error locating codes" have higher rates than ECCs?

2012-06-06T07:52:32Z

A bit of terminology:

An error-detection-code usually means something else. An error-detection-code is expected to raise a flag if something is wrong, IOW if the received sequence is not a valid codeword, or yet IOW at least one of the symbols $c_i$ is incorrect. It is NOT about telling that, for example, $c_{235}$, $c_{1123}$ and $c_{4095}$ are wrong but the rest are ok. A common (but not the only) technique for error-detection is a cyclic redundancy check aka CRC. To learn more look up CRC-polynomials.

As Chris Godsil points out, a code with minimum Hammind distance $2e+1$, thus guaranteed to be able to correct any $e$ errors at unknown locations, is also guaranteed to detect the presence of any pattern up to $2e$ errors. Simply because the received vectors will then not be a valid codeword - there are no other valid codewords within Hamming distance $2e$.

Some good error correcting codes (such as RS-codes) can also correct erasures = unknown errors at known locations. This is handy in e.g. CD-players, because the scratches can be detected, their locations are known, and can be filled in be an erasure-correcting-code. For example an RS-code with minimum distance $d$ can correct up to $d-1$ erasurers. This follows basically from Lagrange's interpolation polynomial formula: the words of an RS-code with length $n$ and minimum distance $d$ can be viewed as graphs of polynomials of degree $\le n-d$. With at most $d-1$ erasures, we know the value of such a polynomial at $n-d+1$ points and can fully recover it. The same does not hold for all error-correcting-codes, though.

You seem to be asking for codes that can find the error locations but not the error values. As Gerry Myerson promptly pointed out, if your alphabet is binary, this amounts to error correction, because the error can have only one value (= the bit has been toggled). Otherwise this does not match with any of the above concepts. For lack of a better term, let's call this an error-locating-code. It seems to me that to be able to locate all patterns of up to $e$ errors, you still need the code to have minimum Hamming distance at least $2e+1$. For if the minimum distance is at most $2e$ you can find vectors in-between two nearby codewords that differ from both at at most $e$ positions, and hence would be torn between two alternative sets of error locations. This argument suggests to me that a code capable of locating $e$ error will also be able to correct $e$ errors.

The scene may change somewhat, if you are only interested in success at high probability. I don't know.

But I'm a bit curious. What kind of an application did you have in mind? Rarely is a single symbol important, or if it is (say matters of national security or some such) we need the entire message to be correct, in which case the usual error-detection will get the job done. High reliability for bulk data is often achieved by some kind of a catenated scheme. Thinks of the data places in a matrix. Do error-correction column per column. If successfull, mark the data reliable. If not, mark it erased (=suspect). Then do erasure-correction row by row. This is actually how CD-players do it (I was just kidding earlier).

Answer by Jyrki Lahtonen for Fibonacci Numbers Modulo m

2012-05-31T17:37:33Z

Sorry, I couldn't get access to the paper you referred to. For a prime modulus $p>5$ it is easy to show that the period of the Fibonacci sequence is a factor of either $p-1$ or $2(p+1)$ depending on whether $5$ is a quadratic residue modulo $p$ or not (or by reciprocity, whether $p\equiv\pm1\pmod5$ or not). This is because the roots of $$ x^2-x-1=0 $$ over $F_p$ are either in $F_p^*$ (if that polynomial factors modulo $p$), or in $F_{p^2}^*$. In the former case they are roots of unity of order that is a factor of $p-1$. And in the latter case the roots $\tau_1,\tau_2$ are conjugates of each other, and hence satisfy both equations $$ \tau_1^p=\tau_2,\qquad \tau_1\tau_2=-1 $$ implying that they both are roots of unity of order dividing $2(p+1)$. The periodicity then follows from Binet's formula.

Oh. Your program is leaving the integer domain. Are you sure you are not getting any overflows/loss of accuracy? You would need accuracy of something like 20 significant digits to handle $F_{200}$. Why aren't you using the recursive code? Storing two last entries is enough!

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

2012-05-29T13:40:42Z

Title question description: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize the lattices in such a way that the fundamental region has area $=1$. Let $B(r)$ be a disk of radius $r$ centered at the origin. Let $N_1,N_2>0$ be two parameters. Select one non-zero vector $\vec{v}_1$ from $B(N_1)\cap \Lambda_1$ and another $\vec{v}_2$ from $B(N_2)\cap \Lambda_2$. Consider the area of the parallelogram with sides $\vec{v}_i,i=1,2.$ Let $D(N_1,N_2)$ be the minimum area of such parallelograms. We want to make the function $D(N_1,N_2)$ as large as possible by selecting the lattices $\Lambda_1$ and $\Lambda_2$ in a clever way. The simplest form of my question is: what can we say about the asymptotic behavior of $D(N_1,N_2)$ as the parameters $N_1,N_2\to\infty$ (either separately or jointly)? As additional questions I would like to ask: Does this ring a bell? What kind of methods have been used in studying this problem? What methods would you use?

What we know about the problem: The pigeon hole principle tells us that there is a constant $K$ such that $$ D(N_1,L_{2,\min})\le \frac{K}{N_1}, $$ where $L_{2,\min}$ is the length of the shortes vector of $\Lambda_2$. The proof is easy. Fix a short non-zero vector $\vec{v}_2$ from $\Lambda_2$. The orthogonal projections of the vectors from $\Lambda_1\cap B(N_1/2)$ on to the line $\perp\vec{v}_2$ have lengths $\le N_1/2$. As there are $O(N_1^2)$ points in $\Lambda_1\cap B(N_1/2)$, some of those projections are within $O(1/N_1)$ of each other. Let $\vec{v}_1$ be the difference vector. As it is the difference between two vectors of length $\le N_1/2$, we have $\vec{v}_1\le N_1$.

In the above image the short arrow is the vector $\vec{v}_2$. The black line is the subspace generated by it, and the grey line is the orthogonal complement. The dots mark the points of the lattice $\Lambda_1$. Two points with nearby projections have been singled out by using larger dots. As is their difference vector $\vec{v}_1$, whose projection is then predictably very short. I also drew another copy (= the other arrow) of $\vec{v}_2$ to begin at the endpoint of $\vec{v}_1$. The two copies of $\vec{v}_2$ are a pair of parallel edges of the parallelogram. The small parallelogram has base $=|\vec{v}_2|$ and height = the length of the projection of $\vec{v}_1$ on the grey line. When drawing this image, I was selecting the lattice points from a square shaped region as opposed to a disk. The effects of that change can be absorbed into the constant $K$, and can IMHO be ignored.

Using real quadratic number fields and Liouville's theorem it is easy to construct lattices $\Lambda_1$ and $\Lambda_2$ in such a way that we always have $$ D(N_1,N_2)\ge \frac{K'}{N_1N_2}. $$ In this sense the pigeon hole bound from the previous paragraph has the correct order, when $N_2=L_{2,\min}$. Ideally I would like to apply Minkowski's bound to the direct sum of the lattices, but the determinant of a 2x2 real matrix is a quadratic form of signature (2,2), so I don't see how to select a usefully large convex region with small determinants (in absolute value). In light of this I think a natural main question would be

Is their a known upper bound $D(N_1,N_2)\le f(N_1,N_2)$ where both $N_1$ and $N_2$ appear effectively?

With the word effectively I mean that a bound should decrease, when we increase either $N_1$ or $N_2$. For example, in the above application of the pigeon hole principle we can trivially switch their roles to get a symmetric function $D(N_1,N_2)\le K\max\{N_1,N_2\}^{-1}$, but this is not effective :-)

The problem we really want to solve: Let $\Lambda_i, i=1,2,\ldots,U$ be lattices of complex (resp. real) $r\times n$ matrices, $n=rU$ of maximal possible rank $2rn$ (resp. $rn$). Select non-zero matrices $X_i$ from $\Lambda_i\cap B(N_i)$. Build an $n\times n$ matrix $X$ by putting these blocks on top of each other. What can we say about the minimal absolute value $D(N_1,N_2,\ldots,N_U)$ of $|\det X|$? We have generalizations of the pigeon hole bound, the best given by a graduate student in our group: http://arxiv.org/abs/1201.5744. He also has a construction based on algebraic number theory and Shidlovskii's bound from Diophantine approximation here: http://arxiv.org/pdf/1202.0675.pdf. That construction meets the pigeon hole bound in the case that $N_2,N_3,\ldots,N_U$ are small constants. Other researchers had earlier given somewhat similar constructions, but Shidlovskii's bound gives worse estimates to their $D$-function - Toni Ernvall managed to keep the matrix entries in a smaller field, which helped quite a bit. My gut feeling is that the constructions are closer to the optimal than the pigeon hole bound, because the latter is kinda trivial.

In the case $U=1$ the answer is known, because then we only need to select a single rank $2n^2$ of complex $n\times n$ matrices. If the said lattice is (a scaled version of) an order of a division algebra of index $n$ with an imaginary quadratic number field as a center, then the determinants will be bounded away from zero. Whenever $U>1$ the pigeon hole bound forces arbitrarily small determinants to occur.

Background: All this is related to the problem of estimating the performance of these lattices as signal sets for multiantenna radio communication: a single row = the signal of a single transmission antenna, $U$ is the number of simultaneous users, a lattice is the signal set of a fixed user. The study of the function $D(N_1,N_2,\ldots, N_U)$ is related to certain asymptotice figures of merit, but unfortunately the information-theory goes over my head. Some colleagues had hoped that it would be possible to have determinants bounded away from zero also, when $U>1$. The pigeon hole bound was our way of showing that they were asking too much. The math is not too hot, but it earned me a trip to ITW2010 in Cairo, so I got to see the pyramids!

Answer by Jyrki Lahtonen for Reed-Muller-Codes

2012-05-22T08:51:42Z

A thing to remember is that the customer is interested in the probability of correct reception after the error-correcting-code has done its magic.

The 5-dimensional Reed-Muller code of length 16 and minimum Hamming distance is capable of correcting 3 errorneous bits. The 6-dimensional Reed-Muller code of length 32 and minimum Hamming distance 16 is capable of correcting 7 errorneous bits. Let us assume a very simplistic model in which all the bits are received errorneously at the same probability $p\in(0,1)$, independently from each other. The probability of correctly decoding a received word of $R(4,1)$ is thus

$$P_4(p)=\sum_{i=0}^3{16\choose i}p^i(1-p)^{16-i},$$

and the same probability with the code $R(5,1)$ is

$$P_5(p)=\sum_{i=0}^7{32\choose i}p^i(1-p)^{32-i}.$$

Unless I made mistake, we have $P_5(p)>P_4(p)$ for most small values of $p$. For example, $P_5(0.1)=0.9883$ and $P_4(0.1)=0.9316$. And at $p=0.01$ we have $1-P_5(0.01)=8.5\cdot10^{-10}$ and $1-P_4(0.01)=1.7\cdot10^{-5}$.

So when transmitting an image of 1000 x 1000 pixels at $p=0.01$, we expect to receive an image free of errors, when using $R(5,1)$, but expect a few dozen garbled pixels, when using $R(4,1)$. Furthermore, to correctly receive 5 pixels worth of image data, we need to correctly receive 5 blocks of $R(5,1)$ instead of 6 blocks of $R(4,1)$. In other words, in terms of payload the fair comparison should be made between $P_4(p)^6$ and $P_5(p)^5$.

Above I assumed a decoding logic decoding up to the guaranteed error-correction probability only. One might attempt a more complicated receiver (using soft input) doing full soft decision decoding (which in this case amounts to a simple Walsh-Hadamard transformation). I don't know whether that would change the verdict, though.

Moral: long codes often work better. The reason is that in a short block the number of errorneous bits has a higher (relative) variance, and thus it is easier for the number of errors to exceed the error-correcting-capability of the code. Or yet in other words, a short code with the same relative Hamming distance will run into problems handling a burst of errors.

But the question of the code rate is not without merit either!!! In the Mariner application it would have meant that it takes a longer time to transmit a single image using $R(5,1)$ than it would with $R(4,1)$. The eager astronomers can wait a bit longer to get the image, but a serious concern is that probe uses a fixed amount of battery power per transmitted bit. This would also need to be taken into account, so my figures are not fair to the shorter code. In terrestrial communication systems we carry out extensive simulations before we choose one coding scheme over another, and plot the probability of an error vs. energy per transmitted bit. With Mariner, we could try and estimate the relation between $p$ and energy consumption per bit, but I don't have the time to get into that.

Trying to add a more meaningful comparison. Let's have Mariner transmit 5 pixels worth of bits. Using $R(5,1)$ it needs to transmit a total of $5\cdot32=160$ bits as opposed to $6\cdot 16=96$ bits required when using $R(4,1)$. Therefore, for a fair comparison, Mariner can spend $160/96=5/3$ times as much power per bit when using $R(4,1)$. So we can assume that using $R(5,1)$ Mariner transmits a real number $+1$ or $-1$ according to whether a bit zero or one is intended. Then using $R(4,1)$ it can transmit $\pm\sqrt{5/3}$ for the same total power consumption. The receiver interprets a positive received number as the bit zero and a negative as the bit one.

Assume that noise has deviation $\sigma=0.5$. With $R(5,1)$ we then get a bit error, when noise exceeds $+2\sigma$, so this happens with probability $p_5=1-\Phi(2.0)=0.0228$. The corresponding bit error probability when using $R(4,19$ is then $p_4=1-\Phi(2.0\sqrt{5/3})=1-\Phi(2.58)=0.0049$, because this time we $\sqrt{5/3}$ times as much noise as earlier. The test is then to compare $$ 1-P_5(0.0228)^5=2.35\cdot10^{-6} $$ to $$ 1-P_4(0.0049)^6=6.01\cdot10^{-6}. $$ We see that we do have a better chance of correctly receiving 5 pixels worth of data using the longer code, but the difference is not nearly as dramatic as the earlier figures, disregarding the energy consumption, would have indicated.

Answer by Jyrki Lahtonen for Stochastic process with Bessel function autocorrelation. (Rayleigh (Jakes) fading for radiowave propagation)

2012-03-29T07:33:21Z

Jakes is a bit beyond me, but I'm fairly sure that the Bessel function $J_0$ emerges, because of the integral presentation $$ J_0(x)=\frac1{2\pi}\int_{-\pi}^{\pi}e^{ix\sin t}dt. $$ If you have two plane waves of the same frequency, the other reflected so that the two copies have angular separation $\theta$. Then their correlation would vary like $e^{ix\cos\theta}$, because the the projection of the wavelength of the other wave along the direction of propagation of the other gets multiplied by $\cos\theta$. Now treat $\theta$ as a random variable uniformly distributed over the circle and compute the average.

IOW, I think that the Bessel function emerges as a consequence of the underlying geometry as opposed to being a design parameter. Hopefully a more knowledgeable person can answer. This was just a bit too long to fit into a comment.

Answer by Jyrki Lahtonen for Hot-topics in error correcting coding related to interesting math. ?

2012-03-26T19:33:30Z

Your list certainly has many nice topics.

1) Yup. This would be nice to have. In practical applications we can get rid of the error-floor by concatenating a decent LDPC with a good high rate algebraic code such as a BCH-code that can then correct the residual errors (the one application I know about is the second generation standard for European digital video broadcast, aka digi-TV, their the code length is 64800 or 16200 bits). What makes this challenging is that designing a good LDPC-code requires familiarity with some tools from stochastics (lost me at that point), but those tools don't say anything about the minimum Hamming distance.

Many a standard (IIRC in addition to European DVB also MediaFlo, a US standard for something similar) uses families of LDPC-codes designed around a specific decoding circuitry. This is more or less necessary, because otherwise the problem of routing the messages generated by the belief propagation algorithm becomes prohibitive. An exception to this rule is the Chinese video broadcast standard. At least the parts of that standard that I have seen describe the LDPC-codes in such a way that no structure is apparent. They may be protecting their intellectual property :-)

So a breakthru in this area would probably have to also keep this in mind in order to end up in future applications.

Hopefully more knowledgable people can comment. I do expect something to happen here in years to come, but the existing LDPC codes already work quite well.

2) This was a relatively hot topic a few years. I am a bit hesitant to call it coding theory - calling it multiantenna signal constellation design might be more fitting, but whatever :-).

By using basic facts of global class field theory my graduate students managed to "improve" upon the Golden code (by Oggier et al). I put the "improve" in quotes, because the improvement is somewhat theoretical. A more precise way of stating their result is that if you carve a given number of multiantenna signals from their lattice (representing a maximal order of a division algebra), you are less likely to make an error at the receiving end than what would happen, if you carve your signal set from one of the codes proposed by Oggier et al. However, that's not the end of the story. If you combine that multiantenna constellation with, for example, an LDPC code, our construction loses its theoretical advantage, because an LDPC-decoder wants to have reliability information about individual bits. When you pack several bits worth of information into a selection of a single multiantenna signal, our method creates more dependencies among those reliability figures, and that makes things worse in the end. Anyway, the math in the construction of my students is fun, and they all graduated, so...

As the number of antennas increases, the computational complexity grows really badly. Some codes suffer more from this than others. A relatively recent idea (B.S. Rajan and his students, couldn't find a proper reference, sorry) is to use representations of Clifford algebras with a view of reducing this complexity. That is a promising idea.

All of the above constructions depend on the receiver knowing the channel state. From some point on you need to allocate too large fraction of the bandwidth to pilot symbols to make that assumption true. So another thread in this area has been to use differential modulation (=use the preceding signal as a pilot for the next) or Grassmannian codes (=the signal is to an extent its own pilot). A lot of fun math going on there, but don't know whether they will stay.

Another theoretically interesting thread within this topic is: "How will the rules change, when two or more independent users transmit simultaneously?" A beginning graduate student in our group has come up with some number theoretic constructions. As a new tool he needed some facts from Diophantine approximation. The information theory in that thread is, I'm sad to say, over my head. I am willing to also bet that this question on MO derives its motivation from this problem area :-)

This question hit too close. It is not entirely clear that I managed to be objective.

The Golden Code (Oggier et al) is in a hyperWLAN standard. Don't know how widely that part of the standard is used. Multiantenna coding in cellular applications goes largely by different rules. This is because there is a feedback channel there, so the transmitter also has an idea of the channel state, and can take advantage. The math becomes easier then (so I've been told). This is not possible in a broadcast application, because there may be millions of receivers, and knowing their channel states is A) impossible, B) useless because you can't optimize the transmission for all of them simultaneously.

3) The Polar codes were a big surprise to me. I can't comment on them for lack of familiarity. Leave this for someone else to answer.

4) The Golay codes have been around. They are a rich source of algebraic and combinatorial miracles - a lot of fun! The codes are way too short to be useful in transmitting bulk data, but do make an appearance in other applications. In their book (SPLAG) Conway & Sloane study these in great detail. Probably the most investigated error-correcting codes of all times!

5) I want to add network coding as a hot topic. It has certainly received a lot of attention lately. It is not clear how deep math they end up using. Sometimes it looks like it is just Grassmannians over a finite field.

Answer by Jyrki Lahtonen for what is parameterization of the Trefoil knot surface in R³?

2012-03-17T11:59:46Z

Start with the parametrization of the torus surface: $$ x=(a+b\cos u)\cos v, $$ $$ y=(a+b\cos u)\sin v, $$ $$ z=b\sin u. $$

On that surface we get a curve that sits inside the trefoil. You get a parametrization of that curve $\vec{\gamma}=(x,y,z)$ by setting $u=3s, v=2s$ and letting $s$ range over the interval $[0,2\pi]$. This way you get a curve that wraps around the hole of the donut twice, and around the tube thrice.

Then you build a tube around that curve. You need a normalized tangent vector $$ \vec{t}(s)=\frac{\vec{\gamma}'(s)}{||\vec{\gamma}'(s)||}, $$ and a normal vector $$ \vec{n}(s)=\frac{\vec{t}'(s)}{||\vec{t}'(s)||}, $$ and a binormal vector $$ \vec{b}(s)=\vec{t}\times\vec{n}. $$

Then you can parametrize the trefoil surface $(x,y,z)=\vec{r}(s,\alpha)$ as follows $$ \vec{r}(s,\alpha)=\vec{\gamma}(s)+c\cos\alpha\vec{n}(s)+c\sin\alpha\vec{b}(s). $$ Here $c$ is the radius of the tube of the trefoil (should be smaller than $b$ = the radius of the tube of the torus). If you want elliptical cross-sections, then you use two constants in place of $c$ above (possibly phase-shifting $\alpha$). Both parameters $s$ and $\alpha$ should range over $[0,2\pi]$.

I've some Mathematica code for this somewhere, but need to dig for it. An image of the resulting trefoil (together with the torus) can be seen in the front cover of my calculus lecture notes. The trefoil is partially obscured by the torus, but that's the best version I have on-line.

Arrggh! I found my code. When producing that image I used the normal vector $$\vec{n}_T(s)=(\cos 2s\cos 3s,\sin 2s\cos 3s,\sin3s)$$ of the torus surface at the point $\vec{\gamma}(s)$ instead of the usual normal $\vec{n}(s)$. The reason may have been the simpler formula. Together with that I then also used $\vec{t}\times\vec{n}_T$ in place of the usual binormal.

I simply wanted a picture of some kind of a tube around the trefoil curve. Therefore my recipe may not be exactly what you want.

Answer by Jyrki Lahtonen for What is "automorphism group of an error-correcting code" ?

2012-03-06T10:55:08Z

The commenters got it right. The automorphism group of a binary code is the set of permutations of coordinates that stabilizes the code. If instead of using the binary alphabet we use a ternary, quaternary,... alphabet, then there is some variation in that some sources allows signed permutations of coordinates. After all, these are also automorphisms that preserve the Hamming distance (or Lee distance) between a pair of inputs. Whichever way gives you a more interesting group is the way to go!

In addition to the celebrated Golay codes (binary and ternary) some other families of codes have a useful group of automorphisms. I will list the Reed-Muller codes. These codes have length $n=2^m$, and the code $RM(r,m)$ has dimension $$ k=\sum_{i=0}^r{m\choose i}.$$ Their coordinate positions can naturally be put into a bijective correspondence with the vectors $v$ of the $m$-dimensional space $F_2^m$ over the field of two elements in such a way that all the the affine linear transformations $f_{A,u}:v\mapsto Av+u$ for all $A\in GL_m(F_2), u,v\in F_2^m$ become automorphisms of the codes. The Hamming codes belong to the hierarchy of Reed-Muller codes --- the extended Hamming code of length $2^m$ is the code $R(m-2,m)$. It is known (see MacWilliams & Sloane) that this is the full automorphism group of the code $RM(r,m)$, when $r\lt m-1$. The codes $RM(m,m)$ (resp. $RM(m-1,m)$) consists of all the binary words of length $2^m$ (resp. of all the binary words of an even weight), and both these codes are stable under all the permutations of the $2^m$ bit positions.

Also the extended BCH-codes have a useful group of automorphisms. In this case the bit positions can be put into a bijective correspondence between the elements $x$ of the finite field $F=GF(2^m)$. The codes can be defined by means of power sum equations, and it is easy to see that the affine linear mappings $x\mapsto ax+b, a\in F^*, b\in F$ are all automorphisms. Together with Frobenius automorphisms, $x\mapsto x^{2^i}$, those will form the entire group of automorphisms in many a case, but unfortunately I'm not up to speed about exactly when that happens. This is a much smaller group of automorphisms in comparison to that of the Reed-Muller codes. Yet, it is doubly transitive, and many an algebraic proof has been simplified by this fact.

Answer by Jyrki Lahtonen for Multiplication of matrices in GF(2) and R

2011-11-02T16:35:48Z

It seems to me that there may be some confusion here. As pointed out by all the commenters, the overall mapping cannot be linear. For me the most compelling reason for that would be that the only additive homomorphism from $GF(2)^k$ to $\mathbf{R}^n$ is the trivial map sending everything to all zeros. Anyway, here is my attempt to make sense out of the question. This is just educated guessing based on the scant given data.

It seems to me that the channel state matrix $H$ is upper triangular. This may have the following natural interpretation. The output of $Gm$ is a transmitted signal (usually mapped from $GF(2)$ to reals as follows: $0\mapsto +1$, $1\mapsto -1$, but other conversion mappings from binary to real are possible). This is transmitted sequentially: the first component in the first time slice, then the next,... The shape of the example matrix $H$ (as well as mentioning the term "channel convolution") suggests that what may be happening is that at instant of time $n$, the receiver sees a linear combination $r(n)=\sum_{i=0}^d w(i) t(n-i)$, where $t(n)$ is the signal transmitted at time $n$ and $w(i)$ is a weight assigned to a signal "delayed" by $i$ time units. I guess other interpretations are possible. Please comment!

If the above holds, then you in some sense equate 'upper triangular' with 'causal', in the sense that only the things transmitted in the past can affect what is being received now. If this (or another equivalent interpretation) is what you wanted to ask, then I can finally give an answer: "Yes". Your encoding matrix $G$ was specified to be upper triangular, meaning that the payload sequence of bits $m_1,m_2,\ldots,m_k$ is turned into an encoded sequence $c_1,c_2,\ldots,c_n$ of bits in such a way that for all $i$, the bit $c_i$ is a (binary linear) function of the bits $m_j, j\le i$, and does not depend on the "future" bits $m_j, j>i$. Several encoder have this property (e.g. convolutional), and all linear codes have an encoder like this (systematic part in the beginning).

But the relation between the $m_i$-sequence and the $r(i)$-sequence is not linear. With the $0\mapsto +1, 1\mapsto -1$ it could be expressed as something like $$ r(n)=\sum_{i=0}^n w(i)(-1)^{\sum_{j\ge0}c(i,j,n) m(n-i-j)}, $$ and the causality is kept, but I don't think this is saying very much?

I also think that you might be better off asking this at, e.g. dsp.stackechange. I don't think this is really a research level math question.

Answer by Jyrki Lahtonen for What programming languages do mathematicians use?

2011-09-12T12:55:41Z

They taught me Pascal in the early 80s, and since I don't want to invest much time to learning the quirks of other languages, it has become a kinda native language for me. Alas, I was forced to migrate from the Borland dialect to FreePascal and/or Delphi with the discontinuation of DOS :-)

My CAS of choice has been Mathematica. Not out of love, but for reasons of availability. It actually is not too bad, once you get used to its idiosyncracies. Earlier I did stuff with Maple for similar reasons.

When I worked in the industry side for a while I had to use ANSI C and Matlab. I will never voluntarily use either again. Too difficult to remember the syntax for file/screen I/O functions or the pointer logic in C, and Matlab is A) outrageously priced, B) for numerical stuff only (but has that excellent support for telecommunications applications, which fitted my former employer nicely).

Answer by Jyrki Lahtonen for Minimum Growth Rate of Hamming Weight of Multiples of Primitive Polynomials

2011-09-11T15:20:16Z

Scratch the use of the parity check matrix. Combine Felipe's idea with a counting argument similar to the scratched solution.

Assume $n\ge4.$ Let $\alpha$ be a root of $f(x)$. The set $P=\{ \alpha^i\mid n+2\lt i\lt N \}$ contains $N-n-3\ge 8$ distinct elements of the field $GF(2^n)$. Therefore it must intersect non-trivially with the set $S=\{ 1+\alpha^i\mid 0\lt i\lt 2^n-1\}=GF(2^n)\setminus\{0,1\} $. So $\alpha^j=1+\alpha^i$ for some $i,j, j\ge n+2$ The trinomial $p(x)=1+x^i+x^j$ is thus divisible by $f(x)$, and the degree of the quotient $a(x)=p(x)/f(x)$ is in the prescribed range. Therefore $W_{min}(f)=3$ for all primitive polynomials $f$. The case $n=3$ can be checked easily, and the same conclusion holds.

Answer by Jyrki Lahtonen for Optimization problem related to parity check code

2011-08-17T05:05:15Z

This is basically a retranslation of the problem into algebraic language. We are given an $n\times(n+k)$ matrix $A$ with entries in $GF(2)$ of the form $A=(I_n\mid B)$, where the matrix $B$ has no zero rows or columns (in practice it can probably be carefully designed, but the question is about finding a working general approach).

The problem at hand is to partition the columns of $A$ into at most $m$ subsets of size at most $b$ with the following property (so obviously $mb\ge n+k$): the removal of any single one of the subsets of columns in the partition leaves us a matrix $A'$ that is of full rank $n$.

The OP seems to be willing to relax the design goal somewhat and offers as an alternative goal to minimize the number of 'critical' partitions whose removal violates the rank criterion. This may be necessary for some combinations of parameters (and a bad value of $B$), so it is understandable, given that he seems to be looking for a general method. OTOH from the point of view of the probable application (if $m$ is 'large') one might also want to optimize the chanches that the removal of any two (or more) partitions of columns still leaves a full rank matrix, but that is a generalization of the original question.

My guess is that an accurate general algorithm may have prohibitively high complexity and offer a natural greedy algorithm of keeping assigning columns to partitions unless the rank condition is violated and hoping for the best (increasing $m$ on the fly if need be). Add reruns and a non-deterministic starting order to the mix.

Answer by Jyrki Lahtonen for MacWilliams Identity for Asymptotic Weight Spectrum of a Code

2011-07-22T06:31:57Z

Only worth a comment, but I'm low-rep, so...

I agree with Math Into Coding in the sense that this question is unlikely to have a useful answer. The observation I want to make is that the weight distribution of a long large binary code really does follow the binomial distribution with $p=0.5$ `closely'. Yes, there are examples of codes with only a handful of weights, but they have a very low rate (asymptotically zero). Therefore the expected weight of a codeword is $n/2$ and the standard deviation is $\approx\sqrt n$. This latter fact means that if we study the cdf of words of weight $\le \delta n$, where $\delta\in[0,1]$, then in a sense that could be made more precise, the cdf jumps from $0$ to $1$ near $\delta=1/2$.

So even if you redefine the average weight distribution using windows of the type $[\delta_1n,\delta_2n]$, where $\delta_2\to\delta_1$, you would still just get a spike at $\delta=1/2$ and nothing else. A scale that is a linear function of the code length just won't capture much information about the code.

Answer by Jyrki Lahtonen for Lee codes and $n$-torus

2011-07-20T19:41:02Z

The best hit I found using IEEEXplore is the following paper by Martinez, Beivide & Gabidulin from August 2009 issue of IEEE Transactions on Inf. Theory.

============================================================

Perfect Codes From Cayley Graphs Over Lipschitz Integers

Abstract

The search for perfect error-correcting codes has received intense interest since the seminal work by Hamming. Decades ago, Golomb and Welch studied perfect codes for the Lee metric in multidimensional torus constellations. In this work, we focus our attention on a new class of four-dimensional signal spaces which include tori as subcases. Our constellations are modeled by means of Cayley graphs defined over quotient rings of Lipschitz integers. Previously unexplored perfect codes of length one will be provided in a constructive way by solving a typical problem of vertices domination in graph theory. The codewords of such perfect codes are constituted by the elements of a principal (left) ideal of the considered quotient ring. The generalization of these techniques for higher dimensional spaces is also considered in this work by modeling their signal sets through Cayley-Dickson algebras.

===========================================================

I don't know if this helps you. Lately Lee-metric has not been a very hot topic in the coding theory community. Lee metric codes experienced a brief revival in the 90s, when it was observed that several good non-linear binary codes can be viewed as isometric images of submodules of $\mathbf{Z}_4^n$ under the isometry $\mathbf{Z}_4^n\rightarrow\mathbf{Z}_2^{2n}$. Here we use the Grey map: $0\mapsto 00, 1\mapsto 01, 2\mapsto 11, 3\mapsto 10$ from $\mathbf{Z}_4$ to $\mathbf{Z}_2^2$. The metric on the mod 4 side is the Lee-metric, and on the binary side we use the Hamming metric.

From your point of view this means that you can add $q=4$ to the list of potentially very useful values. Just last year I heard about a couple of new record breaking constructions of binary codes based on this same isometry.

Answer by Jyrki Lahtonen for Reducible trinomials $x^{odd}+x^2+s(t)$ in characteristic $2$

2011-06-04T19:03:41Z

Sorry, this is only worth a comment, but I'm a new guy here, so not enough rep to do that :-)

As you discuss trinomials, the silly counterexample of $(x^3+x^2+x)(x^2+x)=x^5+x^2$ is probably not interesting. Anyway, for which values of $m$ have you verified this? Here's how it goes in the case $m=2$ (you undoubtedly know this, but let's get the ball rolling).

So assume $m=2$. In order to make the quartic and cubic terms vanish from the product, we must set $K(x)=x^2+a_2(t) x+ [a_1(t)+a_2(t)^2]$, so we can compute the product (I leave out the $t$:s for now): $$ D(x)K(x)=x^5+x^2(a_0+a_2^3)+x(a_0a_2+a_1a_2^2+a_1^2)+(a_0a_1+a_0a_2^2)=T(x). $$ A comparison of quadratic terms gives us the relation $a_0=1+a_2^3$. This gives your second claimed relation unless $a_2(t)=1$ (, which leads to the silly case above). Then a comparison of the linear terms gives the relation $$ 0=a_2+a_2^4+a_1a_2^2+a_1^2. $$ If here $\deg a_1>2\deg a_2$, then the last term has a higher degree than the others, which is no-no (non-archimedean triangle inequality w.r.t to the infinite place). OTOH if $\deg a_1<2\deg a_2$, then the term $a_2^4$ dominates the others, and we again have a contradiction.

This is admittedly a very elementary approach, but do you know how far you can go with methods like this? We can always determine the coefficients of the other factor by using the known coefficients (down to the cubic term) of the product, and then get conditions by comparing the quadratic and linear terms. I am uncertain as to how many values of $m$ I want to check by hand :-)

Comment by Jyrki Lahtonen

2013-04-09T10:33:22Z

If the problem with MDS-codes is that there maximum length is $q+1$ ($q=|F|$), and you need to be able to make them longer, then an option is algebraic-geometry codes (aka Goppa codes). If you use a maximal curve of genus $g$, then the resulting codes are "within (the constant) $g$ of being MDS". The maximal attainable length (when $q$ is a square) is $q+1+2g\sqrt{q}$. Several families of such curves are known. But here typically $q$ is a bit larger, $q=16, 64, 256,\ldots$

Comment by Jyrki Lahtonen

2013-04-07T20:46:10Z

MDS codes would be nice, but there aren't any non-trivial binary ones. Furthermore, then $n(m)$ could never exceed the size of the field (+1).

Comment by Jyrki Lahtonen

2013-04-07T20:44:27Z

Something very similar is happening with so called fountain codes. IIRC they have results of the type: in a carefully designed matrix any $k(m)=(1+\varepsilon)*m$ rows will work with a high probability. Some constructions are known. Not exactly what you want, but may be worth checking out (in coding theory the roles of the rows and columns would be opposite to yours, but I'm sure you'll manage :-)

Comment by Jyrki Lahtonen

2013-01-21T08:31:27Z

I am not sure, but it seems to be that you have not included the key condition (for decoding of a tail-biting convolutional code) that the state of the encoder should return to the same after a full period. I'm not an expert on this, but I think that the term pseudo codeword seeks to describe exactly the phenomenon that you have observed. The state space can be described as a quotient of the (binary) signal space by a direct sum of two subspaces. The legal codewords are those that return to the same coset after a single period.

Comment by Jyrki Lahtonen

2012-08-15T13:50:37Z

If the $x,y,z$ are selected from the same set of 65 alternatives, then it seems clear to me that you want to use the 65 points on the 3D-diagonal, i.e. select the points of the form $(x,x,x)$. There are 65 of them, and the minimum Hamming distance between two points within this set is three. As any pair of points has Hamming distance at most three, this cannot be beaten. Or did you want to ask something else?

Comment by Jyrki Lahtonen

2012-08-06T10:06:36Z

Alexander: I forgot to say that "concatenation" of codes (instead of "superposition") is the standard term. So you may have better luck searching for more information using "concatenated codes" as a buzzword. The combinations that I have seen are convolutional+algebraic (such as here) or LDPC+algebraic. An algebraic code is a common choice as the last code, because they can effectively deal with a small number of errors, but are bad at dealing with soft errors. The code exposed to the horrors of radio propagation should always be able to deal with soft errors.

Comment by Jyrki Lahtonen

2012-07-31T16:51:59Z

I didn't see it right away either. I have a vague recollection of having once brute forced it (when searching for suitable exercise problems for my students), but had to split it into so many cases that it wouldn't work well in a homework session setting.

Comment by Jyrki Lahtonen

2012-07-31T10:41:18Z

I don't think any "clean" methods of construction (like the BCH/RS-codes from the theory of linear block codes) are known for convolutional codes. At least Johannesson & Zigangirov only describe a somewhat optimized brute force search. You are more than welcome to find a good general construction :-)

Comment by Jyrki Lahtonen

2012-07-30T21:31:34Z

I don't know. ${}$

Comment by Jyrki Lahtonen

2012-07-30T16:13:41Z

It's the ceiling. I think that the trivial bound $d\le 2(n+1)$ corresponds to $m=0$ (in other words: $p=1$) in my formula.

Comment by Jyrki Lahtonen

2012-07-30T15:08:10Z

When I first posted this comment, I accidentally reversed the inequality sign, sorry! I think that this bound shows that the slope is at most 1. I don't know, if a non-zero lower bound for the slope is known. According to the tables in Johannesson & Zigangirov dfree>n when $n\le24$. Assuming $(f,g)$ were chosen optimally, of course.

Comment by Jyrki Lahtonen

2012-07-30T11:26:56Z

"If I Recall/Remember Correctly"

Comment by Jyrki Lahtonen

2012-07-27T21:35:27Z

IIRC David Forney was the first to draw these graphs in order to make the correctness of the Viterbi decoding algorithm clear to all and sundry. He also coined the term "trellis". At least that's the way the history was once told to me by another big name in coding theory.

Comment by Jyrki Lahtonen

2012-07-25T06:40:31Z

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.

Comment by Jyrki Lahtonen

2012-07-20T12:06:37Z

(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.