13 Обработка ошибок. Результаты теории кодирования.

Корректирующее кодирование

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

Кодовое расстояние (расстояние Хэмминга) – количество битов, которыми различаются два кодовых слова. Кодовое расстояние – это наименьшее расстояние Хэмминга между различными парами кодовых слов.

Способности кода по обнаружению и исправлению ошибок зависят от его минимального кодового расстояния. Для обнаружения d ошибок в одном кодовом слове необходим код с минимальным кодовым расстоянием d + 1, поскольку d однобитовых ошибок не смогут изменить одну допустимую комбинацию так, чтобы получилась другая допустимая комбинация. Когда приемник встречает запрещенную кодовую комбинацию, он понимает, что при передаче произошла ошибка. Аналогично для исправления d ошибок в одном кодовом слове, требуется код с минимальным расстоянием 2d + 1, так как в данном случае даже при d однобитовых ошибках результат окажется ближе к исходному кодовому слову, чем к любому другому, и, следовательно, его можно будет однозначно восстановить.

Основные результаты.

Основные зависимости между кратностью обнаруживаемых ошибок t_о, исправляемых ошибок t_u, исправлением стираний t_c и кодовым расстоянием d₀ кода:

d₀ ≥ t₀ + 1; d₀ ≥ t₀ + t_u + 1 (при t₀ > t_u );

d₀ ≥ 2 t_u + 1; d₀ ≥ 2 t_u + t_c + 1

d₀ ≥ t_c + 1;

Стиранием называется потеря значения передаваемого символов некоторой позиции кодового слова, которая известна. Т.о. расстояние Хэмминга между верными кодовыми словами должно быть больше, чем оно может получиться в результате ошибок.

Граница Хэмминга близка к оптимальной для высокоскоростных q-ичного и двоичного кодов

n – k ≥ log_q ∑_{i = 0…tu} ( C_nⁱ ( q - 1)ⁱ );

Обработка ошибок может быть осуществлена с помощью контрольных сумм.

Контрольные суммы – значение, полученное путем сложения битов информационной последовательности:

Позволяет обнаруживать однократные ошибки (в случае нескольких – нечетное количество).

Ещё количество ошибок можно уменьшить введением бита паритета.

14 Полиномиальное кодирование (crc).

На практике активно применяются полиномиальные коды или циклические избыточные коды (Cyclic Redundancy Code — CRC).

CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. k-битовая строка соответствует полиному степени k − 1. Самый левый бит строки — коэффициент при старшей степени. Например, строка 110001 представляет полином x⁵ + x⁴ + x⁰.

Основная идея заключена в том, чтобы пересылать только такие сообщения, полиномы которых делятся на некоторый фиксированный полином G(x) (образующий многочлен). Если мы получаем сообщение, что чей –то полином не делится на G(x), значит при передаче сигнал был искажен. Мы не заметим ошибок, если они один допустимый полином (то есть полином делящийся на G(x)) преобразовали в другой допустимый полином. Полином G(x) тем лучше, чем больше среднее расстояние Хемминга на парах допустимых полиномов.

В CRC используется добавление к нашему сообщению некоторого количества бит так, чтобы результирующий полином делился на G(x).