8.2. Алгоритмы БПФд с прореживанием по времени (БПФд — t)

Первый этап факторизации матрицы ДПФ по методу прореживания по времени определяется выражением

Если то согласно может быть представлено через два так как

В силу комплексной сопряженности спектра матрица может быть преобразована к виду

где

Рассмотрим вектор Так как то спектральный вектор удовлетворяет свойству комплексной сопряженности, т.е. отсюда

Таким образом, можно представить в виде

где

Подставляя (8.20) и (8.21) в (8.19), получаем окончательное выражение первого этапа факторизации алгоритма БПФд — (рис, 8.8)

где

Проводя в (8.22) аналогичную факторизацию для и получаем полное матричное представление алгоритма БПФд —

Путем несложных преобразований можно показать, что одна из матриц является лишней, и выражение (8.23) можно упростить

где

На рис. 8.9 приведен полный граф алгоритма БПФд для Структура вычислений данного алгоритма, в которой показано размещение действительной и мнимой частей комплексных данных, показана на рис. 8.10.

Число арифметических операций для данного алгоритма БПФд — определяется рекуррентными оценками

Рис. 8.8. Первый этап факторизации алгоритма БПФд по основанию 2

Рис. 8.9. Граф алгоритма БПФд - по основанию 2

решение которых дает следуюшии результат

Сравнение (8.25) с (8.16) показывает, что алгвритм БПФд — требует на больше умножений и на меньше сложений, чем алгоритм БПФд —

Как следует из рис. 8.10 для алгоритма БПФд — также возможна организация вычислений с замещением, те. требуемая емкость ОЗУ равна вещественных слов.

Аналогично рассмотренному подходу приведем методику синтеза алгоритма БПФд — по основанию 4. Здесь также начнем с первого этапа

Рис. 8.10. Вычислительная схема алгоритма БПФд - t по основанию 2

факторизация

где

Раскроем сгуктуру матоицы

учитывал комплексную сопряженность спектра, (8.27) можно преобразовать к виду

где

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

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

Применяя описанный подход к следующим этапам факторизации, получаем полное матричное выражение для алгоритма БПФд по основанию 4

На рис. 8.11 изображен граф алгоритма БПФд - по основанию 4 для случая

Оценки числа вещественных арифметических операции алгоритма (8.32) определяются из следующих оекуррентных соотношений

решение которых дает