Lexicographic code

Lexicographic code

Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently byLevenshtein [V.I. Levenstein. A class of systematic codes. Soviet Math. Dokl, 1(1):368-371, 1960.] and Conway and Sloane [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.] and are known to be linear over some finite fields.

Construction

A lexicode of minimum distance d and length n over a finite field mathbb{F} 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 2would consist of the vectors marked by an "X" in the following example:



Since lexicodes are linear, they can also be constructed by means of their basis. [A. Trachtenberg, Designing Lexicographic Codes with a Given Trellis Complexity, IEEE Transactions on Information Theory, January 2002.]

Notes

External links

[http://burtleburtle.net/bob/math/lexicode.html Bob Jenkins table of binary lexicodes]

[http://www.research.att.com/~njas/sequences/A075928 Entry in the On-Line Encyclopedia of Integer Sequences ]

[http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs ]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Binary Golay code — In mathematics and computer science, a binary Golay code is a type of error correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory …   Wikipedia

  • Error detection and correction — In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data (information) integrity across noisy channels and less than reliable storage… …   Wikipedia

  • Forward error correction — In telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding[1] is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is… …   Wikipedia

  • List of algebraic coding theory topics — This is a list of algebraic coding theory topics. ARQ[disambiguation needed  ] Adler 32 BCH code BCJR algorithm Berger code Berlekamp Massey algo …   Wikipedia

  • lexicode — noun lexicographic code …   Wiktionary

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • On-Line Encyclopedia of Integer Sequences — URL oeis.org Created by Neil Sloane Launched 1996 ( …   Wikipedia

  • Radix sort — In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is… …   Wikipedia

  • Nomenclature — For conventions governing Wikipedia article names, see Wikipedia:Naming conventions, for soviet class, see Nomenklatura. Nomenclature is a term that applies to either a list of names and/or terms, or to the system of principles, procedures and… …   Wikipedia

  • Combinatorial number system — In mathematics, and in particular in combinatorics, the combinatorial number system of degree k (for some positive integer k), also referred to as combinadics, is a correspondence between natural numbers (taken to include 0) N and k… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”