Лекция 20. Строение матрицы Адамара
Элементы матрицы можно вычислить непосредственно. Нумерацию строк и столбцов начнем с 0. В этом случае номер строки или столбца задается двоичным вектором: . Положим .
Предложение. Элемент матрицы .
Доказательство. Для утверждение очевидно. Рассмотрим , где каждый блок есть матрица Адамара меньшего порядка. Если элемент находится в блоке , то и по предположению индукции формула верна. Если элемент находится в блоке , то . Однако . Если же элемент находится в блоке , то и .
Данное предложение позволяет при работе с матрицами высокого порядка генерировать элементы матрицы, а не хранить их в памяти.
Код Грея.
Ниже будет показана связь матриц Адамара со специальным способом кодирования целых чисел. Выберем натуральное и выпишем в виде таблицы двоичные представления всех чисел от 0 до . Например, для
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1


Обратим внимание на два обстоятельства. Таблица обладает симметрией, которую можно описать следующим образом. Таблица для состоит из двух экземпляров таблицы для , что подчеркнуто наличием стрелок , при этом в первом экземпляре добавлена нулевая строка, а во втором - единичная. Другой момент заключается в том, что соседние столбцы могут различаться более чем в одном разряде. Последнее обстоятельство препятствует использованию данной кодировки в асинхронных цифровых схемах. В этой связи возникла задача придумать такую кодировку целых чисел, чтобы два стоящих рядом числа различались лишь в одной позиции. Наиболее популярной является кодировка под названием код Грея. Если число имеет двоичное представление , то код Грея для него имеет вид , где , а , , а знак означает суммирование по модулю 2.
Предложение. В коде Грея коды соседних чисел различаются лишь в одном разряде.
Доказательство. Рассмотрим двоичные представления двух соседних чисел: и . . Число , где серия из единиц может быть и пустой, но 0 обязательно присутствует. В этом случае (серия из 1 заменилась серией той же длины из 0, а 0 заменился на 1). Сравнивая коды Грея обоих чисел, убедимся, что они различаются лишь в одной позиции.
Переход от обычного кода к коду Грея и обратно можно выразить с помощью линейного преобразования над полем : , а . У этой матрицы есть обратная .


Последовательные числа, закодированные кодом Грея, также обладают определенной симметрией: таблица для представляется в виде, указанном на рисунке. При этом направление стрелок означает зеркальную симметрию соответствующих частей кода Докажем это. Для справедливость проверяется непосредственно. Таблицу закодированных чисел, используя выражения для , представим в виде, представленном на рисунке. Используя предположении индукции и правило построения кода, получим
Это и означает указанную симметрию таблицы.