19551

Строение матрицы Адамара

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

2 Лекция 20. Строение матрицы Адамара Элементы матрицы можно вычислить непосредственно. Нумерацию строк и столбцов начнем с 0. В этом случае номер строки или столбца задается двоичным вектором: . Положим . Предложение. Элемент матрицы . Доказательство. Для ...

Русский

2013-07-12

448.32 KB

8 чел.

2

Лекция 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). Сравнивая коды Грея обоих чисел, убедимся, что они различаются лишь в одной позиции.

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

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

Это и означает указанную симметрию таблицы.


 

А также другие работы, которые могут Вас заинтересовать

60061. Київська Русь 62 KB
  Великим племенем венедами нас звали Між Дніпром і Віслою ми проживали Житла з дерева ми будували Стіни з хмизу виплітали Ще й обмазували глиною щоб тепліша була хата.
60062. Урок – свято «Загадки осені» 35 KB
  Вчитель: У нас сьогодні свято зібралося гостей багато але яке ж це свято Загадка: Жовте листячко летить Під ногами шелестить Сонце вже не припікає Коли дітки це буває Восени 1й учень: Осінь червона в гості іде Щедрі дарунки...
60063. Загадки про птахів 40.5 KB
  Сизокрилий добрий птах Знається він на листах Голуб Вдень вона лягає спатиБо всю ніч їй знов літати Ловить мишок гризунів З нею їм вже не до снів Сова Як зима вона на гілці І співа мов на сопілці.
60064. Свято Купала. Загальнотабірний захід 78 KB
  Дія відбувається на природі. Дівчата та хлопці вбрані в національні українські костюми; на «відьмі» - чорний плащ з каптуром, мітла. На сцену виходить ведучий-вихователь.
60065. Сценарий посвящен Дню Победы 28.5 KB
  Вот и наступил долгожданный День Победы! 9 Мая—светлый и радостный праздник. 68 лет назад в этот день закончилась война с немецким фашизмом. Мы с благодарностью вспоминаем наших воинов, защитников, отстоявших мир в жестокой битве.
60066. Їжачок-хитрячок і лісова школа 50 KB
  Мета. Учити дітей співвідносити кількість предметів із цифрами, розуміти і правильно використовувати слова та вирази: порівну, більше на один, менше на один; виділяти загальні ознаки предметів...
60068. Вечорниці-фантазії “На Андрія робиться дівицям надія” 32 KB
  Заходять дівчата1 ДІВЧИНА: Дівчата не роздягайтеся.2 ДІВЧИНА: Чого причепились Не смішіть не заважайте ідіть геть2 ХЛОПЕЦЬ: Макітру вареників на стіл підемо 1 ДІВЧИНА: Та вже будуть вам вареники їжте хоч лусніть тільки воду дайте донести...
60069. Ранок: «Зимонька – зима» 41 KB
  Вгадайте хто це зима Прийшла до нас бабуся У білому кожусі Поля причепурила Сріблястим снігом вкрила. Зима Прийшла зима біловолоса Неначе білим полотном Блискучим снігом одяглося Село і поле за селом.