Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

где Н( — транспонированная контрольная матрица. По­ этому если принятое слово X принадлежит кодовому множеству, т. е. в .нем отсутствуют ошибки, то матричное •произведение

Другими словами, выполнение равенства (2-3) свиде­ тельствует о том, "что слово X принадлежит кодовому множеству. Это же равенство непосредственно следует из правила построения и использования •контрольной ма­ трицы Н, если вспомнить, что

k

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

EiUt^0 для всех £ г £ Ф . (2-5)

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

EiHi^EjHi, если

Теорема 2-1. Линейный групповой код имеет мини­ мальное расстояние d в том и только в том случае, если любые d—1 или менее вектор-столбцов контрольной ма­ трицы Н линейно независимы.

Доказательство. Матричное произведение (2-4) запи­ шем следующим образом:

где 6j — компоненты вектора ошибок, hi— i-fi векторстолбец матрицы Н (или i-я вектор-строка матрицы Н,).

Тогда неравенство (2-5)

п

является условием линейной независимости векторов hi. Так как кратность возникшей ошибки определяется чис­ лом в{фО (или весом вектора ошибки), то для обнару­ жения произвольных >(d—1) или менее ошибок необхо­ димо и достаточно, чтобы любые (d—1) или менее век­ торов hi были линейно независимы. Отсюда непосредст­ венно следует утверждение теоремы, если вспомнить, что максимальная кратность ошибок, обнаруживаемых ко­

няет минимального расстояния d. Справедливость этого непосредственно следует из доказанной теоремы, так как исключение из рассмотрения части столбцов /г, матрицы Н не может повлиять на линейную независимость (зави­ симость) оставшихся столбцов.

Рассмотренные линейные 'групповые корректирующие •коды допускают весьма компактное описание с помощью порождающей или проверочной матриц. Эти коды пред­ ставляют особый интерес по следующей причине: описан конструктивный способ кодирования и декодирования, т. е. исправления возникших ошибок, отличный от метода перебора. Поэтому групповые коды имеют центральное значение, хотя существуют некоторые негрупловые коды, которые также поддаются простому математическому

этом кодовые векторы, соответствующие этим кодам, от­ личаются только порядком следования символов. Отсюда следует, что перестановка столбцов матрицы G порож­ дает эквивалентный код.

где Ci — контрольные разряды, s; — информационные раз ­ ряды.

Если при передаче кодового слова возникнет одиноч­ ная ошибка, то окажутся невыполненными те контроль­ ные соотношения (уравнения для с^, в которые входит значение ошибочного разряда. Например, если ошибка возникла в ^первом информационном разряде, то окажут­ ся невыполненными третье и четвертое уравнения, т. е. корректор будет равен ООП, совпадая с первым векторстолбцом матрицы Н. Отсюда получаем алгоритм опре­ деления места одиночной ошибки: местоположение век­ тор-столбца матрицы Н, совпадающего с вычисленным корректором, указывает место ошибки. Ясно, что вычис­ ленное значение корректора обязательно совпадает с одним из вектор-столбцов матрицы Н, так как в каче­ стве вектор-столбцов были выбраны все возможные дво­ ичные 4-разрядные числа.

Если возникнет ошибка кратности 2, то полученное значение корректора также будет совпадать с одним из вектор-столбцов матрицы Н и ошибки автоматически ис­ правляются. Однако заметим, что после такого «исправ­ ления» получается кодовое слово, не совпадающее с тре­ буемым кодовым словом. Значение корректора, соответ­ ствующее ошибке кратности 2 и более, получается при помощи поразрядного суммирования по модулю 2 век­ тор-столбцов матрицы Н, соответствующих ошибочным разрядам.

Например, если ошибка произойдет в первом и втором инфор­ мационных разрядах, то, складывая первый и второй вектор-столбцы, получаем:

но является кодовым. Поэтому, когда вероятность воз­ никновения ошибок кратности более единицы значитель­ на, автоматическое исправление ошибок оказывается не36