Implementing The Lexicographic Construction (Lexicodes)

This web page is about binary lexicodes.

Lexicodes are error correcting codes that are generated by running a greedy algorithm over lexicographically ordered vector space.

In binary case, the binary lexicodes are linear.

Lexicographic construction is simply a faster greedy algorithm that exploits the linearity and outputs binary lexicodes.

Follow this link if you want the C/C++ source code of the lexicographic construction. You can download this already compiled executable for Windows.

Did you know that you can generate the first four lexicographic basis vectors even by hand?

If you want to know how, and you want to learn more about the lexicographic construction you can download and read this paper.

Shorter version will be available soon....

In this project we tried to solve the problem of efficiently generating lexicodes. We are concerned with finding the optimal algorithm to generate lexicodes in terms of time and space. Originally the problem was posted here.

The goal of the second part of this research was to extend the tables of known lexicodes, posted on http://www.burtleburtle.net/bob/math/errorcor.html

The algorithm that we used to extend these tables is a combination of the lexicographic construction and the traditional greedy construction. You can download it if you want to try it.

Here are the extensions of the A matrices that we were able to get with this algorithm:

1. [8778,8745,5]

2. [532,498,7]

3. [171,136,9]

4. [101,65,11]

5. [74, 37,13]

6. [67,29,15]

7. [58,18,17]

8. [50,8,23]

Follow these links to obtains the parameters of lexicodes up to [n,k,d].

The generator matrix G is obtained by attaching identity matrix to the A matrix: G=[I A]

Lexicode [51,20,13] is an improvement of the Brouwer's table for n=51, k=20

None of these results could have been obtained without the help from Twister, Scrabble, Marbles, Crayon, Litebrite, Hotwheels, Kite, Pogo, Frisbee, and Domino. They are part of the IBM's pSeries 690 and 655 and they live and work at the Boston University's Scientific Computing and Visualization facilities. In particular they borrowed to us 8 GB of RAM memory and if you want to improve our lists of known lexicodes we recommend that you obtain access to a pSeries-like member.

If you have any questions you can email me at dejan@bu.edu