Научная литература
booksshare.net -> Добавить материал -> Математика -> Аршинов М.Н. -> "Коды и математика (рассказы о кодировании) " -> 37

Коды и математика (рассказы о кодировании) - Аршинов М.Н.

Аршинов М.Н., Садовский Л.Е. Коды и математика (рассказы о кодировании) — М.: Наука, 1983. — 144 c.
Скачать (прямая ссылка): kodiimatematika1983.pdf
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 50 >> Следующая


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 информационный символов может быть составлено четыре ортогональных проверки. Например, первая, четвертая, седьмая и десятая,
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 50 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed