6.3.2. ДРУГИЕ ФОРМЫ АЛГОРИТМОВ

Из полученного результата вытекает, что все графы в § 6.2 имеют «двойников» типа с прореживанием по частоте. Это, конечно, соответствует тому факту, что, как и прежде, можно переставить узлы грйфа без изменения конечного результата.

Если применить такую процедуру к рис. 6.12, то получим рис. 6.21. В этом графе выходы расположены в обычном порядке, а входы - в порядке с двоичной инверсией. Транспонирование графа на рис. 6.13 дает граф рис. 6.22, где как входы, так и выходы расположены в обычном порядке.

Рис. 6.21. Направленный граф алгоритма ДПФ с прореживанием по частоте, полученный из рис. 6.18 (входы имеют двоично-инверсный порядок, а выходы — обычный порядок; рисунок получен транспонированием из рис. 6.12)

Как и в случае рис. 6.13, этот граф не соответствует вычислению с замещением.

Рис. 6.22. Перегруппировка направленного графа рис. 6.18, при которой как входы, так и выходы имеют обычный порядок (получен транспонированием из рис. 6.13)

Рис. 6.23. Перегруппировка направленного графа рис. 6.18, при которой каждая ступень имеет одинаковое начертание, тем самым позволяя использовать последовательный доступ к данным и их запоминание (получен транспонированием из рис. 6.14.)

Путем транспонирования рис. 6.14 получим рис. 6.23. Каждая ступень на рис. 6.23 имеет одно и то же начертание, что является желательным в том случае, когда имеется память с последовательным доступом.