Брейсуэлл Р. - Преобразование Хартли (теория и приложения) (1044117), страница 19
Текст из файла (страница 19)
Представляет интерес вопрос: почему оба этих подхода требуют разных времени!их затрат на вычисление соответствующих алгоритмов? Суть этого различия заключается в многоэтапном характере организации вычислительного процесса, обусловленном процедурой последовательного разбиения.
Структура данного алгоритма, хотя мы к ней пришли независимо, соответствует операции факторизации матриц. С целью иллюстрации последовательности выполнения арифметических операций обратимся к табл. 8.2, в которой приведены соотношения, реализующие операции преобразований. Соотношении дла случаи !а'= 16 Как и в случае факторизации матриц, все свойства процедуры преобразования могут быть выявлены при рассмотрении примера, когда М = [6.
В табл. 8.2 первый столбец содержит исходную последовательность данных Г!О, р). Во втором столбце приводятся результаты выполнения определенной в предыдущей главе операции перестановки элементов исходной последовательности. В последующих СтОЛбцаХ СИМВОЛ Е!а тт) ИСПОЛЬЗуЕтСя дпя ОбОЗНаЧЕНИя тс-ГО ЭЛЕМЕНта )6-элементной последовательности на этапе с номером л ее преобразования. Таким образом, столбец с элементами Г(), р) содержит результаты )-го этапа преобразования. Стрелки, используемые в операторах присвоения, подчеркивают направление перехода на данном этапе. Видим, что во всех случаях величина Р(1, о) получается просто как сумма или разность двух элементов последовательности Г!О, р). На 2-м этапе этн комбинации используются в качестве операндов, а именно осуществляется суммирование трех слагаемых, заимствованных нз формулы разложения; аналогичным образом реализуются 3-й и 4-й этапы.
Значения Г(3, р), имеющие сннусные коэффициенты, в явном виде иллюстрируют явление возвратной индексации. Очевидно, имеет место экономия числа операций умножения по сравнению с )т'э, требуемым для формирования суммы, предусмотренной по определению ДПХ. Однако табл. 8.2 непригодна для точного подсчета количества операций из-за вырождения отдельных членов, на~ладно иллюстрируемого в табл. 8.3, что становится очевидным при замене коэффициентов в виде тршонометрических функций их числовыми значениями.
Как на [-м, так и на 2-м этапах не требуется ни одной операции умножения, а на 3-м этапе необходимо выполнить только (6 операций умножения, в каждой из которых используе~си умножение на один и тот же коэффициент г, равный 1,! ут2. Полный эффект от оценки, характеризующейся сложным механизмом упрощения, анализируется ниже при исследовании временных затрат на вычисления. Таблиеа 8.3 Соотпонмнии Ллн 16-элементной посаедователыоостн при подстановке числовых значений коэффнииентов (т = !/,„Г2) 1-й этап Перестановка поспопо- овтооспостс 3-й этап 2-н этап Г[1,0) + Г(1,2) Г(2,0! Г[1, Ц + Г(1,3) Г(2, Ц Г(1,0) — Г(1,2) Г(2,2) Г(1, Ц вЂ” Г(1,3) Г(2,3) Г(1,4)+Г(1,6) Г(2,4) Г(1,5) + Г(1,7) Г(2,5) Г(1,4) — Г(1,6) Г[2,6) Г(1,5) — Г(1,7) Г(2,7) Г(1,8) + Г(1, 10! Г(2,8) Г(1,9)+Г(1,1Ц Г(2,9) Г(1, 8) — Г(1, 10) Г(2, 10) Г(1с9) Г(! !Ц т Г(2с !Ц Г(1, 12) + Г(1, 14) Г(2, 12) Г(1, 13) + Г(1, 15) -т Г(2, 13) Г(1, 12) — Г(1, 14) Г(2,!4) Г(1, 13) — Г(1, 15) Г(2, 15) Направленный сигнальный граф По приведенным выше таблицам можно проследить траектории, .
иллюстрирующие характер влияния каждого элемента исходной последовательности на значения результирующего преобразования. Соответствующий направленный граф для тт' = 8 показан на рис. 8.3. 10! Г(0, 0) Г[0, Ц Г(0,2) Г(0,3) Г(0,4) Г[0, Ь) Г(0, 6) г(о 7) Г(0,8) Г(0,9) Г(0, 10) Г(0,11) Г(0,12) , Г(0,13) Г(0,14) Г(0,15) Г(0,0) Г(0,0) Г(0,8) Г(0, Ц Г(0,4) Г(0,2) Г(0,12) Г(0,3) Г(0,2) Г(0,4) Г(0, Ю) - Г(0, 5) Г(0,6! - Г(О,6) Г(0, !4) Г(0, 7) г(о, ц - г[о,8) Г(0,9) Г(0,9) Г(0,5) -о Г(0,10) Г(0,13) Г(0,!Ц Г(0,3) Г(0,12) Г(0,1Ц Г(0, 13) Г(0,7) Г(0,14) Г(0,15) Г(0, 15) Г[о,о! + Г[о, ц Г(1, о) г(о,о) — г(о, ц - Г(!, 'ц Г(0,2) + Г(0,3) Г(1,2) Г(0,2) — Г(0,3) Г(1,3) Г(0,4)+Г(0,5) Г(1,4) Г(0, 4) — Г(0, 5) Г(1, 5) Г(0,6)+ Г(0,7) Г(1,6) Г(0,6) — Г(0,7) Г(1,7) Г(0,8) + Г[0,9) Г(1,8) Г(0,8) — Г(0,9) — т Г(1,9) Г(0,1О) + Г(О, КЦ Г(1,1О) Г(0, 1О) — Г(0, 1 Ц Г[1, 1Ц Г(0, 12) + Г(0, !3) Г[1, 12) Г(0, 12) — Г(0, !3) Г(1, 13) Г(0, 14) + Г(0, 15) Г[1, !4) Г(0, 14) — Г(0, 15) Г( 1, 15) Г(2, О! + Г(2,4) Г(3,0) Г(2, ц + гГ(2,5) + гГ[2,7) Г(3, ц Г(2,2) + Г(2,6) Г(3,2) Г(2, 3) — гГ[2,7) + тг(2, Ь) Р[3, 3) Г(2, 0) — Г(2, 4) Г(3, 4) Г(2, Ц вЂ” тг(2,5) — гг(2,7) Г(3,5) Г(2,2) — Г[2,6) -о Г(3,6) Г[2,3) + тГ(2,7) — тг(2,5) Г(3,7) Г(2,8) + Г(2,12) Г(3,8) Г(2, 9) + гг(2, 13) + гг(2, 15) — т Г(3, 9) Г(2,10) + Г(2,14) Г(3,10) Г(2, 1Ц вЂ” тг(2, 15) + гг(2, 13) Г(3, 1 Ц Г(2,8) — Г(2,12) Г(3,12) Г(2,9) — тГ(2,13) + гг(2,15) Г(3,13) Г(2, 10) — Г(2, 14) Г(3, 14) Г(2, 1 Ц + гг(2, 15) — тг(2, 13) Г(3, 15) »!»'(г! = 6(г) Нг! фбе! Цг) Ря !г) Рис.
8.3, Характер преобразования каждого элемента исходной последовательности в элементы результирующего преобразования ври реализации быстрого алгоритма иллюстрируется линиями направленного графа, которым соответствуют косввусвые и сиаусиые коэффициенты С„и 5„, которые в частных случаях своляэся к 1 (сплошаые линии) или — ! (штриховые линии). Первым структурным элементом является блок под названием «Перестановка», состав элементов которого анализируется ниже; в этом блоке просто осуществляется изменение порядка следования элементов исходной последовательности. Блоки, соответствующие 1-му этапу, имеют два входа и два выхода и реализуют операцию ДПХ двухэлементной последовательности (Н = 2), аналитически описываемую соотношением ! Н(ч) = (!/2) 2, Г(т) саз 2ячт!2.
э=О Расскрывая знак суммы в определении преобразования для этого частного случая, получим Н(0) = (112) !)(0) + 1(1)3; Н(1) = (1!2) ()(О) — !'(!)3. Фигурируннций в этих равенствах коэффициент 1/2 не включен в направленный граф, соответствующий 1-му э~аду; аналогично этот коэффициент отсутствует на 2-м и 3-м этапах реализации алгоритма, что в дальнейшем учитывается в совокупности в виде коэффициента 8. На практике, чтобы избежать многократного выполнения операции умножения на промежуточных этапах, эта величина включается в !02 состав масштабного коэффициента, необходимого при реализации процедур нормировки, преобразования результатов или их графического отображения. В резулзпате переноса коэффициентов 1!2 в завершающую стадию процедуры преобразования блок, соответствующий его 1-му этапу, просто реализует сложение двух элементов входной последовательности (выход тракта суммирования изображен в верхней части блока) и их вычитание (выход разностного канала изображен в нижней части).
В приведенной диаграмме можно избежать использования в явном виде разностного тракта, если провести штриховые линии и полагать коэффициент передачи соответствующего канала равным — 1. Блоки, соответствующие 2-му этапу, являются четырехвходовыми„как это следует из приведенных на рис. 8.3 соотношений„ являющихся основой направленного графа, и имеют четыре выхода; при этом, как было установлено выше, не требуется выполнение операций умножения. В этой области графа имеются две пунктирные и шесть сплошных линий. И только на третьем этапе осуществления преобразования начинает проявляться эффект возвратной индексации.
Реализуется дублирование 4-элементного преобразования, сформированного на выходе верхнего блока столбца, соответствующего 2-му этапу, с целью получения 8-элементной последовательности, которая была приведена выше в виде Н, (ч) = (аэ!),уэбэа,Ц„у,б,); элементы этого преобразования воспроизводятся на выходах каналов с нулевого по седьмой включительно. Выходы нижнего блока, на которых формируется 4-элементное преобразование, разделяются на косинусный и синусный каналы.
Для косинусного канала по аналогии с процедурой, выполненной для верхнего блока, осуществляется дублирование четырех коэффициентов перед операцией умножения на коэффициенты ф— Сэ, после чего реализуется суммирование соответствующих произведений, формируемых на выходах с нулевого по седьмой.
Для синусного канала осуществлению процедуры согласования порядка, должен предшествовать блок, реализующий схему перекрестных переходов, что необходимо для обеспечения требуемой возвратной индексации. После использования синусных коэффициентов соответствующие произведения подаются на восемь идентичных суммирующих выходов блока, осуществляющего их комбинирование и получившего название «СОМВ11чЕ», Вычисление с замещением При описании потока операций в неявном виде подразумевалось, что Н-элементный массив памяти готов к приему выходной последовательности, являющейся результатом вычислений на предыдущем э~вне. Этот подход упрощает объяснение и реализуется в программах вычислений ГНТВАЯ и РНТВАБ.РОК, приведенных в приложении 1. Однако имеется возможность более рационального использования 103 памяти ЭВМ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
