Б3. Коды, обнаруживающие и исправляющие ошибки

Расстояние Хэмминга. Пусть мы получили код, в котором каждая -выборка закодирована словом, состоящим из символов (рис. 532). Будем предполагать, что символы взяты из конечного множества, обладающего структурой поля (тогда эти

символы можно складывать и перемножать). Особенно удобно пользоваться конечными полями характеристики 2, что мы и будем делать.

Хэмминг определил расстояние между двумя кодовыми словами как число мест, в которых символы этих слов не совпадают. Если, например,

то

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

Рис. 532.

Тогда

в самом деле, при передаче символа по двоичной симметрической линии вероятность ошибки равна а у нас символов переданы правильно, а символов — неверно.

Так как всегда меньше 0,5, то увеличивается, когда уменьшается; отсюда получаем правило: при получении на выходе кодового слова следует в качестве кодового слова на входе брать слово с наименьшим расстоянием от (рис. 533).

Рис. 533.

Можно проверить, что расстояние Хэмминга удовлетворяет всем обычным аксиомам расстояния:

причем равенство имеет место тогда и только тогда, когда

Для расстояния Хэмминга справедливо соотношение

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

Если

то имеется возможность исправить все простые ошибки, двойные ошибки, ошибки на местах. Ошибки на местах можно обнаружить, но исправить, вообще говоря, нельзя.

Действительно, если расстояние между кодовыми словами не меньше при получении слова его следует интерпретировать по установленному выше правилу как слово (рис. 534), так как от любого другого слова С, оно находится на расстоянии, не меньшем Заметим, что исправить можно самое большее ошибок.

Рис. 534.

Рис. 535.

Если минимальное расстояние между двумя словами в коде равно то можно найти два слова с расстоянием от полученного слова следовательно, обнаруженную ошибку исправить нельзя (рис. 535).

Точно так же можно было бы показать, что для исправления ошибок и обнаружения ошибок при необходимо, чтобы

Верно также и обратное утверждение.

Из сказанного выше очевидна необходимость кодирования. Выяснены также условия, которым оно должно удовлетворять. Остается лишь показать, каким способов кодирование можно осуществить. Известные способы кодирования, дающие возможность обнаружения и исправления ошибок, используют:

1) подпространства векторного пространства размерности , при этом слова имеют длину это — линейные

2) отношение делимости мйогочленов; это — циклические коды.

Предшественником последних является код Бодо. Циклические коды, будучи менее доступными для теоретической трактовки, чем линейные, практически реализуются значительно легче.

Двоичные линейные коды. Пусть

— вектор, все компоненты которого равны нулю, кроме равной 1. Эти векторы в совокупности линейно независимы и образуют базис линейного пространства над полем (1 можно считать единицей поля). Их можно записать как строки матрицы порядка

Пусть вектор

где а — элементы поля, преобразуется матрицей в вектор

т. е.

тогда

Если взять другие линейно независимых векторов и записать их как строки матрицы то при

имеем» вообще говоря,

но, как и в предыдущем случае, умножением на матрицу получаются все векторы из

Точно так же можно определить матрицу строки которой представляют собой линейно независимых векторов (ранга с помощью этой матрицы можно получить все векторы из подпространства размерности пространства

Приведение матриц к каноническому виду. Рассмотрим следующие действия с матрицами:

1) перестановка строк;

2) умножение строки на произвольный ненулевой элемент поля;

3) прибавление к строке матрицы другой строки, умноженной на элемент поля.

С помощью этих действий всегда можно привести матрицу ранга к следующему каноническому виду:

При этом строки матрицы (как векторы) определяют то же линейное подпространство <от, что и строки матрицы т. е.

Заметим, что матрица преобразует -выборку в -мерный вектор таким образом, что первые координат вектора совпадают с соответствующими компонентами выборки, а последние являются их линейными комбинациями:

Приходим к кодам, которые называют систематическими, при передаче кодового слова первые мест называют информационными, а последние проверочными, так как эти линейные комбинации позволяют обнаружить или даже исправить ошибки при передаче информационных символов. Такой код обозначается через . Если использовать линейные пространства над полем из двух элементов, то с его помощью можно передать сообщений.

