Обнаружение и исправление ошибок. Декодирующее устройство.

Рассмотрим процедуру обнаружения ошибок в принятой кодовой комбинации. Обнаружение ошибок может быть основано на сравнении принятой кодовой комбинации со всеми разрешенными. Если принятая кодовая комбинация совпадает с одной из разрешенных, то можно сделать вывод о том, что ошибок при передаче не было или переданная (разрешенная) кодовая комбинация А, перешла в другую разрешенную кодовую комбинацию Если принятая кодовая комбинация не совпадает ни с одной из разрешенных, то делается вывод о том, что произошла ошибка (или ошибки) в этой кодовой комбинации. Однако такой алгоритм декодирования требует сравнения принятой кодовой комбинации со всеми разрешенными и является поэтому весьма громоздким, особенно в том случае, когда число разрешенных кодовых комбинаций велико.

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

Рис. 7.1 Кодер кода (7,4)

Рис. 7.2. Декодирование с обнаружением ошибок для кода (7,4)

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

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

Пример 7.4. Пусть код (6,3) задан системой проверок (7.4) — (7 6) и при передаче кодовой комбинации 101 100 на приеме получили 001 101, т. е. искажены элементы Вычислим элементы синдрома

Так как синдром отличен от нуля, то ошибка обнаружена.

Декодер для кода (7,4), работающий в режиме обнаружения ошибок, представлен на рис. 7.2.

Выходы сумматоров, в которых формируются элементы синдрома, подаются на схему ИЛИ С выхода последней снимается единица (сигнал «ошибка») при обнаружении ошибок. При этом приемник отвергает принятое кодовое слово. Такой отказ от принятого кодового слова называется стиранием и обычно предполагает повторение кодового слова заново.

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

Отсюда имеем систему уравнений

Вид синдрома будет определяться только вектором ошибок и не зависит от вида переданной кодовой комбинации. Действительно,

так как где Е — вектор ошибок, то

Рассмотренный в примере (7.4) код (6,3) имеет кодовое расстояние и способен исправлять однократные ошибки. Если неправильно принят элемент то из системы уравнений

получаем так как входит в (7.9) и (7 10) и не входит в (7.8). Значение синдромов для случая, когда имеется одиночная ошибка в том или ином элементе, приведены в табл 7.1.

Таблица 7.1

Рис. 7.3 Декодирование с исправлением ошибок для кода (7,4)

Нетрудно заметить, что вид синдрома, соответствующий искаженному элементу совпадает с столбцом матрицы (7.7). Это со всей очевидностью следует из следующей записи:

для случая, когда Е= 100000. Нетрудно догадаться, что если имела место двухкратная ошибка, например в элементах, то синдром был бы равен сумме столбцов матрицы Н. Так, если , то , т. е. будет сделан неверный вывод о том, что искажен элемент , так как код двукратные ошибки не исправляет.

Структурная схема декодера с исправлением одиночных ошибок для кода (6,3) приведена на рис. 7.3. На вход декодера поступает кодовая комбинация, сформированная кодером, изображенным на рис. 7.1. По принятой комбинации вычисляется синдром, который подается на дешифратор «синдром-ошибка». При одиночной ошибке на одном из выходов дешифратора появляется (элемент вектора ошибки). Сложение вектора ошибки с принятой комбинацией приводит к исправлению ошибки.