Дискретне перетворення Фур'є — Вікіпедія

Дискретне перетворення Фур'є (ДПФ, англ. Discrete Fourier Transform) — це математична процедура, що використовується для визначення гармонічного, або частотного, складу дискретних сигналів. ДПФ є однією з найбільш розповсюджених і потужних процедур цифрової обробки сигналів. ДПФ дозволяє аналізувати, перетворювати і синтезувати сигнали такими способами, які неможливі при неперервній (аналоговій) обробці.

Формули перетворень[ред. | ред. код]

Витоком ДПФ є неперервне перетворення Фур'є ${\displaystyle X(f)}$ , яке визначається:

${\displaystyle X(f)=\int _{-\infty }^{+\infty }x(t)e^{-j2\pi ft}\,dt}$

Експоненціальна форма:

${\displaystyle X(m)=\sum _{n=0}^{N-1}x(n)e^{-j2\pi nm/N}}$

Тригонометрична форма:

${\displaystyle X(m)=\sum _{n=0}^{N-1}x(n)(\cos(2\pi nm/N)-j\sin(2\pi nm/N))}$

Позначення:

• ${\displaystyle X(m)}$ — ${\displaystyle m}$-ий компонент ДПФ, тобто ${\displaystyle X(0),X(1),X(2),...}$,
• ${\displaystyle m}$ — індекс ДПФ в частотній області, ${\displaystyle m=0,1,2,3,...,N-1}$,
• ${\displaystyle x(n)}$ — послідовність вхідних відліків, ${\displaystyle x(0),x(1),x(2),...}$,
• ${\displaystyle n}$ — часовий індекс вхідних відліків, ${\displaystyle n=0,1,2,3,...,N-1}$,
• ${\displaystyle N}$ — кількість відліків вхідної послідовності і кількість частотних відліків результату ДПФ.

Якщо представити довільний відлік ДПФ ${\displaystyle X(m)}$ як суму дійсних і уявних частин:

${\displaystyle X(m)=X_{re}(m)+jX_{im}(m)=X_{mag}}$ з кутом ${\displaystyle X_{\phi }(m)}$,

то амплітуда ${\displaystyle X(m)}$ обчислюється:

${\displaystyle X_{mag}(m)=|X(m)|={\sqrt {X_{re}(m)^{2}+X_{im}(m)^{2}}}}$

Фазовий кут ${\displaystyle X(m)}$, ${\displaystyle X_{\phi }(m)}$, обчислюється так:

${\displaystyle X_{\phi }(m)=\tan ^{-1}(X_{im}(m)/X_{mag}(m))}$

Потужність відліків ${\displaystyle X(m)}$, яка називається спектром потужності, являє собою амплітуду, піднесену до квадрату:

${\displaystyle X_{PS}(m)=X_{mag}(m)^{2}=X_{re}(m)^{2}+X_{im}(m)^{2}}$

Властивості[ред. | ред. код]

1. Симетрія
   ${\displaystyle X(N-m)=\sum _{n=0}^{N-1}x(n)e^{-j2\pi nm/N}}$
2. Лінійність
   Якщо вхідна послідовність ${\displaystyle x_{1}(n)}$ має ДПФ ${\displaystyle X_{1}(m)}$, а інша вхідна послідовність ${\displaystyle x_{2}(n)}$ має ДПФ ${\displaystyle X_{2}(m)}$, то ДПФ суми цих послідовностей ${\displaystyle x_{sum}(n)=x_{1}(n)+x_{2}(n)}$ рівна: ${\displaystyle X_{sum}(m)=X_{1}(m)+X_{2}(m)}$
3. Зсув в часі
   ${\displaystyle X_{shifted}(m)=e^{j2\pi km/N}X(m)}$

Приклад обчислення[ред. | ред. код]

У цьому прикладі ДПФ застосовується до послідовності довжиною ${\displaystyle N=4}$, а саме, до вхідного вектора

${\displaystyle \mathbf {x} ={\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}1\\2-i\\-i\\-1+2i\end{pmatrix}}.}$

Обчислимо ДПФ ${\displaystyle \mathbf {x} }$ за допомогою експоненциальної форми:

