Hot-topics in error correcting coding related to interesting math. ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T07:09:26Z http://mathoverflow.net/feeds/question/92192 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92192/hot-topics-in-error-correcting-coding-related-to-interesting-math Hot-topics in error correcting coding related to interesting math. ? Alexander Chervov 2012-03-25T19:21:31Z 2013-01-04T11:48:52Z <p>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. </p> <p>Let me try to mention what I heard about.</p> <p>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".)</p> <p>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 : <a href="http://arxiv.org/abs/cs/0604093" rel="nofollow">http://arxiv.org/abs/cs/0604093</a>. I am not aware how "hot" is this topic and how far it is from practical applications...</p> <p>3) Polar codes is a hot topic. What kind of math is playing role here ?</p> <p>4) Probably most classical example is the Golay code (1948) and sporadic simple Mathieu groups. Let me quote Wikipedia: <a href="http://en.wikipedia.org/wiki/Binary_Golay_code" rel="nofollow">http://en.wikipedia.org/wiki/Binary_Golay_code</a> : "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 ?</p> http://mathoverflow.net/questions/92192/hot-topics-in-error-correcting-coding-related-to-interesting-math/92300#92300 Answer by Jyrki Lahtonen for Hot-topics in error correcting coding related to interesting math. ? Jyrki Lahtonen 2012-03-26T19:33:30Z 2012-03-26T19:39:24Z <p>Your list certainly has many nice topics.</p> <hr> <p>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. </p> <p>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 :-)</p> <p>So a breakthru in this area would probably have to also keep this in mind in order to end up in future applications.</p> <p>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.</p> <hr> <p>2) This was a relatively hot topic a few years. I am a bit hesitant to call it coding theory - calling it <em>multiantenna signal constellation design</em> might be more fitting, but whatever :-). </p> <p>By using basic facts of global class field theory my graduate students managed to <a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=5165177&amp;isnumber=5165162" rel="nofollow">"improve" upon the Golden code</a> (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...</p> <p>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. </p> <p>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.</p> <p>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 <a href="http://mathoverflow.net/questions/76839/any-references-on-zeta-function-like-sums-of-inverse-determinants-over-lattices-o" rel="nofollow">this question on MO</a> derives its motivation from this problem area :-)</p> <p>This question hit too close. It is not entirely clear that I managed to be objective.</p> <p>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.</p> <hr> <p>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.</p> <hr> <p>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 &amp; Sloane study these in great detail. Probably the most investigated error-correcting codes of all times!</p> <hr> <p>5) I want to add <a href="http://en.wikipedia.org/wiki/Network_coding" rel="nofollow">network coding</a> 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.</p> http://mathoverflow.net/questions/92192/hot-topics-in-error-correcting-coding-related-to-interesting-math/118041#118041 Answer by Yuichiro Fujiwara for Hot-topics in error correcting coding related to interesting math. ? Yuichiro Fujiwara 2013-01-04T11:14:57Z 2013-01-04T11:48:52Z <p>Edit: since I only implicitly answered your question in the title (i.e., hot topics in error coding codes related to interesting math), I think one of the current hottest ones is quantum error-correcting codes. Since the discovery by P. Shor of the fact that we can correct quantum errors, the field of quantum information science exploded and made a quantum leap towards realization of large-scale quantum computation and reliable quantum communication. The list of the branches of mathematics used in the field is endless and growing as we speak. [\end Edit]</p> <p>Jyrki already gave a great answer to many of your questions. So, here's to complement it by addressing a couple points he (she?) didn't cover:</p> <blockquote> <p>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 ?</p> </blockquote> <p>That depends on the channel (and decoding method) you have in mind. In what follows, we only consider a binary code (because I don't know much about the non-binary case!).</p> <p>The simplest case is BEC (the binary erasure channel), where <em>stopping sets</em> determine the characteristic of the BER of an LDPC code. Small stopping sets are like small weight codewords in a traditional code; the more your code has small stopping sets, the worse its error correction performance gets in general.</p> <p>Stopping sets can be described in a completely combinatorial way. A stopping set of a parity-check matrix $H$ is a set of columns in which every row has at least two $1$'s (within the columns). You can rephrase the definition in the language of set systems by regarding $H$ as an incidence matrix; it's equivalent to a <em>full</em> configuration. Or you can reword it by using terms like check nodes and variable nodes as is standard in the LDPC code literature.</p> <p>Anyway, the smallest stopping sets dominate at sufficiently high SNR. So improving BER directly corresponds to an avoidance problem (or equivalently a forbidden configuration problem) in a binary matrix. So, it's a combinatorial problem that studies a set system avoiding full configurations that gives the desired code length, rate, other additional properties you want such as a particular automorphism. So it's pretty much the same as good ol' algebraic coding theory; avoiding low weight codewords (or equivalently achieving larger minimum distances) is now replaced by avoiding small stopping sets. In fact, the size of a smallest stopping set is called the <em>stopping distance</em> of $H$.</p> <p>One thing to note is that the notion of stopping distance is defined for a parity-check matrix. Since one same linear code has various different parity-check matrices, you don't say the stopping distance of a code. Other than this, stopping distance is more or less the analogue of minimum distance when it comes to an LDPC code over BEC.</p> <p>Things are much more complicated for other well-studied channels like everyone's favorite, the AWGN channel, and the coding theory 101 channel, the binary symmetric channel. Some say that in general better stopping distances tend to lead to better BER or at least it's not a bad sign. But this isn't always the case. The kind of sub-structure in $H$ that screws up your decoding algorithm at high SNR for channels other than BEC is typically not easy to describe by simple combinatorics. If you're curious, searching IEEE Xplore with keywords like "trapping sets" and "pseudo-codewords" should direct you to the right papers.</p> <p>You can also correct quantum errors by taking advantage of the theory of LDPC codes. But I haven't seen a paper that directly studies the analogue of stopping sets, trapping sets, etc. for quantum channels. The main difficulty in the quantum domain is that not every $H$ defines a quantum LDPC code; the rows should correspond to the generators of a stabilizer that is an abelian subgroup of the Pauli group or otherwise you need either a certain number of qubits in the Bell states shared between sender and receiver or assume a very reliable auxiliary quantum channel to "force" your $H$ to define a stabilizer of a larger group. So, you have more things to consider before you can translate the error floor problem of LDPC coding for quantum channels into the language of mathematics. Or you can say the kind of math playing a role for this particular subfield is the ones you need for quantum information on top of the usual math for LDPC codes such as combinatorics, information theory, and probability.</p> <p>Since you mentioned polar codes in your third question, <em>spatially-coupled</em> LDPC codes are among the hottest classes of LDPC codes that are competing with polar codes. The noise threshold of spatially-coupled ensamble under iterative decoding matches the MAP decoding's threshold over BEC. The quantum analogues of spatially-coupled LDPC codes and polar codes have been/are being studied, too, albeit with a limited success compared to the remarkable progress for the classical case.</p> <blockquote> <p>4) Probably most classical example is the Golay code (1948) and sporadic simple Mathieu groups... [Quote from Wikipedia about how Mathieu groups are automorphism groups of the Golay codes, extended Golay codes, etc. goes here] ...Is this a coincidence, or is there something behind it?</p> </blockquote> <p>Yes. There's something behind it. For instance, the Mathieu group $M_{24}$ is by definition the automorphism group of the extended binary Golay code, or equivalently, of the Steiner $5$-design of order $24$ and block size $8$, which is called the <em>Witt design</em> in combinatorial design theory. <a href="http://www.win.tue.nl/~aeb/2WF02/Witt.pdf" rel="nofollow">Here</a> is a lecture note on this by A. E. Brouwer. This is one of those interesting interactions between finite simple groups, designs, and codes.</p> <p>I think this answer is getting too long for a forum post, so for the rest I'll just recommend you search the internet with google or your favorite searching engine by keywords like Golay codes, Steiner designs, Witt designs, simple groups, and the like. That way, I won't upset my previous and current posdoc mentors and Ph.D. supervisor at the same time by writing something stupid about what I should know better.</p>