Дискретное преобразование Фурье


Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.

Формулы преобразований

Прямое преобразование:

X k = ∑ n = 0 N − 1 x n e − 2 π i N k n = ∑ n = 0 N − 1 x n ⋅ [ cos ⁡ ( 2 π k n / N ) − i ⋅ sin ⁡ ( 2 π k n / N ) ] , ( k = 0 , … , N − 1 ) . {displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-{frac {2pi i}{N}}kn}=sum _{n=0}^{N-1}x_{n}cdot [cos(2pi kn/N)-icdot sin(2pi kn/N)],qquad (k=0,dots ,N-1).}

Обратное преобразование:

x n = 1 N ∑ k = 0 N − 1 X k e 2 π i N k n = 1 N ∑ k = 0 N − 1 X k ⋅ [ cos ⁡ ( 2 π k n / N ) + i ⋅ sin ⁡ ( 2 π k n / N ) ] , ( n = 0 , … , N − 1 ) . {displaystyle x_{n}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}e^{{frac {2pi i}{N}}kn}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}cdot [cos(2pi kn/N)+icdot sin(2pi kn/N)],quad quad (n=0,dots ,N-1).}

Вторая часть выражения следует из первой по формуле Эйлера.

Обозначения:

  • N {displaystyle N} — количество значений сигнала, измеренных за период, а также количество компонент разложения;
  • x n , n = 0 , … , N − 1 , {displaystyle x_{n},quad n=0,dots ,N-1,} — измеренные значения сигнала (в дискретных временных точках с номерами n = 0 , … , N − 1 {displaystyle n=0,dots ,N-1} ), которые являются входными данными для прямого преобразования и выходными для обратного;
  • X k , k = 0 , … , N − 1 , {displaystyle X_{k},quad k=0,dots ,N-1,} — N {displaystyle N} комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;
  • | X k | N {displaystyle |X_{k}| over N} — обычная (вещественная) амплитуда k {displaystyle k} -го синусоидального сигнала;
  • arg ⁡ ( X k ) {displaystyle arg(X_{k})} — фаза k {displaystyle k} -го синусоидального сигнала (аргумент комплексного числа);
  • k {displaystyle k} — индекс частоты. Частота k {displaystyle k} -го сигнала равна k T {displaystyle {frac {k}{T}}} , где T {displaystyle T} — период времени, в течение которого брались входные данные.

Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от N {displaystyle N} колебаний за период до одного колебания за период. Поскольку частота дискретизации сама по себе равна N отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены — возникает муаровый эффект. Это приводит к тому, что вторая половина из N {displaystyle N} комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.

Вывод преобразования

Рассмотрим некоторый периодический сигнал x ( t ) {displaystyle x(t)} c периодом равным T. Разложим его в ряд Фурье:

x ( t ) = ∑ k = − ∞ + ∞ c k e i ω k t , ω k = 2 π k T . {displaystyle x(t)=sum _{k=-infty }^{+infty }c_{k}e^{iomega _{k}t},qquad omega _{k}={frac {2pi k}{T}}.}

Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: x n = x ( t n ) {displaystyle x_{n}=x(t_{n})} , где t n = n N T {displaystyle t_{n}={frac {n}{N}}T} , тогда эти отсчеты через ряд Фурье запишутся следующим образом:

x n = ∑ k = − ∞ + ∞ c k e i ω k t n = ∑ k = − ∞ + ∞ c k e 2 π i N k n . {displaystyle x_{n}=sum _{k=-infty }^{+infty }c_{k}e^{iomega _{k}t_{n}}=sum _{k=-infty }^{+infty }c_{k}e^{{frac {2pi i}{N}}kn}.}

Используя соотношение: e 2 π i N ( k + m N ) n = e 2 π i N k n {displaystyle e^{{frac {2pi i}{N}}left(k+mN ight)n}=e^{{frac {2pi i}{N}}kn}} , получаем:

x n = ∑ k = 0 N − 1 X k e 2 π i N k n , {displaystyle x_{n}=sum _{k=0}^{N-1}X_{k}e^{{frac {2pi i}{N}}kn},} где X k = ∑ l = − ∞ + ∞ c k + l N . {displaystyle qquad X_{k}=sum _{l=-infty }^{+infty }c_{k+lN}.}

Таким образом мы получили обратное дискретное преобразование Фурье.

Умножим теперь скалярно выражение для x n {displaystyle x_{n}} на e − 2 π i N m n {displaystyle e^{-{frac {2pi i}{N}}mn}} и получим:

∑ n = 0 N − 1 x n e − 2 π i N m n = ∑ k = 0 N − 1 ∑ n = 0 N − 1 X k e 2 π i N ( k − m ) n = ∑ k = 0 N − 1 X k 1 − e 2 π i ( k − m ) 1 − e 2 π i ( k − m ) N = ∑ k = 0 N − 1 X k N δ k m . {displaystyle sum _{n=0}^{N-1}x_{n}e^{-{frac {2pi i}{N}}mn}=sum _{k=0}^{N-1}sum _{n=0}^{N-1}X_{k}e^{{frac {2pi i}{N}}(k-m)n}=sum _{k=0}^{N-1}X_{k}{frac {1-e^{2pi i(k-m)}}{1-e^{frac {2pi i(k-m)}{N}}}}=sum _{k=0}^{N-1}X_{k}Ndelta _{km}.}

Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:

X k = 1 N ∑ n = 0 N − 1 x n e − 2 π i N k n . {displaystyle X_{k}={frac {1}{N}}sum _{n=0}^{N-1}x_{n}e^{-{frac {2pi i}{N}}kn}.}

Эта формула описывает прямое дискретное преобразование Фурье.

В литературе принято писать множитель 1 N {displaystyle {frac {1}{N}}} в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:

X n = ∑ m = 0 N − 1 x m e − 2 π i N n m , x m = 1 N ∑ n = 0 N − 1 X n e 2 π i N m n . {displaystyle X_{n}=sum _{m=0}^{N-1}x_{m}e^{-{frac {2pi i}{N}}nm},qquad x_{m}={frac {1}{N}}sum _{n=0}^{N-1}X_{n}e^{{frac {2pi i}{N}}mn}.}

Иногда можно встретить симметричную форму записи преобразования

X n = 1 N ∑ m = 0 N − 1 x m e − 2 π i N n m , x m = 1 N ∑ n = 0 N − 1 X n e 2 π i N m n . {displaystyle X_{n}={frac {1}{sqrt {N}}}sum _{m=0}^{N-1}x_{m}e^{-{frac {2pi i}{N}}nm},qquad x_{m}={frac {1}{sqrt {N}}}sum _{n=0}^{N-1}X_{n}e^{{frac {2pi i}{N}}mn}.}

Матричное представление

Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов x → {displaystyle {vec {x}}} в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор:

X → = A ^ x → , {displaystyle {vec {X}}={hat {A}}{vec {x}},}

матрица A ^ {displaystyle {hat {A}}} имеет вид:

A ^ = ( 1 1 1 1 … 1 1 e − 2 π i N e − 4 π i N e − 6 π i N … e − 2 π i N ( N − 1 ) 1 e − 4 π i N e − 8 π i N e − 12 π i N … e − 2 π i N 2 ( N − 1 ) 1 e − 6 π i N e − 12 π i N e − 18 π i N … e − 2 π i N 3 ( N − 1 ) ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ 1 e − 2 π i N ( N − 1 ) e − 2 π i N 2 ( N − 1 ) e − 2 π i N 3 ( N − 1 ) … e − 2 π i N ( N − 1 ) 2 ) . {displaystyle {hat {A}}={egin{pmatrix}1&1&1&1&ldots &11&e^{-{frac {2pi i}{N}}}&e^{-{frac {4pi i}{N}}}&e^{-{frac {6pi i}{N}}}&ldots &e^{-{frac {2pi i}{N}}(N-1)}1&e^{-{frac {4pi i}{N}}}&e^{-{frac {8pi i}{N}}}&e^{-{frac {12pi i}{N}}}&ldots &e^{-{frac {2pi i}{N}}2(N-1)}1&e^{-{frac {6pi i}{N}}}&e^{-{frac {12pi i}{N}}}&e^{-{frac {18pi i}{N}}}&ldots &e^{-{frac {2pi i}{N}}3(N-1)}vdots &vdots &vdots &vdots &ddots &vdots 1&e^{-{frac {2pi i}{N}}(N-1)}&e^{-{frac {2pi i}{N}}2(N-1)}&e^{-{frac {2pi i}{N}}3(N-1)}&ldots &e^{-{frac {2pi i}{N}}(N-1)^{2}}end{pmatrix}}.}

Элементы матрицы задаются следующей формулой:

A ( m , n ) = exp ⁡ ( − 2 π i ( m − 1 ) ( n − 1 ) N ) . {displaystyle A(m,n)=exp left(-2pi i{frac {(m-1)(n-1)}{N}} ight).}

Свойства

  • Линейность
    a x ( n ) + b y ( n ) ⟷ a X ( k ) + b Y ( k ) . {displaystyle {ax(n)+by(n)}longleftrightarrow {aX(k)+bY(k)}.}
  • Сдвиг по времени
    x ( n − m ) ⟷ X ( k ) e − 2 π i N k m . {displaystyle {x(n-m)}longleftrightarrow X(k)e^{-{frac {2pi i}{N}}km}.}
  • Периодичность
    X ( k + r N ) = X ( k ) , r ∈ Z . {displaystyle X(k+rN)=X(k),rin mathbb {Z} .}
  • Выполняется Теорема Парсеваля.
  • Обладает спектральной плотностью
    S ( k ) = | X ( k ) | 2 . {displaystyle S(k)=|X(k)|^{2}.}
  • x ( n ) ∈ R , {displaystyle x(n)in mathbb {R} ,}
    X ( 0 ) ∈ R , {displaystyle X(0)in mathbb {R} ,}
    N mod 2 = 0 ⇒ X ( N / 2 ) ∈ R . {displaystyle Nmod 2=0Rightarrow X(N/2)in mathbb {R} .} Нулевая гармоника является суммой значений сигнала.

  • Танеев, Владимир Иванович
  • Теорема Нётер
  • Закон Ньютона — Рихмана
  • Канал связи
  • Базовая работа с веб-документом на основе html5 для начинающих веб-мастеров

  •  

    • Яндекс.Метрика
    • Индекс цитирования