What are topics in error-correcting coding which are related to interesting math. ?
I am primarely interested in nowdays hot topics, but old days topics are also welcome.
Let me try to mention what I heard about.
1) Hot topic in error-correction is finding LDPC codes with very low "error-floor" for code lengths dozens thoursands bits, this might be useful for optic transmission. However it is not clear for me what kind of math playing role here ? ("Error-floor" is related with codewords with small Hamming weight. So the code might be quite good – means majority of codewords have big Hamming weight,
so in most case code performs well, but very small number having small Hamming weight will cause small number of errors – it can be seen on the BER/SNR plot as a "floor".)
2) There is certain number of papers applying number theory (lattices in algebraic number fields) to consruct good codes.
One may see papers by F. Oggier, G. Rekaya-Ben Othman, J.-C. Belfiore, E. Viterbo:
e.g. this one : http://arxiv.org/abs/cs/0604093.
I am not aware how "hot" is this topic and how far it is from practical applications…
3) Polar codes is a hot topic. What kind of math is playing role here ?
4) Probably most classical example is the Golay code (1948) and sporadic simple Mathieu groups.
Let me quote Wikipedia: http://en.wikipedia.org/wiki/Binary_Golay_code :
"The automorphism group of the binary Golay code is the Mathieu group . The automorphism group of the extended binary Golay code is the Mathieu group . The other Mathieu groups occur as stabilizers of one or several elements of W." By the way – is it occasional coincidence of there is something behind it ?
Best Answer
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.