Брейсуэлл Р. - Преобразование Хартли (теория и приложения) (1044117), страница 22
Текст из файла (страница 22)
Ниже будет описан метод быстрого поворота, введенный Бьюнеманом (О. Вилелган. 1пчегяол о( бзе Не!ш)во11х (ог 1.ар!асс-Ро)мол) Орега1ог (ог 81аЬ Оеошеггу, Е Сглпрц1айопа! РЬув., чо!. 12, рр. 124 — 130, 1973.— Обращение оператора Гельмгольца (Лапласа — Пуассона) для геометрии на плоскости). Посредством довольно удачного приема количество операций умножения уменьшено до трех. Число операций сложения возросло до трех, однако для многих ЭВМ, затрачивающих больше времени на выполнение операций умножения, чем на сложение, имеет место существенное сокращение машинного времени. Для пояснения алгоритма Бьюнемана рассмотрим рис. 8.7.
При 112 Рнс. 8.7. Иллюстрация быстрого влгорнтма Бьюнеманв для поворота прямо- угольной системы координат. заданных координатах (х', у') точки Р мы получаем ее новые координаты (х, у) в ррзультате поворота исходных осей на угол 0 и проектирования исходных координат на оси х, у. Таким образом, имеем х = 011 — Д/1 = х'сов  — у'ил В. В качестве альтернативного подхода отложим на оси х отрезок 05, такой, что 05 = х'.
Тогда х = 05 — Д8 = х' — Д8, что представляет собой интересное соотношение, так ках слагаемое х' не имеет коэффициентов. В этом случае Д5 является горизонтальной проекцией отрезка РТ, выражаемого в виде суммы отрезков РУ = у' (одной нз исходных координат) и ьГТ, просто равного х'188/2. Следовательно, х = х' — РТяп О, где РТ= у'+ х'18(0/2).
Зная координату х, можем выразить у в виде суммы др и И'. Таким образом, имеем у = х180/2+ РТ. Вспомогательный линейный сегмент РТ, введение которого ускоряет выполнение рассматриваемой процедуры, является связующим звеном между исходными данными н искомым результатом и ниже обозначается Т,. Таким образом, алгоритм, заменяющий общепринятые преобразования, имеет вид Т =у'+х'180/2, х = х' — Твилб, У = х180/2+ Тв. Данный метод, реализуемый в программе РНТ8()В, требует наличия таблицы значений функции 18 (О/2), которые, как было 113 в изб отмечено в предыдущем разделе, могут быть также использованы для определения функции косинуса. Вычисление тангенсов может быть осуществлено с помощью таблицы синусов посредством соотношения 180/2 = 11 — з(п 1(я/2) — Щ/ зш О.
Фрагмент программы, реализующий эту процедуру, имеет вид 9000 И И4 9000 ГОН 1 1 ТО И4 9000 Т(1)-(1-9(К))УИ(1) 9000 И 8-1 9000 ИИХТ 1 где 5( ) †син, а Т( ) †танге половинного угла. Быстраи перестановка Как отмечалось при анализе полосковой диаграммы для оценки затрат машинного времени, на процедуру перестановки может затрачиваться значительная доля времени при выполнении программы расчета спектров.
Традиционный медленный алгоритм перестановки использует процедуру изменения порядка следования символов последовательности на обратный (см. разд. «Ячеистая структура перестановочной диаграммы» в гл. 7) и требует для его реализации число операций, пропорциональное М(Р— 1). Следовательно, даже для длинных последовательностей данных доля времени, затрачиваемая на перестановку элементов, никогда не становится пренебрежимо малой.
Процедуру перестановки целесообразно осуществлять и иллюстрировать с помощью кристаллической структуры, упомянутой выше при рассмотрении перестановочной диаграммы. Сначала определим координаты ячеек с помощью следующих равенств: х»о ™оц+ Р» (о), У»„™«о+ Р» ((г) где Мо — число ячеек, укладывающихся вдоль одной координаты, (Мо = [М7(4 или 8)5п~ в зависимости от того, является ли величина Р четной (семейство 1) илн нечетной (семейство П), а Ра(1) — перестановочная функция для М элементов. Так как общее число ячеек Мо пропорционально М, время, затрачиваемое на вычисление координат ячеек, возможно, окажется просто пропорциональным М.
Если должно быть удовлетворено именно данное требование, то доля Ря в суммарных затратах »о времени будет незначительной. Для асимптотической оценки сложности процедуры, предусматривающей подсчет числа операций в пределе для больших М, считается, что так как перестановка предполагает выполнение (Р— 1) этапов для каждой из М операций, время вычисления для х„„будет асимптотически стремиться к М(Р— 1). Однако был предложен интересный способ преодоления этого не- 114 достатка. Так как Мо становится все меньше по сравнению с М при его увеличении, время, затрачиваемое на определение Р„(1), стано"о вится несущественным. При этом доминирующими окажутся затраты времени на выполнение последовательных операций сложения для установления х„„н у„„. После вычислений координат элементов одной ячейки всегда имеется 4 или 8 изменений соответствующих состояний, т.е.
различных значений координат, так как число «атомов», содержащихся в одной ячейке, не увеличивается с ростом М, а принимает поочередно значения 4 и 8. Экспериментальная опенка фактических затрат времени подтверждает, что для геометрического подхода требуется время, пропорциональное М. Для диаграммы временных затрат (рис. 8.4), на которой используется нормировка времени относительно МР, «ширина» полос по вертикали убывает по закону Р ' до пренебрежимо малого значения. Описанный здесь метод иллюстрируется в программе вычислений ЕАБТРЕКМ(1ТЕ, приведенной в приложении 1. В эту программу в качестве подпрограммы включен сегмент, реализующий перестановку элементов с целью получения Р„((И в прежние времена мы бы .о использовали термин Ые?)л?г(о га с(гси!о, теперь же мы употребим термин «уплотненная упаковка». Парадоксально, но факт: вся программа реализуется быстрее, чем ее отдельный сегмент.
При этом можно представить себе реккурентную процедуру в виде операции, осуществляющей перестановку элементов укороченной последовательности с дальнейшим уменьшением ее размеров. Вскоре окажется, что результирующая последовательность будет состоять из двух элементов, вследствие чего не потребуется дальнейшая перестановка элементов. Преобразование для последователыюстей с основанием 4 и другие модификации С чисто иллюстративной целью рассмотрение было ограничено последовательностями длины М, где М = 2, 4, 8, 16, ...; другими словами, М вЂ” это число 2, возведенное в степень Р: М = 2». Однако возникает вопрос; какова специфика ситуацни и что следует делать, когда последовательность состоит из 300 элементов? Возможно, следует исключить 44 элемента, чтобы уменьшить их общее число до 256.
Можно также дополнить исходную последовательность 212 нулями, тогда число элементов результирующей последовательности окажется равным 512. Ясно, что на практике нецелесообразно оценивать время, затрачиваемое на реализацию процедур иад искусственно удлиненными последовательностями; в результате обычно используются средства, реализующие удлинение исходных последовательностей дополнительными элементами и согласующиеся с операцией вида 2"; вычисления и отображения цифровых изображений рассчитаны на формат 512 х 512 либо на формат вида 2»з х 2»з, 115 в наших руках; Однако выбор некоторых средств не находится в на например, число строк телевизионного изображения колеблется между 512 и 1024, а в ряде случаев составляет всего 525.
Вне нашего контроля находятся также временные ряды, возникающие в геофизических исследованиях, астрономические данные и другая инфорнечных пятен с мация естес~венного происхождения. Последовательность чисел сол!х пятен содержала в 1985 г. 286 членов, поскольку регистрация числа пятен началась в 1700 г., очень немного информации можно извлечь относительно А1, и остается только ждать дальнейших р з ль- резульЕсли вернуться к обоснованию доводов в пользу выбора закона вида 2г, то всп «аз ел " вспомним, что этот выбор был обусловлен принци р д яй и властвуи», посредством которого поэтапно уменьшалась длина последовательности, пока не осталось два элемента.
В рез льтате мы имели тривиальные двухэлементные преобразования, для которых затем выполнялась процедура нх объединения, т.е. получеявля ния ком инированного преобразования. Ясно, что простейши ляется также трехзлементное преобразование м г (1!3) 2. 7'(т) саз(2лкт73); г=« диаграмма для этого преобразования, имеющая форму бабочки, приведена на рис. 8.8.
Как показал Гаусс, любые факторы, со аю е г, сокращ щие число элементов последовательности, позволяют уменьшить время, затрачиваемое на вычисление. Разумеется, в случае когда число представляется не только степенью 2, еб тся о , тр ую д полннтельные операции умножения, однако имеет место экономия времени вычисления. Алгоритм, реализующий в пределе данную идею для ДПФ посредством представления величины )ч' в виде б( = 2'г Зкг 5'э 7'к ..., где последовательно расположенные основания 2, 3, 5, 7, ... , ...
представляют собой ряд простых чисел, был усовершенствован С. Виноградом. Соответствующий материал рассматривается в литературе иггю, Т. )т'. Раг)гя 13РТ/ГЕТ Сопко1пйоп А!8ог(бгшз, %11еу 1п!егзс!енсе, 1985.— (Алгоритмы свертки для ДПФ)БПФ)). Этими авторами рассмотрены алгоритмы перестановки для оснований степеней, отличающихся от числа 2.
При использовании этих алгоритмов на практике, когда возникают затруднения в представлении числа А1, его часто все-таки можно представить в наиболее удобной и эффективной с точки зре ро и реализации алгоритмов форме. Если мы потребуем пред- очки зрения . ставления )ч' в виде 4г, что представляет собой четную величину, принадлежащую к более узкому классу, нежели класс четных значений вида ~, то при этом будут использованы преимушества в скорости реализации алгоритма. Для 4-элементного ДПХ коэффициенты передачи (весовые коэффициенты усиления) равны 1 нли 116 Рвс.
8.8. Диаграмма в форме бабочки для 3-элементного ДПХ, Сплошные линии представляют коэффициент передачи„равный !/3; штриховые линии используются дяя обозначения коэффяцвента передачи ( 73 — !)/6.= 0,122, а остальные линии — для обозначения коэффициентов передачи а (»ГЗ вЂ” ! !)/6 = = + 0,455. — 1, что. не влечет за собой операций умножения: аналогичное упрощение характерно и для диаграммы в форме бабочки прн ч) = 4г. При этом уменьшение длины исходной последовательности прекращается при получении 4-элементных подпоследовательностей, в результате чего существенно сокращается общее число операций умножения, для типового случая приблизительно на одну треть.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
