Dyskretna transformata Fouriera

Dyskretna transformata Fouriera (DFT z ang. Discrete Fourier Transform) jest transformatą Fouriera wyznaczoną dla sygnału próbkowanego, a więc dyskretnego.

DFT przekształca skończony ciąg próbek sygnału $(a_{0}, a_{1}, a_{2},\dots, a_{N-1}), \ a_{i}\in\mathbb{R}$ w ciąg harmonicznych $(A_{0}, A_{1}, A_{2},\dots, A_{N-1}), \ A_{i}\in\mathbb{C}$ zgodnie ze wzorem:

$A_{k}=\sum_{n=0}^{N-1}{a_{n}w_{N}^{-kn}}, \ 0 \leqslant k \leqslant N-1$

Próbkowanie (dyskretyzacja, kwantowanie w czasie) - proces tworzenia sygnału dyskretnego, reprezentującego sygnał ciągły za pomocą ciągu wartości nazywanych próbkami. Zwykle jest jednym z etapów przetwarzania sygnału analogowego na cyfrowy.

Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.

$w_{N}=e^{i\frac{2\pi}{N}}$

gdzie:

$i$ - jednostka urojona, $k$ - numer harmonicznej, $n$ - numer próbki sygnału, $a_{n}$ - wartość próbki sygnału, $N$ - liczba próbek.

Przekształcenie odwrotne

Przekształcenie odwrotne do DFT dane jest następującym wzorem:

$a_{n}=\frac{1}{N}\sum_{k=0}^{N-1}{A_{k}w_{N}^{kn}}, \ 0 \leqslant n \leqslant N-1$

Postać macierzowa DFT

Wzory na przekształcenie proste, jak i odwrotne można zdefiniować w postaci macierzowej, odpowiednio w sposób następujący:

$\mathbf{A}=\mathbf{Ma}$

Szybka transformacja Fouriera (ang. FFT od Fast Fourier Transform) to algorytm liczenia dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.

Matematyka dyskretna - zbiorcza nazwa wszystkich działów matematyki, które zajmują się badaniem struktur nieciągłych, to znaczy zawierających zbiory co najwyżej przeliczalne (czyli właśnie dyskretne).

$\mathbf{a}=\mathbf{WA}$

Macierze $a$ , $A$ , $M$ , $W$ mają następującą postać:

$\mathbf{a}=\left[\begin{matrix} a_{0} \\ a_{1} \\ \vdots \\ a_{N-1} \end{matrix}\right]$ $\mathbf{A}=\left[\begin{matrix} A_{0} \\ A_{1} \\ \vdots \\ A_{N-1} \end{matrix}\right]$

$\mathbf{M}=\left[\begin{matrix} w_{N}^{-0\cdot 0} & w_{N}^{-1\cdot 0} & \dots & w_{N}^{-(N-1)\cdot 0} \\ w_{N}^{-0\cdot 1} & w_{N}^{-1\cdot 1} & \dots & w_{N}^{-(N-1)\cdot 1} \\ \vdots & \vdots & \ddots & \vdots \\ w_{N}^{-0\cdot (N-1)} & w_{N}^{-1\cdot (N-1)} & \dots & w_{N}^{-(N-1)(N-1)} \end{matrix}\right]$ $\mathbf{W}=\frac{1}{N}\left[\begin{matrix} w_{N}^{0\cdot 0} & w_{N}^{1\cdot 0} & \dots & w_{N}^{(N-1)\cdot 0} \\ w_{N}^{0\cdot 1} & w_{N}^{1\cdot 1} & \dots & w_{N}^{(N-1)\cdot 1} \\ \vdots & \vdots & \ddots & \vdots \\ w_{N}^{0\cdot (N-1)} & w_{N}^{1\cdot (N-1)} & \dots & w_{N}^{(N-1)(N-1)} \end{matrix}\right]$

Macierze $M$ i $W$ mają wymiar $N$ x $N$ oraz spełniają warunek $W=M^{-1}$ lub zapisując inaczej $WM=I$ , gdzie $I$ - macierz jednostkowa.

Dwuwymiarowa dyskretna transformata Fouriera

Dwuwymiarowe przekształcenie Fouriera w punkcie $(m,n)$ definiujemy jako:

$V(m,n)=\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}{U(x,y)w_{N}^{-ny}w_{M}^{-mx}}$

DCT (ang. discrete cosine transform, czyli dyskretna transformacja kosinusowa) - jedna z najpopularniejszych blokowych transformacji danych. Jest szczególnie popularna w stratnej kompresji danych.

Składowa harmoniczna jest pojęciem często używanym w teorii sygnałów. Jest to składowa szeregu Fouriera analizowanego sygnału (poza składową zerową zwaną składową stałą). Składowa harmoniczna jest częścią reprezentacji sygnału w dziedzinie widmowej (częstotliwości).

Przekształcenie odwrotne:

$U(x,y)=\frac{1}{N M}\sum_{n=0}^{N-1}\sum_{m=0}^{M-1}{V(m,n)w_{N}^{ny}w_{M}^{mx}}$

Dwuwymiarowa transformata Fouriera wykorzystywana jest m.in. do cyfrowego przetwarzania obrazów.

Powiązanie z transformatą Z

Transformata Z stanowi uogólnienie dyskretnej transformaty Fouriera. Dyskretna transformata Fouriera może być określona przez określenie wartości transformaty Z $X(z)\,$ dla $z=e^{j\omega}\,$

lub innymi słowy określenie jej wartości na okręgu jednostkowym. Aby określić charakterystykę częstotliwościową układu wartość transformaty Z musi być określona na okręgu jednostkowym, co oznacza, że obszar zbieżności układu musi zawierać okrąg jednostkowy. W przeciwnym przypadku dyskretna transformata Fouriera nie istnieje.

Jednostka, jedność urojona (łac. imaginarius, urojony, zmyślony) – w matematyce pewna ustalona liczba zespolona oznaczana zwykle literą i (czasami również j), która spełnia równanie

Macierz – w matematyce układ liczb, symboli lub wyrażeń zapisanych w postaci prostokątnej tablicy. Choć słowo „macierz” oznacza najczęściej macierz dwuwskaźnikową, to możliwe jest rozpatrywanie macierzy wielowskaźnikowych (zob. notacja wielowskaźnikowa). Macierze jednowskaźnikowe nazywa się często wektorami wierszowymi lub kolumnowymi, co wynika z zastosowań macierzy w algebrze liniowej. W informatyce macierze modeluje się zwykle za pomocą (najczęściej dwuwymiarowych) tablic.

Zobacz też

dyskretna transformata kosinusowa

szybka transformata Fouriera

cyfrowe przetwarzanie sygnałów

matematyka dyskretna