3.7. Выполнение бпф для случаев

Если , то в этом случае выполняется алгоритм БПФ по смешанному основанию. Он может быть реализован как алгоритм с прореживанием по частоте или как алгоритм с прореживанием по времени. В обоих случаях такой алгоритм выполняется заитераций. Однако на каждой итерации выполняется различное число базовых операций, причём размерность матрицы ядра ДПФ базовой операции на каждой итерации различна и составляет, а число БО соответственно на каждой итерации составляет -, где до первой итерации элементы вектора переупорядочиваются с шагом [8]. На рис. 3.5. приведен в качестве примера граф БПФ для N = 6 = 3x2.

Рис.3.5. Граф БПФ для N=6

Если же является простым числом и не может быть разложено на взаимно-простые множители, то в этом случае также можно использовать алгоритм быстрого преобразования, но особого вида - так называемый алгоритм Винограда [15]. Этот алгоритм позволит значительно сократить число операций умножения, но зато число операций сложения сокращается не столь существенно, причем требуются достаточно сложные процедуры перекомпоновки векторов промежуточных результатами.

Поэтому для современных ЭВМ, и особенно спецпроцессоров, когда ( а в некоторых из них одинаково время любой операции), такие алгоритмы, как и БПФ по смешанному основанию, не приносят слишком большого выигрыша по времени.

С точки зрения экономии времени целесообразно дополнить вектор до (желательно или) нулями. Однако такой прием приводит к некоторому искажению результата, что связано с введением так называемой оконной функции. Пусть исходных сигнал задан в виде вектора из N₁ отсчетов(рис.3.6.).

Для того, чтобы иметь возможность использовать алгоритмы БПФ дополним сигнал нулевыми отсчетами до общего числа отсчетов N= 2^M , причем N – ближайшее большее к N₁ .В этом случае исходный сигнал оказывается заданным с помощью функции

,

где g(x) – функция окна вида

Рис. 3.6. Проявление эффекта окна

Поэтому при вычислении преобразования Фурье от проявляется эффект, получивший название “эффекта окна”.

,

гдепри этом функциябудет тем ближе к- функции, чем ширеили чемближе кN. Проявляется “эффект окна” в искажении периферийных областей спектра сигнала [21]. Поэтому, во избежание проявления “эффекта окна” удобнее функцию при переходе отксделать периодической с периодом, дополнив вектор исходных данных до длины, повторив первыеотсчетов за последние элементы вектора.