Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
19. ЛАТИНСКИЕ КВАДРАТЫ И КОДЫ
Латинские квадраты долгое время были известны лишь математикам и любителям головоломок и, в основном, благодаря одной знаменитой задаче Л. Эйлера-*). В 1782 г. Эйлер предложил следующую проблему.
*) Леонард Эйлер (1707—1783) — один из великих математиков XVIII века, создавших основы математического анализа, Швейцарец
,102Среди 36 офицеров находится по шесть офицеров шести различных званий из шести полков. Можно ли построить этих офицеров в каре так, чтобы в каждой колонне и каждой шеренге встречались офицеры всех званий и всех полков?
Лишь в 1901 г. удалось доказать, что это невозможно. Однако связанные с задачей Эйлера латинские квадраты не потеряли интереса, так как вскоре обнаружилось, что они имеют многообразные практические применения. А совсем недавно (конец шестидесятых годов) они были применены и в теории кодирования. Получающиеся на их основе коды, хотя и далеки по своим параметрам от оптимальных, но зато допускают простые алгоритмы декодирования (голосование в один шаг).
Будем рассматривать квадратные матрицы порядка п, элементы которых — числа 1,2, . . .,п. Такую матрицу называют латинским квадратом, если всякий элемент входит ровно один раз в каждую строку и в каждый столбец.
Следующие матрицы являются примерами латинских квадратов (соответственно порядка 2, 3 и 4):
Существенным при построении кодов является свойство ортогональности матриц, которое определяется следующим образом.
Две матрицы порядка п называются ортогональными (не путать с ортогональностью векторов!), если при наложении любой из них на другую мы получим множество всех упорядоченных пар (і, /), l^ijgCrt, 1^/^rt.
Вот пример ортогональных латинских квадратов порядка 3:
по происхождению, он жил и работал преимущественно в России. Эйлер, выделявшийся своей исключительной интуицией и разносторонностью интересов, оставил глубокий след практически во всех областях современной ему математики. Большое количество его замечательных результатов явилось основой для дальнейшего развития многих разделов математики. ,
,103Ортогональны также и следующие две матрицы:
А
B =
2 3 2 3 2 3
\
1 2 3
(1)
Легко видеть, что матрица порядка п является латинским квадратом тогда и только тогда, когда она ортогональна обеим матрицам А и В.
При построении кодов используются матрицы (1) и им ортогональные. Способ построения обеспечивает нужное для декодирования число ортогональных проверок; состоит этот способ в следующем.
Для матрицы С указанного типа и для любого ее элемента k определим двоичную матрицу Ck, которая получается из С заменой всех элементов, равных k, единицами, а всех остальных элементов — нулями. Таким образом,
по матрице С порядка п строятся матрицы C1, C2.....Cn.
Каждой из этих матриц Ck сопоставим вектор Vk, первые п координат которого являются последовательными элементами первой строки матрицы Ck, следующие п координат — элементами второй строки и т. д. Иными словами, координат вектора Vk— это все элементы матрицы Ck, «вытянутой» в одну общую строку. Образуем, наконец, матрицу С порядка пхп*, строками которой являются векторы Vk:
fVl)
Например, для матрицы
С
1 2 3
2 3 1
3 1 2
)
имеем:
C1 =
1 0 0\ О О I О 1 о
C1=(Iooooioio),
0 і о
1 о о о о 1
у2=(010100001), 10 0 0 0 10 10 с = ( 0 1 0 1 0 0 0 0 1 0 0 10 10 10 0
с,=
OOb
0 1 о
1 О 0/ —(001010100)
104Пусть теперь Л и В — матрицы (1), a Di, Di,. . .,Dr — попарно ортогональные латинские квадраты. Образуем из
них указанным выше способом матрицы А, В, DuD.....
. . . , Dr, а затем построим матрицу Ht которую можно условно представить в виде:
# =
' ~А В Di Dt
KDr
(матрицы Л, BtDitDi.....Dr подписываются одна под другой и к получившейся матрице приписывается справа единичная матрица Em соответствующего порядка т).
Матрицу H будем считать проверочной матрицей кода, построенного с помощью латинских квадратов. Число строк этой матрицы, как вытекает из построения, равно (г+2)п, а число столбцов составляет rt^+(r+2)n. Кодовое расстояние полученного кода, как мы увидим, будет не меньше г+3.
В качестве примера рассмотрим код, построенный с помощью двух ортогональных латинских квадратов порядка 3;
¦12 3 D1 =I 2 3 1 \3 I 2
D,
1 2 3 3 1 2
2 3 1
В этом случае Л =(2 2
\з з з/
/I I I О О О О О 0\ Л — І 0 0 0 1 1 1000), Vo 0 0 0 0 0 I 1 1/
/1 0 0 0 0 I О 1 0\ Di = (010100001),
\0 0 1 0 1 0 1 о о/
/1 0 0 1 0 0 I 0 0\
?;=(o 1 0 0 1 0 0 1 0 ], Vo о 1 о о 1 о о 1/
Л 0 О О 1 0 0 0 1ч D1 = (010001100). Vo 0 1 1 0 0 0 1 0/
,105Наконец, проверочная матрица искомого кода такова:
О
H =
1110 0 0 0 0 0 1 000 111000 1 0 0 0 0 0 0 111 1 10 0 1 0 0 10 0 ! 0 10 0 1 0 0 1 0 1 0 0 10 0 10 0 1 1 10 0 0 0 10 10 S
0 10 10 0 0 0 1 I
0 0 10 10 10 0 10 0 0 10 0 0 1 0 10 0 0 110 0 1 \0 0 1 1 0 0 0 1 0 W
Легко видеть, что для каждого из 9 информационный символов может быть составлено четыре ортогональных проверки. Например, первая, четвертая, седьмая и десятая,