Е. Графы БПФ.

Обращаясь к рассматриваемому далее графическому изображению процедуры БПФ, дополним то, что ранее было сказано о БПФ. Как и при описании рис. 3.6, ограничимся примером выполнения восьмиточечного БПФ (N = 8). Аналогичным образом могут быть представлены графы БПФ и при больших значениях

Рассмотрим БПФ с прореживанием по времени. Покажем сначала, как для рассматриваемого примера графически представляется в соответствии с формулами (3.75) и (3.76) операция вычисления -точечной (для данного примера -точечной) последовательности но представляющим собой ДПФ одной и другой из выделенных ранее указанным способом -точечных (в рассматриваемом примере -точечных) последовательностей.

Обратимся к рис. 3.7,а и к верхней части рис. Здесь каждым из прямоугольников условно показана операция выполнения соответствующего -точечного ДПФ, которая в дальнейшем тоже будет описана. Стрелка без дополнительных обозначений указывает на то, что просто передается указанное значение или Стрелкой с обозначением под ней показана передача данной величины, умноженной на Кружками обозначены или исходные точки, или при подходе к кружку двух линий точки выполнения операции суммирования.

Рис. 3.7,а отражена процедура получения лишь значений Согласно графу в соответствии с формулой получается в виде суммы величины и величины умноженной на Для определения должно быть добавлено произведение на Но, как было указано раньше, повторяется с периодом в данном случае - с периодом 4. Поэтому, имея в виду рассматриваемый пример, можно в соответствии с формулой (3.76) заменить на и на Это и сделано при изображении на рис. 3.7, а операции получения

Аналогично, графически представляется и определение а также и определение (5), Весь граф, отражающий процедуру получения -точечного ДПФ по двум -точечным, приведен для в верхней части рис. 3.7, б.

Каждое из показанных в верхней части рис. -точечных ДПФ получается из -точечных ДПФ, которые при являются первичными ДПФ. Выполнение этой операции для одной из -точечных последовательностей с получением значений изображено в средней части рис. Таким же образом при использовании тех же множителей вьшолняется указанная операция и для второй из -точечных последовательностей с получением значений

В этой части рис. каждым из квадратов обозначено выполнение операции получения -точечного ДПФ по двум двухточечным ДПФ. Всего при данных рассматриваемого примера выполняются четыре такие операции. При каждой из них используются множители и

Выполнение одной из четырех операций -точечного ДПФ, в данном примере — двухточечного, иллюстрируется графом, изображенным в нижней части рис. 3.7, б.

Рис. 3.7 (см. скан)

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

Практически важным является следующее замечание. Множители не должны заново определяться, так как

каждый из них является одним из множителей которые бьши использованы при выполнении первоначально рассмотренной нами операции разложения исходной -точечной последовательности. Действительно, применяя формулу (3.71), приходим к Следовательно,

Принимая это во внимание, представим граф полного разложения 8-точечного ДПФ так, как показано на рис.

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

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

Так же представляется графом и БПФ с прореживанием по частоте. На рис. 3.8, а изображен граф БПФ с прореживанием по частоте для -точечной исходной последовательности. Ход построения его аналогичен ходу построения ранее рассмотренного графа (описан, например, в книге [85]). Основное отличие его от этого графа в том, что (в соответствии с формулами (3.78) и умножение на поворачивающий множитель каждый раз проводится после операции суммирования или вычитания, а не до этого, как в соответствии с формулами (3.75) и (3.76) было указано на графах БПФ с прореживанием по времени.

Отличие изображенного на рис. 3,8, а графа от графа БПФ с прореживанием по времени, приведенного на рис. 3,7, в, и в том, что в первом из них расположены в нормальном порядке, а в двоично-инверсном порядке (смысл этого выражения будет пояснен в разделе Ж), согласно же представленному на рис. 3.7, в графу БПФ с прореживанием по времени, наоборот, расположены в двоично-инверсном порядке, в нормальном порядке. Общим для обоих указанных выше графов является то, что они отражают выполнение БПФ как совокупности операций "бабочка" при отмеченном ранее различии между этими операциями для БПФ с прореживанием по частоте и с прореживанием по времени.

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

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

Рис. 3.8 (см. скан)

рассматриваемого примера при N = 8 имеем log2 8=2 ступени). На каждой ступени производится N комплексных умножений и N комплексных сложений. Общее количество комплексных умножений равно здесь При прореживании по частоте производится такое же количество комплексных умножений и комплексных сложений.

Обычно используются графы указанного выше вида. В некоторых источниках рекомендуются к применению и иные представления операций "бабочка". Так, в книге [101] принято для базовой операции алгоритма БПФ с прореживанием по времени изображение, указанное на рис. 3.8, б, а для базовой операции алгоритма БПФ с прореживанием по частоте — изображение, приведенное на рис. 3,8, в. Здесь буквами обозначены

входы "бабочки". В дальнейшем для графического представления данной операции будем пользоваться ранее указанными ее изображениями.