Конспект лекций по цос

БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ

1. ОСНОВЫ АЛГОРИТМОВ БПФ
Дискретное преобразование Фурье (ДПФ) X(k) конечной последовательности x(n), n = 0, 1, ..., N – 1
X(k) = , k = 0, 1, ..., N – 1; (1)
обратное ДПФ x(n) = , (2)
где n = 0, 1, ..., N – 1; W_N = – периодическая последовательность с периодом N
, m = 0, 1, 2, ... .
Непосредственное вычисление ДПФ X(k) (12.1) при комплексных значениях x(n) требует (N–1)² комплексных умножений и N(N–1) сложений комплексных чисел. Для больших значений N (сотни, тысячи) прямое вычисление ДПФ (12.1) требует выполнения очень большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычисления в реальном масштабе времени.
Быстрым преобразованием Фурье (БПФ) называют набор алгоритмов, реализация которых приводит к существенному уменьшению вычислительной сложности ДПФ (12.1). Основная идея этих алгоритмов состоит в разбиении исходной N-точечной последовательности на две (N/2)-точечные последовательности, из ДПФ которых конструируется ДПФ исходной последовательности. Для двух (N/2)-точечных последовательностей требуется примерно 2(N/2)² = N²/2) умножений комплексных чисел – количество операций уменьшается примерно в 2 раза. Аналогично вместо вычисления ДПФ (N/2)-точечной последовательности можно вычислить ДПФ для двух (N/4)-точечных последовательностей и таким образом вновь уменьшить требуемое количество операций. Если N = 2^v, v > 0 и целое, то процесс уменьшения размера ДПФ может быть продолжен до тех пор, пока не останутся только 2-точечные ДПФ. Общее число этапов вычисления ДПФ равно v = log₂N, а количество требуемых арифметических операций для вычисления N-точечной ДПФ, порядка Nv, уменьшается примерно в N/log₂N раз. Так, при N = 1000 для прямого вычисления ДПФ согласно (12.1) требуется примерно N ² = 10⁶ операций комплексных умножений и сложений, а при использовании алгоритмов БПФ таких операций требуется всего порядка 10⁴, т. е. объем вычислений сокращается примерно на два порядка.
БПФ с прореживанием по времени требует перестановку отсчетов входной последовательности x(n), а БПФ с прореживанием по частоте – перестановку отсчетов выходной последовательности X(k).
2. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ
Пусть требуется вычислить ДПФ (12.1) при N = 2^v, где v > 0 — целое. Если N  2^v, то последовательность x(n) дополняется в конце нулевыми элементами так, чтобы длина результирующей последовательности была степенью 2.
Исходную N-точечную последовательность
х(n) = х_v(n), где v = log₂N, n = 0, ...., N – 1,
разобьем на две (N/2)-точечные последовательности x_v—1,0(n) и x_v—1,1(n), состоящие соответст­венно из четных и нечетных членов х(n Т), т. е.
(4)
При этом N-точечное ДПФ (12.1) можно записать в виде
. (5)
Учитывая, что , получаем
, (6)
где и — -точечные ДПФ соответственно последовательностей и :

.
Преобразование X_v(k) должно быть определено для N точек
(k = 0, 1, ..., N – 1), а последовательности и определяются только для точек (k = 0, 1, ..., – 1), поэтому доопределим (12.6) для значений k = , +1, ..., N – 1. Учитывая, что и периодические функции с периодом , можно записать
(7)
так как W_N = ;
Формулы (12.6) и (7) дают алгоритм вычисления N-точечной ДПФ через -точечные ДПФ, который можно пред­ставить направленным графом, имеющим вид «бабочки» – рис. 1.

.

Рис. 1. Направленный граф «бабочка»

Выходные числа X и Y графа на рис. 1 получаются из входных чисел A и B по правилам
(8)
В качестве примера граф на рис. 1 представляет операции (6) и (7). Аналогично можно выразить -точечные ДПФ
и
через - точечные ДПФ:
(8а)
и
(8б)
где X_v–2,0(k) и X_v–2,1(k) – соответственно -точечные ДПФ четных