30. Избыточное кодирование

Избыточное кодирование – вид кодирования, использующий избыточное количество информации с целью контроля целостности данных при записи/воспроизведении информации или при ее передаче по линиям связи.

Для обнаружения и исправления ошибок используют две стратегии: корректирующее кодирование и код с обнаружением ошибок.

Рассмотрим, что из себя представляет ошибка. Кадр состоит из m битов данных и r избыточных контрольных битов. Полная длина кадра равна n=m+r. Набор из n бит, содержащий информационные и контрольные биты, часто называют «битовым кодовым словом».

Если рассмотреть два кодовых слова, то количество битов, которыми различаются два кодовых слова, называется кодовым расстоянием. Смысл этого числа в том, что если два кодовых слова находятся на кодовом расстоянии d, то для преобразования одного кодового слова в другое понадобиться d ошибок в одиночных битах.

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

Попробуем создать код, состоящий из т информационных и r контрольных битов, способный исправлять одиночные ошибки. Каждому из допустимых сообщений будет соответствовать n недопустимых кодовых слов, отстоящих от сообщения на расстояние 1. Их можно получить инвертированием каждого из n битов n-битового кодового слова. Таким образом, каждому из допустимых сообщений должны соответствовать n + 1 кодовых комбинаций. Поскольку общее количество возможных кодовых комбинаций равно , получается, что (n+1) < . Так как n = т + r, это требование может быть преобразовано к виду (т + r + 1) < . При заданном т данная формула описывает нижний предел требуемого количества контрольных битов для возможности исправления одиночных ошибок.

Этот теоретический нижний предел может быть достигнут на практике с помощью метода Хэмминга (1950). Биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4, 8, 16 и т. д.), являются контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются т битами данных. Каждый контрольный бит обеспечивает четность Обнаружение и исправление ошибок (или нечетность) некоторой группы битов, включая себя самого. Один бит может входить в несколько различных групп битов, четность которых вычисляется. Чтобы определить, в какие группы контрольных сумм будет входить бит данных в k-й позиции, следует разложить k по степеням числа 2. Например, 11 = 8 + 2 + 1, а 29 =16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами, номера которых входят в этот ряд разложения (например, 11-й бит проверяется битами 1, 2 и 8).

Когда прибывает кодовое слово, приемник обнуляет счетчик. Затем он проверяет каждый контрольный бит k (k = 1, 2, 4, 8, ...) на четность. Если сумма оказывается нечетной, он добавляет число k к счетчику. Если после всех проверок счетчик равен нулю, значит, все проверки были пройдены успешно. В противном случае он содержит номер неверного бита. Например, если ошибку дают проверки битов 1, 2 и 8, это означает, что инвертирован бит 11, так как он является единственным битом, контролируемым битами 1, 2 и 8.

Коды Хэмминга позволяют исправлять только одиночные ошибки. Однако один не слишком хитрый трюк позволяет исправлять при помощи этого кода и наборы ошибок. Для этого последовательность k кодовых слов организуется в виде матрицы, по одному кодовому слову в ряду.

Это и есть корректирующее кодирование.

Следующий метод можно реализовать по-разному. Широко используется метод «полиномиальный код». В основе полиномиальных кодов лежит представление битовых строк в виде многочленов с коэффициентами, равными только 0 или 1. Кадр из к бит рассматривается как список коэффициентов многочлена степени к –1.

При использовании такого кода отправитель и получатель должны сначала договориться насчет образующего многочлена, G(x). Старший и младший биты образующего многочлена должны быть равны 1. Для вычисления контрольной суммы для некоторого кадра из т бит, соответствующего полиному М(х), необходимо, чтобы этот кадр был длиннее образующего многочлена. Идея состоит в добавлении контрольной суммы в конец кадра таким образом, чтобы получившийся многочлен делился на образующийся многочлен G(x) без остатка. Получатель, приняв кадр, содержащий контрольную сумму, пытается разделить его на G(x). Ненулевой остаток от деления означает ошибку.

Алгоритм вычисления контрольной суммы при этом может быть следующим:

1. Пусть r — степень многочлена G(x). Добавим r нулевых битов в конец кадра так, чтобы он содержал т + r бит и соответствовал многочлену .

2. Разделим по модулю 2 битовую строку, соответствующую многочлену , на битовую строку, соответствующую образующему многочлену G{x).

3. Вычтем по модулю 2 остаток от деления (он должен быть не более r бит) из битовой строки, соответствующей многочлену . Результат и будет передаваемым кадром, который мы будем называть многочленом Т(х).