Transform??e de Fourier discr??te

Contexte des ??coles Wikip??dia

SOS Enfants, qui se d??roule pr??s de 200 sos ??coles dans le monde en d??veloppement, a organis?? cette s??lection. Parrainer un enfant de faire une r??elle diff??rence.

transform??es de Fourier
Transform??e de Fourier en continu
s??rie de Fourier
Temps discret transform??e de Fourier
Transform??e de Fourier discr??te
Analyse de Fourier
Transformations connexes

En math??matiques , la transform??e de Fourier discr??te (DFT) est l'une des formes sp??cifiques de analyse de Fourier. En tant que tel, il se transforme en une autre fonction, qui est appel?? le repr??sentation dans le domaine fr??quence, ou simplement la TFD, de la fonction d'origine (ce qui est souvent une fonction du dans le domaine temporel). Mais la DFT n??cessite une fonction d'entr??e qui est valeurs discr??tes et dont les non-z??ro ont une (finie) de dur??e limit??e. Ces entr??es sont souvent cr????es par ??chantillonnage d'une fonction continue, comme la voix d'une personne. Et, contrairement ?? la discret dans le temps ?? transform??e de Fourier (DTFT), on ??value seulement assez de composantes de fr??quence pour reconstruire le segment fini qui a ??t?? analys??. Sa transform??e inverse ne peut pas reproduire le domaine temporel enti??re, ?? moins que l'entr??e se trouve ??tre p??riodique (toujours). Par cons??quent, il est souvent dit que la DFT est une transformation pour l'analyse de Fourier des fonctions ?? temps discret finie domaine. Les fonctions de base de la d??composition sinuso??dales ont les m??mes propri??t??s.

Etant donn?? que la fonction d'entr??e est une s??quence finie de r??els ou des nombres complexes , la TFD est id??al pour les informations de traitement stock??es dans les ordinateurs . En particulier, la TFD est largement utilis?? dans traitement du signal et des domaines connexes pour analyser les fr??quences contenues dans une ??chantillonn?? signaler, pour r??soudre des ??quations aux d??riv??es partielles et d'effectuer d'autres op??rations telles que circonvolutions. La DFT peut ??tre calcul?? de mani??re efficace dans la pratique en utilisant un transform??e de Fourier rapide (FFT).

Depuis algorithmes FFT sont si couramment utilis??es pour calculer la DFT, les deux termes sont souvent utilis??s indiff??remment dans des contextes familiers, bien qu'il y ait une distinction claire: "DFT" se r??f??re ?? une transformation math??matique, ind??pendamment de la fa??on dont il est calcul??, tandis que "FFT" fait r??f??rence ?? un quelconque de plusieurs algorithmes efficaces pour la TFD. Cette distinction est plus floue, cependant, par le synonyme transform??e de Fourier finie pour le DFT, qui pr??c??de apparemment le terme ??transform??e de Fourier rapide?? (Cooley et al., 1969) mais a le m??me sigle.

D??finition

La s??quence de N nombres complexes x _0, ..., x _N-1 est transform?? en la s??quence de N nombres complexes X _0, ..., X _N-1 par la TFD d'apr??s la formule:

$X_k = \ sum_ {n = 0} ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N}} kn \ quad \ quad k = 0, \ dots, N-1$

o?? $e ^ {\ frac {2 \ pi i} {N}}$ est un Ni??me primitive racine de l'unit??.

La transformation est parfois d??sign?? par le symbole $\ Mathcal {F}$ , Comme dans $\ Mathbf {X} = \ mathcal {F} \ left \ {\ mathbf {x} \ right \}$ ou $\ Mathcal {F} \ left (\ mathbf {x} \ right)$ ou $\ Mathcal {F} \ mathbf {x}$ .

Le Fourier discr??te inverse (IDFT) est donn??e par

$x_n = \ frac {1} {N} \ sum_ {k = 0} ^ {N-1} x_k e ^ {\ frac {2 \ pi i} {N}} kn \ quad \ quad n = 0, \ dots , N-1.$

Une simple description de ces ??quations est que les nombres complexes $X_k$ repr??senter l'amplitude et la phase des diff??rents composantes sinuso??dales du "signal" d'entr??e $x_n$ . La DFT calcule la $X_k$ du $x_n$ , Tandis que l'IDFT montre comment calculer le $x_n$ comme la somme des composantes sinuso??dales $X_k \ exp (2 \ pi i k n / N) / N$ avec fr??quence $k / N$ cycles par ??chantillon. En ??crivant les ??quations sous cette forme, nous faisons un usage intensif des La formule d'Euler pour exprimer en termes de sinuso??des exponentielles complexes, qui sont beaucoup plus faciles ?? manipuler. (De la m??me mani??re, par ??crit $X_k$ en forme polaire , on obtient imm??diatement l'amplitude de sinuso??de $| X_k |$ et la phase de la argumentation complexe.) Une subtilit?? importante de cette repr??sentation, aliasing, est discut??e ci-dessous.

A noter que le facteur de normalisation et multiplier la transform??e DFT IDFT (ici 1 et 1 / N) et les signes des exposants sont simplement conventions, et diff??rent dans certains traitements. Les seules exigences de ces conventions sont que la DFT et IDFT ont des exposants de signes oppos??s et que le produit de leurs facteurs de normalisation ??tre 1 / N. Une normalisation de $1 / \ sqrt {N}$ ?? la fois pour la TFD et IDFT rend les transformations unitaire, ce qui pr??sente certains avantages th??oriques, mais il est souvent plus pratique de calcul num??rique pour effectuer la mise ?? l'??chelle en une seule fois comme ci-dessus (et une mise ?? l'??chelle de l'unit?? peut ??tre pratique d'une autre mani??re).

