Transformimi Diskret Furje

Stampa:Equation box 1$X_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{-i2\pi {\tfrac {k}{N}}n}$Stampa:EquationNote can be interpreted or derived in various ways, for example:

Fig 1: Marrëdhënia midis transformimit Furier (të vazhdueshëm) dhe transformimit diskret të Furjesë.
Majtas: Një funksion i vazhdueshëm (lart) dhe transformimi i tij Furier (poshtë).
Qendra-majtas: Shuma periodike e funksionit origjinal (lart). Transformimi Furier (poshtë) është zero, përveçse në pikat diskrete. Transformimi i anasjelltë është një shumë e sinusoideve të quajtur seri Furier .
Qendra-djathtas: Funksioni origjinal është i diskretizuar (shumëzuar me një krehër të Dirakut ) (lart). Transformimi i tij Furier (poshtë) është një përmbledhje periodike ( DTFT ) e transformimit origjinal.
Djathtas: DFT (poshtë) llogarit kampione diskrete të DTFT-së së vazhdueshme. DFT e anasjelltë (lart) është një shumim periodik i kampioneve origjinale. Algoritmi FFT/TSHF llogarit një cikël të DFT/TFD dhe anasjellta e tij është një cikël i inversit DFT/TFD.

Në matematikë, transformimi diskret i Furierit ( DFT/TDF ) konverton një varg të fundëm të kampioneve të baraslarguara të një funksioni në një varg me gjatësi të njëjtë të kampioneve të baraslarguara të transformimit të Furierit në kohë diskrete (TFKD), e cila është një funksion me vlera komplekse i frekuencës. Intervali në të cilin TFKD kampionohet është i anasjellti e kohëzgjatjes së vargut hyrës.  Një TDF i anasjelltë (ATDF) është një seri Fourier, duke përdorur kampionet TFKD si koeficientë të sinusoidave komplekse në frekuencat përkatëse TFKD. Ka të njëjtat vlera të kampioneve si vargu origjinal i hyrjes. Prandaj thuhet se TDF është një paraqitje e rrafshit të frekuencës së vargut origjinal të hyrjes. Nëse vargu origjinal përfshin të gjitha vlerat jo-zero të një funksioni, TFKD-ja e tij është e vazhdueshme (dhe periodike) dhe TDF ofron kampione diskrete të një cikli. Nëse vargu origjinal është një cikël i një funksioni periodik, TDF siguron të gjitha vlerat jo zero të një cikli TFKD.

TDF është transformimi diskret më i rëndësishëm, i përdorur për të kryer analizën Furier në shumë zbatime praktike. Në përpunimin numerik të sinjalit, funksioni është çdo madhësi ose sinjal që ndryshon me kalimin e kohës, siç është shtypja e një vale zanore, një sinjal radioje ose leximet ditore të temperaturës, të marra në kampione gjatë një intervali kohor të fundëm (shpesh i përcaktuar nga një funksion dritare ). Në përpunimin e imazhit, kampionet mund të jenë vlerat e pikselëve përgjatë një rreshti ose kolone të një imazhi raster . TDF përdoret gjithashtu për të zgjidhur në mënyrë efikase ekuacionet diferenciale të pjesshme dhe për të kryer operacione të tjera si thurjet ose shumëzimin e numrave të plotë të mëdhenj.

Meqenëse ka të bëjë me një sasi të kufizuar të dhënash, mund të zbatohet në kompjuterë me algoritme numerike apo edhe harduer të dedikuar. Këto zbatime zakonisht përdorin algoritme efikase të transformimit të shpejtë të Furierit (TSHF); aq sa termat "TSHF" dhe "TDF" shpesh përdoren në mënyrë të ndërsjellë. Para përdorimit të tij të tanishëm, akronimi "TSHF" mund të jetë përdorur gjithashtu për termin e paqartë " transformim i fundëm Furier ".

TDF ka shumë aplikime, duke përfshirë ato thjesht matematikore pa interpretim fizik. Por fizikisht mund të lidhet me përpunimin e sinjalit si një version diskret (dmth. kampione) të transformimit të Furierit në kohë diskrete (DTFT), i cili është një funksion i vazhdueshëm dhe periodik. DFT llogarit N kmapione të baraslarguara të një cikli të DTFT.

Përkufizimi

Transformimi diskret i Furjesë transformon një varg N numrash kompleksë $\left\{\mathbf {x} _{n}\right\}:=x_{0},x_{1},\ldots ,x_{N-1}$ në një sekuencë tjetër të numrave kompleks, $\left\{\mathbf {X} _{k}\right\}:=X_{0},X_{1},\ldots ,X_{N-1},$ e cila përcaktohet nga:

