Diskreetti Fourier-muunnos

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. heinäkuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Diskreetti Fourier-muunnos (englanninkielisessä kirjallisuudessa DFT , Discrete Fourier Transform ) on yksi Fourier-muunnoksista , joita käytetään laajalti digitaalisissa signaalinkäsittelyalgoritmeissa ( sen muunnelmia käytetään MP3 :n äänen pakkaamisessa, JPEG - kuvan pakkaamisessa jne.), sekä toisilla aloilla, jotka liittyvät diskreetin (esimerkiksi digitalisoidun analogisen) signaalin taajuuksien analysointiin. Diskreetti Fourier-muunnos vaatii diskreetin funktion syötteenä. Tällaiset toiminnot syntyvät usein diskretisoimalla (arvovalinnat jatkuvista funktioista). Diskreetit Fourier-muunnokset auttavat ratkaisemaan osittaisdifferentiaaliyhtälöitä ja suorittamaan operaatioita, kuten konvoluutioita . Diskreettejä Fourier-muunnoksia käytetään aktiivisesti myös tilastoissa, aikasarjojen analysoinnissa. On olemassa moniulotteisia diskreettejä Fourier-muunnoksia [1] .

Muunna kaavat

Suora muunnos:

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

Käänteinen muunnos:

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.

Lausekkeen toinen osa seuraa ensimmäisestä Eulerin kaavan mukaan .

Nimitykset:

$N$ on ajanjakson aikana mitattujen signaaliarvojen lukumäärä sekä hajoamiskomponenttien lukumäärä;

$x_{n},\quad n=0,\dots ,N-1,$ - signaalin mitatut arvot (diskreetteissä aikapisteissä numeroilla ), jotka ovat syöttötietoja suoraa muuntamista varten ja lähtötietoja käänteisessä tilassa; $n = 0,\pisteet,N-1$

$X_{k},\quad k=0,\dots ,N-1,$ - sinimuotoisten signaalien kompleksiset amplitudit, jotka muodostavat alkuperäisen signaalin; ovat lähtödataa suoraa muuntamista varten ja syöttödataa käänteistä varten; koska amplitudit ovat monimutkaisia, niin amplitudi ja vaihe voidaan laskea niistä samanaikaisesti; $N$

$|X_k| \N:n päällä$ on : nnen sinimuotoisen signaalin tavallinen (todellinen) amplitudi ; $k$

$\arg(X_k)$ on th sinimuotoisen signaalin vaihe ( kompleksiluvun argumentti ); $k$

$k$ on taajuusindeksi. - :nnen signaalin taajuus on yhtä suuri kuin , jossa on aikajakso, jonka aikana tulodata on otettu. $k$ $\frac{k}{T}$ $T$

Jälkimmäisestä voidaan nähdä, että muunnos hajottaa signaalin sinimuotoisiksi komponenteiksi (joita kutsutaan harmonisiksi), joiden taajuudet ovat värähtelystä jaksoa kohti värähtelyihin jaksoa kohden (plus vakio). Koska itse näytteenottotaajuus on yhtä suuri kuin näytteet per jakso, korkeataajuisia komponentteja ei voida näyttää oikein - syntyy moiré-efekti . Tämä johtaa siihen, että kompleksisten amplitudien toinen puolisko on itse asiassa peilikuva ensimmäisestä eikä sisällä lisätietoa. $yksi$ $N-1$ $N$ $N$

Muunnostulos

Tarkastellaan jotakin jaksollista signaalia , jonka jakso on yhtä suuri kuin T. Laajenna se Fourier-sarjaksi : $x(t)$

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

Diskretisoidaan signaali siten, että näytettä on N jaksoa kohden. Esitämme diskreetin signaalin lukemien muodossa: , missä , niin nämä Fourier-sarjan lukemat kirjoitetaan seuraavasti: $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}.

Käyttämällä suhdetta saamme: $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},

missä

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

Siten olemme saaneet käänteisen diskreetin Fourier-muunnoksen .

Kerromme nyt lausekkeen for skalaarilla ja saamme: $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}.

Tässä käytetään: a) lauseketta geometrisen progression äärellisen määrän termien (eksponenttien) summalle ja b) Kronecker-symbolin lauseketta kompleksilukujen Euler-funktioiden suhteen rajana. Tästä seuraa, että:

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

Tämä kaava kuvaa suoran diskreetin Fourier-muunnoksen .

Kirjallisuudessa on tapana kirjoittaa kerroin käänteisessä muunnoksessa, ja siksi muunnoskaavat kirjoitetaan yleensä seuraavassa muodossa: $\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}.

Joskus voit löytää symmetrisen muodon muunnoksen kirjoittamiselle

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

Matriisiesitys

Diskreetti Fourier-muunnos on lineaarinen muunnos, joka muuntaa aikanäytteiden vektorin samanpituisten spektrinäytteiden vektoriksi. Siten muunnos voidaan toteuttaa kertomalla symmetrinen neliömatriisi vektorilla: $\vec x$

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

