Лексикографічний код (англ. lexicographic code) або лексикод жадібно створений код з виправлянням помилок з надзвичайно гарними властивостями. Був розроблений незалежно Левенштейном[1] та Конвеєм зі Слоуном.[2] Відомий як лінійний код над деякими скінченними полями.
Побудова
Лексикод мінімальної відстані d і довжини n над скінченним полем утворюється починаючи з нульового вектора та ітеративно додається кожен наступний вектор (у лексикографічному порядку) мінімальної відстані Геммінга d від векторів доданих до сих пір. В якості прикладу, лексикод довжина 3 та мінімальної відстані 2 буде складатися з векторів помічених знаком «X» у наступному прикладі:
Вектор
|
У коді?
|
000
|
X
|
001
|
|
010
|
|
011
|
X
|
100
|
|
101
|
X
|
110
|
X
|
111
|
|
Так як, у прикладі, лексикоди є лінійними, то їх можна побудувати за базисом.[3]
Примітки
- ↑ В. И. Левенштейн, Об одном классе систематических кодов, Докл. АН СССР, 131, 5, 1960, 1011—1014.
- ↑ 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.
- ↑ Ari Trachtenberg, Designing Lexicographic Codes with a Given Trellis Complexity, IEEE Transactions on Information Theory, January 2002.
Посилання