16. Алгоритмы бпф с прореживанием по времени. Основные свойства.

Принцип прореживания по времени наиболее удобно иллюстрируется в частном случае, когда N является целой степенью числа 2, т. е. В этом случае из исходной последовательности x(n), формируют две -точечные подпоследовательности и из четных и нечетных членов соответственно:

(1.155)

С учетом этого прямое ДПФ последовательности можно представить следующим образом:

С учетом того, что последнее выражение можно переписать в виде:

(1.156)

или

0  k  N – 1, (1.157)

где и – -точечные ДПФ последовательностей и соответственно.

Поскольку определено для а и определены только для то необходимо доопределить полученное выражение для Для этой цели воспользуемся свойством периодичности ДПФ. Действительно, и – периодические функции переменной k с периодом Следовательно

(1.158)

(1.159)

Тогда

(1.160)

Так как то выражение (1.157) и (1.160) можно записать таким образом:

(1.161)

В этом случае для вычисления двух -точечных ДПФ требуется комплексных умножений и приблизительно столько же комплексных сложений. Затем два -точечных ДПФ должны быть объединены, что потребует комплексных умножений и комплексных сло­жений. Следовательно, для всех значений k требуется или комплексных умножений, что уже при меньше чем

Проиллюстрируем вычисление X(k) в соответствии с полученным выражением для Для этой цели используем направленные сигнальные графы следующего вида (рис. 1.23).

Рис. 1.23. Направленные сигнальные графы

При этом предполагается, что ветви, входящие в узел суммируются (вычитаются), причем верхний выход соответствует сумме, а нижний – разности. Стрелка обозначает операцию умножения на значение множителя, указанного под стрелкой; если множитель не указан – передача по ветви равна 1.

Из рисунка 1.24 видно, что вычисляются два четырехточечные ДПФ четных и нечетных значений входной последовательности. Затем получается путем умножения на и прибавления Значение получается умножением на и прибавления Значение получается умножением на и вычитания из

Аналогичным образом вычисляются и остальные значения.

Рис. 1.24. Вычисление ДПФ для N = 8 на основе двух 4-х точечных

Рассмотренная схема вычислений может быть использована для расчета -точечных ДПФ в соответствии с полученными формулами. В этом случае -точечные ДПФ могут быть представлены как комбинация двух -точечных ДПФ (рис. 1.25).

Рис. 1.25. Вычисление ДПФ для N = 8 на основе четырех 2-х точечных

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

(1.162)

Здесь – преобразуемая двухточечная последовательность. Поскольку и то для вычислений по данным формулам действительно не нужны операции умножения. Таким образом, восьмиточечное ДПФ в итоге сводится к алгоритму, описываемому следующим графом (рис. 1.26).

Рис. 1.26. Направленный граф алгоритма БПФ с прореживанием по времени для N=2³

Из анализа графов видно, что на каждом этапе БПФ (т. е. при каждом сокращении размера ДПФ) необходимо выполнять комплексных умножений. Поскольку общее число этапов равно то число комплексных умножений, необходимых для нахождения N – точечного ДПФ, приблизительно равно Мы говорим приблизительно по той причине, что умножение на и в действительности сводится к сложению и вычитанию комплексных чисел.

Описанный алгоритм был назван алгоритмом с прореживанием по времени, поскольку на каждом этапе входная, т. е. временная последовательность разделяется на две обрабатываемые подпоследовательности меньшей длины, т. е. входная последовательность прореживается на каждом этапе.

Общими свойствами таких алгоритмов БПФ являются:

1. Этот алгоритм наиболее удобен, когда

2. Базовая операция алгоритма с прореживанием по времени (так называемая «бабочка») состоит в том, что два входных числа и объединяются для получения двух выходных чисел и следующим образом:

(1.163)

Направленный граф базовой операции выглядит следующим образом (рис. 1.27).

Рис. 1.27. Базовая операция алгоритма с прореживанием по времени

3. Каждый из этапов, как видно из рис. 1.26, содержит базовых операций. В случае, когда множитель – нетривиальный, для каждой базовой операции необходимо выполнять только одно умножение, поскольку величину можно вычислить и запомнить. Структура базовых операций такова, что для выполнения БПФ N – точечной последовательности, размещенной в памяти, достаточно иметь лишь одну дополнительную ячейку памяти. Результаты вычислений на всех промежуточных этапов БПФ можно размещать в те же ячейки памяти, где находились исходные данные. Поэтому для хранения входной и выходной последовательности можно использовать один и тот же массив ячеек памяти. Алгоритмы, у которых для размещения входной и выходной последовательностей используются одни и те же ячейки памяти, называются алгоритмами БПФ с замещением.

Проиллюстрируем алгоритм БПФ с основанием 2 несколько иначе. Все ДПФ являются двухточечными и не требуют операций умножения. Однако при объединении двух – точечных ДПФ в одно N – точечное приходится выполнять около умножений, причем все они используются только при объединении результатов ДПФ. Поскольку эти умножения используются во всех алгоритмах БПФ, соответствующие множители получили специальное название поворачивающих множителей (иногда их называют фазовыми множителями или множителями вращения).

4. Еще одной особенностью алгоритма данного типа является необходимость такой перестановки элементов входной последовательности чтобы выходная последовательность имела естественный (прямой) порядок расположения, т. е. В примере при для этого требовался следующий порядок размещения входной последовательности: и Оказывается, что если является степенью 2, то входная последовательность должна быть расположена в памяти в двоично-инверсном порядке для того, чтобы выходная последовательность получалась в прямом порядке. Двоично-инверсный порядок определяется следующим образом. Записываются порядковые номера элементов входной последовательности в двоичном коде, используя двоичных разрядов, причем а затем осуществляется их инверсия. Полученные при этом числа и будут номерами элементов входной последовательности. Для прямой и двоично-инверсный порядок отсчетов входной последовательности приведен в табл. 1.7.

Таблица 1.7