20 Матрицы Адамара (Конспект лекций по ЦОС)
Описание файла
Файл "20 Матрицы Адамара" внутри архива находится в папке "Конспект лекций по ЦОС". Документ из архива "Конспект лекций по ЦОС", который расположен в категории "". Всё это находится в предмете "цифровая обработка сигналов (цос)" из 8 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "цифровая обработка сигналов" в общих файлах.
Онлайн просмотр документа "20 Матрицы Адамара"
Текст из документа "20 Матрицы Адамара"
3
Лекция 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). Сравнивая коды Грея обоих чисел, убедимся, что они различаются лишь в одной позиции.
Переход от обычного кода к коду Грея и обратно можно выразить с помощью линейного преобразования над полем : , а . У этой матрицы есть обратная .
Последовательные числа, закодированные кодом Грея, также обладают определенной симметрией: таблица для представляется в виде, указанном на рисунке. При этом направление стрелок означает зеркальную симметрию соответствующих частей кода Докажем это. Для справедливость проверяется непосредственно. Таблицу закодированных чисел, используя выражения для , представим в виде, представленном на рисунке. Используя предположении индукции и правило построения кода, получим