• It completely describes the discrete-time Fourier transform (DTFT) of an $N$-periodic sequence, which comprises only discrete frequency components. (Using the DTFT with periodic data)
• It can also provide uniformly spaced samples of the continuous DTFT of a finite length sequence. (Transformimi Diskret Furje § Shënime)
• It is the cross correlation of the input sequence, $x_{n}$, and a complex sinusoid at frequency ${\textstyle {\frac {k}{N}}.}$ Thus it acts like a matched filter for that frequency.
• It is the discrete analog of the formula for the coefficients of a Fourier series:

  $C_{k}={\frac {1}{P}}\int _{P}x(t)e^{-i2\pi {\tfrac {k}{P}}t}\,dt.$

Transformimi nganjëherë shënohet me simbolin ${\mathcal {F}}$, si në $\mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}$ ose ${\mathcal {F}}\left(\mathbf {x} \right)$ ose ${\mathcal {F}}\mathbf {x}$ .

Transformimi i anasjelltë jepet nga:

$x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}\cdot e^{i2\pi {\tfrac {k}{N}}n}$

Shembull

Ky shembull tregon se si të zbatohet TDF në një varg me gjatësi $N=4$ dhe vektori i hyrjes

$$\mathbf {x} ={\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}1\\2-i\\-i\\-1+2i\end{pmatrix}}.$$

Llogaritja e DFT-së së $\mathbf {x}$ duke përdorur:

$${\begin{aligned}X_{0}&=e^{-i2\pi 0\cdot 0/4}\cdot 1+e^{-i2\pi 0\cdot 1/4}\cdot (2-i)+e^{-i2\pi 0\cdot 2/4}\cdot (-i)+e^{-i2\pi 0\cdot 3/4}\cdot (-1+2i)=2\\X_{1}&=e^{-i2\pi 1\cdot 0/4}\cdot 1+e^{-i2\pi 1\cdot 1/4}\cdot (2-i)+e^{-i2\pi 1\cdot 2/4}\cdot (-i)+e^{-i2\pi 1\cdot 3/4}\cdot (-1+2i)=-2-2i\\X_{2}&=e^{-i2\pi 2\cdot 0/4}\cdot 1+e^{-i2\pi 2\cdot 1/4}\cdot (2-i)+e^{-i2\pi 2\cdot 2/4}\cdot (-i)+e^{-i2\pi 2\cdot 3/4}\cdot (-1+2i)=-2i\\X_{3}&=e^{-i2\pi 3\cdot 0/4}\cdot 1+e^{-i2\pi 3\cdot 1/4}\cdot (2-i)+e^{-i2\pi 3\cdot 2/4}\cdot (-i)+e^{-i2\pi 3\cdot 3/4}\cdot (-1+2i)=4+4i\end{aligned}}$$

rezulton në $$\mathbf {X} ={\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}2\\-2-2i\\-2i\\4+4i\end{pmatrix}}.$$

Vetitë

Lineariteti

TDF është një transformim linear, dmth nëse ${\mathcal {F}}(\{x_{n}\})_{k}=X_{k}$ dhe ${\mathcal {F}}(\{y_{n}\})_{k}=Y_{k}$, pastaj për çdo numër kompleks $a,b$ :

${\mathcal {F}}(\{ax_{n}+by_{n}\})_{k}=aX_{k}+bY_{k}$

Kthimi i kohës dhe frekuencës

Kthimi i kohës (dmth. zëvendësimi $n$ nga $N-n$ ) in $x_{n}$ korrespondon me ndryshimin e frekuencës (d.m.th $k$ nga $N-k$ ). Matematikisht, nëse $\{x_{n}\}$ paraqet vektorin x atëherë

nëse ${\mathcal {F}}(\{x_{n}\})_{k}=X_{k}$

atëherë ${\mathcal {F}}(\{x_{N-n}\})_{k}=X_{N-k}$

Konjugimi në kohë

Nëse ${\mathcal {F}}(\{x_{n}\})_{k}=X_{k}$ atëherë ${\mathcal {F}}(\{x_{n}^{*}\})_{k}=X_{N-k}^{*}$ .

Pjesa reale dhe imagjinare

Kjo tabelë tregon disa veprime matematikore në $x_{n}$ në domenin kohor dhe efektet përkatëse në DFT-në e tij $X_{k}$ në fushën e frekuencës.

Vetia	Rrafshi i kohës $x_{n}$	Rrafshi i frekuencës $X_{k}$
Pjesë e vërtetë në kohë	$\operatorname {Re} {\left(x_{n}\right)}$	${\frac {1}{2}}\left(X_{k}+X_{N-k}^{*}\right)$
Pjesë imagjinare në kohë	$\operatorname {Im} {\left(x_{n}\right)}$	${\frac {1}{2i}}\left(X_{k}-X_{N-k}^{*}\right)$
Pjesë reale në frekuencë	${\frac {1}{2}}\left(x_{n}+x_{N-n}^{*}\right)$	$\operatorname {Re} {\left(X_{k}\right)}$
Pjesë imagjinare në frekuencë	${\frac {1}{2i}}\left(x_{n}-x_{N-n}^{*}\right)$	$\operatorname {Im} {\left(X_{k}\right)}$