Что более идеально

thesz — 19.11.2025 https://en.wikipedia.org/wiki/Binary_Golay_code и https://en.wikipedia.org/wiki/Lexicographic_code

А вот если мы возьмём генератор вида x_t= x₀ + t * c mod q, с большими q, c и x₀, мы легко можем получить коды шириной, допустим в N=1000 битов и с возможностью исправления до d=237 ошибок со входным алфавитом 256 (8 битов). N=2000 битов для того же алфавита позволят быстро получить исправление d=480 ошибок, N=5000 битов исправляют d=1220 ошибок и N=10000 битов исправляют d=2546 ошибок. Отношение исправляемых ошибок d стремиться к 0,25N, снизу.

Для случайных кодов разница между значениями будет примерно половина битов, и при поиске мы ищем, как в случае лексикографических кодов, код, расстояние Хэмминга которого для любого ранее найденного кода не менее 2d+1. Вот и вылезает четверть.

Интересно в этом вот, что.

https://en.wikipedia.org/wiki/Concatenated_error_correction_code

Для создания составного кода из особо компактного кода Голея мы должны применить его дважды (входной символ 12 битов, выходной - 23). У нас получится составной код длиной в 46 битов, что может исправлять 3*3/4=2,25 ошибок. Это 5% ошибок! Мы можем легко получить случайный код длиной в 54 бита и входным алфавитом размером 4096 (12 битов), что исправляет 7 ошибок. Это в пять с лишним раз лучше.

И даже для 12 входных битов получить исправление 2420 ошибок в коде размером 10000 битов не составляет труда.

Получается, случайные коды могут быть довольно выгодны.

Оставить комментарий

Популярные посты: