Diszkrét Fourier transzformáció

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 22-én felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A Discrete Fourier Transform (az angol szakirodalomban DFT , Discrete Fourier Transform ) a digitális jelfeldolgozó algoritmusokban széles körben használt Fourier-transzformációk egyike (módosításait használják MP3 -ban hangtömörítésben, JPEG -ben képtömörítésben stb.), valamint más területeken a diszkrét (például digitalizált analóg) jelek frekvenciáinak elemzésével kapcsolatos területek. A diszkrét Fourier-transzformáció bemenetként diszkrét függvényt igényel. Az ilyen funkciók gyakran diszkretizálással jönnek létre (értékek kiválasztása folyamatos függvényekből). A diszkrét Fourier-transzformációk segítenek megoldani a parciális differenciálegyenleteket és végrehajtani olyan műveleteket, mint a konvolúciók . A diszkrét Fourier-transzformációkat a statisztikákban, idősorok elemzésében is aktívan használják. Vannak többdimenziós diszkrét Fourier transzformációk [1] .

Képletek átalakítása

Közvetlen konverzió:

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

Fordított konverzió:

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

A kifejezés második része az elsőből következik az Euler-képlet szerint .

Megnevezések:

$N$ az időszak alatt mért jelértékek száma, valamint a bomlási összetevők száma;

$x_{n},\quad n=0,\dots ,N-1,$ - a jel mért értékei (diszkrét időpontokban számokkal ), amelyek bemeneti adatok a közvetlen átalakításhoz és kimeneti adatok a fordított átalakításhoz; $n = 0,\pontok,N-1$

$X_{k},\quad k=0,\dots ,N-1,$ - az eredeti jelet alkotó szinuszos jelek komplex amplitúdói ; kimeneti adatok a közvetlen transzformációhoz és bemeneti adatok a fordított átalakításhoz; mivel az amplitúdók összetettek, így az amplitúdó és a fázis egyszerre számítható ki belőlük; $N$

$|X_k| \N felett$ a szinuszos jel szokásos (valós) amplitúdója ; $k$

$\arg(X_k)$ a szinuszos jel fázisa ( egy komplex szám argumentuma ); $k$

$k$ a gyakorisági index. A -edik jel frekvenciája egyenlő a -val , ahol az az időtartam, amely alatt a bemenő adatokat vették. $k$ $\frac{k}{T}$ $T$

Ez utóbbiból látható, hogy a transzformáció a jelet szinuszos komponensekre bontja (ezeket harmonikusoknak nevezzük), amelyek frekvenciája a periódusonkénti oszcillációtól a periódusonkénti oszcillációig terjed (plusz egy állandó). Mivel maga a mintavételezési frekvencia megegyezik a periódusonkénti minták számával, a magas frekvenciájú komponensek nem jeleníthetők meg megfelelően – moaré effektus lép fel . Ez ahhoz a tényhez vezet, hogy a komplex amplitúdók második fele valójában az első tükörképe, és nem hordoz további információkat. $egy$ $N-1$ $N$ $N$

Konverziós kimenet

Tekintsünk néhány T-vel egyenlő periódusú periodikus jelet . Bővítsük ki Fourier-sorrá : $x(t)$

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

A jelet diszkretizáljuk úgy, hogy periódusonként N minta legyen. A diszkrét jelet leolvasások formájában ábrázoljuk: , ahol , akkor ezeket a Fourier-soron keresztüli leolvasásokat a következőképpen írjuk le: $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}.

Az arányt használva a következőket kapjuk: $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},

ahol

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

Így megkaptuk az inverz diszkrét Fourier transzformációt .

Most megszorozzuk a kifejezést skalárral , és megkapjuk: $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}.

Itt a következőket használjuk: a) egy geometriai progresszió véges számú tagjának (kitevőjének) összegének kifejezését, és b) a Kronecker-szimbólum kifejezését az Euler-függvények arányának határaként komplex számokra. Ebből az következik, hogy:

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

Ez a képlet a közvetlen diszkrét Fourier transzformációt írja le .

A szakirodalomban a szorzót inverz transzformációban szokás írni , ezért a transzformációs képleteket általában a következő formában írják fel: $\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}}\sum _{n=0}^{N-1}X_{n}e^{{\frac {2\pi i}{N}}mn}.

Néha megtalálhatja a transzformáció írásának szimmetrikus formáját

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}}}\sum _{n=0}^{N-1}X_{n}e ^{{\frac {2\pi i}{N}}mn}.

Mátrix ábrázolás

A diszkrét Fourier-transzformáció olyan lineáris transzformáció, amely az időminták vektorát azonos hosszúságú spektrális minták vektorává alakítja. Így a transzformáció megvalósítható egy szimmetrikus négyzetmátrix szorzataként egy vektorral: $\vec x$

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

mátrix így néz ki: ${\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}&\lpontok &\omega _{n}^{n-1}\\1&\omega _{n}^{2}&\omega _{ n}^{4}&\omega _{n}^{6}&\lpontok &\omega _{n}^{2(n-1)}\\1&\omega _{n}^{3}& \omega _{n}^{6}&\omega _{n}^{9}&\ldots &\omega _{n}^{3(n-1)}\\\vdots &\vdots &\vdots &\vpontok &\dpontok &\vpontok \\1&\omega _{n}^{n-1}&\omega _{n}^{2(n-1)}&\omega _{n}^{3 (n-1)}&\lpontok &\omega _{n}^{(n-1)^{2}}\end{pmátrix}}.}

A mátrix elemeit a következő képlet adja meg:

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

, hol .

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

A mátrix sajátértékei az egység negyedik fokú gyökei a , és a többszörösséggel , ahol a szám lefelé kerekítve . ${\megjelenítési stílus \{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 }$ $\lfloor x\rfloor$ $x$

Alkalmazás a számok szorzására

Egy vektor diszkrét Fourier-transzformációja úgy értelmezhető, mint a polinom értékeinek kiszámítása egységgyökökben , , , …, . $(a_{0};a_{1};\dots ;a_{n-1})$ ${\displaystyle p(x)=a_{0}+a_{1}x+\pontok +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))$

A pontokban lévő harmadfokú polinom értékei egyértelműen meghatározzák magát a polinomot. Ugyanakkor, ha és , akkor tehát a polinomok értékéből és a polinom ugyanazon pontjain lévő értékeket is meghatározhatjuk, és inverz diszkrét Fourier-transzformációval visszaállíthatjuk. $n$ $n+1$ $p(x)=a$ $q(x)=b$ $(p\cdot q)(x)=ab$ $p(x)$ $q(x)$ $p\cdot q$

Mivel bármely szám polinomként ábrázolható a számrendszer alapjából , két szám szorzása viszont redukálható két polinom szorzására és az eredmény normalizálására. $N=a_{n-1}\dots a_{1}a_{0}=a_{0}+a_{1}\cdot 10+\dots +a_{n-1}\cdot 10^{n -egy}$

Tulajdonságok

Linearitás
${ax(n)+by(n)}\longleftrightarrow {aX(k)+bY(k)}.$
Időeltolódás
${x(nm)}\longleftrightarrow X(k)e^{-{\frac {2\pi i}{N}}km}.$
Periodikaság
$X(k+rN)=X(k),r\in \mathbb {Z} .$
Parseval tétele teljesül .
Spektrális sűrűsége van
$S(k)=|X(k)|^{2}.$
$x(n)\in \mathbb {R} ,$
$X(0)\in \mathbb {R} ,$
$N\mod 2=0\Jobbra X(N/2)\in \mathbb {R} .$ A nulla harmonikus a jelértékek összege.

Lásd még

Irodalom

Sergienko AB Digitális jelfeldolgozás. - 2. - Szentpétervár. : Péter, 2006. - S. 751. - ISBN 5-469-00816-9 .
M. A. Pavleino, V. M. Romadanov. Spektrális transzformációk a MatLabban . - Szentpétervár. , 2007. - P. 160. - ISBN 978-5-98340-121-1 .

Robert J. Marks II. A Fourier-analízis és alkalmazásai kézikönyve . - Oxford: Oxford University Press, 2009. - P. 744. - ISBN 978-0-19-533532-7 .
Mehta M. L. A véges Fourier-transzformáció sajátértékei és sajátvektorai // J. Math. Phys. - AIP , 1986. - 1. évf. 28, Iss. 4. - P. 781-785. — ISSN 0022-2488 ; 1089-7658 ; 1527-2427 - doi:10,1063/1,527619

Jegyzetek

↑ Fedorenko S. V. – A Gretzel-Bleihut algoritmus módosítása A Wayback Machine 2022. március 24-i archív példánya . - Cikk. - Műszerészeti folyóirat. - UDC 621.391

Linkek

Diszkrét Fourier transzformáció (DFT) (holt link) . Letöltve: 2010. november 15. Az eredetiből archiválva : 2012. január 1.. (Orosz)

A diszkrét Fourier-transzformáció (DFT) tulajdonságai (holt kapcsolat) . Letöltve: 2010. november 15. Az eredetiből archiválva : 2012. május 8.. (Orosz)

Digitális jelfeldolgozás
Elmélet	Jel diszkrét jel Kotelnyikov tétele A statisztikai becslések elmélete Jelészlelési elmélet
alszakaszok	Digitális audiojel feldolgozás Az automatikus vezérlés elmélete Digitális képfeldolgozás Beszédfeldolgozás Statisztikai jelfeldolgozás
Technikák	Diszkrét Fourier transzformáció (DFT) Idő diszkrét Fourier transzformáció (DTFT) Impulzusválasz Bilineáris transzformáció Konzisztens Z-transzformáció Módosított Z-transzformáció
Mintavétel	Szupermintavétel almintavétel Felbontás csökkentése Felbontás növelése Aliasing szűrő Mintavételi gyakoriság Nyquist frekvencia