Линейный код общего вида состоит из всех векторов некоторого подпространства линейного -мерного пространства.

Двойственный код. Исходя из кода можно непосредственно образовать двойственный код Действительно, если подпространство, порожденное матрицей

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

последних векторов образуют базис подпространства пространства

Для матрицы (образованной первыми строками матрицы имеем тогда

для матрицы (образованной последними строками матрицы имеем

где матрица, транспонированная к матрице единичная матрица порядка Выполняется следующее матричное соотношение:

Действительно, записывая сомножители с помощью блоков подходящих размеров (т. е. таких, что число строк блока-множимого равно числу столбцов блока-множителя), получаем

Пространство, порожденное векторами матрицы называют нулевым пространством для матрицы и наоборот. Если -мерный вектор, полученный из -выборки с помощью матрицы е.

то

Мы видим, что переводит в нулевой вектор любой вектор IIVII из

Проверочная матрица. Матричное соотношение

можно переписать в виде

Это — система линейных однородных уравнений с неизвестными, и -мерные векторы, компоненты которых — символы кодовых слов на контрольных местах, будут ее решениями. Ввиду этого называют проверочной матрицей.

Обнаружение ошибок. Для вектора из подпространства порожденного строками матрицы имеем

Если теперь на выходе получаем некоторый вектор с

то не принадлежит и мы обнаружили ошибку.

Замечание. Очевидно, что при можно лишь утверждать, что при передаче по линии не произошло ошибки какого-то определенного типа, но нет гарантии, что отсутствуют ошибки других типов. Действительно, вектор имеет компонент и поэтому не дает возможности выявить больше чем типов ошибок число элементов поля). Поэтому необходимо с самого начала установить, какие ошибки мы хотим обнаруживать.

Запишем матрицу в виде последовательности ее столбцов:

Для вектора

в пространстве над полем из двух элементов имеем

Если при передаче принимается как с ошибками на местах то пусть

Складывая по модулю 2, получаем

Так как

то

Всегда возможно указать сочетания столбцов матрицы соответствующие наиболее вероятным ошибкам, исходя из значений ненулевого вектора

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

Хэмминг доказал, что минимальное расстояние равно если любые столбцов матрицы линейно независимы.

С другой стороны, Мак-Класки доказал методами линейного программирования, что дает код с минимальным расстоянием тогда и только тогда, когда подматрица этой матрицы обладает тем свойством, что каждый ее столбец содержит не меньше ненулевых элементов, а любые столбцов — не меньше ненулевых произведений элементов по строке,

Примеры линейных двоичных кодов. 1) Код Хэмминга для исправления простой ошибки Если длина кодового слова равна то необходимо, чтобы

При имеем По Мак-Класки каждый столбец матрицы должен иметь не меньше единиц, каждаяпара столбцов — не меньше ненулевых произведений элементов по строке и каждая триада — не меньше таких произведений. Матрица

удовлетворяет этим условиям Дополняя ее единичной матрицей порядка 3, получаем проверочную матрицу

Заметим, что каждый столбец матрицы совпадает с вектором когда ошибка произошла на соответствующем месте кодового слова:

Если переставить столбцы в матрице так, чтобы столбец представлял собой двоичную запись числа

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

Пусть кодовое слово обозначается

Из в форпе получаем матрицу , порождающую код:

Выпишем полностью линейный код, получающийся с помощью для всех возможных двоичных слов длины 4:

Три контрольных соотношения для кодовых слов:

или

Пусть, например, передается сообщение

закодированное

и на третьем месте принимается ошибочный символ, т. е. при приеме получается

который не принадлежит , т. е. не является кодовым словом; тогда

что как раз и означает, что ошибка была допущена на третьем месте и там нужно 0 исправить на 1.

2) Код Хэмминга, исправляющий простую ошибку и обнаруживающий двойную. Из кода можно получить код со словами длины имеющий информационных символов, если присоединить 1 на месте каждого слова кода и ввести еще одно проверочное соотношение:

Тогда:

если проверочных соотношений выполняются, то не произошло простой ошибки;

если последнее соотношение не выполняется, то произошла простая ошибка, которую можно исправить с помощью первых соотношений;