matriisi näyttää tältä: ${\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 &\vpisteet &\dpisteet &\vpisteet \\1&\omega _{n}^{n-1}&\omega _{n}^{2(n-1)}&\omega _{n}^{3 (n-1)}&\lpisteet &\omega _{n}^{(n-1)^{2}}\end{pmatrix}}.}

Matriisielementit saadaan seuraavalla kaavalla:

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

, missä .

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

Matriisin ominaisarvot ovat neljännen asteen yksikön juuria, joissa on monikertaisuus , ja vastaavasti , jossa luku on pyöristetty alaspäin . ${\näyttötyyli \{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$

Sovellus lukujen kertomiseen

Vektorin diskreetti Fourier-muunnos voidaan tulkita niin , että se laskee polynomin arvot yksikköjuurissa , , , …, . $(a_{0};a_{1};\dots ;a_{n-1})$ ${\displaystyle p(x)=a_{0}+a_{1}x+\dots +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))$

Kolmannen asteen polynomin arvot pisteissä määräävät yksiselitteisesti itse polynomin. Samanaikaisesti, jos ja , niin , siis polynomien arvoista ja voidaan myös määrittää arvot polynomin samoissa pisteissä ja palauttaa se käänteisellä diskreetillä Fourier-muunnolla. $n$ $n+1$ $p(x)=a$ $q(x)=b$ $(p\cdot q)(x)=ab$ $p(x)$ $q(x)$ $p\cdot q$

Koska mikä tahansa luku voidaan esittää polynomina lukujärjestelmän kannasta , kahden luvun kertolasku voidaan puolestaan pelkistää kahden polynomin kertomiseen ja tuloksen normalisointiin. $N=a_{n-1}\dots a_{1}a_{0}=a_{0}+a_{1}\cdot 10+\dots +a_{n-1}\cdot 10^{n -yksi}$

Ominaisuudet

Lineaarisuus
${ax(n)+by(n)}\longleftrightarrow {aX(k)+bY(k)}.$
Ajansiirto
${x(nm)}\longleftrightarrow X(k)e^{-{\frac {2\pi i}{N}}km}.$
Jaksoisuus
$X(k+rN)=X(k),r\in \mathbb {Z} .$
Parsevalin lause täyttyy .
Sillä on spektritiheys
$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} .$ Nollaharmoninen on signaaliarvojen summa.

Katso myös

Kirjallisuus

Sergienko AB Digitaalinen signaalinkäsittely. - 2. - Pietari. : Peter, 2006. - S. 751. - ISBN 5-469-00816-9 .
M. A. Pavleino, V. M. Romadanov. Spektrimuunnokset MatLabissa . - Pietari. , 2007. - s. 160. - ISBN 978-5-98340-121-1 .

Robert J. Marks II. Fourier-analyysin ja sen sovellusten käsikirja . - Oxford: Oxford University Press, 2009. - S. 744. - ISBN 978-0-19-533532-7 .
Mehta M. L. Äärillisen Fourier-muunnoksen ominaisarvot ja ominaisvektorit // J. Math. Phys. - AIP , 1986. - Voi. 28, Iss. 4. - P. 781-785. — ISSN 0022-2488 ; 1089-7658 ; 1527-2427 - doi:10.1063/1.527619

Muistiinpanot

↑ Fedorenko S. V. - Gretzel-Bleihut-algoritmin muutos Arkistokopio 24. maaliskuuta 2022 Wayback Machinessa . - Artikkeli. - Journal of Instrumentation. - UDC 621.391

Linkit

Diskreetti Fourier-muunnos (DFT) (kuollut linkki) . Haettu 15. marraskuuta 2010. Arkistoitu alkuperäisestä 1. tammikuuta 2012. (Venäjän kieli)

Diskreetin Fourier-muunnoksen (DFT) ominaisuudet (kuollut linkki) . Haettu 15. marraskuuta 2010. Arkistoitu alkuperäisestä 8. toukokuuta 2012. (Venäjän kieli)

Digitaalinen signaalinkäsittely
Teoria	Signaali diskreetti signaali Kotelnikovin lause Tilastollisten arvioiden teoria Signaalin havaitsemisen teoria
alajaksot	Digitaalinen äänisignaalin käsittely Automaattisen ohjauksen teoria Digitaalinen kuvankäsittely Puheenkäsittely Tilastollinen signaalinkäsittely
Tekniikat	Diskreetti Fourier-muunnos (DFT) Aikadiskreetti Fourier-muunnos (DTFT) Impulssivasteen Bilineaarinen muunnos Johdonmukainen Z-muunnos Muokattu Z-muunnos
Näytteenotto	Supersampling osanäytteenotto Tarkkuuden vähentäminen Resoluution lisäys Aliasing suodatin Näytteenottotaajuus Nyquist-taajuus