Лексикографічний код
Перейти до навігації
Перейти до пошуку
Лексикографічний код (англ. lexicographic code) або лексикод жадібно створений код виправлення помилки[en] з надзвичайно гарними властивостями. Був розроблений незалежно Левенштейном[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 [Архівовано 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