6.9. Алгоритмы БПФ с основанием 2
В настоящее время значительно чаще используются алгоритмы БПФ не со смешанным, а с фиксированным основанием. В последнем случае значительно проще проводить анализ, программировать и разрабатывать специализированные устройства. В принципе разницы между алгоритмами со смешанным и фиксированным основаниями нет. Действительно, если 
, где 
— целое, то сначала N представляется в виде произведения 
, затем 
представляется как 
и т. д. Например, если 
, то можно поступить следующим образом:
1. Пусть отсчеты 0 — 15 составляют первую строку матрицы размером (2x16), а отсчеты 16—31 составляют ее вторую строку. Начнем с выполнения двухточечных ДПФ всех 16 столбцов, как показано на фиг. 6.14, а результаты затем умножим на матрицу поворачивающих множителей, также содержащую 2 строки и 16 столбцов.
2. Пусть каждая строка, подлежащая преобразованию, представляется в виде матрицы, составленной из 2 строк и 8 столбцов.
Фиг. 6.14. Направленный граф 32-точечного БПФ с замещением по основанию 2.
Вычислим по восемь ДПФ столбцов каждой из обеих матриц размером (2x8) и умножим их элементы на поворачивающие множители, рассчитываемые с помощью множителя 
, матрица которых имеет размер (2x8). Полученный результат будет соответствовать второму этапу алгоритма, граф которого показан на фиг. 6.14.
3. Аналогично каждую из строк, содержащих по восемь элементов, представим в виде матрицы размером (2x4), а затем каждую из строк, содержащих по четыре элемента, — в виде матрицы (2x2), которая в данном случае является конечной целью.
В качестве упражнения читателю предлагается выполнить 32-точечное ДПФ с прореживанием по времени, используя двумерный подход (или какой-либо другой).
На этом заканчивается рассмотрение алгоритмов БПФ, проведенное с целью дальнейшего их использования главным образом в задачах спектрального анализа.
Поскольку применение ДПФ в последующих разделах этой главы было бы не совсем обосновано без хорошего понимания алгоритмов БПФ, последние изложены достаточно подробно, хотя, конечно, и не исчерпывающе. Дальнейшее изложение идей БПФ содержится в гл. 10, где будет описана аппаратурная реализация алгоритмов БПФ
