Transformată Fourier discretă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 iulie 2021; verificările necesită 6 modificări .

Discrete Fourier Transform (în literatura engleză DFT , Discrete Fourier Transform ) este una dintre transformările Fourier utilizate pe scară largă în algoritmii de procesare a semnalului digital (modificările sale sunt utilizate în compresia audio în MP3 , compresia imaginii în JPEG etc.), precum și în alte domenii legate de analiza frecvențelor într-un semnal discret (de exemplu, analog digitizat). Transformata Fourier discretă necesită o funcție discretă ca intrare. Astfel de funcții sunt adesea create prin eșantionare (valori de eșantionare din funcții continue). Transformele Fourier discrete ajută la rezolvarea ecuațiilor diferențiale parțiale și la efectuarea de operații precum convoluțiile . Transformele Fourier discrete sunt folosite activ și în statistică, în analiza seriilor de timp. Există transformări Fourier discrete multidimensionale [1] .

Transformă formule

Conversie directă:

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,\dots ,N-1.

Conversie inversă:

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 doua parte a expresiei decurge din prima conform formulei lui Euler .

Denumiri:

$N$ este numărul de valori ale semnalului măsurate pe parcursul perioadei, precum și numărul de componente de descompunere;

$x_{n},\quad n=0,\dots, N-1,$ - valorile măsurate ale semnalului (în puncte temporale discrete cu numere ), care sunt date de intrare pentru conversie directă și date de ieșire pentru inversare; $n = 0,\dots,N-1$

$X_{k},\quad k=0,\dots, N-1,$ - amplitudini complexe ale semnalelor sinusoidale care compun semnalul original; sunt date de ieșire pentru transformare directă și date de intrare pentru inversare; întrucât amplitudinile sunt complexe, atunci atât amplitudinea, cât și faza pot fi calculate din ele simultan; $N$

$|X_k| \peste N$ este amplitudinea obișnuită (reală) a celui de-al- lea semnal sinusoidal; $k$

$\arg(X_k)$ este faza celui de-al- lea semnal sinusoidal ( argumentul unui număr complex ); $k$

$k$ este indicele de frecvență. Frecvența celui de-al-lea semnal este egală cu , unde este perioada de timp în care au fost preluate datele de intrare. $k$ $\frac{k}{T}$ $T$

Din acestea din urmă, se poate observa că transformarea descompune semnalul în componente sinusoidale (care se numesc armonice) cu frecvențe de la oscilații pe perioadă la oscilații pe perioadă (plus o constantă). Deoarece frecvența de eșantionare în sine este egală cu eșantioanele pe perioadă, componentele de înaltă frecvență nu pot fi afișate corect - apare un efect moiré . Acest lucru duce la faptul că a doua jumătate a amplitudinilor complexe, de fapt, este o imagine în oglindă a primei și nu conține informații suplimentare. $unu$ $N-1$ $N$ $N$

Ieșire de conversie

Luați în considerare un semnal periodic cu o perioadă egală cu T. Să-l extindem într- o serie Fourier : $x(t)$

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

Să discretizăm semnalul astfel încât să existe N eșantioane pe perioadă. Reprezentăm semnalul discret sub formă de citiri: , unde , atunci aceste citiri prin seria Fourier se vor scrie astfel: $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}.

Folosind raportul , obținem: $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},

Unde

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

Astfel, am obținut transformata Fourier discretă inversă .

Înmulțim acum expresia pentru cu scalar și obținem: $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}.

Aici folosim: a) o expresie pentru suma unui număr finit de termeni (exponenți) ai unei progresii geometrice și b) o expresie pentru simbolul Kronecker ca limită a raportului funcțiilor Euler pentru numere complexe. Din aceasta rezultă că:

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

Această formulă descrie transformata Fourier discretă directă .

În literatură, se obișnuiește să se scrie multiplicatorul în transformarea inversă și, prin urmare, formulele de transformare sunt de obicei scrise în următoarea formă: $\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}.

Uneori puteți găsi o formă simetrică de scriere a transformării

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}.

Reprezentare matrice

Transformarea Fourier discretă este o transformare liniară care transformă un vector de mostre de timp într-un vector de eșantioane spectrale de aceeași lungime. Astfel, transformarea poate fi implementată ca o multiplicare a unei matrice pătrate simetrice cu un vector: $\vec x$

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

