All Topics  
Lexicographic code

 

 
   Email Print
   Bookmark   Link
 

 

Lexicographic code
 
 
  Topics Lexicographic code Topic Home

Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Levenshtein and Conway and Sloane and are known to be linear
Linear code

In mathematics and information theory, a linear code is an important type of block code used in error correction and detection schemes. Linear codes allow for more efficient encoding and decoding algorithms than other codes ....
 over some finite field
Finite field

In abstract algebra, a finite field or Galois field is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory....
s.

xicode of minimum distance d and length over a finite field
Finite field

In abstract algebra, a finite field or Galois field is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory....
  is generated by starting with the all zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance from the vectors added so far.






Discussion
Ask a question about 'Lexicographic code'
Start a new discussion about 'Lexicographic code'
Answer questions from other users
Full Discussion Forum



Encyclopedia


Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Levenshtein and Conway and Sloane and are known to be linear
Linear code

In mathematics and information theory, a linear code is an important type of block code used in error correction and detection schemes. Linear codes allow for more efficient encoding and decoding algorithms than other codes ....
 over some finite field
Finite field

In abstract algebra, a finite field or Galois field is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory....
s.

Construction

A lexicode of minimum distance d and length over a finite field
Finite field

In abstract algebra, a finite field or Galois field is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory....
  is generated by starting with the all zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance from the vectors added so far. As an example, the length lexicode of minimum distance would consist of the vectors marked by an "X" in the following example:

Vector In code?
000 X
001 
010 
011 X
100 
101 X
110 X
111 


Since lexicodes are linear, they can also be constructed by means of their basis
Basis (linear algebra)

In linear algebra, a basis is a set of vectors that, in a linear combination, can represent every vector in a given vector space or free module, and such that no element of the set can be represented as a linear combination of the others....
.

External links

  • Entry in the On-Line Encyclopedia of Integer Sequences
    On-Line Encyclopedia of Integer Sequences

    The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an extensive searchable database of integer sequences, freely available on the World Wide Web....