Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Vladimir Levenshtein and by John Horton Conway and Neil Sloane. The binary lexicographic codes are linear codes, and include the Hamming codes and the binary Golay codes.

Construction

A lexicode of length n and minimum distance d over a finite field is generated by starting with the all-zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance d from the vectors added so far. As an example, the length-3 lexicode of minimum distance 2 would consist of the vectors marked by an "X" in the following example:

Lexicographic code

{ | class="wikitable" |- ! Vector ! In code? |- | 000 | X |- | 001 | |- | 010 | |- | 011 | X |- | 100 | |- | 101 | X |- | 110 | X |- | 111 | |}

Lexicographic code

Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2m codewords dictionnary. For example, F4 code (n=4,d=2,m=3), extended Hamming code (n=8,d=4,m=4) and especially Golay code (n=24,d=8,m=12) shows exceptional compactness compared to neighbors. { | class="wikitable"

Lexicographic code

|-

! n \ d

! 1

! 2

! 3

! 4

! 5

! 6

! 7

! 8

! 9

! 10

! 11

! 12

! 13

! 14

! 15

! 16

! 17

! 18

|-

! 1

| 1

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|-

! 2

| 2

| 1

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|-

! 3

| 3

| 2

| 1

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|-

! 4

| 4

|

| 1

| 1

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|-

! 5

| 5

| 4

| 2

| 1

| 1

|

|

|

|

|

|

|

|

|

|

|

|

|

|-

! 6

| 6

| 5

| 3

| 2

| 1

| 1

|

|

|

|

|

|

|

|

|

|

|

|

|-

! 7

| 7

| 6

| 4

| 3

| 1

| 1

| 1

|

|

|

|

|

|

|

|

|

|

|

|-

! 8

| 8

| 7

| 4

|

| 2

| 1

| 1

| 1

|

|

|

|

|

|

|

|

|

|

|-

! 9

| 9

| 8

| 5

| 4

| 2

| 2

| 1

| 1

| 1

|

|

|

|

|

|

|

|

|

|-

! 10

| 10

| 9

| 6

| 5

| 3

| 2

| 1

| 1

| 1

| 1

|

|

|

|

|

|

|

|

|-

! 11

| 11

| 10

| 7

| 6

| 4

| 3

| 2

| 1

| 1

| 1

| 1

|

|

|

|

|

|

|

|-

! 12

| 12

| 11

| 8

| 7

| 4

| 4

| 2

| 2

| 1

| 1

| 1

| 1

|

|

|

|

|

|

|-

! 13

| 13

| 12

| 9

| 8

| 5

| 4

| 3

| 2

| 1

| 1

| 1

| 1

| 1

|

|

|

|

|

|-

! 14

| 14

| 13

| 10

| 9

| 6

| 5

| 4

| 3

| 2

| 1

| 1

| 1

| 1

| 1

|

|

|

|

|-

! 15

| 15

| 14

| 11

| 10

| 7

| 6

| 5

| 4

| 2

| 2

| 1

| 1

| 1