Быстрое преобразование Фурье (БПФ)

Быстрое преобразование Фурье (FFT) является не более, чем алгоритмом для ускоренного вычисления ДПФ путем сокращения требуемого числа операций умножения и сложения. Данное преобразование было предложено в 1960-ых годах. Алгоритм быстрого преобразования Фурье значительно сокращает количество арифметических операций и объем памяти, необходимой для вычисления ДПФ. ДПФ может быть сильно упрощено, если использовать свойства симметрии и периодичности коэффициентов поворота.

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

Таблица 1.1

Эффективность БПФ

Если необходимо рассчитать только несколько точек спектра, ДПФ может быть более эффективным. Вычисление одного выходного отсчета спектра с использованием ДПФ требует только N умножений с комплексными числами.

Мы будем предполагать далее, что N=2ⁿ. При этом общность не теряется, так как N выбирается достаточно большим для того, чтобы удовлетворять теореме дискретизации Котельникова, т.е.

N ³ 2BT,

где B – полоса частот сигнала x(t); T – его длительность.

Теорема Котельникова-Найквиста-Шеннона: если сигнал таков, что его спектр ограничен частотой F, по после дискретизации сигнала с частотой не менее 2F можно восстановить непрерывный сигнал по полученному цифровому сигналу абсолютно точно. Для этого нужно проинтерполировать цифровой сигнал «между отсчетами» специального вида функциями.

Рассмотрим случай вещественно-значной последовательности {X(m)} при N=8. Из свойства комплексной сопряженности ДПФ следует, что

; .

Тогда

; ;

W=e^-i2p/8=e^-ip/4;

. (1.17)

Используя свойство N-периодичности экспонент, для N=8 матрица будет иметь вид

.

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

W_k+N/2=-W_k, где .

То есть W₄=-W₀;

W₅=-W₁;

W₆=-W₂;

W₇=-W₃.

Тогда матрица F будет иметь вид

.

Используя двоичную инверсию (перестановку) строк,

(0,1,2,3,4,5,6,7)® (0,4,2,6,1,5,3,7) будем иметь

=

= . (1.18)

В свою очередь, матрицы A₁¹ и B₁¹ можно представить в виде, где верхний индекс представляет собой номер шага процедуры БПФ

(1.19)

Подставляя выражения для A₁¹ и B₁¹ в (1.18) получим

;

;

;

. (1.20)

Наконец, на последнем шаге получим

(1.21)

Описанный алгоритм удобно представить графически (рис. 1.6).

Рис. 1.6. Граф-схема быстрой процедуры вычисления коэффициентов преобразования Фурье

Для определения степеней W на одном шаге необходимо выразить последовательность l=0, 1, 2, …, N/2-1 в виде (n-1) – разрядных двоичных последовательностей. В результате для N=16, к примеру, получим множество

S₁=(000,001,010,011,100,101,110,111).

Для получения S₂ необходимо выполнить двоичную инверсию каждой (n-1) -разрядной последовательности множества S₁, т.е.

S₂=(000,100,010,110,001,101,011,111),

и записать двоичную последовательность в виде десятичных чисел

S₃=(0,4,2,6,1,5,3,7),

и таким образом имеем W₀, W₄, W₂, W₆, W₁, W₅, W₃, W₇. (табл. 1.2).

Итерация r для БПФ состоит из 2^r-1 групп, где (N=2ⁿ). Для N=16, .

Таблица 1.2

Значения степени W

Первый элемент первой строки таблицы равен нулю. Последующие первые элементы каждой из строк определяются как n_s=N/2^s, где , N=2ⁿ. Каждая k строка таблицы получается прибавлением элемента n_k-1 к каждому элементу предыдущих строк. Тогда таблица будет иметь вид

0

n₁

n₂ (n₁+n₂)

n₃ (n₁+n₃) (n₂+n₃) (n₁+n₂+n₃)

n₄ (n₁+n₄) (n₂+n₄) (n₁+n₂+n₄) …

.

.

n_k …

Требуемая последовательность L_n, соответствующая двоичной инверсии, определяется как L_n=(0, n₁, n₂, (n₁+n₂), n₃, (n₁+n₃), …, n_k, …). В качестве примера рассмотрим случай для N=16. Тогда n₁=8, n₂=4, n₃=2, n₄=1, т.е. таблица будет иметь вид

0

8

4 12

2 10 6 14

1 9 5 13 3 11 7 15

L_n=(0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15).

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

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

. (1.22)

Для N=8 , где ; I₄ – единичная матрица размерностью 4 ´ 4; D₁ – диагональная матрица с элементами W₀;

.

D₂ -диагональная матрица с элементами W₀, W₂:

;

; .

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

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