${\displaystyle X_{0}=e^{-i2\pi 0\cdot 0/4}\cdot 1+e^{-i2\pi 0\cdot 1/4}\cdot (2-i)+e^{-i2\pi 0\cdot 2/4}\cdot (-i)+e^{-i2\pi 0\cdot 3/4}\cdot (-1+2i)=2}$ ${\displaystyle X_{1}=e^{-i2\pi 1\cdot 0/4}\cdot 1+e^{-i2\pi 1\cdot 1/4}\cdot (2-i)+e^{-i2\pi 1\cdot 2/4}\cdot (-i)+e^{-i2\pi 1\cdot 3/4}\cdot (-1+2i)=-2-2i}$ ${\displaystyle X_{2}=e^{-i2\pi 2\cdot 0/4}\cdot 1+e^{-i2\pi 2\cdot 1/4}\cdot (2-i)+e^{-i2\pi 2\cdot 2/4}\cdot (-i)+e^{-i2\pi 2\cdot 3/4}\cdot (-1+2i)=-2i}$ ${\displaystyle X_{3}=e^{-i2\pi 3\cdot 0/4}\cdot 1+e^{-i2\pi 3\cdot 1/4}\cdot (2-i)+e^{-i2\pi 3\cdot 2/4}\cdot (-i)+e^{-i2\pi 3\cdot 3/4}\cdot (-1+2i)=4+4i}$

що дає ${\displaystyle \mathbf {X} ={\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}2\\-2-2i\\-2i\\4+4i\end{pmatrix}}.}$

Приклад програми[ред. | ред. код]

Нижче подано приклад функції обчислення ДПФ на мові програмування C#

// Структура комлексних чисел public struct Complex {     public double Re;     public double Im;     public Complex(double Re, double Im)     {         this.Re = Re;         this.Im = Im;     } } public double Sqr(double x) {      return x*x; } // x - послідовність вхідних відліків // X - послідовність вихідних відліків // AS - спектр амплітуд // FS - спектр фаз // PS - спектр потужностей // N - кількість відліків public void DFT(double[] x, ref Complex[] X, ref double[] AS, ref double[] FS, ref double[] PS, int N) {     Complex S = new Complex();     Complex[] XC = new Complex[N];     int k, n;     for (k = 0; k < N; k++)     {          S.Re = 0.0;          S.Im = 0.0;          for (n = 0; n < N; n++)          {               S.Re += x[n] * Math.Cos(2 * Math.PI * k * n / N);               S.Im -= x[n] * Math.Sin(2 * Math.PI * k * n / N);          }          X[k].Re = S.Re;          X[k].Im = S.Im;      }      for (k = 0; k < N; k++)      {           AS[k] = Math.Sqrt(Sqr(X[k].Re) + Sqr(X[k].Im)) / (N / 2);           PS[k] = X[k].Re * X[k].Re + X[k].Im * X[k].Im;           if (Math.Abs(X[k].Re) < 1e-5)           {                if (X[k].Im > 1e-5)                    FS[k] = 90;                if (Math.Abs(X[k].Im) < 1e-5)                    FS[k] = 0;                if ((X[k].Im < 0) && (Math.Abs(X[k].Im) > 1e-5))                    FS[k] = -90;            }            else                FS[k] = Math.Atan2(X[k].Im, X[k].Re) * 180.0 / Math.PI;       } } 

Див. також[ред. | ред. код]

• Ряд Фур'є
• Швидке перетворення Фур'є

Джерела[ред. | ред. код]

• Ричард Лайонс. Цифровая обработка сигналов. — 2-е. — Москва : Бином, 2006. — 656 с. — ISBN 5-9518-0149-4.
• Сергиенко А. Б. Цифровая обработка сигналов. — 2-е. — Спб : Питер, 2006. — 751 с. — ISBN 5-318-00666-3.

Посилання[ред. | ред. код]

• Дискретне перетворення Фур'є [Архівовано 24 червня 2012 у Wayback Machine.](рос.)
• Властивості дискретного перетворення Фур'є [Архівовано 26 серпня 2021 у Wayback Machine.](рос.)
• Реалізація дискретного перетворення Фур'є на процесорі TMS320C55x фірми Texas Instruments [Архівовано 1 травня 2013 у Wayback Machine.](укр.)
• Аналіз спектру сигналів [Архівовано 8 лютого 2015 у Wayback Machine.]