Представление алгоритма БПФ в виде рекурсивных соотношений

Вернемся к рассмотрению процедуры БПФ. Мы говорили, что на каждой ступени вычисляются группы однородных операций:

- умножение на матрицу D поворачивающих множителей;

- умножение на матрицу ;

- перестановка элементов вектора результатов.

Основная сложность в записи алгоритма БПФ состоит именно в описании перестановок элементов вектора.

Если рассмотреть граф БПФ (например, для N=8, рис3.1), то можно увидеть, что на первой итерации как бы независимо отрабатывается 4 фрагмента исходного вектора, содержащие по 2 элемента: такие фрагменты назовем подвекторами. В данном случае это подвектор X={x₀, x₄}; X={x₁, x₅}; X={x₂, x₆}; X={x₃, x₇}. На второй итерации отрабатывается 2 подвектора по 4 элемента, а на третий - один вектор из восьми элементов.

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

Подобная процедура может быть описана как [11]:

где l=2^m-1, , k=(n)_{mod l}, , - текущий индекс элемента вектора, k - соответствует номеру Б0 при обработке подвектора, , - длина подвектора, причём для m=0 вектор . Номер обрабатываемого на данной итерации блока данных определяется целой частью (n)_{mod l}

Выражение (3.9) определяет обработку отдельного, но любого подвектора на каждой итерации из общего их числа . Индекс n определяется следующим образом:

,

где - начальный индекс для i-го подвектора.

В свою очередь, (3.9) может быть переписано в виде системы из двух уравнений:

(8.10)

Это выражение соответствует базовой операции, для которой указаны правила формирования текущих индексов по “входным” и “выходным” бабочкам, а также правила вычисления поворачивающего множителя