MURI Research
Topic: Group Action Codes
By: Louay Bazzi (MIT), Sanjoy Mitter (MIT), Daniel Spielman (MIT)
The main problem under investigation is the explicit construction of binary linear codes that have asymptotically good distance properties and fast decoding algorithms. One goal is a polynomial time decodable explicit construction that meets the Gilbert-Varshomev (GV) bound -- the best known lower bound that known explicit binary constructions do not provably achieve. Motivated by the resulting structure, we started by looking in general at binary codes that are invariant under the action of some group working on the bits of the codewords. In this framework we found a specific group action under which almost all the invariant codes achieve the GV bound. In this ensemble of invariant codes there is a natural choice of an explicit code that seems to be the best. We can express the minimum distance of this code in terms of the maximum number of rational points on curves from a special family of curves over finite fields, where each curve corresponds to a codeword. We are currently trying to use the special features of the curves in this family to get a good bound on the number of rational points. The other direction being explored is the implication of the representation theory of the acting group on the code minimum distance and decodability. Lately we started investigating a related problem using similar tools, namely the problem of constructing pseudo-random number generator for derandomization purposes. Before going in the direction of group action codes we were looking at how the distance properties and the deocodability of codes are related to the complexity of the code encoder and tester. One of the concrete results we obtained from the investigation is about Turbo codes. Turbo codes are are known to be asymptotically bad when the underlying permutation is selected at random, a fact that did not exclude the possibility of the existence of a good Turbo code that can be constructed in some way. We argued that this is not possible in the sense that all Turbo codes are asymptotically bad. This includes also various generalizations of Turbo codes such as repeat-accumulate codes and nonlinear Turbo codes. The result was presented at the Asymptotic and Computational Aspects of Coding Theory Workshop 2001, Institute of Advanced Study, Princeton.

Questions and comments to the webmaster. This page is copyrighted by the Massachusetts Institute of Technology.