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


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

Пряме перетворення:

X_k = \ sum_ {n = 0} ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N} kn} \ qquad k = 0, \ dots, N-1

Зворотне перетворення:

x_n = \ frac {1} {N} \ sum_ {k = 0} ^ {N-1} X_k e ^ {\ frac {2 \ pi i} {N} kn} \ quad \ quad n = 0, \ dots , N-1.

Позначення:

  • N - Кількість значень сигналу, виміряних за період, а також кількість компонент розкладу;
  • x_n, \ quad n = 0, \ dots, N-1, - Виміряні значення сигналу (в дискретних тимчасових точках з номерами n = 0, \ dots, N-1 , Які є вхідними даними для прямого перетворення і вихідними для зворотного;
  • X_k, \ quad k = 0, \ dots, N-1, - Nкомплексних амплітуд синусоїдальних сигналів, що складають вихідний сигнал; є вихідними даними для прямого перетворення і вхідними для зворотного; оскільки амплітуди комплексні, то по них можна обчислити одночасно і амплітуду, і фазу;
  • | X_k | \ over N - Звичайна (речова) амплітуда k-го синусоїдального сигналу;
  • k - Індекс частоти. Частота k-го сигналу дорівнює \ Frac {k} {T} , Де T - Період часу, протягом якого бралися вхідні дані.

З останнього видно, що перетворення розкладає сигнал на синусоїдальні складові (які називаються гармоніками) з частотами від N коливань за період до одного коливання за період. Оскільки частота дискретизації сама по собі дорівнює N відліків за період, то високочастотні складові не можуть бути коректно відображені - виникає муаровий ефект. Це призводить до того, що друга половина з N комплексних амплітуд, фактично, є дзеркальним відображенням першої та не несе додаткової інформації.


2. Висновок перетворення

Розглянемо деякий періодичний сигнал x (t) c періодом рівним T. Розкладемо його в ряд Фур'є :

x (t) = \ sum_ {k = - \ infty} ^ {+ \ infty} c_k e ^ {i \ omega_k t}, \ qquad \ omega_k = \ frac {2 \ pi k} {T}

Проведемо дискретизацію сигналу так, щоб на періоді було N відліків. Дискретний сигнал представимо у вигляді відліків: x_n = x (t_n) , Де t_n = \ frac nN T , Тоді ці відліки через ряд Фур'є запишуться наступним чином:

x_n = \ sum_ {k = - \ infty} ^ {+ \ infty} c_k e ^ {i \ omega_k t_n} = \ sum_ {k = - \ infty} ^ {+ \ infty} c_k e ^ {\ frac {2 \ pi i} {N} kn}

Використовуючи співвідношення: e ^ {\ frac {2 \ pi i} {N} \ left (k + mN \ right) n} = e ^ {\ frac {2 \ pi i} {N} kn} , Отримуємо:

x_n = \ sum_ {k = 0} ^ {N-1} X_k e ^ {\ frac {2 \ pi i} {N} kn}, де \ Qquad X_k = \ sum_ {l = - \ infty} ^ {+ \ infty} c_ {k + lN}

Таким чином ми отримали зворотне дискретне перетворення Фур'є.

Помножимо тепер скалярно вираз для x_n на e ^ {- \ frac {2 \ pi i} {N} mn} і отримаємо:

\ Sum_ {n = 0} ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N} mn} = \ sum_ {k = 0} ^ {N-1} \ sum_ {n = 0} ^ {N-1} X_k e ^ {\ frac {2 \ pi i} {N} (km) n} = \ sum_ {k = 0} ^ {N-1} X_k \ frac {1-e ^ {2 \ pi i (km)}} {1-e ^ {\ frac {2 \ pi i (km)} {N}}} = \ sum_ {k = 0} ^ {N-1} X_k N \ delta_ {km}

Тут використані: а) вираз для суми кінцевого числа членів (експонент) геометричній прогресії, і б) вираження символу Кронекера як межі відносини функцій Ейлера для комплексних чисел. Звідси випливає, що:

X_k = \ frac 1N \ sum_ {n = 0} ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N} kn}

Ця формула описує пряме дискретне перетворення Фур'є.

У літературі прийнято писати множник \ Frac {1} {N} в зворотному перетворенні, і тому зазвичай пишуть формули перетворення в наступному вигляді:

X_k = \ sum_ {n = 0} ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N} kn}, \ qquad x_n = \ frac 1N \ sum_ {k = 0} ^ { N-1} X_k e ^ {\ frac {2 \ pi i} {N} kn}

3. Матричне уявлення

Дискретне перетворення Фур'є є лінійним перетворенням, яке переводить вектор часових відліків \ Vec x в вектор спектральних відліків тієї ж довжини. Таким чином перетворення може бути реалізовано як множення квадратної матриці на вектор:

\ Vec X = \ hat A \ vec x

матриця А має вигляд:

\ Hat A = \ begin {pmatrix} 1 & 1 & 1 & 1 & \ ldots & 1 \ \ 1 & e ^ {- \ frac {2 \ pi i} {N}} & e ^ {- \ frac {4 \ pi i} {N }} & e ^ {- \ frac {6 \ pi i} {N}} & \ ldots & e ^ {- \ frac {2 \ pi i} {N} (N-1)} \ \ 1 & e ^ {- \ frac {4 \ pi i} {N}} & e ^ {- \ frac {8 \ pi i} {N}} & e ^ {- \ frac {12 \ pi i} {N}} & \ ldots & e ^ {- \ frac {2 \ pi i} {N} 2 (N-1)} \ \ 1 & e ^ {- \ frac {6 \ pi i} {N}} & e ^ {- \ frac {12 \ pi i} { N}} & e ^ {- \ frac {18 \ pi i} {N}} & \ ldots & e ^ {- \ frac {2 \ pi i} {N} 3 (N-1)} \ \ \ vdots & \ vdots & \ vdots & \ vdots & \ ddots & \ vdots \ \ 1 & e ^ {- \ frac {2 \ pi i} {N} (N-1)} & e ^ {- \ frac {2 \ pi i} { N} 2 (N-1)} & e ^ {- \ frac {2 \ pi i} {N} 3 (N-1)} & \ ldots & e ^ {- \ frac {2 \ pi i} {N} ( N-1) ^ 2} \ end {pmatrix}

Елементи матриці задаються наступною формулою:

A (m, n) = \ exp \ left (-2 \ pi i \ frac {(m-1) (n-1)} {N} \ right)

4. Властивості

  1. лінійність
    {Ax (n) + by (n)} \ longleftrightarrow {aX (k) + bY (k)}
  2. зсув по часу
    {X (nm)} \ longleftrightarrow X (k) e ^ {- \ frac {2 \ pi i} {N} km}
  3. періодичність
    X (k + rN) = X (k), r \ in \ mathbb Z
  4. виконується Теорема Парсеваля
  5. володіє спектральною щільністю
    S (k) = | X (k) | ^ 2
  6. x (n) \ in \ mathbb R
    X (0) \ in \ mathbb R
    N \ mod 2 = 0 \ Rightarrow X (N / 2) \ in \ mathbb R
    Варто відзначити, що нульова гармоніка є сумою значень сигналу.

Література

  • Сергієнко А. Б. Цифрова обробка сигналів. - 2-е. - Спб: Пітер, 2006. - С. 751. - ISBN 5-469-00816-9
  • М. А. Павлейно, В. М. Ромаданов Спектральні перетворення в MatLab. - СПб, 2007. - С. 160. - ISBN 978-5-98340-121-1