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

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

Сначала информационные символы кодовой комбинации записываются в виде таблицы, которая, например, может иметь такой вид:

Затем к каждой строке таблицы и к каждому столбцу дописываются проверочные символы в соответствии с каким-нибудь кодом Применим в качестве кода код с проверкой на четность:

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

кодов с проверкой на четность. Передача одного сообщения комбинацией итеративного кода обычно происходит по строкам последовательно, от первой строки к последней. Приведенный код является простейшим итеративным кодом с , причем число кодовых комбинаций веса при где количество информационных символов в строке; I — количество информационных символов в столбце.

Этот код обнаруживает [90, 130) все ошибки кратностью до трех и все ошибки нечетной кратности. Не обнаруживаются четырехкратные ошибки, располагающиеся в вершинах правильного четырехугольника, а также некоторые шестикратные, восьмикратные и т. д. ошибки (рис. 18). Количество четырехкратных ошибок, имеющих показанную на рис. 18 структуру, равно

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

Рис. 18. Структуры ошибок, не обнаруживаемые простейшим двумерным итеративным кодом: а — ошибки кратности 4; б - ошибки кратности 6; в — ошибки кратности 8.

Необнаруживаемые ошибки кратности 6 расположены в трех столбцах, по две в каждом. Количество различных столбцов первого типа равно Второй столбец может быть выбран способами. Третий столбец однозначно определяется первыми двумя. Все три столбца могут быть выбраны способами. Поэтому

После преобразования

С помощью подобных рассуждений можно определить

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

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

где параметры итерируемых кодов; кратность итерирования; знак произведения.

Пример. Определить параметры двумерного итеративного кода, в котором в качестве кода по строкам используется код с проверкой на четность с параметрами а в качестве кода по столбцам — код Хэмминга с параметрами Согласно формулам

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

Пусть, например, заданы производящие матрицы кодов А к

Векторное произведение этих производящих матриц

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

Согласно (3.55) имеем

где

Следовательно, производящая матрица итеративного кода

После преобразования получим матрицу в каноническом виде:

которая порождает код с параметрами

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

Существенным недостатком итеративных кодов, использующих для проверок по строкам и столбцам коды с проверками на четность, является их сравнительно высокая избыточность, которая обычно составляет 15—20% и значительно превышает при прочих равных условиях избыточность циклических кодов. Однако кодирование и декодирование с помощью ЭВМ таких итеративных кодов обычно гораздо проще, чем циклических.

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