Различные авторы использовали самые разнообразные условные обозначения в публикациях, посвященных алгоритмам БПФ. Так, Кули и Тьюки (J.W.Cooley и J.W.Tukey) использовали алгебраическую систему обозначений; некоторые авторы пользовались матричным обозначением. По-видимому, наиболее распространенным способом описания БПФ является представление его с помощью направленных графов (впервые использованных Рэйдером и Стокхэмом). Далее мы проведем сравнение обозначений, используемых в предлагаемом учебном пособии, и обозначений, принятых при представлении алгоритмов в виде направленных графов. Обе системы обозначений нетрудно усвоить, и в зависимости от конкретных условий можно использовать любую из них, не испытывая при этом никаких неудобств.
Алгоритм БПФ по основанию 2 разделяет полное вычисление ДПФ на комбинацию 2-точечных ДПФ. Каждое 2-точечное ДПФ содержит базовую операцию умножения с накоплением, называемую «бабочкой» (рис. 1.26). На диаграмме показаны два представления «бабочки»: верхняя диаграмма фактически является функциональным представлением «бабочки», построенным на цифровых умножителях и сумматорах. В упрощенной нижней диаграмме операции умножения помечаются множителем возле
стрелки, а под суммированием подразумеваются две стрелки, сходящиеся в точке. Таким образом, в направленных графах точка суммирования представляется узлом, а умножение – стрелкой, так что базовую операцию алгоритма БПФ с основанием 2 и прореживанием по времени можно изобразить так, как это сделано на рис. 1.26.
Упрощенный направленный граф лучше использовать для представления полного алгоритма БПФ, однако при пользовании им может показаться, что на одну базовую операцию вместо одного приходятся два умножения в комплексной форме. Для обозначения элементарного ДПФ в пособии использован специальный символ:
· для алгоритма БПФ с прореживанием по времени он изображен на рис. 1.18;
· для алгоритма БПФ с прореживанием по частоте – на рис. 1.23.
Для примера, на рис. 1.27 приведен направленный граф полного 8-точечного алгоритма БПФ по основанию 2 и с прореживанием по времени. Сравните его с направленным графом (см. рис. 1.17).
Читатель сам должен решить, какое из представлений алгоритма БПФ в виде направленных графов предпочтительнее. Отметим лишь существенные отличия между ними:
1) первый способ (рис. 1.27) обычно применяется при изображении направленных графов, он хорошо известен и очень широко используется;
2) первый способ можно использовать и для графического описания работы цифровых фильтров;
3) все общие и важные теоремы о свойствах направленных графов применимы и к графам алгоритмов БПФ;
4) при втором способе (см. рис. 1.17) используется в два раза меньше линий при основании 2 (и в r раз меньше линий при основании r);
5) второй способ легко использовать при построении графа алгоритма БПФ со смешанным основанием;
6) для второго способа число символов умножителей равно фактическому числу умножений в алгоритме БПФ с основанием 2.
