10.3. Методы построения гнездовых алгоритмов «прямоугольного» ДПФ-m

"Прямоугольное" класс -мерных массивов данных различной координатной размерности Согласно (1.16) векторно-матричное представление "прямоугольного" ДПФ-m имеет вид

где

Пусть Тогда согласно методу факторизации (3.29) можно непосредственно записать матричное выражение алгоритма прямоугольного

где

В случае матричного представления данных (10.30) эквивалентно следующему рекуррентному выражению:

где и матрица определяются из

Более подробно вычисления типа (10.31) описываются в устройстве процессора БПФ-2 [18].

Для частного случая БПФ-2 общее число вещественных арифметических операций при равно

Аналогично для БПФ-2 методом получаем

Отсюда

Число нетривиальных арифметических операций для гнездового алгоритма БПФ-2 равно

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

случае получаем следующий алгоритм БПФ-2, вычисляемый за этапов:

где

Число вещественных арифметических операций, требуемых для вычисления (10.32), в случае равно