(La convention d'un signe n??gatif dans l'exposant est souvent pratique car cela signifie que $X_k$ est l'amplitude d'une "fr??quence positif" $2 \ pi k / N$ . ??quivalente, la DFT est souvent consid??r?? comme un Filtre adapt??: lors de la recherche pour une fr??quence de 1, une corr??lation du signal entrant avec une fr??quence de -1).

Dans la discussion qui suit les termes "s??quence" et "vecteur" seront consid??r??s comme interchangeables.

Propri??t??s

??tat complet

La transform??e de Fourier discr??te est une inversible, transformation lin??aire

$\ Mathcal {F}: \ mathbb {C} ^ N \ to \ mathbb {C} ^ N$

avec $\ Mathbb {C}$ repr??sentant l'ensemble des nombres complexes . En d'autres termes, pour tout n> 0, un vecteur de dimension N a un complexe DFT et une IDFT qui sont ?? leur tour N vecteurs complexes de dimension.

Orthogonalit??

Les vecteurs $e ^ {\ frac {2 \ pi i} {N}} kn$ pour homme base orthogonale sur l'ensemble des vecteurs complexes de N:

$\ Sum_ {n = 0} ^ {N-1} \ left (e ^ {\ frac {2 \ pi i} {} N kn} \ right) \ left (e ^ {- \ frac {2 \ pi i} {N}} K'N \ right) = N ~ \ delta_ {kk '}$

o?? $~ \ {Kk delta_ '}$ est le Kronecker. Cette condition d'orthogonalit?? peut ??tre utilis??e pour d??river la formule de l'IDFT de la d??finition de la TFD, et est ??quivalent ?? la propri??t?? unitarity ci-dessous.

Le th??or??me de Plancherel et le th??or??me de Parseval

Si X et Y _{k k} sont les TFD de x _n et y _n respectivement alors le Th??or??me de Plancherel ??tats:

$\ Sum_ {n = 0} ^ {N-1} x_n y ^ _ * n = \ frac {1} {N} \ sum_ {k = 0} ^ {N-1} x_k Y ^ _ * k$

o?? l'??toile d??signe conjugaison complexe. ??galit?? de Parseval est un cas particulier du th??or??me et les Etats Plancherel:

$\ Sum_ {n = 0} ^ {N-1} | x_n | ^ 2 = \ frac {1} {N} \ sum_ {k = 0} ^ {N-1} | x_k | ^ 2.$

Ces th??or??mes sont ??galement ??quivalente ?? la condition unitaire ci-dessous.

P??riodicit??

Si l'expression qui d??finit la DFT est ??valu??e pour tous les entiers $k$ au lieu de simplement pour $k = 0, \ dots, N-1$ , Alors la s??quence infinie r??sultant est une extension p??riodique de la TFD, p??riodique de p??riode N.

La p??riodicit?? peut ??tre d??montr?? directement ?? partir de la d??finition:

$X_ {k + N} = \ sum_ {n = 0} ^ {N-1} e x_n ^ {- \ frac {2 \ pi i} {N} (k + N) n} = \ sum_ {n = 0 } ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N}} kn e ^ {- 2 \ pi dans} = \ sum_ {n = 0} ^ {N-1} e x_n ^ {- \ frac {2 \ pi i} {N}} = kn x_k$

o?? nous avons utilis?? le fait que $e ^ {- 2 \ pi i} = 1$ . De la m??me mani??re il peut ??tre d??montr?? que la formule IDFT conduit ?? une extension p??riodique.

Le th??or??me de changement de vitesse

Multipliant $x_n$ d'une phase lin??aire $e ^ {\ frac {2 \ pi i} {N} n m}$ pour un certain entier $m$ correspond ?? un d??calage circulaire de la sortie $X_k$ : $X_k$ est remplac?? par $X_ {k-m}$ , O?? l'indice est interpr??t??e modulo $N$ (Ce est-p??riodique). De m??me, un d??placement circulaire de l'entr??e $x_n$ correspond ?? multiplier la sortie $X_k$ d'une phase lin??aire. Math??matiquement, si $\ {X_n \}$ repr??sente le vecteur x puis

si $\ Mathcal {F} (\ {x_n \}) _ k = x_k$

puis $\ Mathcal {F} (\ {x_n \ cdot e ^ {\ frac {2 \ pi i} {N} nm} \}) _ k = X_ {} km$

et $\ Mathcal {F} (\ {x_ {nm} \}) _ k = x_k \ cdot e ^ {- \ frac {2 \ pi i} {N}} km$

Circulaire th??or??me de convolution et de corr??lation crois??e th??or??me

Le th??or??me de convolution du temps continu et discret transform??es de Fourier qui indique une convolution de deux s??quences infinite peut ??tre obtenue comme la transform??e inverse du produit des transformations individuelles. Avec les s??quences et les transform??es de longueur n, a circularit?? se pose:

$\ Begin {align} \ mathcal {F} ^ {- 1} \ left \ {\ mathbf {X \ cdot Y} \ right \} _ n \ & \ stackrel {\ mathrm {def}} {=} \ \ frac { 1} {N} \ sum_ {k = 0} ^ {N-1} x_k \ cdot y_k \ cdot e ^ {\ frac {2 \ pi i} {N}} \\ & kn = \ frac {1} { N} \ sum_ {k = 0} ^ {N-1} \ left (\ sum_ {l = 0} ^ {N-1} x_l e ^ {- \ frac {2 \ pi i} {N}} kl \ droite) \ cdot \ left (\ sum_ {m = 0} ^ {N-1} y_m e ^ {- \ frac {2 \ pi i} {N}} km \ right) \ cdot e ^ {\ frac {2 \ pi i} {N}} \\ & kn = \ sum_ {l = 0} ^ {N-1} x_l \ sum_ {m = 0} ^ {N-1} y_m \ left (\ frac {1} { N} \ sum_ {k = 0} ^ {N-1} e ^ {\ frac {2 \ pi i} {N} k (NLM)} \ right). \ End {align}$