если последнее соотношение выполняется, но не выполняется по крайней мере одно из первых соотношений, то обнаружена двойная ошибка; исправить ее нельзя.

Вернемся к предыдущему примеру, Действуя, как описано, получаем код (8,4) с проверочной матрицей

и соотношениями

Циклические коды. Чтобы изучать эти коды, нам потребуются некоторые сведения из современной алгебры, которые мы кратко изложим.

Теория присоединения. Многочлен не имеет корней над полем действительных чисел Он неприводим над этим полем, т. е. не разлагается в произведение многочленов меньшей степени с действительными коэффициентами. Присоединим теперь к элементам поля символ для которого предполагаем выполненным соотношение и на этом расширенном множестве элементов рассмотрим операции считая для них справедливыми все аксиомы операций поля. Получаем тогда новое поле в котором многочлен уже разлагается на множители:

Таким образом, мы приходим к полю комплексных чисел котором операции задаются соотношениями

В общем случае, если задан неприводимый над полем К (основным полем) многочлен степени

где то всегда можно присоединить к К последовательно символы чтобы полностью разлагался на множители в новом поле называемом полем разложения многочлена

В дальнейшем мы будем рассматривать лишь конечные поля где число элементов поля, и, как правило, ограничиваться случаем

Над полем любой многочлен можно представить в виде

где если степень многочлена равна

Если неприводим над то можно добиться его разложения на неприводимые сомножители, присоединяя к лишь один элемент а. Можно показать (см. § А5), что корней этого многочлена — степени элемента а:

Так как корень то в поле выполняется

или

что можно также записать как

если

Соотношение показывает, что все степени а можно выразить как линейные комбинации первых степеней с коэффициентами из Действительно,

и, если заменить по формуле то получаем

Вообще в поле где характеристика поля, всегда существует элемент а, для которого является периодом (минимальным показателем Все элементы поля тогда представляются как линейные комбинации

Элемент а называется элементом порядка а неприводимый многочлен такой, что примитивным многочленом. Каждой степени соответствует -выборка элементов поля (всего таких -выборок будет Поле называется расширением поля Многочлен имеет в корней

Если рассмотреть кольцо многочленов над то каждый элемент фактор-множества

соответствует линейной комбинации и обратно. Элементы вместе с образуют множество со структурой поля — неприводимый многочлен). Элементы называют вычетами по модулю многочленов

где

и

Для любых между найдутся такие в этих же пределах, что

и

Пример. Пусть

Это — примитивный многочлен над Действительно, он, во-первых, неприводим над так как

и

во-вторых, присоединяя к элемент а, для которого

видим, что а имеет порядок Покажем теперь непосредственно, что

Действительно,

и аналогично

Если период элемента меньше то этот элемент, порождает циклическую группу порядка

Неприводимый многочлен для которого является корнем, не будет примитивным. Период любого элемента конечного поля с элементами — делитель

Пример. Многочлен

неприводим над Если присоединить к элемент такой, что

то имеем

Период равен 5, делителю Корнями будут и мы имеем

С помощью степеней элемента мы не можем получить все классы вычетов по модулю

Принцип обнаружения и исправления ошибок. Пусть -неприводимый над многочлен степени Построим с его помощью код со словами длины Для этого рассмотрим все возможные кратные многочлена степени не выше

кодовое слово

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

Разделим, далее, на

откуда

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

Кодирование. Пусть имеем сообщение

Представим его с помощью многочлена

Затем умножим на (см. (Б3.93)), разделим произведение на и получающийся остаток вычтем из

Получаем кодовое слово

Декодирование. В случае, когда полученное слово С совпадает с переданным словом С, при делении на не может получиться ненулевого остатка; поэтому если

то при передаче была допущена ошибка.

Замечание. При можно сделать вывод лишь об отсутствии ошибок определенного типа, но не об отсутствии ошибок вообще.

Пример. Предположим, что требуется передать сообщение с помощью кода с длиной слова 7, позволяющего исправить простую ошибку.

Имеем 3; многочлен примитивный многочлен. Действуем по правилам, изложенным выше:

Пусть при передаче С мы получили При делении на получаем остаток который указывает на наличие простой ошибки.