16. Граф-схема алгоритма бпф

Граф алгоритма БПФ с прореживанием по времени. Двоично-инверсная перестановка

Рис. 1

Представим в виде графа алгоритм БПФ с прореживанием по времени основанный на разбиении — объединении при (рисунок 1).

Рис 2: Граф алгоритма БПФ с прореживанием по времени при N=8

На первом этапе отсчеты входного сигнала переставляются местами и исходная последовательность делится на «четную» и «нечетную последовательности» (обозначены красными и синими стрелками). Потом «четная» и «нечетная» последовательности в свою очередь делятся на «четную» и «нечетную» последовательности. При N = 2^L, такое деление можно делать L – 1 раз. В нашем случае L =3.

Граф алгоритма с прореживанием по частоте

Граф бабочка для алгоритма с прореживанием по частоте представлен на рисунке:

Поворотные коэффициенты в алгоритме с прореживанием по частоте полностью совпадают с поворотными коэффициентами алгоритма БПФ с прореживанием по времени.

Представим в виде графа алгоритм БПФ с прореживанием по времени основанный на разбиении — объединении при N = 8

Рис 3: Граф алгоритма БПФ с прореживанием по частоте для N=8

На первом этапе исходный сигнал делится на 2 половины (красные и синие стрелочки). Далее вычисляются

Тогда если выполнить ДПФ S₀(n) , то получим четные отсчеты спектра в соответствии с (9), а если ДПФ S₁(n) - то нечетные отсчеты спектра. Таким образом одно ДПФ длительности N =8 заменили двумя ДПФ длительности N/2 = 4. Для вычисления каждой из ДПФ половинной длительности снова применим прореживание по частоте.

В результате получили 4 ДПФ по 2 точки каждое, которые также можно выполнить при помощи графа бабочки. На выходе получим спектральные отсчеты, которые будут переставлены. На первом уровне преобразования получались четные и нечетные отсчеты спектра, на втором уровне четные и нечетные отсчеты делились снова на четные и нечетные. В результате для расстановки спектральных отсчетов на места необходимо применить двоично-инверсную перестановку.