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

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

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

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


 

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

47866. Організаційна структура та бюджетні повноваження Державного казначейства України. Функції Державного казначейства України 72 KB
  Саме останні дають нам можливість оцінити якість дії Державного казначейства а також його завдання та обовязки які повязані з його діяльністю. Більше того через функції визначається сутність та основна мета діяльності певного об'єкта в нашому випадку Державного казначейства. На Державне казначейство в Україні покладено виконання таких функцій: здійснення касового виконання державного бюджету та бюджетів самоврядування за доходами та видатками; здійснення контролю за цільовим спрямуванням бюджетних коштів на стадії проведення...
47867. Предмет і метод політичної економіки 1.86 MB
  Сукупність економічних відносин між людьми у сфері виробництва розподілу обміну і споживання продукції що утворюють певну економічну систему. Юм Фізіократи 1718 ст питання походження багатства перенесено із сфери обігу в сферу виробництва. Основні риси виробництва Стадії суспільного виробництва Основні елементи процесу виробництва Праця це свідома доцільна діяльність людини яка спрямована на створення тих чи інших благ з метою задоволення потреб.
47868. Проектний аналіз 1.67 MB
  Він дає інформаційну базу у вигляді проекту як спеціально оформленого інвестиційного плану чи результатів проведеної експертизи проекту для ухвалення рішення щодо включення проекту в інвестиційний портфель підприємства початку його інвестування постійного моніторингу реалізації. Аналіз інвестиційних проектів це комплекс методичних та практичних прийомів розробки обґрунтування й оцінки доцільності реалізації проекту. Більшість проектів що виявилися збитковими могла бути не допущена до реалізації за умови якісного попереднього аналізу з...
47869. Міжнародна економіка. Конспект лекцій 905.5 KB
  Конспект лекцій містить зміст лекційного курсу, завдання до самостійного вивчення теоретичного матеріалу курсу, що вивчається в позааудиторний час, список рекомендованої літератури і ресурсів Інтернет, ілюстративний матеріал до лекцій
47870. Многочлени. Властивості многочленів 5.51 MB
  Ділення многочлена на лінійний двочлен. Розклад многочлена за степенями лінійного двочлена. Означення многочлена Вираз виду: Повністю визначається коефіцієнтами. Многочленомполіномомвід однієї змінної над областю цілісності К називається вираз виду 3 де довільне ціле невідємне число елементи К а деякі символи; називається степенем змінної або невідомого а м коефіцієнтом многочлена 3 або коефіцієнтом при .
47871. Основи геометрії 63.5 KB
  Історичний нарис обґрунтування геометрії Предмет основ геометрії. Відкриття неевклідової геометрії.
47872. Основи державного регулювання економіки 303 KB
  Обєктивна необхідність і теоретичні основи державного регулювання економіки. Моделі державного регулювання економіки в зарубіжних країнах. Таким чином метою державного регулювання економіки є досягнення ефективного поступального та стабільного економічного соціального наукового розвитку України.
47873. МЕТОДИ НАВЧАННЯ 393.5 KB
  Методи цієї групи насамперед характеризують логіку руху змісту навчального матеріалу – від конкретного до загального, від загального до конкретного, за аналогією. Залежно від того, як логічно побудований зміст, виділяють індуктивний, дедуктивний, традуктивний, аналітичний і синтетичний методи навчання
47874. Зміст категорії ефективність управління 136.5 KB
  Зміст категорії €œефективність управління Результативність управління розуміється як його цільова спрямованість на створення потрібних корисних речей здатних задовольняти певні потреби забезпечити досягнення кінцевих результатів адекватних поставленим цілям управління.