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 "

Privacy Policy and Contacts (IT)