Б3. Коды, обнаруживающие и исправляющие ошибки. Расстояние Хэмминга. Пусть мы получили код, в котором каждая -выборка закодирована словом, состоящим из символов (рис. 532). Будем предполагать, что символы взяты из конечного множества, обладающего структурой поля (тогда эти. символы можно складывать и перемножать).
Особенно удобно пользоваться конечными полями характеристики 2, что мы и будем делать. Хэмминг определил расстояние между двумя кодовыми словами как число мест, в которых символы этих слов не совпадают.
Если, например. Расстояние Хэмминга тесно связано с вероятностью ошибки при передаче сообщения. Действительно, пусть передано слово которое принято как слово и. в самом деле, при передаче символа по двоичной симметрической линии вероятность ошибки равна а у нас символов переданы правильно, а символов — неверно. Так как всегда меньше 0,5, то увеличивается, когда уменьшается; отсюда получаем правило: при получении на выходе кодового слова следует в качестве кодового слова на входе брать слово с наименьшим расстоянием от (рис. 533).
Можно проверить, что расстояние Хэмминга удовлетворяет всем обычным аксиомам расстояния:. причем равенство имеет место тогда и только тогда, когда. Для расстояния Хэмминга справедливо соотношение. Это означает, что при кодировании словами, расположенными одно от другого на расстоянии не меньше получаем возможность исправить все простые ошибки (на одном месте), все двойные ошибки (на двух местах), все ошибки на местах. то имеется возможность исправить все простые ошибки, двойные ошибки, ошибки на местах.
Ошибки на местах можно обнаружить, но исправить, вообще говоря, нельзя. Действительно, если расстояние между кодовыми словами не меньше при получении слова его следует интерпретировать по установленному выше правилу как слово (рис.
534), так как от любого другого слова С, оно находится на расстоянии, не меньшем Заметим, что исправить можно самое большее ошибок. Если минимальное расстояние между двумя словами в коде равно то можно найти два слова с расстоянием от полученного слова следовательно, обнаруженную ошибку исправить нельзя (рис. 535).
Точно так же можно было бы показать, что для исправления ошибок и обнаружения ошибок при необходимо, чтобы. Верно также и обратное утверждение. Из сказанного выше очевидна необходимость кодирования. Выяснены также условия, которым оно должно удовлетворять. Остается лишь показать, каким способов кодирование можно осуществить. Известные способы кодирования, дающие возможность обнаружения и исправления ошибок, используют:.
1) подпространства векторного пространства размерности , при этом слова имеют длину это — линейные. 2) отношение делимости мйогочленов; это — циклические коды.
Предшественником последних является код Бодо. Циклические коды, будучи менее доступными для теоретической трактовки, чем линейные, практически реализуются значительно легче. Двоичные линейные коды. Пусть. — вектор, все компоненты которого равны нулю, кроме равной 1.
Эти векторы в совокупности линейно независимы и образуют базис линейного пространства над полем (1 можно считать единицей поля). Их можно записать как строки матрицы порядка.
где а — элементы поля, преобразуется матрицей в вектор. Если взять другие линейно независимых векторов и записать их как строки матрицы то при.
имеем» вообще говоря. но, как и в предыдущем случае, умножением на матрицу получаются все векторы из.
Точно так же можно определить матрицу строки которой представляют собой линейно независимых векторов (ранга с помощью этой матрицы можно получить все векторы из подпространства размерности пространства. Приведение матриц к каноническому виду. Рассмотрим следующие действия с матрицами:.
1) перестановка строк;. 2) умножение строки на произвольный ненулевой элемент поля;. 3) прибавление к строке матрицы другой строки, умноженной на элемент поля. С помощью этих действий всегда можно привести матрицу ранга к следующему каноническому виду:. При этом строки матрицы (как векторы) определяют то же линейное подпространство Б3.
Коды, обнаруживающие и исправляющие ошибки.