La quantit?? entre parenth??ses est ??gal ?? 0 pour toutes les valeurs de $m$ l'exception de ceux de la forme $n-l-pN$ O?? $p$ est un entier quelconque. Lors de ces valeurs, il est ??gal ?? 1. Il peut donc ??tre remplac?? par une somme infinie de Fonctions delta de Kronecker, et nous continuons en cons??quence. Notez que nous pouvons ??galement ??tendre les limites de $m$ ?? l'infini, avec la compr??hension que le $x$ et $y$ des s??quences sont d??finis comme 0 en dehors de [0, N-1]:

$\ Begin {align} \ mathcal {F} ^ {- 1} \ left \ {\ mathbf {X \ cdot Y} \ right \} _ n & = \ sum_ {l = 0} ^ {N-1} x_l \ sum_ {m = - \ infty} ^ {\ infty} y_m \ left (\ sum_ {p = - \ infty} ^ {\ infty} \ delta_ {m (nl-PN)} \ right) = \\ & \ {sum_ l = 0} ^ {N-1} x_l \ sum_ {p = - \ infty} ^ {\ infty} \ left (\ sum_ {m = - \ infty} ^ {\ infty} y_m \ cdot \ delta_ {m ( nl-PN)} \ right) = \\ & \ sum_ {l = 0} ^ {N-1} x_l \ left (\ sum_ {p = - \ infty} ^ {\ infty} {y_ nl-PN} \ droite) \ \ stackrel {\ mathrm {def}} {} = \ (\ mathbf {x} * y_n) _ n \, \ end {align}$

qui est la convolution de la $\ Mathbf {x}$ avec une s??quence p??riodiquement ??tendu $\ Mathbf {y}$ s??quence d??finie par:

$(\ Mathbf {} y_n) _ n \ \ stackrel {\ mathrm {def}} {} = \ \ sum_. {P = - \ infty} ^ {\ infty} y _ {(n-PN)} \,$

De m??me, il peut ??tre montr?? que:

$\ Mathcal {F} ^ {- 1} \ left \ {\ mathbf {X ^ * \ cdot Y} \ right \} _ n = \ sum_ {l = 0} ^ {N-1} x_l ^ * \ cdot (y_n ) _ {n + l} \ \ stackrel {\ mathrm {def}} {} = \ \ (\ mathbf {x \ star y_n}) _ n \ \,$

qui est le corr??lation crois??e de $\ Mathbf {x}$ et $\ Mathbf {} y_n.$

Une ??valuation directe de la convolution ou de corr??lation sommation, ci-dessus, n??cessite $O (N ^ 2)$ op??rations. Une m??thode indirecte, en utilisant des transformations, peut profiter de la $O (N \ log N)$ l'efficacit?? de la transform??e de Fourier rapide (FFT) afin d'obtenir de bien meilleures performances. Par ailleurs, les circonvolutions peuvent ??tre utilis??s pour calculer efficacement par TFD L'algorithme FFT et de Rader L'algorithme FFT de Bluestein.

M??thodes ont ??galement ??t?? d??velopp??s pour utiliser convolution circulaire dans le cadre d'un processus efficace qui r??alise normale (non circulaire) convolution avec un $\ Mathbf {x}$ ou $\ Mathbf {y}$ s??quence potentiellement beaucoup plus longue que la taille transformer pratique (N). Deux de ces m??thodes sont appel??es chevaucher-enregistrer et empi??tement additif.

Trigonom??trique interpolation polynomiale

Le trigonom??trique interpolation polynomiale

$p (t) = \ frac {} {X_0 N} + \ frac {} {X_1 N} e ^ {it} + \ cdots + \ frac {{X_ N / 2}} {n} \ cos (Nt / 2 ) + \ frac {{X_ N / 2 + 1}} {N} e {^ (- N / 2 + 1), il} + \ cdots + \ frac {{X_ N-1}} {N} e ^ { -il}$ pour $N$ m??me,

$p (t) = \ frac {X_0} {N} + \ frac {X_1} {N} e ^ {it} + \ cdots + \ frac {X _ {\ lfloor N / 2 \ rfloor}} {N} e ^ {\ lfloor N / 2 \ rfloor it} + \ frac {X _ {\ lfloor N / 2 \ rfloor + 1}} {N} e ^ {- \ lfloor N / 2 \ rfloor it} + \ cdots + \ frac { X_ {N-1}} {N} e ^ {- it}$ pour $N$ impair,

o?? les coefficients X _k / N sont donn??es par la transform??e DFT x _n ci-dessus, satisfait ?? la propri??t?? d'interpolation $p (2 \ pi n / N) = x_n$ pour $n = 0, \ ldots, N-1$ .

Pour encore $N$ , Notez que la Composante de Nyquist $\ Frac {{X_ N / 2}} {N} \ cos (NT / 2)$ est trait??e sp??cialement.

Cette interpolation est pas unique: aliasing implique que l'on peut ajouter ?? l'une quelconque des N fr??quences de sinuso??de complexe (par exemple, changement $e ^ {- it}$ ?? $e ^ {i (N-1) t}$ ) Sans changer la propri??t?? d'interpolation, mais donnant des valeurs diff??rentes entre le $x_n$ Le secteur. Le choix ci-dessus, cependant, est typique parce qu'il a deux propri??t??s utiles. Tout d'abord, il se compose de sinuso??des dont les fr??quences ont la plus petite des amplitudes possibles, et donc minimise la moyenne quadratique pente $\ Int | p '(t) | 2 dt ^$ de la fonction d'interpolation. Deuxi??mement, si le $x_n$ sont des nombres r??els, puis $p (t)$ est r??el ainsi.

En revanche, la plus ??vidente trigonom??trique interpolation polynomiale la est celui dans lequel les fr??quences comprises entre 0 et $N-1$ (Au lieu de plus ou moins $-N / 2$ ?? $+ N / 2$ comme ci-dessus), similaire ?? la formule DFT inverse. Cette interpolation ne minimise pas la pente, et ne est g??n??ralement valeurs r??elles pour de vrai $x_n$ ; son utilisation est une erreur commune.

Le DFT unitaire

Une autre fa??on de regarder le DFT est ?? noter que, dans la discussion ci-dessus, la DFT peut ??tre exprim??e comme une Vandermonde matrice:

$\ Mathbf {F} = \ begin {bmatrix} \ omega_N ^ {0 \ cdot 0} et \ omega_N ^ {0 \ cdot 1} & \ & ldots \ omega_N ^ {0 \ cdot (N-1)} \\ \ omega_N ^ {1 \ cdot 0} et \ omega_N ^ {1 \ cdot 1} & \ & ldots \ omega_N ^ {1 \ cdot (N-1)} \\ \ vdots & \ & vdots \ ddots & \ vdots \\ \ omega_N ^ {(N-1) \ cdot 0} et \ omega_N ^ {(N-1) \ cdot 1} & \ & ldots \ omega_N ^ {(N-1) \ cdot (N-1)} \\ \ end {} bmatrix$

o??

$\ Omega_N = e ^ {- 2 \ pi i / N} \,$

est une primitive Racine ni??me de l'unit??. La transform??e inverse est alors donn??e par l'inverse de la matrice ci-dessus:

$\ Mathbf {F} ^ {- 1} = \ frac {1} {N} \ mathbf {F} ^ *$

Avec unitaires constantes de normalisation $1 / \ sqrt {N}$ , La DFT devient transformation unitaire, d??finie par une matrice unitaire:

$\ Mathbf {U} = \ mathbf {F} / \ sqrt {N}$

$\ Mathbf {U} ^ {- 1} = \ mathbf {U} ^ *$

$| \ Det (\ mathbf {U}) | = 1$

o?? det () est le facteur d??terminant fonction. Le d??terminant est le produit des valeurs propres, qui sont toujours $\ H 1$ ou $\ H i$ comme d??crit ci-dessous. Dans un espace vectoriel r??el, une transformation unitaire peut ??tre consid??r??e comme une simple rotation rigide du syst??me de coordonn??es, et toutes les propri??t??s d'une rotation rigide peut ??tre trouv??e dans la DFT unitaire.

L'orthogonalit?? de la TFD est maintenant exprim?? en condition de orthonormalit?? (qui se pose dans de nombreux domaines des math??matiques comme d??crit dans racine de l'unit??):

$\ Sum_ {m = 0} ^ {N-1} {U_ km} {U_ mn} ^ * = \ {delta_ kn}$

Si $\ Mathbf {X}$ est d??fini comme la DFT du vecteur unitaire $\ Mathbf {x}$ puis

$X_k = \ sum_ {n = 0} ^ {N-1} {U_ kn} x_n$

et le Plancherel th??or??me est exprim?? comme suit:

$\ Sum_ {n = 0} ^ {N-1} x_n y_n ^ * = \ sum_ {k = 0} ^ {N-1} x_k y_k ^ *$

Si nous consid??rons la DFT comme juste une transformation qui sp??cifie simplement les composantes d'un vecteur dans un nouveau syst??me de coordonn??es de coordonn??es, le pr??c??de est juste la d??claration que le produit scalaire de deux vecteurs est conserv?? sous une transformation unitaire DFT. Pour le cas particulier $\ Mathbf {x} = \ mathbf {y}$ Ceci implique que la longueur d'un vecteur est conserv?? comme bien ce est juste De Parseval th??or??me:

$\ Sum_ {n = 0} ^ {N-1} | x_n | ^ 2 = \ sum_ {k = 0} ^ {N-1} | x_k | ^ 2$

Exprimant le DFT inverse en termes de DFT

Une propri??t?? utile de la TFD est que la TFD inverse peut ??tre facilement exprim?? en termes de (avant) DFT, via plusieurs ??trucs?? bien connus. (Par exemple, dans les calculs, il est souvent commode de mettre en oeuvre uniquement une transform??e de Fourier rapide de transform??e correspondant ?? une direction et ensuite pour obtenir la transformation autre direction ?? partir de la premi??re).

Premi??rement, nous pouvons calculer la DFT inverse en inversant les entr??es:

$\ Mathcal {F} ^ {- 1} (\ {x_n \}) = \ mathcal {F} (\ {x_ {N - n} \}) / N$

