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 (буквой М, как и раньше, обозначен мажоритарный элемент).