Lexicographic code: Difference between revisions

Revision as of 14:02, 27 March 2018

Revision as of 00:29, 15 March 2020

Line 1:

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

[[Vladimir Levenshtein]]<ref>{{citation

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]]s.

| last = Levenšteĭn | first = V. I. | authorlink = Vladimir Levenshtein

| issue = 5

| journal = [[Proceedings of the USSR Academy of Sciences|Doklady Akademii Nauk SSSR]]

| language = Russian

| mr = 0122629

| pages = 1011–1014

| title = Об одном классе систематических кодов

| trans-title = A class of systematic codes

| url = http://mi.mathnet.ru/dan39976

| volume = 131

| year = 1960}}; English translation in ''Soviet Math. Doklady'' 1 (1960), 368–371</ref> and by [[John Horton Conway]] and [[Neil Sloane]].<ref>{{citation

| last1 = Conway | first1 = John H. | author1-link = John Horton Conway

| last2 = Sloane | first2 = N. J. A. | author2-link = Neil Sloane

| doi = 10.1109/TIT.1986.1057187

| issue = 3

| journal = [[IEEE Transactions on Information Theory]]

| mr = 838197

| pages = 337–348

| title = Lexicographic codes: error-correcting codes from game theory

| volume = 32

| year = 1986}}</ref> They are [[linear code]]s over some [[finite field]]s.

== Construction ==

Line 35 ⟶ 56:

|}

Since lexicodes are linear, they can also be constructed by means of their [[Basis (linear algebra) | basis]]. <ref>[[Ari Trachtenberg]], Designing Lexicographic Codes with a Given Trellis Complexity, IEEE Transactions on Information Theory, January 2002.</ref>{{citation

| last = Trachtenberg | first = Ari

| doi = 10.1109/18.971740

| issue = 1

| journal = [[IEEE Transactions on Information Theory]]

| mr = 1866958

| pages = 89–100

| title = Designing lexicographic codes with a given trellis complexity

| volume = 48

| year = 2002}}</ref>

== Notes ==