Брейсуэлл Р. - Преобразование Хартли (теория и приложения), страница 16

Тогда 1 будет функцией величин г' и Ж, что можно записать в виде 7'=Рай Таблица 7.! Перссганоаочные воследонательностн длн разных значонаа М К 256 К=256 К=64 Х 128 К = 128 К= 128 К = 128 К=В К=16 К=32 К=64 ! 36 9 41 25 Ь7 ! 18 82 $0 114 3 0 0 16 8 24 ! у О О 8 4 12 40 5 37 21 53 13 45 29 61 40 1О 74 42 108 26 90 58 122 4 4 20 12 28 4 2 10 6 14 8 8 72 40 Ю4 24 88 56 120 80 Ь 69 37 101 21 85 53 1П 112 7 71 39 !03 23 87 55 119 8 16 144 80 208 48 176 112 240 8 4 36 20 52 !2 44 28 60 40 20 148 84 2!2 52 180 116 244 8 2 18 10 26 8 1 9 Ь 13 48 3 35 19 51 11 43 27 59 48 6 70 38 102 22 86 54 118 12 6 22 14 30 12 3 11 7 15 16 4 68 ЗВ 100 20 84 Ь2 ИВ 16 2 34 18 50 10 42 26 58 88 13 77 45 109 29 93 61 125 120 15 79 47 111 31 95 63 127 48 12 140 76 204 44 172 108 236 ! 0 0 1 ! 16 1 17 9 25 56 7 39 23 55 15 47 31 83 56 14 78 46 110 30 94 62 )20 Ь 2! 13 29 24 12 76 44 108 28 92 60 124 24 6 38 22 54 14 48 30 62 ! у 0 0 1 2 2 1 3 3 96 3 67 35 99 19 83 51 115 56 28 156 92 220 60 188 124 252 24 3 19 11 27 84 1 6Ь ЗЗ 97 17 81 49 113 7 23 15 31 32 2 86 34 98 32 1 33 П 49 На рис.

7.3 иллюстрируется характер изменения этой функции для разных К. Эти графы напоминают статистические диаграммы рассеяния с отсутствием явной зависимости 7' от Ь В действительности коэффициент корреляции в каждом случае равен нулю, однако направление связи между ! и 7' является строго детерминированным. На диаграммах рис. 7.3 направление отсчета величины у совпадает с положительным направлением оси ординат декартовой системы координат, т.е.

отсчет 7' осуществляется по вертикали снизу вверх. Однако последовательный отсчет строк матрицы (рис. 7.2) выполняется, как это принято в европейской письменности, сверху вниз; 80 81 6-)236 ! 0 0 4 2 2 В 4 1 5 В 3 7 з у 0 0 32 1В 48 8 40 24 Ьа 4 0 0 84 32 96 16 80 48 112 ! у 72 9 73 41 !05 25 89 57 121 3 ! !04 1! 75 43 107 27 91 59 123 з у О, О 128 64 192 32 160 96 224 16 8 136 72 200 40 168 104 232 88 24 24 152 88 216 56 184 120 248 у 32 4 132 68 198 36 184 100 228 Ы~Х Рв Параметр Семейство ! Семейство П Пояазвтсвь степени Р Количество атомов в ячейке Количество ячеек, С Швг решетки в ячейке, 1г'в Количество ячеек вдоль одной координаты, Жс Размер ячейки, гз//Фс Четный Нсч тный 4 М/4 /М/4 /М/4 Рга 83 82 Рис. 7.3. Псрсстановочные диаграммы вида/ = Рлбг) для возрастающих зна- чений М. Квящвя последующая диаграмма имеет масштаб, уменьшенный в 2 раза по сравнению с предыдущей диаграммой, находящейся слева от нес.

