Алгоритм БПФ с основанием 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.

 

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

 

Другая распространенная форма алгоритма БПФ при условии, что N – равно степени 2 – алгоритм БПФ с прореживанием по частоте.

 

Разобьем входную последовательность x(n) на две равные последовательности.

 

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

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

 

Тогда:

 

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

Запишем выражение (*) отдельно для четных и нечетных отсчетов ДПФ:

 

Из выражений (**) и (***) видно, что четные и нечетные отсчеты ДПФ можно получить из N/2 – точечных ДПФ последовательностей f(n) и g(n), равных:

 

Т.о. снова вычисление N – отсчетов ДПФ удалось свести к вычислению двух (N/2) – точечных ДПФ

 

Описанную методику можно применить повторно и каждая из (N/2) – точечных ДПФ в виде комбинации двух (N/4) – точечных ДПФ, и т.д.

 

Отличия алгоритма БПФ с прореживанием по частоте, от алгоритма БПФ с прореживанием по времени.

 

1. При прореживании по времени входные отсчеты – в двоично-инверсном порядке следования, а входные в прямом. При прореживании по частоте – наоборот, входные – в прямом, выходные – в инверсном.

2. Несколько иная базовая комбинация:

Сходство алгоритмов:

1. В общих случаях требуется примерно

Операций.

2. Операции могут быть выполнены с замещениями.