Брейсуэлл Р. - Преобразование Хартли (теория и приложения) (1044117), страница 15
Текст из файла (страница 15)
Теорема о модуляции. Объяснить, почему теоремы о модуляции полностью идентичны как для преобразования Хартли, так и для преобразования Фурье. 6.6. Функция, имеющая форму дама иэ гофрированного железа. Показать, что функция (аз — хз)цэ П (х/2а) П (у/4а) имеет преобразование Хартли вида (а~/2х) а, (2ках) ппс4ае. 6.7. Сдвиг чвнщай функции. При условии, что) (х, у) является четной функцией относительно х и у, показать, что функция /(х — а, у — Ь) имеет преобразование Хартли сав [2к(аи+ Ьи)] И(и, с). 6.8. Пары яреабраэаваянй.
Убедиться в справедливости соотношений, приведенных в табл. 6.1. 6.9. Элементарные преобразования. Получить дискретные преобразования Хартли следующих функций, представляющих собой матрицы с единственным единичным элементом, и объяснить характер каждого из этих преобразонаний; 6.10. Даяаянвние нулями. При условии что дискретное преобразование Хартли (ДПХ) двумерной последовательности Э! равно ![ д~ Ь найти ДПХ матрицы 6.11.
Днфракция на и!ели. С целью получения некоторого подобия дифракционной картины на щели, а затем, возможно, и на других апертурах рассмотрим преобразования двух цифровых изображений квадратной формы: одно из них (т.е. соответствующая матрица) содержит единственный единичный элемент в левом нижнем углу, а все остальные элементы равны нулю, а другое изображение имеет элементы, равные единице, вдоль главной диагонали и нулевые иедиагональные элементы. а) Определить преобразования этих изображений для )ц, = Мз = 4 и получить результаты для изображений больших размеров.
б) Идентичны ли при этом ДПХ и ДПФ? в) Согласуютск ли полученные результаты с условиями теоремы о вращении для непрерывных переменных? 6.12. Выбор начала отсчета. Начало отсчета цифрового изображения выбирается в его левом нижнем углу, как в декартовой системе координат, а не в левом верхнем углу, что является общепринятым для матриц. Программист утверждает, что это никоим образом не повлияет на результат преобразования Хартли. за исключением того, разумеется, что преобразование будет перевернутым, т.
е. его первая строка оказывается последней, последняя-первой и т.п. Справедливо ли подобнос заявление программиста? 6.13. Чвтырехэяемеятиые коэффициенты, а) Табулировать 4 чегырехэлементных двумерных образа саз [2к(т,т,/2 + + тзтз/2)] в т-области для всех т, и ты убедившись в том, что выполняются принятые допущения относительно строк и столбцов соответствующей матрицы.
Га Ь] б) Отсюда цоказатзч что матРица [ имеет двумерное ДПХ с и 6.!4. Васьмиэяементные коэффициенты. Сформировать шестнадцать 16-эчемснтных образов саз [2к (т,т114 4- т тг14)] в т-области. 6,15. Специальное ирсобразование. Было предложено новое преобразование, определяемое соотношением 1](и, а) = ] ] [(х, у) саз(2ких) саз(2кеу)дхду. Показать, что если ланное преобразование дважды примени!в к веще- ственной функции, то вновь получается исходная функция. Проверить это для нескольких случаев в численной форме и установить, каким образом это преобразование связано с преобразованием Хартли. Глава 7 ФАКТОРИЗАЦИЯ МАТРИЦЫ ПРЕОБРАЗОВАНИЯ И вставь в него оправленные камни в четыре ряда.
Рядом: рубин, топаз, изумруд — один ркд. Второй рлд: карбункул, сапфир н алмаз. Третий рлд: яхонт, агат и аметист. Четвертый рдд: хрвзолвт, оникс н коппс. В золотых гнездах должны быть вставлены онн. Библия, Вторая книга Моисеева; Исход, глава го Матричное представление дискретного оператора Для усвоения излагаемого материала не требуется обширных познаний из области матричной алгебры, так как единственной операцией, используемой ниже, является умножение матрицы на вектор-столбец. При этом результатом является другой вектор-столбец, г-й элемент которого равен сумме произведений элементов г-й строки квадратной матрицы на элементы исходного вектор-столбца.
Таким образом, авенство справедливо р а Ьсс/ е/дЬ с //с/ га л о р А аА + ЬВ + сС + с/)л В еА +/В + дС+ Ь)г С сА + /В + /сС + /В с! гпА + пВ+ оС+р0 Если раскрыть знак суммы в формуле дискретного преобразования, то получится М отдельных равенств. Так, для случая М = 4 76 Один из подходов к рассмотрению операции суммирования, определяющей значение дискретного преобразования Хартли, заключается в приведении квадратной матрицы к М-мерному вектору.
Ниже будет развит именно этот подход, так как он ведет к пониманию основ формирования быстрого алгоритма. Каждый элемент матрицы соответствует одному этапу реализации алгоритма, или его подпрограмме. Матричный подход проясняет операцию перестановки, когда сложная матрица может рассматриваться просто в виде графа (или диаграммы рассеяния), устанавливающего соответствие между выходным и входным индексами. Процедура перехода от преобразования Хартли к преобразованию Фурье к тому же может быть выражена с помощью матричного умножения, так как факторизация матрицы преобразования Хартли непосредственно ведет к новой факторизации матрицы преобразования Фурье; именно этой характерной особенностью обусловлена важность настоящей главы.
' ДПФ, соответствующее формуле я — с р(и) = М ' 2,' /'(т)ехр [ — с2яот/М1, х о будет иметь вид р (О) = /4 [/(О) + /(1) +„/(2) +/ (3)~ Р (1) = '/4 (/ (О) +/ (1) ехр [ — с2к/МЗ +/ (2) ехр [ — с 2сс 2/МЗ + + /'(3) ехр [ — с 2п 3/МД ), р (2) = '/4 (/(0) + /'(1) ехр [ — с 2л 2/МД +/'(2) ехр [ — с 2к4/М) + + /'(3) ехр [ — с 2я б/М) ), р (3) = '/л (/ (О) +/(1) ехр [ — /2к 3/МД +/(2) ехр [ — /2п б/МД + +/:(3) ехр [ — !2к9/МЗ). Такая система уравнений может быть выражена через матричное ' умножение, связывающее входной 4-мерный вектор вида [/(О) /'(1) /'(2) /'(3) ) с' выходным вектором (г (0) Р(!) Р(2) е (3)).
Изящный способ компактного представления матричного уравнения, поясняемый ниже, предполагает использование обозначения Иг= ехр [ — с 2я/МЗ, что оправдано наличием экспоненциального множителя ехр [ — с'2л/МЗ в большинстве слагаемых; там, где этот множитель о отсутствует, можно предположить существование множителя И', равного единице. В матричном представлении приведенные уравнения сводятся к одному уравнению Р(О 1 1 1 1 /'[О г (1 1 И' И" И' /'(1 р(2 = 1 Игг Ига Р (3 1 Ига Игв Иг /'(3 Квадратная матрица представляет собой оператор„ преобразующий последовательность Т() в последовательность преобразования Фурье , е (). Используя буквы, набранные жирным шрифтом, для обозначения матриц, можем записать (опуская величину М ' в соответствии с разделом «коэффициент М с» гл.
5): К=%Т, где 1 — вектор-столбец с элементами /(0), /(1), ..., /(М вЂ” 1); Š— вектор-столбец с элементами Р (0), г" (1), ..., Р (М вЂ” 1) и 77 1 1 1 Игз ! И'"" И" Иг!и-з)г Иг)п — зкл'-з) Иг)л'-ц!и-з) Иг)п-зкп-з) !П-з)г И, )и-г))п-з) Иг)л-ц)л -з) !Р)п-зкп-Ц Иг)п-!)' Интересным свойством матрицы %' является возможность ее факторизации с помощью метода, который приводит к алгоритму быстрого преобразования Фурье (БПФ). Факторизация матрицы Ч' в виде Ч' = ЬгЬг,...ЬзЬзЬ,Рп приводит к новому своеобразному быстрому алгоритму вычисления матрицы Н дискретного преобразования Хартли.
Наименьшее значение 7ч', для которого можно пояснить суть процедуры факторизации, равно 16, когда имеется пять матричных коэффициентов и постоянный коэффициент и '. Если и = 2", то число этих матричных коэффициентов равно Р + 1, Первый матричный коэффициент, который в порядке очередности первым осуществляет отображение последовательности Ь является оператором перестановки.
Последующие Р операторов Ь, могут быть названы каскадными матрицами. Если 1з' = 16, то Р = 4, т. е, имеются четыре каскадные матрицы, если 1п = 32, то нх число равно 5 и т.д. Перестановка Перестановка-.это изменение порядка следования элементов исходной матрицы Г и может быть образно названо идеальным тасованием. Колоду карт можно перетасовать, разделив ее пополам так, чтобы одна половина входила в другую.
Если каждая карта одной половины Ряс. 7.1. Идеальное тасоваяве. 78 Аналогично существует другая матрица Ч', преобразующая исходную последовательность Г в последовательность дискретного преобразования Хартли Н=Чгй в с о Е Р о с е о М -М 1 с -с о —:= ~о и о о о 1 в в в l о г К Е г г ! и и Ьг М l и О и l. и о — Ео г.— ~ и Р Р Р Р Рис. 7.2. Направленный граф, яляюстряруюшяй операцию перестановки.
колоды размещается между картами другой половины, то имеем идеальное тасование (рис. 7.1). Аналогичную терминологию можно применить и к последовательностям: мы утверждаем, что переход от последовательности )а Ь с г1 е7 д Ь) к последовательности 1а е Ь 7 с д аг Ь) представляет собой процедуру идеального тасования (перемешивания). Инверсный переход от )а Ь с г1 е7д Ь) к (а с е д Ь г1 7'Ь) является операцией инверсного перемешивания.
Перестановка последовательности из )з' элементов включает в себя следующие этапы: 1) инверсное перемешивание всей исходной последовательности, 2) инверсное перемешивание каждой половины полученной на первом этапе последовательности, 3) инверсное перемешивание каждой четверти, полученной на втором этапе и так далее до тех пор, пока не сформируются группы из 4 элементов. Данная операция завершается выполнением инверсного перемешивания этих «четвероюц С целью детального анализа операции перестановки для 16-элементной последовательности проиллюстрнруем выполнение трех последовательных перегруппировок строк: Исходная последовательность )аЬоао1дйг)Мотор) Первое церемешявание )аоод!)гтоьгд Ь1)пр) Второе перемешявавяе )аегтод1соЬ11паыр) Третье перемешввавяе )а1ето)гдоЬ7)пг11Ьр) В данном случае, для которого Р= 4, искомая перестановка реализуется в результате выполнения третьего перемешивания.
Другой способ представления этой операции, а именно с помощью направленного графа, иллюстрируется на рис. 73Ь Перестановочные диаграммы Предположим, что г-й элемент последовательности нз и = 2г элементов в результате операции перестановки становится 1зм элементом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