следовательно, перестановочные диаграммы оказываются пЕреверну- тыми сверху вниз по отношению к перестановочным матрицам, приведенным ниже. В табл. 7.1 в качестве справочного материала приводится ряд перестановочных последовательностей. Перестаноночнаи матрица Теперь может быть определена перестановочная матрица как матрица размера М х М, единичные элементы которой имеют координаты (1,/) = [1, Р Щ, а на остальных позициях располагаются нули. Таким образом: Ячеистая структура перестановочной диаграммы Если проанализировать диаграммы, представленные на рис. 7.3,или данные табл. 7.1, то обнаружится нх повторяющийся характер, что иллюстрируется на рис. 7.4.

Выполняя разбиение перестановочиой диаграммы для М = 32 на четыре ромбовидные ячейки и соединяя между собой атомы в пределах каждой ячейки, чтобы подчеркнуть форму соответствующих фигур, обнаруживаем наличие кристаллической структуры, периодически повторяющейся на непрямоугольном базисе в обоих направлениях. Интересно отметить, что контур фигуры в каждой ячейке повторяет по форме перестановочную диаграмму для М = 8, но по сравнению с последней имеет в два раза больший масштаб. Теперь если масштаб полной диаграммы для М = 32 увеличить в два раза, то получим периодически повторяющуюся структуру, соответствующую диаграмме, для которой й1 = 128.

Для нечетных показателей степени Р1/1 = 8, 32, 128,...) имеем одно семейство диаграмм, а для четных Р (г/ = 4, 16, 64,...) — другое семейство. Данная топология совсем не является очевидной из определения алгоритма, иллюстрируемого на рис. 7.2, но проявляется в явном виде в случае, когда мы располагаем информацией о числе перестановочных матриц с целью соответствующей проверки. Очевидно, имеются два семейства ячеек; семейство 1 включает в себя ячейки, содержащие по четыре атома, в совокупности образующие фигуру, напоминающую бумажного змея, тогда как семейство П состоит из ячеек, содержащих восемь атомов, расположенных в форме лягушки.

Легко убедиться в правомерности следующих характеристик: Хотя диаграммы обоих типов, соответствующие этим двум семействам, в явном виде иллюстрируют наличие ячеистой конфигурапии периодического характера, структура, получаемая при замене каждой ячейки точкой, не является достаточно регулярной и должна быть подвергнута исследованию. На перестаиовочной диаграмме для М = 128 отметим нижние левые элементы каждой из ячеек.

Легко убедиться в том, что координаты р-го элемента в шй строке при /Ч = 128 есть С„, = соз 2ли/2*, К„, = сая 2пи/2*. с, с, Сз К< зз Сз 1 Яз Кз с, с, Сзо дзо сн зн Ки дзз с„ с дн 1 ян С!5 Рис. 7.4. При 1Ч = 32 перестановочная диаграмма подобна кристаллической решетке с четырьмя ячейками, каждая из которых состоит из восьми атомов. х, = 4р + Р (ч), у„„= 4ч + Рз (р). Коэффициент 4 обусловлен тем, что зпаг решетки атомов в пределах одной ячейки равен х„з 1 „— х„, = 4. Подстрочный индекс 4 означает число ячеек вдоль одной оси координат. Так как общее количество атомов равно зЧ, а в ячейке содержится 4 или 8 атомов, то полное число ячеек составляет С = Ж/(4 или 8), а число ячеек вдоль одной осн координат Хо есть корень квадратный из этой величины: ж = зф зз и~д~ з ззЗ Шаг решетки в пределах одной ячейки равен «ширине» этой ячейки )Ч/)Че, деленной на число содержащихся в ней атомов (т.е.

на 4 или 8), и таким образом равен Мо, чем и обусловлено двукратное появление числа 4 в уравнениях для координат элементов ячеек. В общем случае имеем хз, = зЧо11 + Ря~ (ч) У», = зЧеч + Р» 11з)' Описанная здесь топологическая струзстура является основой алгоритма быстрой перестановки ГАБТРЕйМ()ТЕ, рассматриваемого ниже. Медленная перестановка, которая является традиционной, выполняется следующим образом. Для определения / при заданных 1 и А1 осуществляются двоичное представление с использованием Р двоичных разрядов, а затем запись элементов полученного числа в обратном порядке их следования и возвращение к десятичному представлению этого числа. Например, нам известно, что для )Ч = 16 имеем: Ров (7) = 14.

