Introduction

One of the fundamental problems in dealing with information is errors. Over the course of time, errors inevitably corrupt information during its storage, transmission, and processing. The challenge of dealing with errors is a fundamental one. It has been studied for over fifty years now, starting with the papers of Shannon [4] and Hamming [2]. We know a lot about dealing with errors now, but there is much more to learn.

To deal with the problem of errors, one encodes information using error-correcting codes. Such an encoding adds a small number of redundant bits to the data. Those bits should allow recovery from errors that may occur later to data. Ideally one would like to minimize the amount of redundancy that is added to data in the process of encoding, and at the same time maximize the error-correcting capacity of the code. Clearly, those two goals contradict each other. The fundamental problem in the theory of error-correcting codes is to come up with (optimal) codes achieving the best possible trade-offs. Our research focuses on a special case of this problem.

Progress

There are three important parameters associated with an error-correcting code. Those are length of the code, the size of the code, and the distance of the code. The length and size of the code characterize the amount of redundancy that in the code. The distance of the code characterizes the error-correcting capacity. The problem of coming up with optimal error-correcting codes translates into the following extremal question.

Let A(q,n,d) denote the maximal size of a q-ary error-correcting code of length n and distance d. We are would like to understand the asymptotic behavior of A(q,n,d). There are several reasonable settings of parameters for such a problem. One possibility is to fix the values of q and d and to ask for upper and lower bounds for A(q,n,d) as n grows to infinity. In a recent paper with Ilya Dumer [6] we improve the asymptotic lower bound for A(q,n,d) in this setup. In particular we design long algebraic codes that are asymptotically larger than the famed Bose-Chaudhuri-Hocquenghem (BCH) codes and the Gilbert-Varshamov bound for any fixed distance. Prior to our work, codes of fixed distance that asymptotically surpass the Gilbert-Varshamov bound were designed only for distances 4, 5 and 6 [1]. Our construction relies on two deep theorems from algebraic geometry and presents a new connection between algebraic geometry and coding theory.

The techniques developed in attempt to further improve the asymptotic lower bound for A(q,n,d) allowed us to make some progress on a seemingly unrelated problem of estimating the minimal genus of pointless curves a over finite field [5].

Future

Currently, our codes are mostly of theoretical interest, since even the shortest codes in our family have very big length. We plan to continue working on this problem. Our goal here is to generalize the construction of codes mentioned above to produce codes of reasonable length with parameters better than the BCH codes. Another (more challenging) goal is to improve the construction to obtain a stronger asymptotic bounds for A(q,n,d).

Research Support

This project was supported in part by NTT Award MIT 2001-2004 and NSF grant CCR 0219218.

References

[1] I. Dumer, Nonbinary double error-correcting codes designed by means of algebraic varieties. IEEE Transactions on Information Theory, vol. 41, pp. 1657-1666, November 1995.

[2] R. W. Hamming, Error detecting and error correcting codes. Bell Systems Technical Journal, vol. 29, pp. 147--160, April 1950.

[3] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam: North-Holland, 1977.

[4] C. E. Shannon, A mathematical theory of communication. Bell Systems Technical Journal, vol. 27, pp.379-423, 623-656, 1948.

[5] S. Yekhanin, A note on plane pointless curves. submitted to Finite Fields and Their Applications.

[6] S. Yekhanin and I. Dumer, Long nonbinary codes exceeding the Gilbert-Varshamov bound for any fixed distance. IEEE Transactions on Information Theory, vol. 50, pp. 2357-2362, October 2004.