matricea arata astfel: ${\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}}.}

Elementele matricei sunt date prin următoarea formulă:

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

, unde .

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

Valorile proprii ale matricei sunt rădăcini de gradul al patrulea ale unității cu multiplicitate , și , respectiv, unde este numărul rotunjit în jos . $\{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$

Aplicație la înmulțirea numerelor

Transformata Fourier discretă a unui vector poate fi interpretată ca calcularea valorilor polinomului în rădăcinile unității , , , …, . $(a_{0};a_{1};\dots;a_{n-1})$ $p(x)=a_{0}+a_{1}x+\dots +a_{n-1}x^{n-1)$ $x_{0}=1$ $x_{1}=\omega _{n)$ $x_{2}=\omega _{n}^{2}$ $x_{n-1}=\omega _{n}^{n-1)$

Valorile polinomului de gradul al treilea în puncte determină în mod unic polinomul însuși. În același timp, dacă și , atunci , prin urmare, din valorile polinoamelor și se pot determina, de asemenea, valorile în aceleași puncte ale polinomului și să le restabilească prin transformarea Fourier discretă inversă. $n$ $n+1$ $p(x)=a$ $q(x)=b$ $(p\cdot q)(x)=ab$ $p(x)$ $q(x)$ $p\cdot q$

Deoarece orice număr poate fi reprezentat ca un polinom de la baza sistemului numeric , înmulțirea a două numere poate fi, la rândul său, redusă la înmulțirea a două polinoame și normalizarea rezultatului. $N=a_{n-1}\dots a_{1}a_{0}=a_{0}+a_{1}\cdot 10+\dots +a_{n-1}\cdot 10^{n -unu}$

Proprietăți

Liniaritate
${ax(n)+by(n)}\longleftrightarrow {aX(k)+bY(k)}.$
Schimbare de timp
${x(nm)}\longleftrightarrow X(k)e^{-{\frac {2\pi i}{N}}km}.$
Periodicitate
$X(k+rN)=X(k),r\in \mathbb {Z} .$
Teorema lui Parseval este îndeplinită .
Are o densitate spectrală
$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} .$ Armonica zero este suma valorilor semnalului.

Vezi și

Literatură

Sergienko AB Procesare digitală a semnalului. - al 2-lea. - Sankt Petersburg. : Peter, 2006. - S. 751. - ISBN 5-469-00816-9 .
M. A. Pavleino, V. M. Romadanov. Transformări spectrale în MatLab . - Sankt Petersburg. , 2007. - P. 160. - ISBN 978-5-98340-121-1 .

Robert J. Marks II. Manual de analiză Fourier și aplicațiile sale . - Oxford: Oxford University Press, 2009. - P. 744. - ISBN 978-0-19-533532-7 .
Mehta M. L. Valori proprii și vectori proprii ai transformării Fourier finite // J. Math. Fiz. - AIP , 1986. - Vol. 28, Iss. 4. - P. 781-785. — ISSN 0022-2488 ; 1089-7658 ; 1527-2427 - doi:10.1063/1.527619

Note

↑ Fedorenko S. V. - Modificarea algoritmului Gretzel-Bleihut Copie de arhivă din 24 martie 2022 la Wayback Machine . - Articol. - Jurnalul de instrumentare. - UDC 621.391

Link -uri

Transformată Fourier discretă (DFT) (legatură moartă) . Consultat la 15 noiembrie 2010. Arhivat din original la 1 ianuarie 2012. (Rusă)

Proprietățile transformatei Fourier discrete (DFT) (legatură moartă) . Consultat la 15 noiembrie 2010. Arhivat din original pe 8 mai 2012. (Rusă)

Procesare digitală a semnalului
Teorie	Semnal semnal discret teorema lui Kotelnikov Teoria estimărilor statistice Teoria detectării semnalului
Subsecțiuni	Procesare digitală a semnalului audio Teoria controlului automat Procesarea digitală a imaginii Procesarea vorbirii Procesarea statistică a semnalului
Tehnici	Transformată Fourier discretă (DFT) Transformată Fourier discretă în timp (DTFT) impuls Transformare biliniară consistent Transformarea Z Transformarea Z modificată
Prelevarea de probe	Supereșantionare subeșantionare Reducerea rezoluției Creșterea rezoluției Alianta Filtru Frecvența de eșantionare frecvența Nyquist