Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
H —(Нп НЛ н*»-{нп -Hn)'
Именно таким образом получались одна из другой матрицы порядков 1,2, 4, 8, приведенные в начале этого параграфа.
Доказать, что матрица Hin является матрицей Адамара^
2. Следующие две операции преобразуют матрицу Адамара снова в матрицу Адамара:
1) перестановка строк (или столбцов);
2) умножение строки (или столбца) на —1.
С помощью этих операций любую матрицу Адамара можно преобразовать в так называемую нормализованную матрицу Адамара, у которой первая строка и первый столбец состоят из одних единиц.
3. Докажем, что если H — матрица Адамара порядка п>2, то п кратно 4.
,109 Действительно, можно считать матрицу H нормализованной матрицей Адамара. Переставляя ее столбцы, всегда можно добиться* Чтобы первые три строки матрицы имели вид:
11.,.1 1 1 . , . 1 11... 1 1 1 ... 1 11.,,1 1 1 . . . 1 -1 —1 ... —1 —1 —1 ... -1 1 j . . . і _1 _1 . . . _1 1 1 . . . 1 —1 —1 . . . —I
Получается четыре типа столбцов. Пусть i, /, k, I означают соответственно число столбцов первого, второго, третьего и четвертого типов. Свойство ортогональности строк влечет тогда также равенства:
i+j—k—l= О, і—/+ft—/=0, i—j—k+l= 0.
Кроме того,
l+i+k+t=n.
Из этих равенств получаем I=j = k = l = ^, откуда и следует наше утверждение.
4. Изложим еще один метод построения матрицы Адамара — метод Пэли. Рассмотрим поле вычетов по модулю р, где р — простое число. Всякий элемент Ър, являющийся квадратом какого-либо элемента того же поля, называется квадратичным вычетом, всякий другой квадратичным невычетом. Определим на следующую функцию Х(0> называемую символом Лежандра *):
( 0, если ( = 0; X (')=] I, если і — квадратичный вычет;
—1, если/—квадратичный невычет.
Исходя из этого определения, можно доказать, что для всякого сф0 выполняется равенство
X (!) * (Т+7) + х (2) X (2+7)+... + х (^ЇЇх (J=~\+o)=-1. (3)
Рассмотрим теперь квадратную матрицу Q порядка р, элементы к оторой qij (і, /=1,2.....р) определяются следующим образом:
QiJ = X (Г—O-
Пусть E — единичная матрица порядка р, a J — квадратная матрица того же порядка, все элементы которой равны 1. Тогда, пользуясь (3), можно доказать равенства
QQT=PE-J1 QJ = JQ=O. (4)
*) Адриен Мари Лежандр (1752—1833) — французский математик, плодотворно работавший в теории чисел и в ряде разделов математического анализа и механики.
ЦО Пусть теперь р= Ak—1. В этом случае матрица
1 ...П
H =
и
является матрицей Адамара порядка р-\-1. Действительно, вычисляя
произведение HHj , получаем:
•р+\ 0 - 0
О
HHt-
0
Далее, как нетрудно проверить, матрица Q порядка р=4А—1 совпадает > с матрицей -Qt . Отсюда с учетом (4) имеем:
j+(g-?)(gT-?)=y+ggT-g-gT+?=
^J+pE-J-q+Q+E=(p+ і) Е.
Таким образом, HH^ = {р+\)Е.
5. В качестве примера построим матрицу Адамара порядка 8, При этом р= 7. Функция x(i) задается следующей таблицей:
О Г 2 3 4 5 6
X (О
О 1 1
Матрицы QnH имеют тогда вид: О 1 1 1
0
Q= 1 -1 -1 — 1
1
— 1
H =
-1 1
-1
1 — 1
0
1 о -1 —1 OJ
6. Построить методом Пэли матрицу Адамара порядка 12 и найти соответствующие коды Адамара,
,111 21. ЗАДАЧА ОБ ОЖЕРЕЛЬЯХ, ФУНКЦИЯ МЁБИУСА И СИНХРОНИЗИРУЕМЫЕ КОДЫ
Некоторые вопросы теории кодирования связаны с известной комбинаторной задачей, называемой «задачей об ожерельях». Эту задачу можно сформулировать следующим образом.
Пусть ожерелье состоит из бусинок нескольких цветов. Спрашивается, сколько существует различных ожерелий, если задано число бусинок каждого цвета.
Расположим п бусинок по окружности, указав для каждой бусинки номер ее цвета. Если обойти эту окружность в определенном направлении, начав с некоторой бусинки, то ожерелью из п бусинок будет сопоставлено СЛОВО (fli Яг- . -а„), где я,-есть номер цвета t'-й бусинки. Но обход можно начать с любой бусинки, поэтому любому ожерелью соответствует п слов, получаемых одно из другого циклическими сдвигами. Например, для ожерелья, представленного на рисунке, получаем следующие слова: 12213, 31221, 13122, 21312, 22131.
Вообще говоря, среди п слов, сопоставленных ожерелью, могут быть и одинаковые. Нас, однако, будут интересовать не все ожерелья, а только такие, которые нельзя составить из, двух или более одинаковых «кусков». Таким ожерельям отвечают слова, которые нельзя составить из нескольких одинаковых слов меньшей длины. Будем называть подобные слова основными. Например, слова 11, 100100100 не являются основными, а слово 1011 —основное. Ясно, что каждому «несоставному» ожерелью отвечает п различных основных слов.
Чтобы указать удобную формулу для числа основных слов, нам потребуется так называемая функция Мёбиуса *),
*) Август Фердинанд Мёбиус (1790—1868) —: немецкий математик и астроном, известный, главным образом, своими работами по проективной геометрии. Им были впервые систематически изучены свойства функции ц(п),
,112 определяемая следующим образом:
( 1 , если п =1;
J (—1)*, если п — произведение k различных простых чисел;
[ 0 в остальных случаях.
