8.1. Алгоритмы БПФд с прореживанием по частоте (БПФд - f)

Первый этап факторизации для алгоритма БПФ с прореживанием по частоте согласно (7.10) имеет вид

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

Так как для справедливо свойство комплексного сопряжения (8.1), то для справедливо и вычисляются отдельно) и для справедливо

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

Вектор по аналогии с (8.2) представим в виде

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

где

Поскольку , то для справедливо

Следовательно, для вычисления достаточно вычислить Выражение для в этом случае имеет вид

где нулевая матрица, матрица оператора комплексного сопряжения

где — символ операции комплексного сопряжения (т. е. инверсии знака мнимой части комплексного числа).

Преобразуем в (8.3) произведение матриц следующим образом. Представим в виде суммы матриц

где

Тогда

Поставляя (8.4) в (8.3), получаем

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

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

Таким образом, в случае вещественного входного сигнала ДПФд размерностью факторизуется через ДПФд размерностью и комплексное ДПФ размерностью Структурная схема такого разбиения приведена на рис. 8.1, где знак означает операцию образования комплексного числа из двух вещественных.

Дальнейшая факторизация выполняется итеративно. Матрица может быть факторизована аналогично (8.5) и матрица может быть факторизована любым из методов построения комплексного БПФ, рассмотренных в гл. 7.

Выполняя далее аналогично (8.5) факторизацию матриц получаем полное выражение для

где

На рис. 8.2 приведен граф алгоритма БПФд для На рис. 8.3 приведена полная вычислительная схема алгоритма БПФд для с соответствующим размещением частей промежуточных данных. Знак — на рисунке обозначает операцию разделения комплексного числа на два вещественных (1 — выход действительной части, 2 — выход мнимой части). Как видно из рис. 8.2, за счет усечения графа

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

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

выходные данные располагаются не в цифроинверсном порядке. Для получения упорядоченного выхода отсчетов спектра (сначала действительные отсчеты, затем мнимые) необходима двойная перестановка рис. 8.4. Как следует из рисунка, после перестановки действительные отсчеты располагаются в прямом порядке следования, за ними идут мнимые отсчеты спектра в обратном порядке.

Обратное БПФд с прореживанием по частоте ОБПФд — имеет алгоритм, отличный от представленного выше (рис. 8.2, 8.3). Приведем методику синтеза алгоритма ОБПФд —

В результате вычисления спектра от вещественного сигнала нам известны спектральных отсчетов Следовательно, для определения всего спектра следует доопределить остальные

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

Рис. 8.4. Структура выходных перестановок для алгоритма БПФд -

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

Рассмотрим первый этап факторизации по методу прореживания по частоте

где

Умножим матрицу на

где

где символ операции инверсии знака действительной части комплексного числа.

Матрица определяется в виде

Дальнейшее умножение матриц в (8.7) приводит к выражению

Определим структуру матрицы

где .

Объединяя получаем выражение для первого этапа факторизации алгоритма СБПФд

где

Структурная схема первого этапа факторизации алгоритма (8.11) изображена на рис. 8.5.

Проводя аналогичную факторизацию для с учетом (8.8) в (8.11) и т.д., получаем следующее выражение для алгоритма ОБПФд

Согласно (8.12) на рис. 8.6 приведен граф алгоритма ОБПФд для

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

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

Рассмотрим показатели вычислительной эффективности алгоритмов БПФд и ОБПФд Для алгоритма БПФд после первого этапа факторизации (8.5) получаем следующие оценки вещественных умножений и сложений:

Для алгоритмов БПФ по основанию 2 имеем оценки

Подставив (8.14) в (8.13), получаем

Решение рекуррентных уравнений (8.15) дает следующие оценки:

Таким образом, алгоритм БПФд требует более чем в 2 раза меньше арифметических операций по сравнению с полным алгоритмом БПФ для комплексного сигнала, приведенного в разд. 7.1.

Для алгоритма ОБПФд получаем рекуррентные соотношения

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

что более чем в 2 раза меньше в сравнении с полным алгоритмом ОБПФ - по основанию .2.

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

арифметических операций:

Решая (8.18а), получаем

Приведенные оценки показывают, что алгоритм БПФд — с расщепленным основанием требует в 1,5 раза меньше умножений и 1,16 раза меньше сложений по сравнению с алгоритмом БПФд — по основанию 2 и в 3 раза меньше умножений и в 2,3 раза меньше сложений по сравнению с полным алгоритмом БПФ по основанию 2, ориентированном на комплексный входной сигнал.

Из рис. 8.1-8.7 структур алгоритмов БПФд и ОБПФд — (рис. 8.1 — 8.7) очевидно, что все вычисления выполняются с замещением и, следовательно, для хранения входных, промежуточных и выходных данных достаточно ОЗУ емкостью в вещественных слов, что в 2 раза меньше, чем при использовании алгоритмов БПФ, ориентированных на обработку комплексных сигналов.