Главная > Теория связи > Введение в теорию помехоустойчивого кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

ГЛАВА XI. СПЕЦИАЛЬНЫЕ КОДЫ

1. Итеративные коды

Идея итеративных кодов принадлежит Элаиесу [179—182]. Суть предложенного им метода построения кодов легче всего пояснить на примере. Сначала информационные символы , выписываются в виде табл. ХI.I

Таблица ХI.I

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

(Проверка проверок находится как сумма по модулю два символов последней строки или последнего столбца).

Приведенный код является простейшим двустепен-ным итеративным кодом с , причем число комбинаций такого веса при

(XI.1.1)

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

В общем случае каждый информационный символ двустепенного итеративного кода является символом комбинаций двух кодов и . Табл. XI.2 иллюстрирует это положение для случая итерации кодов (7, 4, 3) и (7, 4, 3).

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

Теорема XI.1. Значность г-степенного итеративного кода

(XI.1.2)

число информационных символов

(XI.1.3)

и кодовое расстояние

(XI.1.4)

где и — параметры итерируемых кодов.

Таблица XI.2

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

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

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

Например итерация кодов (7, 4, 3) и (7, 4, 3) (табл. XI.2) приводит к коду (49, 16, 9). Если бы такой код декодировался как обычный линейный код, то в его комбинациях можно было бы исправить все ошибки вплоть до четырехкратных. Однако если использовать процедуру Элайеса, то оказывается невозможным исправить четырехкратные ошибки, сконцентрированные в двух строках и двух столбцах, например сконцентрированную в верхнем левом углу табл. XI.2.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление