Алгоритм БПФ с основанием 2.

ДПФ конечной последовательности {x(n)} определено ранее:

 

W – является периодической последовательностью с периодом N.

 

Иногда записывают вместо

Подчеркивая периодичность с периодом N.

 

Если x(n) – комплексная последовательность, то из (*) при вычислении N-точечного ДПФ нужно вычислить

N(N-1) – комплексных сложений.

 

Идея БПФ: разбить исходную последовательность из N – отсчетов на две более короткие т.о. что бы ДПФ всей последовательности было вычислено исходя из этих двух.

 

Рассмотрим N-точечную последовательность {x(n)}, считая, что N=степень 2, т.е.

N=2, 4, 8, 16, 32, 64, 128, 256, …

Возьмем две последовательности

{x1(n)} и {x2(n)} из четных и нечетных отсчетов последовательности {x(n)}

 

x1(n)=x(2n) n=0, 1, … , (N/2) – 1

x2(n)=x(2n+1) n=0, 1, … , (N/2) – 1

 

N – точечные ДПФ последовательности x(n)

 

Учитывая, что

Перепишем (**)

 

,где X1(k) и X2(k) равны соответственно (Т/2) – точечным ДПФ последовательностей x1(n) и x2(n). Из (***) следует, что N – точечное ДПФ может быть разложено на два (N/2) – точечных ДПФ.

 

Т.к. X(k) определено при

А X1(k) и X2(k) определено при

То необходимо доопределить формулу (***)

x1(0)=x(0) X1(0) X(0)

x1(1)=x(1) X1(1) X(1)

x1(2)=x(2) X1(2) X(2)

x1(3)=x(3) X1(3) X(3)

 

x2(0)=x(0) X2(0) X(0)

x2(1)=x(1) X2(1) X(1)

x2(2)=x(2) X2(2) X(2)

x2(3)=x(3) X2(3) X(3)

 

Квадраты – четырехточечные ДПФ.

 

Первый столбец – разбивка на x(n) последовательностей x1(четн) x2(нечетн)

 

Аналогично N/2 – точечные ДПФ могут быть записаны как комбинация двух N/4 – точечных ДПФ и т.д.

 

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

Двухточечное ДПФ может быть вычислено по формуле:

 

Т.о. вычисляется восьми точечная ДПФ.

 

Восьми точечное ДПФ, полученное последовательным прореживанием в 2 раза – БПФ.

 

О – операция +и

- - операция умножения.

 

a a+b

 

O

b a-b

 

 

Этот алгоритм БПФ называется алгоритмом БПФ с основанием два с прореживанием по времени.

 

Свойства алгоритма БПФ с основанием 2 и прореживанием по времени.

 

1. На каждом этапе БПФ (т.е. при каждом сокращении размеров БПФ) необходимо выполнить N/2 - комплексных умножений.

2. Общее количество этапов сокращения равно.

3.
Общее число комплексных умножений равно

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

4.
Для выполнения БПФ N – точечной последовательности, размещенной в памяти, достаточно иметь лишь одну дополнительную ячейку памяти.

5. Результаты всех промежуточных этапов БПФ можно размещать в те же ячейки памяти, где находились исходные ячейки памяти.

 

6. Перестановка данных и двоичная инверсия.

 

 

Для 8-ми точечного БПФ необходим такой порядок следования отсчетов.

 

x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7);

 

В случае, когда N – равно степени 2, входная последовательность должна быть разложена в двоично-инверсном порядке для того, что бы выходная последовательность получалась в прямом.

 

Номер	Двоичное представление	Двоичная инверсия	Двоичный инв. номер.

 

7. На всех этапах БПФ используются коэффициенты

 

Алгоритм БПФ с прореживанием по частоте. Обратное ДПФ с помощью алгоритма обратного ДПФ. Алгоритмы БПФ с основанием 2.