7.4. Алгоритм БПФ с расщепленным основанием

Данный класс алгоритмов предложен сравнительно недавно для случая Более раннее описание такого алгоритма принадлежит Гречишникову [19]. Основной принцип построения алгоритмов состоит в объединении ряда весовых коэффициентов в соседних диагональных матрицах .

Алгоритм БПФ с расщепленным основанием (прямая форма) строится согласно следующему рекуррентному правилу [16]:

Аналогичный подход, только в полипомиальчом представлении, предложен в [20] (алгоритм RCFA - Recursive Cyclotomic Factorization Algorithm), в котором выражение для заменяемся его полиномиальным аналогом

В этом случае алгоритм БПФ с расщепленным основанием строится по следующей системе полиномиальных выражений:

Рассмотрим более подробно матричную интерпретацию алгоритма БПФ с расщепленным основанием. Пусть тогда согласно (7.10)

Представим матрицу в виде

где с другой стороны, где Тогда

где Отсюда после первого этапа факторизации получаем

где

Как следует из (7.23), матрицы весовых коэффициентов преобразованы в одну матрицу при этом на месте возникла диагональная матрица содержащая только

Далее для матрицы также возможна аналогичная факторизация, а именно:

Отсюда после второго этапа факторизации получаем

где Продолжая аналогичную факторизацию для матриц

получаем окончательное зыражелке горилла БПФ с расщепленным основанием

где

Матриць весовых коэффициентов окре деляг отся согласно следующему правилу;

где

Таким образом, в (7.25) каждая матрица I к в порождает две подматрицы в и каждая магрииа

Приведем пример матичной записи алгоритма (7.24) при

где

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

Рис. 7.8. (см. скан) Алгоритм БПФ с расщепленным основанием

нетривиальных вещественных арифметических операций для данного алгоритма БПФ равно (табл. 7.1)

Дальнейшие исследования в этом направлении показали [21], что другие способы факторизации по указанному методу (например, аналогичная факторизация по основаниям 4, 8 и смешанные варианты) являются менее эффективными (по числу умножений), чем рассмотренный алгоритм.