Transformada de Fourier discreta no uniforme

En matemàtiques aplicades, la transformada de Fourier discreta no uniforme (NUDFT o NDFT) d'un senyal és un tipus de transformada de Fourier, relacionada amb una transformada de Fourier discreta o transformada de Fourier en temps discret, però en la qual el senyal d'entrada no es mostra igual. punts o freqüències espaiades (o ambdues). És una generalització de la DFT desplaçada. Té aplicacions importants en el processament de senyals, imatges de ressonància magnètica, i la solució numèrica d'equacions diferencials parcials.

Com a enfocament generalitzat per al mostreig no uniforme, el NUDFT permet obtenir informació del domini de la freqüència d'un senyal de longitud finita a qualsevol freqüència. Una de les raons per adoptar el NUDFT és que molts senyals tenen la seva energia distribuïda de manera no uniforme en el domini de la freqüència. Per tant, un esquema de mostreig no uniforme podria ser més convenient i útil en moltes aplicacions de processament de senyal digital. Per exemple, el NUDFT proporciona una resolució espectral variable controlada per l'usuari.

Definició

La transformada discreta de Fourier no uniforme transforma una seqüència de $N$ nombres complexos $x_0,\dots ,x_{N-1}$ en una altra seqüència de nombres complexos $X_0,\dots ,X_{N-1}$ definit perPlantilla:NumBlkon $p_0,\dots ,p_{N-1}\in [0,1]$ són punts de mostra i $f_0,\dots ,f_{N-1}\in [0,N]$ són freqüències. Tingueu en compte que si $p_n=n/N$ i $f_k=k$, aleshores l'equació (Plantilla:EquationNote) es redueix a la transformada de Fourier discreta. Hi ha tres tipus de NUDFT. Tingueu en compte que aquests tipus no són universals i diferents autors es referiran a diferents tipus amb números diferents.

• La transformada discreta de Fourier no uniforme de tipus I (NUDFT-I) utilitza punts de mostra uniformes $p_n=n/N$ però freqüències no uniformes (és a dir, no enteres). $f_k$. Això correspon a avaluar una sèrie de Fourier generalitzada en punts equiespaiats. També es coneix com a NDFT o NDFT endavant
• La transformada discreta de Fourier no uniforme de tipus II (NUDFT-II) utilitza freqüències uniformes (és a dir, enters) $f_k=k$ però punts de mostra no uniformes $p_n$. Això correspon a l'avaluació d'una sèrie de Fourier en punts no equiespaiats. També es coneix com a NDFT adjunt.
• La transformada discreta de Fourier no uniforme de tipus III (NUDFT-III) utilitza els dos punts de mostra no uniformes $p_n$ i freqüències no uniformes $f_k$. Això correspon a l'avaluació d'una sèrie de Fourier generalitzada en punts no equiespaiats. També es coneix com NNDFT.

Un conjunt similar de NUDFT es pot definir substituint $-i$ per $+i$ a l'equació (Plantilla:EquationNote). A diferència del cas uniforme, però, aquesta substitució no està relacionada amb la transformada de Fourier inversa. La inversió del NUDFT és un problema separat, que es discuteix a continuació.

Relació amb la transformació Z

El NUDFT-I es pot expressar com una transformada Z. El NUDFT-I d'una seqüència $x[n]$ de llargada $N$ és

$X(z_k)=X(z){|}_{z=z_k}=\sum _{n=0}^{N-1}x[n]z_k^{-n},k=0,1,...,N-1,$

on $X(z)$ és la transformada Z de $x[n]$, i $\{z_i{\}}_{i=0,1,...,N-1}$ són punts arbitràriament diferents en el pla z. Cal tenir en compte que la NUDFT es redueix a la DFT quan els punts de mostreig es troben al cercle unitari a angles igualment espaiats.

Transformada ràpida de Fourier no uniforme

Mentre que una aplicació ingènua de l'equació ( Plantilla:EquationNote ) dóna lloc a an $O(N^2)$ algorisme per calcular el NUDFT, $O(N\log N)$ Existeixen algorismes basats en la transformada ràpida de Fourier (FFT). Aquests algorismes s'anomenen NUFFT o NFFT i s'han desenvolupat basant-se en el sobremostreig i la interpolació, interpolació min-max, i aproximació de rang baix. En general, els NUFFT aprofiten la FFT convertint el problema no uniforme en un problema uniforme (o una seqüència de problemes uniformes) al qual es pot aplicar la FFT. Les biblioteques de programari per realitzar NUFFT estan disponibles en 1D, 2D i 3D.

Aplicacions

Les aplicacions del NUDFT inclouen:

• Processament digital del senyal
• Imatge de ressonància magnètica
• Equacions diferencials parcials numèriques
• Esquemes semi-lagrangianos
• Mètodes espectrals
• Anàlisi espectral
• Disseny de filtres digitals
• Disseny de matriu d'antenes
• Detecció i descodificació de senyals multifreqüència de doble to (DTMF).