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

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

Формули перетворень

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

$X(f)=\underset{-\mathrm{\infty }}{\overset{+\mathrm{\infty }}{\int }}x(t)e^{-j2\pi ft}dt$

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

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

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

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

Позначення:

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

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

$X(m)=X_{re}(m)+j{X}_{im}(m)=X_{mag}$ з кутом $X_{\varphi }(m)$,

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

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

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

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

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

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

Властивості

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

Приклад обчислення

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

$𝐱=\left(\begin{array}{c}{x}_0\\ x_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}1\\ 2-i\\ -i\\ -1+2i\end{array}\right).$

Обчислимо ДПФ $𝐱$ за допомогою експоненциальної форми:

$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$ $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$ $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$ $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$

що дає $𝐗=\left(\begin{array}{c}{X}_0\\ X_1\\ X_2\\ X_3\end{array}\right)=\left(\begin{array}{c}2\\ -2-2i\\ -2i\\ 4+4i\end{array}\right).$

Приклад програми

Нижче подано приклад функції обчислення ДПФ на мові програмування 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;
      }
}

Див. також

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

Джерела

• Шаблон:Фіхтенгольц.укр
• Шаблон:Книга
• Шаблон:Книга

Посилання

• Дискретне перетворення Фур'є Шаблон:WebarchiveШаблон:Ref-ru
• Властивості дискретного перетворення Фур'є Шаблон:WebarchiveШаблон:Ref-ru
• Реалізація дискретного перетворення Фур'є на процесорі TMS320C55x фірми Texas Instruments Шаблон:WebarchiveШаблон:Ref-uk
• Аналіз спектру сигналів Шаблон:Webarchive