7.7.2. Коды на основе ортогональных латинских квадратов

Используя ортогональные латинские квадраты Боссен и Чень [14, 18] построили класс кодов для исправления независимых ошибок, ортогонализируемых в один шаг и, следовательно, допускающих пороговое декодирование [14, 18]. Этим кодам посвящен данный раздел. Обычно достичь большой скорости декодирования кодов, исправляющих независимые ошибки, при небольшой избыточности бывает очень трудно. Это связано с тем, что эффективные с точки зрения избыточности коды имеют очень сложные декодирующие устройства, а в результате и низкую скорость декодирования. В подобных случаях часто возникает необходимость повысить скорость декодирования за счет использования более простых алгоритмов декодирования и некоторого увеличения избыточности кода. Пороговые методы декодирования являются как раз такими методами, которые позволяют достичь высокой скорости декодирования. Из особенностей рассматриваемых ниже кодов следует отметить то, что они не являются циклическими и что введение избыточности для повышения корректирующей способности кода осуществляется целыми модулями.

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

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

Проверочная матрица кода, построенного на основе латинских квадратов, имеет следующий вид:

где единичная матрица размера

матрицы, которые строятся указанным ниже образом на основе ортогональных латинских квадратов:

где

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

Определение 7.2. Пусть латинский квадрат, и пусть произвольный его элемент. Матрица инцидентности элемента определяется равенством

«Но.

Для каждого латинского квадрата порядка можно построить матриц инцидентности Каждой из этих матриц сопоставим вектор

Подматрица проверочной матрицы строится следующим образом;

где векторы, определяемые формулой (7.81) и соответствующие латинскому квадрату

Теорема 7.2. Линейный код с проверочной матрицей построенной описанным выше образом по ортогональным латинским квадратам порядка исправляет любые или менее ошибок, где

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

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

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

Схема декодирования 1-го информационного символа приведена на фиг. 7.46.

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

Фиг. 7.46. Декодер -кода исправляющего одиночные ошибки.

В этом случае код задается проверочной матрицей (7.76), нижние две подматрицы которой имеют следующий вид: