10.4. Методы построения алгоритмов БПФ-m для обработки вещественных данных

Пусть массив входных данных является вещественным, т.е. Тогда согласно свойству 7 (разд. 2.2) для спектра ДПФ-m справедливо свойство комплексного сопряжения

В (10.31) не учтены составляющие с координатами которые вычисляются отдельно. Например, для ДПФ-2 получаем следующие условия:

Покажем, как учитывая свойство комплексной сопряженности спектра, можно синтезировать специальные алгоритмы БПФ для обработки вещественных сигналов, которые более чем в 2 раза эффективнее алгоритмов БПФ-m, предназначенных для обработки комплексных сигналов.

10.4.1. Построчно-столбцовые алгоритмы БПФ-m для обработки вещественных данных. Наиболее тривиальным способом в этом случае является вычисление по первой координате -точечного вещественного БПФ с общим числом проходов и затем по остальным координатам — точечных комплексных БПФ с общим числом проходов по координате Оценки вычислительной сложности для такого алгоритма вещественного равны

(аналогично для

Недостатком такого алгоритма БПФ-m является необходимость применения одномерных БПФ различных классов — вещественного и комплексного. Это значительно усложняет реализацию алгоритма.

Для преодоления данного недостатка используем подход, предложенный в [19,20].

Без потери общности рассмотрим двумерное ДПФ размерностью Пусть тогда:

1. Считывается столбец Вычисляется вещественное БПФ от

Так как для спектра справедливо свойство комплексной сопряженности

то для определения всего спектрального вектора достаточно комплексных отсчетов и два вещественных и Таким образом, для хранения спектрального вектора достаточно вещественных отсчетов.

Отсюда из без потери информации можно сформировать новый вектор по принципу

Полученный в результате таких преобразований вектор записывается во внешнее ОЗУ вместо

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

2. Считывается строка матрицы

Вычисляется "вещественное" БПФ от

Так как для спектра также справедливо свойство комплексной сопряженности

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

В результате получаем матрицу, равную

3. В матрице строки и получены соответственно из векторов и которые, в свою очередь, являются спектрами

Таким образом, полный спектр равен

или

Согласно (10.38) и (10.39), для того чтобы в строке разместить все части отсчетов спектра, а в строке части, необходимо из векторов и скомпоновать векторы и по правилам

При такой перестановке мы получаем половину комплексного спектра

где в строках с номерами хранятся части спектра в строках части спектра и отдельно расположены отсчеты в 0-й и строках по правилам

(аналогично для

Таким образом, спектр вещественного сигнала может быть вычислен за вещественных БПФ размером вещественных БПФ размером и перестановок данных на последнем этапе с инверсией знака согласно (10.40).

Оценки вычислительной сложности для такого алгоритма в общем случае для -мерного БПФ равны

(аналогично

Пусть оценки (10.35) обозначаются а оценки (10.41) . Тогда как

Приведем пример конкретных оценок для двумерного вещественного БПФ размерностью с покоординатным применением одномерных вещественных БПФ типа

10.4.2. Гнездовые алгоритмы БПФ-m для обработки вещественных данных. Выполним первый этап факторизации где согласно (10.26). Пусть входной массив Тогда после построчно-столбцового преобразования

получаем массив

Так как все массивы то для спектров

справедливы следующие свойства комплексной сопряженности:

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

Оценки числа арифметических операций, исходя из выражений (10.26) и (10.44), определяются рекуррентными выражениями

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

Сравнение оценок (10.45) и (10.42) показывает, что гнездовой подход к синтезу алгоритмов вещественного БПФ-2 уменьшает число арифметических операций в 1,3 —1,5 раза по сравнению с методом ПСА.