ПРИЛОЖЕНИЕ. УСЛОВНЫЕ ОБОЗНАЧЕНИЯ ДЛЯ БПФ
Различные авторы использовали самые разнообразные условные обозначения в публикациях, посвященных алгоритмам БПФ Так, Кули и Тьюки [1] использовали алгебраическую систему обозначений; некоторые авторы пользовались матричным обозначением.
Фиг. А.6.1. Старое обозначение базовой операции алгоритма БПФ с основанием 2 и прореживанием по времени.
Фиг. А.6.3. Новое обозначение базовой операции алгоритма БПФ с основанием 2 и прореживанием по времени.
Фиг. А.6.5. Направленный граф четырехточечного БПФ с прореживанием по времени в старой системе обозначений.
Фиг. А.6.2. Улучшенное обозначение базовой операции алгоритма БПФ с основанием 2 и прореживанием по времени.
Фиг. А.6.4. Новое обозначение базовой операции алгоритма БПФ с основанием 2 и прореживанием по частоте.
Фиг. А.6.6. Направленный граф четырехточечного БПФ с прореживанием по времени в новой системе обозначений.
По-видимому, наиболее распространенным способом описания БПФ является представление его с помощью направленных графов (впервые использованных Рэйдером и Стокхэмом). Ниже будет проведено сравнение обозначений, используемых в данной книге, и обозначений, принятых при представлении алгоритмов в виде направленных графов. Обе системы обозначений нетрудно усвоить, и в зависимости от конкретных условий можно использовать любую из них, не испытывая при этом никаких неудобств.
В направленных графах точка суммирования представляется узлом, а умножение — стрелкой, так что базовую операцию алгоритма с основанием 2 и прореживанием по времени можно изобразить так, как это сделано на фиг. А.6.1. При построении направленного графа полного алгоритма БПФ этот граф не совсем удобен; его можно заменить другим, изображенным на фиг. А.6.2. Последний лучше использовать для представления полного алгоритма БПФ, однако при пользовании им может показаться, что на одну базовую операцию вместо одного приходятся два умножения в комплексной форме.
Для обозначения элементарного ДПФ в книге использован специальный символ. Так, например, базовая операция для алгоритма БПФ с прореживанием по времени показана на фиг. А.6.3, а для алгоритма БПФ с прореживанием по частоте — на фиг. А.6.4. На фиг. А.6.5 и А.6.6 изображен направленный граф четырехточечного алгоритма БПФ с прореживанием по времени с использованием обеих систем обозначений. Читатель сам должен решить, какое из них предпочтительнее. Отметим лишь существенные отличия между ними:
1. Первый способ (фиг. А.6.5) обычно применяется при изображении направленных графов, хорошо известен и очень широко используется.
2. Первый способ можно использовать и для графического описания работы цифровых фильтров.
3. Все общие и важные теоремы о свойствах направленны! графов применимы и к графам алгоритмов БПФ.
4. При втором способе (фиг. А.6.6) используется в два раза меньше линий при основании 2 (и в r раз меньше линий при основании r).
5. Второй способ легко использовать при построении графа алгоритма БПФ со смешанным основанием.
6. Для второго способа число символов умножителей равно фактическому числу умножений в алгоритме БПФ с основанием 2.
