6.3.1. ВЫЧИСЛЕНИЯ С ЗАМЕЩЕНИЕМ

Направленный граф на рис. 6.18 изображает один из алгоритмов БПФ с прореживанием по частоте. Можно заметить ряд. сходных черт и ряд различий при сравнении этого графа с графом, выведенным на основе прореживания по времени. Конечно, как и в случае с прореживанием по времени, граф рис. 6.18 соответствует вычислению дискретного преобразования Фурье

независимо от того, как он начерчен, поскольку одни и те же узлы соединены друг с другом с соответствующими передачами. Другими словами, как и в случае вывода алгоритма с прореживанием по времени, сигнальный граф на рис. 6.18 не основан на каком-либо априорном предположении о порядке, в котором запоминаются входные данные. Однако, как и в случае алгоритмов с прореживанием по времени, можно считать, что последовательные вертикальные узлы на графе рис. 6.18 соответствуют запоминающим регистрам памяти. В этом случае замечаем, что граф на рис. 6.18 начинается с входных данных в обычном порядке и дает выходные точки в порядке с двоичной инверсией. Мы также отмечаем, что основным вычислением является вычисление в форме «бабочки», хотя эта «бабочка» отличается от той, которая возникает в алгоритмах с прореживанием по времени. Однако в силу такого характера вычисления граф на рис. 6.18 можно интерпретировать как вычисление с замещением дискретного преобразования Фурье. Как и прежде, обозначим последовательность комплексных чисел на ступени вычисления через где На рис. 6.19 показана «бабочка» вычислений, уравнение которой имеет вид

Сравнивая рис. 6.9 и 6.19 или выражения (6.16) и (6.22), убеждаемся, что «бабочки» вычислений отличаются для этих двух классов алгоритмов БПФ.

Рис. 6.19. Направленный граф операции «бабочка» для рис. 6.18

Рис. 6.20. Направленный граф обратного ДПФ, получаемый из рис. 6.10 путем обращения операций «бабочка»

Отмечаем также поразительное сходство между вычислениями, соответствующими «бабочкам», и между рис. 6.10 и 6.18, т. е. то, что рис. 6.18 можно получить из рис. 6.10, изменив направление сигналов и поменяв местами вход и выход. Согласно терминологии гл. 4 рис. 6.18 является транспонированным по отношению к графу на рис. 6.10 и, следовательно, из теоремы о

транспонировании характеристики обоих графов должны быть одинаковыми. Чтобы убедиться в этом, другим путем рассмотрим «бабочку» в алгоритме с прореживанием по времени, изображенную на рис. 6.9. Соответствующее уравнение имеет вид

Если начать с выхода как на рис. 6.10, можно обратить (6.23), выражая через т. е.

Таким образом, так как и равно в порядке с двоичной инверсией, то можно вычислить в порядке с двоичной инверсией, последовательно применяя (6.24). Направленный граф для показан на рис. 6.20.

Рисунок 6.20 изображает алгоритм обратного быстрого преобразования Фурье (ОБПФ). Заметим, что обратное дискретное преобразование Фурье имеет вид так что для вычисления ОДПФ можно использовать БПФ-алгоритм, если разделить результат на и подставить вместо степеней степени Аналогично алгоритм ОБПФ может быть использован для вычисления ДПФ, если мы умножим выход на и вместо степеней будем использовать степени Таким образом, направленный граф на рис. 6.20, представляющий алгоритм ОБПФ, может быть преобразован в БПФ-алгоритм путем замены на так как отсутствие коэффициента 1/2 на каждой стадии эквивалентно умножению выхода на При этом изменении и при подаче на вход в обычном порядке и двоичноинверсном порядке из рис. 6.20 получим рис. 6.18.

Таким образом, видно, что любому алгоритму БПФ с прореживанием по времени соответствует алгоритм обратного преобразования, который является алгоритмом с прореживанием по частоте, или, ввиду простой связи между алгоритмами прямого и обратного преобразования, можно в общем случае утверждать, что для каждого алгоритма БПФ с прореживанием по времени существует алгоритм БПФ с прореживанием по частоте, который соответствует взаимной замене входа и выхода и обращению направлений всех стрелок в направленном графе.