Брейсуэлл Р. - Преобразование Хартли (теория и приложения) (1044117), страница 17
Текст из файла (страница 17)
Матричный оператор, удваиваюшнй четную составляющую дискретного преобразования Хартли, имеет вид 1 1 1 1 1 1 г 1 1 1 1 1 а оператор, удваиваюший нечетную компоненту, равен Умножая последнюю матрицу на — !и осуществляя сложение резуль- тата с первой матрицей, получим матрицу преобразования Ф !точнее 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факторизации матриц), с помощью соотношения Р = ФЬ,Ь,Ь,Ь,Р„Ь Так как Р = %Г, имеем ь!Ц = ФЬвЬзЬгЬ|Р!в.
Это выражение является новым факторизованным представлением матрицы преобразования % для ДПФ и является основой формирования быстрого алгоритма, рассматриваемого в следующей главе. Задачи 7.1. Фактаризацин для БПФ. Для случая Ж = 4 показать 1 Исвоо 0010 !Ой!0 7.2. П а рв браэаванис матрицы Ф. Получать матрицу преебразоаааня 16-эле- ДПФ в ДП ности Е ДПХ цри одной и той же исходной псследова тель- 7.3. ..
Пвследавательнасти коэффициентов. Оператор ЬвЬьЬьв! применяется к последовательности Г без предварительного выполнения опе становки. С ве пра длнво ли утверждение, что получающаяся при этом последовательность состоит нз истинных элем лемеатов прео разованна 6 Хартлн Н, но расположенных в другом порядке! 7.4. Диас (1Ц вЂ” 1)/2 = т. .. Д рамма рассеяния. а) Показать, что средюве значения (!) и (/) чевия (!) и (/) равны б) Оценить центральные моменты ((! — т)!) н (Π— яб'). в) Показагьь что коэффициент коРРелЯции ((!' — т)(/ — т)) Лла пепе- 1Ц > 1024.
становочной диаграммы рассеяния достаточно, !в/ мал, менее ь для 7.5. Перестановка на кольце. а) Изобразить 1Ц малых окружностей, равномерно расположенных вдоль окружности многа большего днам а. малой окружности к точке, угловое положение аметра. которой характеризуется азимутом 72я/81, где / = Рк(!) для всех !. Если 1 ~ !', то осуществить замещение для этой малой окру!кностн.
Выполнить данную процедуру лля Ж = 8, !6, 32 и 64. 6 7.6. О ) Сколько осей симметрии у полученной фигуры7 тносительнае число ясрестанавак. Путем подсчета колячества лнннй на кольцевой диаграмме предыдущей задачи нлн другим способом показать, что число операций перестановки (замещения), деленное на 1Ц, равно О 3 2 — !силь !цв! где 7Р(х) — целая часть х. Глава 8 АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ Минуя древа мололые, По грубой треснувшей земле Скакал он на коне галопом К подножию холма. И лишь внизу коню дал отдых И сам был цел н невредим. А.
Б. (Банджа) Питерсон. Человек са снежной Реки Мы убедились в том, что может быть определеяо вещественное дискретное преобразование по аналогии с дискретным преобразованием Фурье; теперь мы покажем, что имеется быстрый метод вычислений, аналогичный быстрому преобразованию Фурье. Как было показано выше при рассмотрении факторизации матрип, данная процедура представляет собой простой способ перехода от дискретного преобразования Хартли к дискретному преобразованию Фурье.
Следовательно, анализируемая ниже процедура быстрого преобразования также создает основу быстрого метода получения дискретного преобразования Фурье. Действительно, метод, предусматривающий переход от преобразования Хартли, оказывается предпочтительным, в основном в силу упрощения, обусловленного тем, что при обработке вещественных данных не требуются операции с комплексными величинами. Определяющие соотнопзения Когда раскрывается знак суммирования, фигурируннций в определении дискретного преобразования Хартли, мы получаем 1!/ равенств, в правой части каждого из которых имеется 1Ц слагаемых.
Четыре равенства, приведенные в предыдущей главе с целью иллюстрации сказанного, применительно к дискретному преобразованию Хартли и — ! Н(ц) = /!/ ' 2 /'(т)сав 2ццт)/Н .=е можно переписать в виде Н(0) = (1/4) 1/(О) +/(1) +/'(2) +/'(ЗЯ; Н (1) = (1/4) [/(0) + / (1) сав 2Я/Н +/ (2) сав 2Я2//ч' + /(3) саз 2Я3/д/3; Н(2) = (1/4) 17(0) +/'(!) сав 2п2//ь/ +/(2) сав 2я4//!/ +/'(3) сав 2яб/Н); Н (3) = (1/4) 1/(О) + / (1) саз 2я3/Ж + / (2) саз 2яб/г/ +/ (3) сав 2я9/1я !. Для /Ц = 2 имеем только два равенства Н(0) = (1/2) (/(О) +/(1Ц, Н(1) = (1/2) [~0) — /(1)3. 91 Можно рассчитать число операций умножения и сложения и исполь- зовать результаты этого расчета для оценки временных затрат, необходимых для вычисления всех Н значений преобразования.
Рис. 8.1. График функции у = саяк, по которому могут быть определены коэффициенты саз 2я/!Ч. Для В! = 4 используются символы йэ. Для случая Ф = 8 значения этих коэффициентов соответствуют точкам на графике, обозначенным символами Е и Сь Случай !9 = 16 в дополнение к этим символам обозначен простыми точками. При Ж = 4, выполняя подстановку численных значений саз, для четырех вышеприведенных равенств получим выражения Н(0) = (1/4) 17 (0) +/(1) +/'(2) + /(3)], Н (1) = (1/4) [/(О) +/'(1) — /'(2) — /'(3)], Н(2) = (1/4)[/'(О) -/'(1) +/'(2) †/'(3)], Н(3) = (1/4)(/'(0) — Я1) †/(2) + /'(3)].
В правильности значений соответствующих коэффициентов можно убедиться, анализируя график функции саз (рис. 8.1) и отмечая точки, равноудаленные друг от друга на четверть периода этой функции, крестиками в кружочке. При /5/ =- 8 соответствующие равенства для ДПХ, в чем можно убедиться нри анализе рис. 8.1, имеют вид Н(0) = (1/8) ЩО) +/(1) +/(2) +/(3) +/(4) +/(5) +/(6) +./(7)] Н(1) = (1/8) 1/(О) + /2Д1) + /'(2) + 0 †/'(4) — /2/'(5) †/'(6) — О], Н(2) = (1/8) 1/'(О) + /'(1) †/ (2) †/'(3) + /'(4) +/'(5) †/'(6) †/'(7)], Н(3) = (1/8)(/(О) + 0 — Я2) + /2/'(3) †/'(4) + 0 +/'(6) — /2/'(7)], Н(4) = (1/8) (/(0) — /'(1) +/(2) — /'(3) +/'(4) — /'(5) +Дб) — /'(7)], Н(5) = (1/8) [/'(О) — /2/(1) + /'(2) + 0 — /(4) + /2/(5) — /(6) + О], Н(6) = (1/8) ~/(0) †/'(1) †/'(2) + /'(3) +/'(4) †/'(5) -/'(6) '-/'(7)], Н(7) = (1/8) ЩО) + 0 †/'(2) — ,/2/'(3) †/'(4) + 0 +/'(6) + /2/'(7)].
92 Свойство Н 1о8 Н Пусть количество элементов Н в последовательности равно числу 2, возведенному в степень Р. Тогда Р = 1082Н. Построение графиков логарифмов по основанию 2 является непростой задачей, однако желательно иметь некоторое представление о величине 1о8 М, просто равной степени Р в равенстве М= 2е. Таблица 84 Значенва аелачан Р, Ф а 74Р 2 8 24 64 160 384 896 2048 4608 10 24О 22 528 49 152 106 496 229 376 491 520 1 046 6ТВ 2 228 224 4 718 592 9 961 472 30 971 530 1 2 з 8 4 !в 5 Зг В 64 В ха 7 128 в 258 = 18 х 16 9 Ыг 10 1024 = 33 х 32 11 2048 12 4096 64 х 84 13 8192 14 16 384 15 32 768 !В ВВ ВЗВ !7 131 072 18 262 144 = 512 х 5!2 19 524 288 20 1 048 678 = 1024 х 1034 93 В табл.
8.1 иллюстрируется взаимосвязь величин Н и Р в пределах их изменения, имеющих практический интерес. Полезно запомнить некоторые компоненты этой таблипы, особенно выделенные жирным шрифтом; тогда соседние компоненты будут восприниматься как таблица умножения. Если вы не знаете, что 2'о приблизительно равно 1000, то вы окажетесь в затруднительном положении при беседах на технические темы.
Другим полезным соотношением является следующее: 2'г бнт = 4 109 бит = 500 ме!.а- !О Р !Ю гр Рис. 8.2. Графики зависимостей величин !ОМР мкс и 5МЯ мкс от Р = !ой,М, построенные в логарифмическом масштабе и иллюстрирующие, каким об- разом быстрые алгоритмы обеспечивают возможность и целесообразность использования значений !О < Р < 20 лля широкого круга приложений. 94 байт. В некоторых случаях значения М приведены в виде произведения сомножителей как напоминание об М, соответствуюппгх изображениям определенных размеров. Для Р= 18 значение М составляет около четверти миллиона и приблизительно равно числу элементов разрешения в телевизионном изображении. Общепринятым является утверждение, что число операций, выполняемых в вышеприведенных равенствах, увеличивается по закону М'. Это не так очевидно для М = 2, 4 и 8.
При больших М возникают сложности в расчете количества этих операций, обусловленные тем, что существенное число коэффициентов принимает значения, равные единице, и в силу этого не требуется умножение; некоторые коэффициенты равны нулю, что исключает выполнение операций и умножения„и деления. Несмотря на подобное усложнение, коэффициенты имеют вполне определенные значения и могут быть рассчитань! для последовательно возрастающих' М. Тогда к оценке времени счета можно подойти с позиций определения количества операций сложения и умножения, что воспринимается как увеличение времени счета пропорционально Мз.
Естественно, имеется также возможность хронометрирования процесса фактических вычислений; этот подход выходит за рамки метода, предусматривающего подсчет количества операций, и предполагает оценку временных затрат на реализацию соответствующих процедур, что не учитывается в вышеописанном методе подсчета. Когда величина М становится большой, зависимость вида М' означает, что мы столкнемся с практическими пределами для временных затрат или стоимости. Быстрый алгоритм — это алгоритм, не реализующий в чистом виде все операции, предусмотренные в соответствии с определением преобразования, вследствие чего требуемое количество операций пропорционально МР, или М 1о8,М, а не М'. В качестве примера, иллюстрирующего практическое значение этих рассуждений, рассмотрим быстрый алгоритм, для реализации которого требуется 10 МР мкс по сравнению с 5 Мз мкс для обычного алгоритма дискретного преобразования. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
