Алгоритм БПФ по основанию 2 разделяет полное вычисление ДПФ на комбинацию 2-точечных ДПФ. Каждое 2-точечное ДПФ содержит базовую операцию умножения с накоплением, называемую «бабочкой» и иллюстрируемую на рис. 5.13. На диаграмме показаны два представления «бабочки»: верхняя диаграмма фактически является функциональным представлением «бабочки», построенным на цифровых умножителях и сумматорах. В упрощенной нижней диаграмме операции умножения помечаются множителем возле стрелки, а под суммированием подразумеваются две стрелки, сходящиеся в точке.

8-точечное БПФ с прореживанием во времени (decimation-in-time, DIT) вычисляет окончательный результат с использованием трех каскадов, как это следует из рис. 5.14.

Восемь входных отсчетов из временной области сначала разделяются (или прореживаются) на четыре группы 2-точечных ДПФ. Затем четыре 2-точечных ДПФ объединяются в два 4-точечных ДПФ. Затем два 4-точечных ДПФ объединяются для того, чтобы получить окончательный результат Х(k). Подробно процесс рассмотрен на рис. 5.15, где показаны все операции умножения и суммирования. Нетрудно заметить, что базовая операция «бабочки» 2-точечного ДПФ формирует основу для всего вычисления. Вычисление осуществляется в трех каскадах. После того, как заканчивается вычисление первого каскада, нет необходимости сохранять какие-либо предыдущие результаты.

Результаты вычисления первого каскада могут быть сохранены в тех же самых регистрах или ячейках памяти, которые первоначально хранили исходные отсчеты из временной области х(n). Точно так же, когда заканчивается вычисление второго каскада, результаты вычисления первого каскада могут быть удалены. Таким же образом осуществляется вычисление последнего каскада, заменяя в памяти промежуточный результат вычисления предыдущего каскада. Обратите внимание, что для того, чтобы алгоритм работал должным образом, входные отсчеты по времени х(n) должны быть упорядочены определенным образом с использованием алгоритма реверсирования битов.

Алгоритм реверсирования битов, используемый для реализации прореживания по времени, представлен на рис. 5.16. Десятичный индекс n преобразуется в его двоичный эквивалент. Затем двоичные разряды располагаются в обратном порядке и преобразуются обратно в десятичное число. Реверсирование битов часто выполняют аппаратурой ЦОС в генераторе адреса данных (DAG), упрощая таким образом программное обеспечение, сокращая количество дополнительных операций и ускоряя вычисления.

На рис. 5.17 и 5.18 представлено вычисление БПФ с использованием алгоритма с прореживанием по частоте (DIF).

Этот метод требует, чтобы алгоритм реверсирования был применен к адресам выходных отсчетов Х(k). Обратите внимание, что «бабочка» для алгоритма с прореживанием по частоте (DIF) слегка отличается от «бабочки» для алгоритма с прореживанием по времени, как это показано на рис. 5.19.

Использование алгоритмов с прореживанием по времени, по сравнению с алгоритмами с прореживанием по частоте, в значительной степени является вопросом предпочтения, так как оба алгоритма дают одинаковый результат. Определенные ограничения той или иной системы могут сделать одно из двух решений оптимальным.

Необходимо отметить, что алгоритмы, требуемые для вычисления обратного БПФ, почти идентичны тем, которые необходимы для вычисления прямого БПФ, если принять во внимание, что речь идет об использовании комплексного БПФ. В действительности, полезный метод проверки алгоритма комплексного БПФ состоит в осуществлении БПФ с отсчетами из временной области х(n), а затем — в вычислении обратного БПФ с отсчетами из частотной области Х(k). В конце этого процесса должны быть получены первоначальные отсчеты из временной области Re х(n), а мнимая часть Im х(n) должна быть нулевой (в пределах ошибки математического округления).

Обсуждавшиеся до сих пор БПФ представляют алгоритм БПФ по основанию 2, то есть их вычисление основано на 2-точечных базовых операциях типа «бабочка».

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

Базовая операция «бабочка» БПФ по основанию 4 с прореживанием по частоте представлена на рис. 5.21.

Алгоритм БПФ по основанию 4 требует меньшего количества умножений с комплексными числами, но большего количества операций суммирования, чем БПФ по основанию 2 для такого же количества точек. По сравнению с алгоритмом БПФ по основанию 2, алгоритм по основанию 4 использует более сложную адресацию и дополнительные коэффициенты поворота, но меньшее количество вычислений. Окончательная экономия времени вычисления различается для разных DSP, но алгоритм БПФ по основанию 4 может быть более чем вдвое быстрым, чем алгоритм по основанию 2 для DSP с оптимальной архитектурой.