Lexicographic code: Difference between revisions

Revision as of 19:54, 16 May 2007

Revision as of 19:56, 16 May 2007

Line 1:

'''Lexicographic codes''' or lexicodes are greedily generated [[error-correcting code | error-correcting codes]] with remarkably good properties. They were produced independently by

Levenshtein<ref>V.I. Levenstein. A class of systematic codes. Soviet Math. Dokl, 1(1):368-371, 1960.</ref> and Conway and Sloane <ref>J.H. Conway and N.J.A Sloane. Lexicographic codes: error-correcting codes from game theory. IEEE Transactions on Information Theory, 32:337-348, 1986.</ref> and are known to be [[linear code | linear]] over some [[finite field][finite fields]].

== Construction ==

A lexicode of minimum distance d and length <math>n</math> over a [[finite field]] <math>\mathbb{F}</math> is generated by starting with the all zero vector and iteratively adding the next vector (in [[lexicographic order]]]) of minimum Hamming distance <math>d</math> from the vectors added so far. As an example, the length <math>3</math> lexicode of minimum distance <math>2</math>

would consist of the vectors marked by an "X" in the following example: