Diskrétní Fourierova transformace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. července 2021; kontroly vyžadují 6 úprav .

Diskrétní Fourierova transformace (v anglické literatuře DFT , Discrete Fourier Transform ) je jednou z Fourierových transformací široce používaných v algoritmech digitálního zpracování signálu (její modifikace se používají při kompresi zvuku v MP3 , kompresi obrazu v JPEG atd.), v jiných oblastech souvisejících s analýzou frekvencí v diskrétním (například digitalizovaném analogovém) signálu. Diskrétní Fourierova transformace vyžaduje jako vstup diskrétní funkci. Takové funkce jsou často vytvářeny diskretizací(výběry hodnot ze spojitých funkcí). Diskrétní Fourierovy transformace pomáhají řešit parciální diferenciální rovnice a provádět operace, jako jsou konvoluce . Diskrétní Fourierovy transformace se také aktivně používají ve statistice, při analýze časových řad. Existují vícerozměrné diskrétní Fourierovy transformace [1] .

Transformujte vzorce

Přímá konverze:

X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}=\sum _{ n=0}^{N-1}x_{n}{\Velký (}\cos(2\pi kn/N)-i\cdot \sin(2\pi kn/N){\Velký )},\ qquad k=0,\tečky ,N-1.

Zpětná konverze:

x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{{\frac {2\pi i}{N }}kn}={\frac {1}{N}}\součet _{k=0}^{N-1}X_{k}{\Velký (}\cos(2\pi kn/N)+i \cdot \sin(2\pi kn/N){\Big )},\qquad n=0,\tečky ,N-1.

Druhá část výrazu vyplývá z první podle Eulerova vzorce .

Označení:

$N$ je počet hodnot signálu naměřených za dané období a také počet složek rozkladu;

$x_{n},\quad n=0,\dots ,N-1,$ - naměřené hodnoty signálu (v diskrétních časových bodech s čísly ), které jsou vstupními daty pro přímý převod a výstupními daty pro zpětný chod; $n = 0,\tečky,N-1$

$X_{k},\quad k=0,\tečky ,N-1,$ - komplexní amplitudy sinusových signálů, které tvoří původní signál; jsou výstupní data pro přímou transformaci a vstupní data pro reverzní; protože amplitudy jsou komplexní, lze z nich současně vypočítat amplitudu i fázi; $N$

$|X_k| \přes N$ je obvyklá (skutečná) amplituda tého sinusového signálu; $k$

$\arg(X_k)$ je fáze t. sinusového signálu ( argument komplexního čísla ); $k$

$k$ je frekvenční index. Frekvence -tého signálu je rovna , kde je časový úsek, během kterého byla vstupní data sbírána. $k$ $\frac{k}{T}$ $T$

Z posledně jmenovaného je vidět, že transformace rozloží signál na sinusové složky (které se nazývají harmonické) s frekvencemi od oscilací za periodu po oscilace za periodu (plus konstanta). Protože samotná vzorkovací frekvence je rovna vzorkům za periodu, nelze vysokofrekvenční složky zobrazit správně - dochází k moaré efektu . To vede k tomu, že druhá polovina komplexních amplitud je ve skutečnosti zrcadlovým obrazem první a nenese další informace. $jeden$ $N-1$ $N$ $N$

Konverzní výstup

Uvažujme nějaký periodický signál s periodou rovnou T. Rozšiřme jej na Fourierovu řadu : $x(t)$

x(t)=\sum _{k=-\infty }^{+\infty }c_{k}e^{i\omega _{k}t},\qquad \omega _{k}= {\frac {2\pi k}{T}}.

Pojďme diskretizovat signál tak, aby bylo N vzorků na periodu. Diskrétní signál reprezentujeme ve formě odečtů: , kde , pak tyto odečty přes Fourierovu řadu budou zapsány následovně: $x_n = x(t_n)$ $t_n = \frac nN T$

x_{n}=\sum _{k=-\infty }^{+\infty }c_{k}e^{i\omega _{k}t_{n))=\součet _{k= -\infty }^{+\infty }c_{k}e^{{\frac {2\pi i}{N}}kn}.

Pomocí poměru dostaneme: $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},

kde

\qquad X_{k}=\sum _{l=-\infty }^{+\infty }c_{k+lN}.

Tak jsme získali inverzní diskrétní Fourierovu transformaci .

Nyní vynásobíme výraz pro skalárně a dostaneme: $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}\součet _{n=0}^{N-1}X_{k}e^{{\frac {2\pi i}{N}}(km)n}=\součet _{k =0}^{N-1}X_{k}{\frac {1-e^{2\pi i(km)}}{1-e^{\frac {2\pi i(km)}{N }}}}=\součet _{k=0}^{N-1}X_{k}N\delta _{km}.

Zde použijeme: a) výraz pro součet konečného počtu členů (exponentů) geometrické posloupnosti a b) výraz pro Kroneckerův symbol jako limitu poměru Eulerových funkcí pro komplexní čísla. Z toho plyne, že:

X_{k}={\frac {1}{N}}\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{ N}}kn}.

Tento vzorec popisuje přímou diskrétní Fourierovu transformaci .

V literatuře je zvykem psát násobitel v inverzní transformaci, a proto se transformační vzorce obvykle zapisují v následujícím tvaru: $\frac{1}{N}$

X_{n}=\sum _{m=0}^{N-1}x_{m}e^{-{\frac {2\pi i}{N}}nm},\qquad x_{ m}={\frac {1}{N}}\součet _{n=0}^{N-1}X_{n}e^{{\frac {2\pi i}{N}}mn}.

Někdy můžete najít symetrickou formu zápisu transformace

X_{n}={\frac {1}{\sqrt {N}}}\sum _{m=0}^{N-1}x_{m}e^{-{\frac {2\ pi i}{N}}nm},\qquad x_{m}={\frac {1}{\sqrt {N}}}\součet _{n=0}^{N-1}X_{n}e ^{{\frac {2\pi i}{N}}mn}.

Maticová reprezentace

Diskrétní Fourierova transformace je lineární transformace, která převádí vektor časových vzorků na vektor spektrálních vzorků stejné délky. Transformaci lze tedy implementovat jako násobení symetrické čtvercové matice vektorem: $\vec x$

{\vec {X}}={\mathcal {F}}{\vec {x}},

matrice vypadá takto: ${\mathcal {F}}$

{\textstyle {\mathcal {F}}={\frac {1}{\sqrt {n}}}{\begin{pmatrix}1&1&1&1&\ldots &1\\1&\omega _{n}&\omega _{n }^{2}&\omega _{n}^{3}&\ldots &\omega _{n}^{n-1}\\1&\omega _{n}^{2}&\omega _{ n}^{4}&\omega _{n}^{6}&\ldots &\omega _{n}^{2(n-1)}\\1&\omega _{n}^{3}& \omega _{n}^{6}&\omega _{n}^{9}&\ldots &\omega _{n}^{3(n-1)}\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega _{n}^{n-1}&\omega _{n}^{2(n-1)}&\omega _{n}^{3 (n-1)}&\ldots &\omega _{n}^{(n-1)^{2}}\end{pmatrix}}.}

Prvky matice jsou dány následujícím vzorcem:

{\displaystyle {\mathcal {F}}(j,k)=\omega _{n}^{(j-1)(k-1)))

, kde .

{\displaystyle \omega _{n}=e^{-{\frac {2\pi i}{n))))

Vlastní čísla matice jsou kořeny čtvrtého stupně jednoty s násobností , a respektive , kde je číslo zaokrouhleno dolů . ${\displaystyle \{1,-1,i,-i\))$ ${\textstyle \lfloor {\frac {n+4}{4}}\rfloor }$ ${\textstyle \lfloor {\frac {n+2}{4}}\rfloor }$ ${\textstyle \lfloor {\frac {n+1}{4}}\rfloor }$ ${\textstyle \lfloor {\frac {n-1}{4}}\rfloor }$ $\lpatro x\rpatro$ $X$

Aplikace na násobení čísel

