7.3. Вычисление ДПФ через быстрое косинусное преобразование

В алгоритмах БПФ данного класса используется представление через дискретное косинусное преобразование (ДКП) с помощью вспомогательных операций сложения и перестановок. Такое представление было впервые рассмотрено Капориным [11] и позже более подробное Уэнгом [12, 13]. При этом также получаются алгоритмы БПФ с вещественными весовыми коэффициентами, однако в силу характерных особенностей данные алгоритмы необходимо выделить в отдельный класс. Рассмотрим метод синтеза таких алгоритмов БПФ.

Первый этап факторизации аналогичен (4.20), но при этом учитывается, что четное

В свою очередь, матрицы по правилам

матрица перестановки, имеющая единицы на пересечении строки и столбца, который определяется правилом

Например, при матрица равна

В (7.16) матрицы типа и к определяются выражениями

и факторизуются в виде

где (M — четное), матрица перестановки, определяемая как и ранее, аналогичным правилом, но для четного дня черного равна

Таким образом, матрица рекуррентно факторизуется через матрицы Дальнейшая факторизация матриц выполняется согдасно (7.16), (7.17). В результате остается фагторизовать матрицы Факторизация может быть выполнена методом [13] или методами [14, 15] за цественных умножений и веще тгвенных сложений

Например, согласно факторизуется в вице

Умножение матрицы вектор требует в общем случае

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

то с учетом (7.19) умножение на -ребует вещественных умножений и вещественных сложении, определяет общее число нетривиальных арифметических операций, равное (табл 7.1)