Лексикографічний код
Лексикографічний код (англ. 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.
Посилання
- Bob Jenkins table of binary lexicodes
- On-line generator for lexicodes and their variants
- послідовність A075928 з Онлайн енциклопедії послідовностей цілих чисел, OEIS Перелік кодів слів у бінарному лексикоді з відстанню Геммінга 4 записані у вигляді десяткових чисел.
- Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.