Коды коррекции ошибок: надёжная связь по зашумлённым каналам

simulation intermediate ~12 min
Загрузка симуляции...

Формула

\text{Hamming}(7,4): \text{syndrome} = H \cdot r^T
R = \frac{k}{n} = \frac{4}{7} \approx 0.571
P_{\text{block error}} = 1 - (1-p)^n - n \cdot p \cdot (1-p)^{n-1}
d_{\min} = 3 \implies \text{corrects } \lfloor(3-1)/2\rfloor = 1 \text{ error}
Каждая система цифровой связи сталкивается с одной и той же фундаментальной проблемой: шум искажает данные. Биты инвертируются, сигналы затухают, помехи вторгаются. Коды коррекции ошибок решают эту проблему, добавляя структурированную избыточность, которая позволяет приёмнику обнаруживать и исправлять ошибки без запроса повторной передачи. Простейший подход — повторение: отправить каждый бит трижды и взять голосование большинства. Это исправляет одиночные ошибки в каждой тройке, но расходует две трети пропускной способности канала. Ричард Хэмминг, раздражённый ненадёжными считывателями перфокарт в Bell Labs, изобрёл куда более элегантное решение в 1950 году. Хэмминг(7,4) кодирует 4 бита данных в 7 битов кода, добавляя 3 бита чётности в тщательно выбранных позициях. Каждый бит чётности покрывает определённое перекрывающееся подмножество битов данных. Когда при передаче происходит одиночная ошибка, приёмник вычисляет синдром — результат проверки всех трёх уравнений чётности. Синдром — 3-битное число, прямо указывающее позицию ошибки (0 означает отсутствие ошибки). Приёмник просто инвертирует этот бит для восстановления исходных данных. Этот симулятор позволяет передать сотни блоков данных через зашумлённый канал и сравнить три стратегии: без кодирования (сырая передача), код повторения и код Хэмминга. Наблюдайте, как ошибки (показаны красным) искажают переданные биты, биты чётности (показаны голубым) обеспечивают обнаружение, а декодер исправляет повреждения. Более глубокий урок — теорема Шеннона о канальном кодировании: для любого зашумлённого канала существует схема кодирования, обеспечивающая надёжную связь на любой скорости ниже пропускной способности канала. Коды Хэмминга — ранний практический шаг к этому теоретическому обещанию. Современные коды вроде LDPC и турбокодов подходят к пределу Шеннона поразительно близко.

Частые вопросы

Что такое код Хэмминга?

Код Хэмминга — линейный код коррекции ошибок, изобретённый Ричардом Хэммингом в 1950 году. Наиболее распространённый вариант, Хэмминг(7,4), кодирует 4 бита данных в 7 битов кода, добавляя 3 бита чётности в позициях 1, 2 и 4. Каждый бит чётности покрывает определённое подмножество битов данных. Синдром — вычисленный путём проверки всех уравнений чётности — определяет позицию одиночной ошибки, позволяя исправить её без повторной передачи.

Как коррекция ошибок связана с теоремой Шеннона о канальном кодировании?

Теорема Шеннона о канальном кодировании (1948) доказывает, что для любого канала с пропускной способностью C надёжная связь возможна на любой скорости ниже C при использовании достаточно длинных кодов. Коды Хэмминга — короткие, простые коды, исправляющие одиночные ошибки. Современные коды вроде турбокодов и LDPC приближаются к пределу Шеннона гораздо точнее за счёт большей длины блока и итеративного декодирования.

Чем обнаружение ошибок отличается от коррекции ошибок?

Обнаружение ошибок определяет, что ошибка произошла, но не указывает где. Простой бит чётности обнаруживает любую одиночную ошибку. Коррекция ошибок и обнаруживает, и локализует ошибку, позволяя приёмнику её исправить. Хэмминг(7,4) может исправить любую одиночную ошибку и обнаружить (но не исправить) любую двойную ошибку. Коррекция требует большей избыточности, чем обнаружение.

Где на практике применяются коды коррекции ошибок?

Коды коррекции ошибок повсеместны: ECC-память использует коды Хэмминга для исправления битовых сбоев; QR-коды используют коды Рида–Соломона для устойчивости к повреждениям; жёсткие диски, SSD и оптические диски используют LDPC и коды Рида–Соломона; сети 5G используют полярные коды и LDPC; связь с дальним космосом использует свёрточные и турбокоды для поддержания контакта на расстоянии миллиардов километров.

Источники

Другие симуляции: Теория информации

simulation

Исследователь пропускной способности канала
simulation

Симулятор сжатия данных
simulation

Калькулятор энтропии Шеннона
View source on GitHub