Направленный сигнальный граф

По приведенным выше таблицам можно проследить траектории, иллюстрирующие характер влияния каждого элемента исходной последовательности на значения результирующего преобразования. Соответствующий направленный граф для N = 8 показан на рис. 8.3.

Рис. 8.3. Характер преобразования каждого элемента исходной последовательности в элементы результирующего преобразования при реализации быстрого алгоритма иллюстрируется линиями направленного графа, которым соответствуют косинусные и синусные коэффициенты которые в частных случаях сводятся к 1 (сплошные линии) или — 1 (штриховые линии).

Первым структурным элементом является блок под названием «Перестановка», состав элементов которого анализируется ниже; в этом блоке просто осуществляется изменение порядка следования элементов исходной последовательности. Блоки, соответствующие 1-му этапу, имеют два входа и два выхода и реализуют операцию ДПХ двухэлементной последовательности (N = 2), аналитически описываемую соотношением

Расскрывая знак суммы в определении преобразования для этого частного случая, получим

Фигурирующий в этих равенствах коэффициент 1/2 не включен в направленный граф, соответствующий 1-му этапу; аналогично этот коэффициент отсутствует на 2-м и 3-м этапах реализации алгоритма, что в дальнейшем учитывается в совокупности в виде коэффициента 8. На практике, чтобы избежать многократного выполнения операции умножения на промежуточных этапах, эта величина включается в

состав масштабного коэффициента, необходимого при реализации процедур нормировки, преобразования результатов или их графического отображения.

В результате переноса коэффициентов 1/2 в завершающую стадию процедуры преобразования блок, соответствующий его 1-му этапу, просто реализует сложение двух элементов входной последовательности (выход тракта суммирования изображен в верхней части блока) и их вычитание (выход разностного канала изображен в нижней части). В приведенной диаграмме можно избежать использования в явном виде разностного тракта, если провести штриховые линии и полагать коэффициент передачи соответствующего канала равным — 1. Блоки, соответствующие 2-му этапу, являются четырехвходовыми, как это следует из приведенных на рис. 8.3 соотношений, являющихся основой направленного графа, и имеют четыре выхода; при этом, как было установлено выше, не требуется выполнение операций умножения. В этой области графа имеются две пунктирные и шесть сплошных линий. И только на третьем этапе осуществления преобразования начинает проявляться эффект возвратной индексации.

Реализуется дублирование 4-элементного преобразования, сформированного на выходе верхнего блока столбца, соответствующего этапу, с целью получения -элементной последовательности, которая была приведена выше в виде

элементы этого преобразования воспроизводятся на выходах каналов с нулевого по седьмой включительно. Выходы нижнего блока, на которых формируется 4-элементное преобразование, разделяются на косинусный и синусный каналы. Для косинусного канала по аналогии с процедурой, выполненной для верхнего блока, осуществляется дублирование четырех коэффициентов перед операцией умножения на коэффициенты после чего реализуется суммирование соответствующих произведений, формируемых на выходах с нулевого по седьмой. Для синусного канала осуществлению процедуры согласования порядка, должен предшествовать блок, реализующий схему перекрестных переходов, что необходимо для обеспечения требуемой возвратной индексации. После использования синусных коэффициентов соответствующие произведения подаются на восемь идентичных суммирующих выходов блока, осуществляющего их комбинирование и получившего название «COMBINE».