7.7. Система рекуррентных уравнений, описывающих БПФ

Обозначим индексами последовательные массивы направленного графа. Тогда будет крайним левым массивом графа на фиг. 7.13, a — крайним правым; — произвольный массив с меняющимся от 1 до , где — число последовательных шагов со взвешиванием входных данных. Например, для столбца операция взвешивания имеет вид

В общем случае, чтобы выразить через необходимо учитывать следующее. При движении справа налево по направленному графу на фиг. 7.13 разнесение между парами, участвующими во взвешивании при каждой итерации, будет уменьшаться в 2 раза. В результате этого:

а) число уравнений будет удваиваться;

б) диапазон изменения независимой переменной должен уменьшаться вдвое;

в) аргумент весовой функции должен удваиваться.

С учетом первого из этих условий пара, участвующая во взвешивании массива имеет вид

Труднее всего выразить условия Их можно удовлетворить, если

Здесь I — число пар функциональных уравнений,

и — диапазон изменения независимой переменной причем

Заметим, что независимо от величины переменная принимает значения от нуля до при условии, что принимают все свои значения. Однако (порядок следования значений зависит от Наконец, условие удовлетворяется, если весовая функция имеет вид Эту функцию можно упростить, если выразить

(кликните для просмотра скана)

через (все целые) и учесть, что . В результате получим . Теперь можно записать окончательные рекуррентные уравнения:

при