19. ЛАТИНСКИЕ КВАДРАТЫ И КОДЫ
Латинские квадраты долгое время были известны лишь математикам и любителям головоломок и, в основном, благодаря одной знаменитой задаче Л. Эйлера ). В 1782 г. Эйлер предложил следующую проблему.
Среди 36 офицеров находится по шесть офицеров шести различных званий из шести полков. Можно ли построить этих офицеров в каре так, чтобы в каждой колонне и каждой шеренге встречались офицеры всех званий и всех полков?
Лишь в 1901 г. удалось доказать, что это невозможно. Однако связанные с задачей Эйлера латинские квадраты не потеряли интереса, так как вскоре обнаружилось, что они имеют многообразные практические применения. А совсем недавно (конец шестидесятых годов) они были применены и в теории кодирования. Получающиеся на их основе коды, хотя и далеки по своим параметрам от оптимальных, но зато допускают простые алгоритмы декодирования (голосование в один шаг).
Будем рассматривать квадратные матрицы порядка п, элементы которых — числа 1,2Такую матрицу называют латинским квадратом, если всякий элемент входит ровно один раз в каждую строку и в каждый столбец.
Следующие матрицы являются примерами латинских квадратов (соответст^чно порядка 2, 3 и 4):
Существенным при построении кодов является свойство ортогональности матриц, которое определяется следующим образом.
Две матрицы порядка п называются ортогональными (не путать с ортогональностью векторов!), если при наложении любой из них на другую мы получим множество всех упорядоченных пар (г, /'), 1<1<п,
Вот пример ортогональных латинских квадратов порядка 3:
по происхождению, он жил и работал преимущественно в России. Эйлер, выделявшийся своей исключительной интуицией и разносторонностью интересов, оставил глубокий след практически во всех областях современной ему математики. Большое количество его замечательных результатов явилось основой для дальнейшего развития многих разделов математики.
Легко видеть, что матрица порядка п является латинским квадратом тогда и только тогда, когда она ортогональна обеим матрицам А и В.
Ортогональны также и следующие две матрицы:
При построении кодов используются матрицы (1) и им ортогональные. Способ построения обеспечивает нужное для декодирования число ортогональных проверок; состоит этот способ в следующем.
Для матрицы С указанного типа и для любого ее элемента к определим двоичную матрицу Ск, которая получается [13 С заменой всех элементов, равных к, единицами, а всех остальных элементов — нулями. Таким образом, по матрице С порядка п строятся матрицы Сг, С~2, . . ., С„. Каждой из этих матриц Ск сопоставим вектор %>к, первые п координат которого являются последовательными элементами первой строки матрицы Ск, следующие п координат — элементами второй строки и т. д. Иными словами, пЯ координат вектора V,,— это все элементы матрицы Ск, «вытянутой» в одну общую строку. Образуем, наконец, матрицу С порядка пХп2, строками которой являются векторы V,;.
Например, для матрицы имеем:
Пусть теперь А и В — матрицы (1), а Б^,. . .,0Г — попарно ортогональные латинские квадраты. Образуем из них указанным выше способом матрицы А, В, Ё)и Г>2, . . . . . . , Бг, а затем построим матрицу Н, которую можно условно представить в виде:
(матрицы Л, В,Ои1)г Вг подписываются одна под другой и к получившейся матрице приписывается справа единичная матрица Ет соответствующего порядка т).
Матрицу Н будем считать проверочной матрицей кода, построенного с помощью латинских квадратов. Число строк этой матрицы, как вытекает из построения, равно (г+2)п, а число столбцов составляет п2+(г+2)«. Кодовое расстояние полученного кода, как мы увидим, будет не меньше
В качестве примера рассмотрим код, построенный с помощью двух ортогональных латинских квадратов порядка 3:
В этом случае
Наконец, проверочная матрица искомого кода такова:
Легко видеть, что для каждого из 9 информационных символов может быть составлено четыре ортогональных проверки. Например, первая, четвертая, седьмая и десятая
строки матрицы Н дают следующие проверки для первого символа а0:
Ортогональность этих соотношений, как можно убедиться, как раз и объясняется свойством ортогональности исходных матриц. При этом число таких соотношений для каждого символа всегда равно числу матриц, используемых для построения, т. е. г+2. А значит, кодовое расстояние не может быть меньше, чем г+3; в нашем примере оно не меньше пятиНа рис. 25 мы приводим часть декодирующей схемы, предназначенную для декодирования символа а0 (буквой М, как и раньше, обозначен мажоритарный элемент).