Помехоустойчивое кодирование

Первые попытки создания кодов с избыточной информацией начались задолго до появления современных компьютеров. К примеру, ещё в 1960-х годах Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось.

Точку в этом вопросе поставила фундаментальная работа Берлекэмпа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих приём RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).

Но далеко не всегда от кода требуется коррекция ошибок. Многие современные каналы связи обладают приемлемыми характеристиками, и зачастую достаточно лишь проверить, успешно ли прошла передача или возникли какие-нибудь сложности; структура же ошибок и конкретные позиции неверных символов совершенно не интересуют принимающую сторону. И в этих условиях очень удачным решением оказались алгоритмы, использующие контрольные суммы. CRC как нельзя лучше подходит для подобных задач: невысокие затраты ресурсов, простота реализации и уже сформированный математический аппарат из теории линейных циклических кодов обеспечили ей огромную популярность.

Хотя код CRC используют обычно только для обнаружения ошибок, его математические свойства дают возможность найти и исправить одиночную ошибку в блоке бит, если каждому биту защищаемого блока (включая проверочные биты) соответствует свой уникальный остаток от деления на порождающий многочлен. Например, если порождающий многочлен неприводим, и длина блока не превышает порядок порождённой циклической группы.


7247
Серверов всего
5873
Серверов онлайн
89743
Игроков онлайн
Добавить сервер