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

N-1

X(k)=∑x(n)e^[-j(2π/N)nk] – формула дискретного преобразования Фурье (ДПФ)

n=0

Необходимо выполнить N²-операций комплексного умножения. Реализация БПФ в реальном времени очень трудоемкий процесс, занимающий много времени.Это не позволяет использовать алгоритмы спектрального преобразования.

Σ-ма спектров=спектру Σ-мы, в каждом интервале N/2-отсчетов(N²/4-операций) .

На каждом цикле преобразования входную последов-ть /2 (делим на 2).

N-1

e^(-j2π/N)=W˛N˛ X(k)=∑x(n)(W˛N˛ )^nk , где nk-аргумент времени

n=0 (номера отсчетов)

Формула Эйлера : е^jφ=cosφ+sinφ

е^(-jφ)=cosφ-sinφ

Временная область определения функции W˛N˛ : ( -∞ ; +∞)

Эта функция периодическая. В интервале (0;N-1) представлены все значения функции. Скорость изменения зависит от k.

W˛N˛ ^(n+mN)(k+Nι)= W˛N˛^nk ,где n и k-целые числа.

e^[-j(2π/N)(n+mN)(k+Nι)]=e^[-j(2π/N)nk]· e^[-j(2π/N)mN], e^[-j(2π/N)mN]=1

Функция W˛N˛ распространяется на всю временную ось.

8-ми точечная БПФ (N=8)

(алгоритм с прореживанием по времени)

Исходную последов-ть делим на 2.

x1(n)=x(2n) – 1-ая последов-ть образована отсчетами с четными номерами (2n)

x2(n)=x(2n+1) – 2-ая ….. с нечетными номерами (2n+1)

N/2-1 N/2-1

X1(k)=Σx1(n) ·W˛N˛^(2nk)= Σx1(n) ·W˛N/2˛^(nk)

n=0 n=0

N/2-1 N/2-1

X2(k)=Σx2(n) ·W˛N˛^[(2n+1)k]= [Σx2(n) ·W˛N/2˛^(nk)] · W˛N˛^k n=0 n=0

N/2-1 N/2-1

X*(k)=X1(k)+X2(k)= Σx2(n)· W˛N/2˛^(nk)+ W˛N˛^k · Σx(2n+1)W˛N/2˛^(nk)

n=0 n=0

Вторая половина спектральных коэффициентов вне пределов суммирования.

N/2>n>0 N=8

N-1>n>N/2 N/2=4

x(2n)=0;2 , т.е. учитывается момент времени t=0

x(2n+1)=1;3

N-1 N-1

X**(k)= Σx2(n)· W˛N/2˛^(n-N/2)k+ W˛N˛^k · Σx(2n+1)W˛N/2˛^(n-N/2)k

n=N/2 n=N/2

X*(k)=X1(k)+ W˛N˛^k · X2(k) , N/2-1>n>0

X**(k)=X1(k)- W˛N˛^k · X2(k) , N-1>n>N/2

Необходимо получить на выходе спектральные отсчеты для частот 0…7.

Верхнее направление стрелки обозначает сумму, направление вниз – разность.

На последнем этапе алгоритма 8-ми точечного ДПФ 4 операции умножения.

P = N/2(log₂N) – количество умножений

N=8 Þ P=12

N=1024 Þ P=5120