10.2. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Объясним суть одного из алгоритмов БПФ для вычисления коэффициентов для массива вещественных данных объёма целое число.

Разобьём исходный массив данных на две части с чётными и нечётными номерами

Согласно (10.8) коэффициенты равны на первом этапе разбиения:

Из (10.12) видно, что последовательности коэффициентов и обладают свойством периодичности с периодом

Кроме того, для множитель в (10.12) можно представить

С учётом (10.12), (10.13) и (10.14) можно написать для всех

причём знак "-" соответствует значениям Подсчитаем, сколько требуется операций умножений при вычислении всех значений по алгоритму (10.15). Для вычисления всех по (10.12) требуется умножений. Столько же умножений потребуется для вычисления всех Кроме того, потребуется умножений С, на числа Следовательно, всего потребуется умножений. При больших требуемое число умножений что в 2 раза меньше, чем по алгоритму (10.8).

Чётные отсчёты исходной последовательности (их всего разобьем далее на втором этапе разбиения на чётные и нечётные компоненты (их число равно последних обозначим и Тогда можно написать

Аналогичное разбиение выполняется над нечетными отсчётами исходной последовательности Для вычисления всех Лсогласно формулам типа по массиву данных понадобится число умножений

Процесс разбиений можно продолжить раз до тех пор, пока не получится последовательность из одного элемента, ДПФ которого совпадает с самим элементом. Далее надо собрать результаты отдельных разбиений для вычисления суммарных значений Анализ показывает, что число операций умножения, необходимых для выполнения не больше чем что при больших существенно меньше, чем по рассмотренному методу (его называют методом прореживания отсчётов во времени) осуществляют, как правило, в следующем порядке. Сначала для получения желательного при обработке сигнала порядка следования отсчётов выполняется двоично-инверсная перестановка элементов исходной последовательности Для этого записывают порядковые номера элементов в двоичном коде и инвертируют порядок следования разрядов. Новый порядок следования элементов определяется номерами, полученными после инверсии разрядов.

Пример при

Новый порядок следования элементов: После этого поступают так. На первом этапе вычислений определяют 2 точечные ДПФ "новой" последовательности объединяя попарно элементы этой последовательности. На втором этапе из 2 точечных ДПФ получают 4 точечные ДПФ, пользуясь основной базовой операцией данного метода (см. ниже). Затем 4 точечные ДПФ объединяют в 8 точечные и т.д.

Базовые операции показывают, как два входных числа объединяются для получения двух выходных чисел Для метода прореживания во времени базовая операция имеет

Рис. 10.4. Операция "бабочка", используемая при реализации алгоритма БПФ

Рис. 10.5. Граф для вычисления БПФ при

Базовая операция (10 17) изображается на рисунке "бабочкой" (см. рис. 10.4)

Надпись у стрелки, идущей вверх, означает умножение на величину В.

При вычислении 2 точечного и выходные числа определяются без операции умножения

Пример. Построим граф вычисления БДПФ с прореживанием во времени для (рис. 10 5)

Учитывая, что получаем согласно приведённому графу

На рис. 10.6 дан граф вычисления БДПФ с прореживанием во времени для

Чтобы воспользоваться рассмотренной процедурой БДПФ для выполнения ОДПФ, запишем (10.11) в виде

Вводя массив данных (вместо можно найти сумму в (10.18) по изложенной выше методике БДПФ, а затем для нахождения найти комплексно-сопряженное значение полученного результата. Существуют и другие методы вычисления БДПФ (другие методы группирования исходных данных [24,10]).

Рис. 10.6. Граф для вычисления БДПФ при