(Comme d'habitude, les indices sont interpr??t??s modulo $N$ ; Ainsi, par $n = 0$ , Nous avons $x_ {N-0} = x_0$ .)

Deuxi??mement, on peut aussi conjuguer les entr??es et les sorties:

$\ Mathcal {F} ^ {- 1} (\ mathbf {x}) = \ mathcal {F} (\ mathbf {x} ^ *) ^ * / N$

Troisi??mement, une variante de cette conjugaison tour, ce qui est parfois pr??f??rable car elle ne n??cessite aucune modification des valeurs de donn??es, comprend la permutation des parties r??elles et imaginaires (qui peut ??tre fait sur un ordinateur simplement en modifiant pointeurs). D??finir swap ( $x_n$ ) Comme $x_n$ avec ses parties r??elles et imaginaires permut??es, ce est-si $x_n = a + b i$ puis ??changer ( $x_n$ ) Est $b + a i$ . ??quivalente, swap ( $x_n$ ) Est ??gal $i ^ * X_n$ . Puis

$\ Mathcal {F} ^ {- 1} (\ mathbf {x}) = \ {textrm ??change} (\ mathcal {F} (\ {textrm ??change} (\ mathbf {x}))) / N$

Autrement dit, la transformation inverse est la m??me que la transform??e directe avec les parties r??elles et imaginaires permut??es pour l'entr??e et la sortie, jusqu'?? une normalisation (Duhamel et al., 1988).

L'astuce de conjugaison peut ??galement ??tre utilis?? pour d??finir une nouvelle transformation, ??troitement li??e ?? la DFT, ce est- involutive qui est, qui est son propre inverse. En particulier, $T (\ mathbf {x}) = \ mathcal {F} (\ mathbf {x} ^ *) / \ sqrt {N}$ est clairement son propre inverse: $T (T (\ mathbf {x})) = \ mathbf {x}$ . Une transformation involutive ??troitement apparent?? (par un facteur de (1 + i) / √2) est $H (\ mathbf {x}) = \ mathcal {F} ((1 + i) \ mathbf {x} ^ *) / \ sqrt {} 2N$ , Depuis la $(1 + i)$ facteurs $H (H (\ mathbf {x}))$ annuler l'2. Pour les entr??es r??elles $\ Mathbf {x}$ , La partie r??elle de $H (\ mathbf {x})$ ne est autre que la transform??e de Hartley discr??te, qui est ??galement involutive.

Valeurs et vecteurs propres

Les valeurs propres de la matrice DFT sont simples et bien connu, alors que les vecteurs propres sont compliqu??es, pas unique, et font l'objet de recherches.

Consid??rons la forme unitaire $\ Mathbf {U}$ d??fini ci-dessus pour la longueur de DFT $N$ O?? $\ Mathbf {U} _ {m, n} = \ omega_N ^ {mn} / \ sqrt {N} = \ exp (-2 \ pi i mn / N) / \ sqrt {N}$ . Cette matrice v??rifie l'??quation:

$\ Mathbf {U} ^ 4 = \ mathbf {I}.$

Ceci peut ??tre vu ?? partir des propri??t??s inverses ci-dessus: en service $\ Mathbf {U}$ donne deux fois les donn??es originales dans l'ordre inverse, afin d'exploitation $\ Mathbf {U}$ quatre fois redonne les donn??es d'origine et est ainsi le matrice identit??. Cela signifie que les valeurs propres $\ Lambda$ satisfaire une ??quation caract??ristique:

$\ Lambda ^ 4 = 1.$

Par cons??quent, les valeurs propres de $\ Mathbf {U}$ sont la quatri??me racines de l'unit??: $\ Lambda$ est une, -1, + i, ou - i.

Depuis il ya seulement quatre valeurs propres distinctes pour ce $N \ N fois$ matrice, ils ont une certaine multiplicit?? . La multiplicit?? donne le nombre de vecteurs propres lin??airement ind??pendants correspondant ?? chaque valeur propre. (Notez qu'il existe N vecteurs propres ind??pendants; une matrice unitaire ne est jamais d??fectueux.)

Le probl??me de leur multiplicit?? a ??t?? r??solu par McClellan et des Parcs (1972), bien qu'il ait ??t?? r??v??l?? plus tard avoir ??t?? ??quivalent ?? un probl??me r??solu par Gauss (Dickinson et Steiglitz, 1982). La multiplicit?? d??pend de la valeur de $N$ modulo 4, et est donn?? par le tableau suivant:

Les multiplicit??s des valeurs propres λ de la matrice unitaire U DFT en fonction de la taille N transformer (en termes d'un nombre entier *m).*
taille N	λ = 1	λ = -1	λ = - i	λ + i =
4 m	m + 1	m	m	m - 1
4 m + 1	m + 1	m	m	m
4 m 2 +	m + 1	m + 1	m	m
4 m + 3	m + 1	m + 1	m + 1	m

Malheureusement, pas de formule analytique simple pour les vecteurs propres est connu. En outre, les vecteurs propres ne sont pas uniques car toute combinaison lin??aire des vecteurs propres pour la m??me valeur propre est aussi un vecteur propre pour cette valeur propre. Diff??rents chercheurs ont propos?? diff??rents choix de vecteurs propres, s??lectionn?? pour satisfaire des propri??t??s utiles comme orthogonalit?? et d'avoir des formes "simples" (par exemple, McClellan et des Parcs, 1972; Dickinson et Steiglitz, 1982; Gr??nbaum, 1982; Atakishiyev et loup, 1997;. Candan et al, 2000; Hanna et al., 2004).

Le choix des vecteurs propres de la matrice DFT a pris de l'importance ces derni??res ann??es dans le but de d??finir un analogue discret de la transform??e de Fourier-fractionn??e matrice DFT peuvent ??tre prises pour les puissances fractionnaires par exponentiation des valeurs propres (par exemple, Rubio et Santhanam, 2005). Pour le continue ?? transform??e de Fourier, les fonctions propres orthogonales naturels sont la Fonctions de Hermite, pour divers analogues discr??tes de celles-ci ont ??t?? utilis??s comme vecteurs propres de la TFD, tels que la Polyn??mes Kravchuk (Atakishiyev et Wolf, 1997). Le ??meilleur?? choix de vecteurs propres ?? d??finir une transform??e de Fourier discr??te fractionn??e reste une question ouverte, cependant.

Le DFT r??elle entr??e

Si $x_0, \ ldots, x_ {N-1}$ sont des nombres r??els , car elles sont souvent dans des applications pratiques, la DFT ob??it ?? la sym??trie:

$X_k = X_ {N-k} ^ *,$

o?? l'??toile d??signe conjugaison complexe et les indices sont interpr??t??s modulo N.

Par cons??quent, la sortie DFT pour les entr??es r??elles est moiti?? redondante, et l'on obtient l'information compl??te en ne regardant ?? peu pr??s la moiti?? des sorties $X_0, \ ldots, X_ {N-1}$ . Dans ce cas, l'??l??ment "DC" $X_0$ est purement r??el, et m??me pour l'??l??ment n "Nyquist" $X_ {N / 2}$ est aussi r??el, donc il ya exactement N non redondants nombres r??els au premier semestre + ??l??ment de Nyquist de la sortie complexe X.

Utilisation La formule d'Euler, le polyn??me d'interpolation trigonom??trique peut alors ??tre interpr??t??e comme une somme de fonctions sinus et cosinus.

G??n??ralis?? / d??cal?? DFT

Il est possible de d??caler l'??chantillonnage transformer dans le temps et / ou dans le domaine fr??quentiel par certains changements r??els a et b, respectivement. Ce est parfois connu comme un DFT g??n??ralis??e (ou GDFT), aussi appel?? le DFT DFT d??plac?? ou offset, et poss??de des propri??t??s analogues ?? la DFT ordinaire:

$X_k = \ sum_ {n = 0} ^ {N-1} x_n e ^ {- \ frac {2 \ pi i} {N} (k + b) (n + a)} \ quad \ quad k = 0, \ dots, N-1$

Le plus souvent, d??cale de $1/2$ (La moiti?? d'un ??chantillon) sont utilis??s. Bien que la DFT ordinaire correspond ?? un signal p??riodique ?? la fois dans les domaines temporel et de fr??quence, $a = 1/2$ produit un signal qui est anti-p??riodique dans le domaine fr??quentiel ( $X_ {k + N} = - x_k$ ) Et vice-versa pour $b = 1/2$ . Ainsi, le cas sp??cifique de $a = b = 1/2$ est connu comme un impair temps impair fr??quence transform??e de Fourier discr??te (ou O ² DFT). Cette d??cal?? transformations sont le plus souvent utilis??s pour les donn??es sym??triques, pour repr??senter les diff??rentes sym??tries limites, et pour les donn??es r??elles sym??triques qu'ils correspondent aux diff??rentes formes de la discr??te et cosinus transformations sinus.

Un autre choix est int??ressant $a = b = - (N-1) / 2$ , Qui est appel?? le DFT centr??e (ou CDFT). Le DFT centr??e a la propri??t?? utile que, lorsque $N$ est un multiple de quatre, chacune de ses quatre valeurs propres (voir ci-dessus) ont multiplicit??s ??gales (Rubio et Santhanam, 2005).

La transform??e de Fourier discr??te peut ??tre consid??r??e comme un cas particulier de la transform??e en z, ??valu??s sur le cercle unit?? dans le plan complexe; plus z transformations g??n??rales correspondent ?? des changements complexes a et b ci-dessus.

Multidimensionnelle DFT

Le DFT ordinaire calcule le transformer d'un ensemble de donn??es "unidimensionnel": une s??quence (ou array) $x_n$ ce est une fonction d'une variable discr??te $n$ . Plus g??n??ralement, on peut d??finir le DFT multidimensionnelle d'un tableau multidimensionnel $x_ {n_1, n_2, \ dots, n_d}$ ce est une fonction de $r??$ variables discr??tes $N_ \ ell = 0, 1, \ dots, N_ \ ell-1$ pour $\ Ell$ en $1, 2, \ dots, d$ :

$X_ {k_1, k_2, \ dots, k_d} = \ {sum_ n_1 = 0} ^ {} N_1-1 \ left (\ omega_ {} ^ {N_1 ~ k_1 n_1} \ {sum_ n_2 = 0} ^ {N_2- 1} \ left (\ omega_ {} ^ {N_2 ~ k_2 n_2} \ cdots \ {sum_ n_d = 0} ^ {N_d-1} \ omega_ {} ^ {N_d ~ k_d n_d} \ cdot x_ {n_1, n_2, \ dots, n_d} \ right) \ cdots \ right) \,,$

o?? $\ Omega_ {N_ \ ell} = \ exp (-2 \ pi i / N_ \ ell)$ comme ci-dessus et le $r??$ Les indices de production ex??cut??s ?? partir $K_ \ ell = 0, 1, \ dots, N_ \ ell-1$ . Ceci est exprim?? dans plus compacte notation vectorielle, o?? nous d??finissons $\ Mathbf {n} = (n_1, n_2, \ dots, n_d)$ et $\ Mathbf {k} = (k_1, k_2, \ dots, k_d)$ comme $r??$ vecteurs de dimension des indices de 0 ?? $\ Mathbf {N} - 1$ , Que nous d??finissons comme $\ Mathbf {N} - 1 = (N_1 - 1, N_2 - 1, \ dots, N_d - 1)$ :

$X_ \ mathbf {k} = \ sum _ {\ mathbf {n} = 0} ^ {\ mathbf {N}} -1 e ^ {- 2 \ pi i \ mathbf {k} \ cdot (\ mathbf {n} / \ mathbf {N})} x_ \ mathbf {n} \,,$

o?? la division $\ Mathbf {n} / \ mathbf {N}$ est d??fini comme ??tant $\ Mathbf {n} / \ mathbf {N} = (n_1 / N_1, \ dots, n_d / N_d)$ ?? effectuer ??l??ment par ??l??ment, et la somme repr??sente l'ensemble des sommations imbriqu??s ci-dessus.

L'inverse de la transform??e DFT multidimensionnelle est analogue au cas unidimensionnel, donn??e par:

$x_ \ mathbf {n} = \ frac {1} {\ prod _ {\ ell = 1} ^ d N_ \ ell} \ sum _ {\ mathbf {k} = 0} ^ {\ mathbf {N} -1} e ^ {2 \ pi i \ mathbf {n} \ cdot (\ mathbf {k} / \ mathbf {N})} X_ \ mathbf {k} \,.$

Le multidimensionnelle DFT a une interpr??tation simple. Tout comme le DFT unidimensionnelle exprime l'entr??e $x_n$ comme une superposition de sinuso??des, la DFT multidimensionnel exprime l'entr??e comme une superposition de ondes planes, ou sinuso??des oscillant long de la direction $\ Mathbf {k} / \ mathbf {N}$ dans l'espace et ayant une amplitude $X_ \ mathbf {k}$ . Une telle d??composition est d'une grande importance pour tout, de traitement num??rique de l'image (d = 2) pour r??soudre des ??quations aux d??riv??es partielles en trois dimensions (d = 3) en brisant la solution dans des ondes planes.

Calcul, la DFT multidimensionnel est simplement la composition d'une s??quence de TFD ?? une dimension le long de chaque dimension. Par exemple, dans le cas bidimensionnel $x_ {n_1, n_2}$ on peut d'abord calculer la $N_1$ TFD ind??pendants des rang??es (par exemple, le long de $n_2$ ) Pour former une nouvelle matrice $y_ {n_1, k_2}$ , Puis calculer la $N_2$ TFD ind??pendants $y$ le long des colonnes (le long de $n_1$ ) Pour former le r??sultat final $X_ {k_1, k_2}$ . Ou, on peut transformer les colonnes et les lignes puis-l'ordre est sans importance parce que les sommations imbriqu??s ci-dessus trajet .

De ce fait, compte tenu de fa??on ?? calculer une DFT unidimensionnelle (par exemple, un algorithme FFT unidimensionnelle ordinaire), on a imm??diatement un moyen pour calculer efficacement la DFT multidimensionnel. Ceci est connu comme un algorithme ligne-colonne, mais il ya aussi intrins??quement algorithmes FFT multidimensionnels.

La v??ritable entr??e multidimensionnelle DFT

Si les entr??es $x_ {n_1, n_2, \ dots, n_d}$ sont des nombres r??els , car elles sont souvent dans des applications pratiques, les sorties DFT pr??sentent une sym??trie conjugu?? similaire au cas unidimensionnel ci-dessus:

$X_ {K_1, k_2, \ dots, k_d} = {X_ N_1 - K_1, N_2 - k_2, \ dots, N_d - k_d} ^ *,$

o?? l'??toile repr??sente la conjugaison complexe et le $\ Ell$ indice -i??me est interpr??t??e modulo $N_ \ ell$ (Par $\ Ell = 1,2, \ ldots, d$ ).

Applications

Le DFT a vu une large utilisation dans un grand nombre de domaines; nous ne esquissons quelques exemples ci-dessous (voir aussi les r??f??rences ?? la fin). Toutes les applications de la TFD d??pendent essentiellement de la disponibilit?? d'un algorithme rapide pour calculer des transform??es de Fourier discr??te et leurs inverses, un transform??e de Fourier rapide.

L'analyse spectrale

Lorsque la TFD est utilis?? pour analyse spectrale, la $\ {X_n \} \,$ s??quence repr??sente g??n??ralement un ensemble fini de uniform??ment espac??s temps-??chantillons de quelque signal $x (t) \,$ , O?? t repr??sente le temps. La conversion du temps continu aux ??chantillons (en temps discret) change le sous-jacent Transform??e de Fourier de x (t) dans un Fourier discr??te en temps de transformer (DTFT), ce qui implique g??n??ralement un type de distorsion appel?? aliasing. Choix d'une fr??quence d'??chantillonnage appropri?? (voir Fr??quence de Nyquist) est la cl?? de minimiser cette distorsion. De m??me, la conversion d'une s??quence tr??s long (ou infinie) ?? une taille implique un type de distorsion appel??e fuites, qui se manifeste comme une perte de d??tail (r??solution alias) dans le DTFT. Choix d'une longueur sous-s??quence appropri??e est la cl?? primaire de minimiser cet effet. Lorsque les donn??es disponibles (et de temps pour le traiter) est sup??rieure ?? la quantit?? n??cessaire pour atteindre la r??solution de fr??quence d??sir??e, une technique classique consiste ?? effectuer plusieurs TFD, par exemple pour cr??er une spectrogramme. Si le r??sultat souhait?? est un spectre de puissance et le bruit al??atoire ou est pr??sente dans les donn??es, la moyenne des composantes d'amplitude de la TFD multiple est un proc??d?? utile pour r??duire la variance du spectre (??galement appel??e p??riodogramme dans ce contexte); deux exemples de ces techniques sont le Proc??d?? et le Welch M??thode Bartlett.

Une derni??re source de distorsion (ou peut-??tre illusion) est la transform??e DFT lui-m??me, parce que ce ne est qu'un ??chantillon de la DTFT discr??te, qui est une fonction d'un domaine fr??quentiel continu. Ce peut ??tre att??nu?? par l'augmentation de la r??solution de la TFD. Cette proc??dure est illustr??e dans le temps discret transform??e de Fourier article.

La proc??dure est parfois appel??e z??ro rembourrage, qui est un mode de r??alisation particulier est utilis?? en conjonction avec le transform??e de Fourier rapide (FFT). L'inefficacit?? du effectuer des multiplications et des additions avec z??ro-??valu??e "??chantillons" est plus que compens??e par l'efficacit?? intrins??que de la FFT.
Comme d??j?? indiqu??, les fuites impose une limite sur la r??solution inh??rente ?? la DTFT. Donc, il ya une limite pratique ?? l'avantage qui peut ??tre obtenu ?? partir d'un DFT fine.

La compression de donn??es

Le domaine du traitement de signal num??rique se appuie fortement sur les op??rations dans le domaine de fr??quence (ce est ?? dire sur la transform??e de Fourier). Par exemple, plusieurs l'image avec perte et les m??thodes de compression audio emploient transform??e de Fourier discr??te: le signal est d??coup?? en courts segments, chacun se transforme, puis les coefficients de Fourier de hautes fr??quences, qui sont suppos??s ??tre imperceptible, sont rejet??s. Le d??compresseur calcule la transform??e inverse sur la base de ce nombre r??duit de coefficients de Fourier. (Applications de compression utilisent souvent une forme sp??cialis??e de la TFD, le transform??e en cosinus discr??te ou parfois le transformer cosinus discr??te modifi??e).

??quations aux d??riv??es partielles

Transform??es de Fourier discr??tes sont souvent utilis??s pour r??soudre des ??quations aux d??riv??es partielles , o?? de nouveau la DFT est utilis??e comme une approximation pour le s??rie de Fourier (qui est r??cup??r?? dans la limite de N infinie). L'avantage de cette approche est qu'elle ??largit le signal dans exponentielles complexes e ^inx, qui sont propres de la diff??renciation: d dx e ^inx / = e dans ^inx. Ainsi, dans la repr??sentation de Fourier, la diff??renciation est simple-nous multiplions simplement en en. Une ??quation diff??rentielle lin??aire ?? coefficients constants est transform??e en une ??quation alg??brique facilement r??soluble. On utilise alors la TFD inverse pour transformer le r??sultat dans la repr??sentation spatiale ordinaire. Une telle approche est appel??e m??thode spectrale.

Multiplication polynomiale

Supposons que nous souhaitons pour calculer le produit polyn??me c (x) = a (x) ?? b (x). L'expression du produit ordinaire pour les coefficients de c implique un lin??aire (acyclique) convolution, o?? les indices ne ont pas "se enrouler autour." Ceci peut ??tre r????crite sous la forme d'une convolution cyclique en prenant les vecteurs de coefficients de a (x) et b (x) avec terme constant, puis l'ajout de z??ros de sorte que le coefficient r??sultant des vecteurs a et b ont la dimension d> deg (a (x) ) + deg (b (x)). Ensuite,

$\ Mathbf {c} = \ mathbf {a} * \ mathbf {b}$

O?? c est le vecteur des coefficients C (x), et l'op??rateur de convolution $* \,$ est d??fini de sorte

$c_n = \ {sum_ m = 0} ^ {1} d-a_m b_ {nm \ \ mathrm {mod} \ d} \ qquad \ qquad \ qquad n = 0,1, ..., D-1$

Mais convolution devient multiplication sous la DFT:

$\ Mathcal {F} (\ mathbf {c}) = \ mathcal {F} (\ mathbf {a}) \ mathcal {F} (\ mathbf {b})$

Voici le produit vectoriel est prise ??l??ment par ??l??ment. Ainsi, les coefficients du produit polyn??me C (X) ne sont que les termes 0, ..., deg (a (x)) + deg (b (x)) du vecteur de coefficient

$\ Mathbf {c} = \ mathcal {F} ^ {- 1} (\ mathcal {F} (\ mathbf {a}) \ mathcal {F} (\ mathbf {b})).$

Avec un Transform??e de Fourier rapide, l'algorithme r??sultant prend O (n log n) op??rations arithm??tiques. En raison de sa simplicit?? et de rapidit??, le Cooley-Tukey algorithme FFT, qui est limit??e ?? tailles composites, est souvent choisi pour l'op??ration de transformation. Dans ce cas, d doit ??tre choisi comme le plus petit entier plus grand que la somme des degr??s de polyn??mes entr??e qui est factorisable en petits facteurs premiers (par exemple de 2, 3 et 5, en fonction de l'application de la FFT).

Multiplication des grands entiers

Le plus rapide connue algorithmes pour la multiplication de tr??s grands nombres entiers utilisent la m??thode de multiplication polyn??me indiqu?? ci-dessus. Les entiers peuvent ??tre trait??es comme la valeur d'un polyn??me ??valu?? sp??cifiquement ?? la base du num??ro, avec les coefficients du polyn??me correspondant ?? des chiffres dans ladite base. Apr??s multiplication polynomiale, une ??tape de propagation de relativement faible complexit?? compl??te la multiplication.

Certains de transform??e de Fourier discr??te paires

**Certaines paires DFT**
$x_n = \ frac {1} {N} \ sum_ {k = 0} ^ {N-1} x_k \ cdot e ^ {i 2 \ pi kn / N}$	$X_k = \ sum_ {n = 0} ^ {N-1} x_n \ cdot e ^ {- i 2 \ pi kn / N}$	Note
$x_n cdot e ^ {i 2 \ pi nl / N} \ \,$	$X_ {k-l} \,$	Maj th??or??me
$x_ {n-l} \,$	$X_k \ cdot e ^ {- i 2 \ pi kl / N}$	Maj th??or??me
$x_n \ in \ mathbb {R}$	$X_k = X_ {N-k} ^ * \,$	Immobilier DFT
$un ^ n \,$	$\ Frac {1-a ^ N} {1-a \ cdot e ^ {- i 2 \ pi k / N}}$
${N-1 \ choisir n} \,$	$\ Left (1 + e ^ {- i 2 \ pi k / N} \ right) ^ {N-1} \,$

D??rivation en s??rie de Fourier

La DFT peut ??tre calcul??e comme une troncature de la s??rie de Fourier d'une suite p??riodique de impulsions.

DFT sur les champs autres que les nombres complexes

Un grand nombre des propri??t??s de la transform??e DFT ne d??pendent que du fait que $e ^ {- \ frac {2 \ pi i} {N}}$ est un racine primitive de l'unit??, parfois not??e $\ Omega_N$ ou $W_N$ (De sorte que $\ Omega_N ^ N = 1$ ). Ces propri??t??s comprennent l'exhaustivit??, l'orthogonalit??, Plancherel / Parseval, la p??riodicit??, d??calage, convolution, et les propri??t??s de unitarit?? ci-dessus, ainsi que de nombreux algorithmes FFT. Pour cette raison, la transform??e de Fourier discr??te peut ??tre d??fini ?? l'aide de racines de l'unit?? en d'autres domaines que les nombres complexes; Pour plus d'informations, voir transform??e de Fourier discr??te (g??n??ral).

R??cup??r?? ?? partir de " http://en.wikipedia.org/w/index.php?title=Discrete_Fourier_transform&oldid=206659692 "