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

Хотя результаты каждой стадии вычислений разумно запоминать в том порядке, в каком появляются узлы на рис. 6.10, вовсе нет необходимости делать именно так. Не важно как переставлены узлы на рис. 6.10, результатом будет всегда дискретное преобразование Фурье последовательностей если только передачи ветвей не изменятся. Изменится только порядок, в котором поступают и запоминаются данные. Если связать узлы с комплексными запоминающими ячейками и порядок этих узлов с индексом: массива комплексных запоминающих ячеек, то из предыдущего рассуждения станет ясно, что направленный граф соответствует алгоритму с замещением только тогда, когда узлы расположены таким образом, что входные ивыходные узлы каждой «бабочки» горизонтально смежны. В противном случае потребуются два массива комплексных запоминающих ячеек. На рис. 6.10 изображено именно такое расположение узлов. Другой вариант изображен на рис. 6.12. В этом случае входная последовательность имеет обычный порядок, а преобразование Фурье имеет порядок с двоичной инверсией. Рисунок 6.12 можно получить из рис. 6.10, если поменять местами все узлы, которые горизонтально смежны с с узлами, горизонтально смежными с Аналогично все узлы, которые горизонтально смежны с на рис. 6.10, меняются местами с узлами, горизонтально смежными с Узлы, горизонтально смежные с не изменяют своего положения. Результирующий сигнальный граф на рис. 6.12 соответствует алгоритму с прореживанием по времени, первоначально предложенному Кули и Тьюки [1].

Как можно видеть, единственным различием между рис. является порядок следования узлов. Передачи ветвей (степени ) остаются теми же. Имеется, конечно, множество возможных упорядочений, однако большинство из них не имеет большого смысла с точки зрения вычислений. В качестве одной из полезных возможностей предположим, что узлы упорядочены так, что входные и выходные данные появляются в обычном порядке.

Рис. 6.12. Перегруппировка рис. 6.10, при которой входы имеют обычный порядок, а выходы — двоично-инверсный

Рис. 6.13. Перегруппировка рис. 6.10, при которой как входы, так и выходы имеют обычный порядок

Сигнальный граф такого типа показан на рис. 6.13. В этом случае, однако, нельзя провести вычисления с замещением. Поэтому понадобилось бы два комплексных массива для того, чтобы провести вычисления в соответствии с рис. 6.13.

При реализации вычислений, изображенных на рис. 6.10, 6.12 и 6.13, как нетрудно видеть, необходим доступ к элементам промежуточного массива в произвольном порядке. Поэтому для большей скорости вычислений комплексные числа должны запоминаться в запоминающем устройстве с произвольным доступом. Например, согласно рис. 6.10 для того, чтобы вычислить первый массив из входного массива, входы каждой «бабочки» находятся по соседству друг с другом и поэтому предполагается, что они будут запоминаться в соседних запоминающих ячейках. При вычислении второго промежуточного массива из первого входы каждой «бабочки» разнесены друг от друга на две запоминающие ячейкй, а при вычислении третьего массива из второго входы «бабочки» разнесены на четыре ячейки. Если разнос между входами «бабочек» будет равен 8 на четвертой ступени, 16 — на пятой ступени и т. д. Разнос на последней ступени равен

На рис. 6.12 имеет место аналогичная ситуация. При вычислении первого массива из входного мы используем данные, разнесенные на 4, при вычислении второго массива из первого мы используем данные, разнесенные на 2, и, наконец, при вычислении последнего массива мы используем данные, находящиеся в соседних ячейках. Хотя легко представить себе простые алгоритмы изменения индексных регистров для доступа к данным как для сигнального графа на рис. 6.10, так и для графа на рис. 6.12, доступ к данным не будет последовательным, и поэтому было бы желательно иметь память с произвольным доступом. В направленном графе на рис. 6.13 доступ к данным не является последовательным, вычисления не проводятся по алгоритму с замещением, а схема индексации данных значительно сложнее, чем в любом из предыдущих случаев.

На рис. 6.14 изображена перегруппировка направленного графа, показанного на рис. 6.10, которая особенно полезна в том случае, когда отсутствует память с произвольным доступом. Этот граф представляет собой алгоритм с прореживанием по времени, данный Сингльтоном (Singleton) [8]. Отметим сначала, что на. этом направленном графе входные данные появляются в порядке с двоичной инверсией, а выходные — в обычном порядке. Важной чертой этого графа является то, что его начертание на каждой стадии одинаково. От стадии к стадии меняются только передачи ветвей.

Это дает возможность последовательного доступа к данным.

Предположим, что имеется четыре блока памяти на магнитной ленте (или четыре последовательные области памяти на магнитных дисках) и первая половина входных данных запоминается в порядке с двоичной инверсией на одной ленте, а вторая на другой. Тогда можно иметь последовательный доступ к данным на лентах и 2, а результаты записывать последовательно на лентах 3 и 5 так, что первая половина нового массива записывается на ленте 3, а вторая половина — на ленте 4. Наследующей стадии вычислений ленты 3 и 4 являются входом, а выходные данные записываются на лентах 1 и 2. Эта процедура повторяется на каждой из ступеней.

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