Diskrétní Fourierovu transformaci vektoru lze interpretovat jako výpočet hodnot polynomu v kořenech unity , , , …, . $(a_{0};a_{1};\dots ;a_{n-1})$ ${\displaystyle p(x)=a_{0}+a_{1}x+\tečky +a_{n-1}x^{n-1))$ $x_{0}=1$ ${\displaystyle x_{1}=\omega _{n))$ ${\displaystyle x_{2}=\omega _{n}^{2))$ ${\displaystyle x_{n-1}=\omega _{n}^{n-1))$

Hodnoty polynomu t. stupně v bodech jednoznačně určují samotný polynom. Současně, if a , tedy , tedy z hodnot polynomů a lze také určit hodnoty ve stejných bodech polynomu a obnovit je inverzní diskrétní Fourierovou transformací. $n$ $n+1$ $p(x)=a$ $q(x)=b$ $(p\cdot q)(x)=ab$ $p(x)$ $q(x)$ $p\cdot q$

Protože jakékoli číslo může být reprezentováno jako polynom ze základu číselné soustavy , násobení dvou čísel může být naopak redukováno na násobení dvou polynomů a normalizaci výsledku. $N=a_{n-1}\tečky a_{1}a_{0}=a_{0}+a_{1}\cdot 10+\tečky +a_{n-1}\cdot 10^{n -jeden}$

Vlastnosti

Linearita
${ax(n)+by(n)}\longleftrightarrow {aX(k)+bY(k)}.$
Časový posun
${x(nm)}\longleftrightarrow X(k)e^{-{\frac {2\pi i}{N}}km}.$
Periodicita
$X(k+rN)=X(k),r\in \mathbb {Z} .$
Parsevalův teorém je splněn .
Má spektrální hustotu
$S(k)=|X(k)|^{2}.$
$x(n)\in \mathbb {R} ,$
$X(0)\in \mathbb {R} ,$
$N\mod 2=0\Rightarrow X(N/2)\in \mathbb {R} .$ Nulová harmonická je součtem hodnot signálu.

Viz také

Literatura

Sergienko AB Digitální zpracování signálu. - 2. - Petrohrad. : Peter, 2006. - S. 751. - ISBN 5-469-00816-9 .
M. A. Pavleino, V. M. Romadanov. Spektrální transformace v MatLabu . - Petrohrad. , 2007. - S. 160. - ISBN 978-5-98340-121-1 .

Robert J. Marks II. Příručka Fourierovy analýzy a její aplikace . - Oxford: Oxford University Press, 2009. - S. 744. - ISBN 978-0-19-533532-7 .
Mehta M. L. Vlastní čísla a vlastní vektory konečné Fourierovy transformace // J. Math. Phys. - AIP , 1986. - Sv. 28, Iss. 4. - S. 781-785. — ISSN 0022-2488 ; 1089-7658 ; 1527-2427 – doi:10.1063/1.527619

Poznámky

↑ Fedorenko S. V. – Modifikace algoritmu Gretzel-Bleihut Archivní kopie z 24. března 2022 na Wayback Machine . - Článek. - Journal of Instrumentation. - MDT 621,391

Odkazy

Diskrétní Fourierova transformace (DFT) (mrtvý odkaz) . Získáno 15. listopadu 2010. Archivováno z originálu 1. ledna 2012. (Ruština)

Vlastnosti diskrétní Fourierovy transformace (DFT) (mrtvý odkaz) . Získáno 15. listopadu 2010. Archivováno z originálu 8. května 2012. (Ruština)

Zpracování digitálních signálů
Teorie	Signál diskrétní signál Kotelnikovova věta Teorie statistických odhadů Teorie detekce signálu
Pododdíly	Digitální zpracování audio signálu Teorie automatického řízení Digitální zpracování obrazu Zpracování řeči Statistické zpracování signálu
Techniky	Diskrétní Fourierova transformace (DFT) Časově diskrétní Fourierova transformace (DTFT) impulsní Bilineární transformace Konzistentní Z-transformace Upravená Z-transformace
Vzorkování	supersampling dílčí vzorkování Snížení rozlišení Zvýšení rozlišení Aliasing filtr Vzorkovací frekvence Nyquistova frekvence