Двоичным представлением числа з = 7 является 0111, а числа 14--1110. Удобный способ выполнения перестановки путем изменения порядка следования двоичных символов на обратный в случае, когда краткость записи более предпочтительна, чем скорость реализации 84 этой процедуры, в формализованном представлении имеет вид 4Е)0 Щ = ОТВ 8 (П 4010 1 = ВТО(ВЕЧЗ(1)3 [17 — Р, 161)).

Функция 1)ТВ5 ( ) преобразует ее десятичный аргумент в двоичное число, состоящее из 16 цифр; функция зхЕЧЗ ( ) осуществляет измене- ние порядка следования этих цифр, составляющих аргумент данной функции, на обратный, а процедура ВТО( ) обеспечивает преобра- зование полученного таким образом двоичного числа в десятичное. Каскадные матрицы После процедуры перестановки выполняется последовательность Р операций,поэтапная реализация которых приводит к окончательному преобразованию. Номера этапов (тактов), которые будем обозначать символом я, изменяются от 1 до Р. Общая форма представления операторов Ь, наиболее наглядно может быть проиллюстрирована в случае /з/ = 16 путем реализации последнего оператора Е в качестве первого действия.

Примем следующие условные обозначения для функций вш(), соя () и сан() аргумента, кратного 2я/2*: Я„, = взп 2я л/2*, С использованием этих обозначений четвертая каскадная матрица Ь будет иметь вид 1 1 1 1 ! -1 1 -1 ! 1 ! 1 1 -1 ! -1 ! 1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 с. с, Яю Къ с. с. с, я! Кф с. 1 Яе с, с, Я~ К! с, 1 Яз с, с. я! Ке Ст 1 Яу С„з — — соз 2я л/8. 1'!' = 32. 86 87 В выражении для данной матрицы опущен индекс ж всегда равный з = 4, поэтому вместо С.

= соз 2кл(16 присутствует величина С„и т. п. В каждой строке приведенной матрицы имеются три ненулевых элемента, а это означает, что в выражение для каждого элемента результирующей последовательности войдут с соответствующими коэффициентами три элемента операнда, т. е. три элемента исходной последовательности, к которой применяется оператор. Косинусные и единичные элементы матрицы размещены вдоль линий, параллельных ее главной диагонали, а синусные элементы имеют другой тип расположения.

В результате независимые переменные в виде элементов операнда после их умножения на синусные коэффициенты Я„йзменяют порядок следования на обратный и размещаются в порядке убывания их номеров от л до 1. Это свойство называется возвратной индексацией. Матрица ! з состоит из двух нулевых квадрантов и двух квадрантов, структуры которых аналогичны матрице Ьч, но в отличие от последней имеют меньшие размеры. Тем не менее и здесь обнаруживается эффект возвратной ин- дексации В матрице ! з в силу того, что индекс «3» опущен, используется сокращенное обозначение С„вместо Матрицы Е, и Е„реализующие более ранние этапы выполнения процедуры преобразования, имеют подобную структуру Так как С„= соз 2ял/4 и 5„1 = зш 2ял/4 могут принимать только значения — 1, 0 и 1, конфигурапия матрнць! Ез в явном виде не отражает характерных черт структуры общего вида для матриц ! „ хотя определенное соответствие и имеется; то же самое справедливо н для матрицы Ь!.

Для того чтобы показать, каким образом видоизменяются зти матрицы при увеличении Ж, примем о -1 1 1 1 Н = Ч ° = 2'4 2 2 В2 1'2 Р261~ -1 1 -1 1 о 1 -! 1 -1 1 -1 1 -1 1 1 1 88 Тогда матрица 1.4 будет состоять из двух нулевых квадрантов и двух квадрантов, каждый из которых идентичен матрице 1.4, полученной для случая М = 16. Новая матрица Ьз, как н следовало ожццать, получается из Ь4 путем симметричного «растягивания» этой матрицы. Резюмируя случай 1!! = 16, отметим, что ДПХ получается из исходной последовательности 1 с помощью соотношения где матрица дискретного преобразования Хартли Ч', сводимая к представлению в виде произведения сомножителей, равна 1'4 1 3 1 2 1 2 Р16 ' В общем случае для любого )!! = 2Р имеем 1 Р~Р— 2' ~ 2~ 1РН' Переход к дискретному преобразованию Фурье Наконец, переход от ДПХ к ДПФ представляет собой задачу установления соотношений между четной и нечетной компонентами ДПХ и вещественной и мнимой компонентами ДПФ.