3.4. Методы исправления ошибок

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

таблица, в первой строке которой располагаются все кодовые слова Вторая строка таблицы заполняется векторами, полученными в результате суммирования по модулю два кодовых слов первой строки с вектором вес которого а единица расположена в первом разряде. Третья строка таблицы — результат сложения по модулю два кодовых слов первой строки с вектором вес которого а единица содержится во втором разряде. Аналогично поступают до тех пор, пока не будут просуммированы с кодовыми словами все векторы весом с единицами в каждом из разрядов. Затем суммируются по модулю два векторы в) весом с последовательным перекрытием всех возможных разрядов.

Вес вектора определяет число исправляемых ошибок. Сказанное ранее иллюстрирует табл. 16. Таким образом, для каждого кодового слова. существует своя группа кодов-спутников, расположенных в соответствующем столбце.

Таблица 16 (см. скан)

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

Пример. Определить коды-спутники для кода, исправляющего одиночную ошибку со следующими четырьмя рабочими комбинациями: 01001, 01110, 10010, 10101. Поскольку достаточно построить коды-спутники, отличающиеся от исходных кодовых комбинаций на Используя табл. 16, имеем

Благодаря кодам-спутникам принятая, например, искаженная комбинация 10111 расшифруется как исходная! 10101.

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

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

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

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

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

Таким образом, определяем синдром путем решения уравнений

Если код используется для исправления ошибок, то при декодировании должно быть заранее определено соответствие между видом синдрома и видом исправляемой ошибки. Установим это соответствие. Пусть ошибка воздействует в первом разряде (комбинация ошибки 1000000). Применим этой комбинации проверки (3.16):

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

Пусть, например, в кодовой комбинации 1101001 при передаче произошла ошибка во втором разряде и на вход декодирующего устройства поступила комбинация 1001001. При декодировании в соответствии с (3.16) будут получены следующие результаты: 1-я проверка проверка проверка

Таблица 17 (см. скан)

Таким образом, синдром равен 101. Это свидетельствует о том (табл. 17), что ошибочен именно второй разряд принятой комбинации. Из табл. 17 видно, что для указания ошибок могут использоваться все комбинации двоичного кода, кроме нулевой. Поэтому число разрядов синдрома, а следовательно, и число проверочных символов при исправлении однократных ошибок определяется неравенством

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

В общем случае где кратность ошибки. Это условие совпадает с границей Хэмминга (см. § 3.2). Но если для

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

До сих пор не имеется в литературе метода, который позволил бы построить систематический код для исправления множества ошибок. В работах [7, 76] разработан метод построения синдромов для кодов, предназначенных для исправления двойных, тройных, а также пачек ошибок длины В табл. 18 представлены синдромы для кода, исправляющего двойные ошибки, а в табл. 19 — для кода, исправляющего тройные ошибки. По этим таблицам находим синдромы двойных и тройных ошибок путем суммирования по модулю два синдромов, в разрядах которых произошли ошибки. Например, для кода, исправляющего двойные ошибки, получен синдром 0000011111. По табл. 18 находим, что данный синдром получается путем суммирования по модулю два 5-го и 6-го разрядов, т. е. искажены пятый и шестой разряды кодовой комбинации.

Таблица 18 (см. скан)

Таблица 19 (см. скан)

В табл. 20 представлены синдромы -разрядного кода, исправляющего пачки ошибок длины

Таблица 20 (см. скан)

Ввиду сложности построения синдромов для исправления множества ошибок обычно процесс построения поручают вычислительным машинам. С помощью вычислительной машины Банерджи построил таблицу кодов для исправления любых двукратных ошибок в кодовых комбинациях длиной до 29 разрядов (приложение 1). В первой графе этой таблицы указан тип кода. Каждая из

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