Лексикографічний код

Лексикографічний код (англ. lexicographic code) або лексикод жадібно створений ^[en] з надзвичайно гарними властивостями. Був розроблений незалежно Левенштейном та Конвеєм зі Слоуном. Відомий як лінійний код над деякими скінченними полями.

Побудова

Лексикод мінімальної відстані d і довжини n над скінченним полем утворюється починаючи з нульового вектора та ітеративно додається кожен наступний вектор (у лексикографічному порядку) мінімальної відстані Геммінга d від векторів доданих до сих пір. В якості прикладу, лексикод довжина 3 та мінімальної відстані 2 буде складатися з векторів помічених знаком «X» у наступному прикладі:

Вектор	У коді?
000	X
001
010
011	X
100
101	X
110	X
111

Так як, у прикладі, лексикоди є лінійними, то їх можна побудувати за базисом.

Примітки

1. В. И. Левенштейн, Об одном классе систематических кодов, Докл. АН СССР, 131, 5, 1960, 1011—1014.
2. 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.
3. Ari Trachtenberg, Designing Lexicographic Codes with a Given Trellis Complexity, IEEE Transactions on Information Theory, January 2002.

Посилання

• Bob Jenkins table of binary lexicodes [ 20 грудня 2006 у Wayback Machine.]
• On-line generator for lexicodes and their variants [ 11 лютого 2015 у Wayback Machine.]
• послідовність A075928 з Онлайн енциклопедії послідовностей цілих чисел, OEIS Перелік кодів слів у бінарному лексикоді з відстанню Геммінга 4 записані у вигляді десяткових чисел.
• Error-Correcting Codes on Graphs: Lexicodes [ 27 вересня 2016 у Wayback Machine.], Trellises and Factor Graphs