next up previous contents
suivant: Calcul du nombre d'opérations monter: La transformée de Fourier précédent: La transformée en cosinus   Table des matières

L'algorithme de calcul de transformée de Fourier rapide

Cet algorithme célèbre a été inventé par Cooley et Tukey, ingénieurs dans le centre de recherche d'IBM au début des années 1960. Il a eu, du fait de son efficacité, un impact considérable sur le développement des applications en traitement numérique des signaux. Un calcul de transformée de Fourier discrète est un calcul de produit d'une matrice par un vecteur. Il nécessite donc $T^2$ multiplications/additions de nombres complexes. Si on suppose qu'un calculateur effectue $10^9$ opérations par seconde, un calcul de transformée sur un signal de $T=10^3$ échantillons nécessitera $10^{-3}$s. Un calcul sur une image de taille $T\times T=10^6$ nécessitera $T^4$ soit $10^{12}$ opérations et une quinzaine de minutes de calcul. Si on envisage de traiter des données dans un domaine à trois dimensions (sur des vecteurs de taille $T \times T\times T$) il faudrait alors effetuer $T^6$ soit $10^{18}$ opérations, ce qui nécessite quelques dizaines d'années. La transformée de Fourier rapide réduit considérablement le nombre d'opérations à effectuer: au lieu d'effectuer $T^2$ opérations il suffira d'en faire $T \log_2
T$. Dans les trois exemples précédents on aura à faire $10^4$, $2\times10^7$ et $3\times10^{10}$ opérations ce qui nécessitera respectivement $10^{-5}s$, $2\times 10^{-2}s$ et $30$s ... Pour expliquer cet algorithme, nous utiliserons la récursivité en montrant que le calcul d'une transformée de Fourier de taille $T$ se ramène au calcul de deux transformée de Fourier de taille $T/2$ suivi de $T/2$ multiplications. On veut calculer Pour $k=0,\cdots,T-1$
\begin{displaymath}
X(k)=\sum_{t=0}^{T-1}x(t)\exp(-2\pi j \frac{k.t}{T})
\end{displaymath} (191)

On pose $t=2n$ si $t$ est pair et $t=2n+1$ si $t$ est impair. $X(k)$ s'écrit alors, en posant $N=T/2$
\begin{displaymath}
X(k)=\sum_{n=0}^{N-1}x(2n)\exp(-2\pi j \frac{k.2n}{T})
+\sum_{n=0}^{N-1}x(2n+1)\exp(-2\pi j \frac{k.(2n+1)}{T})
\end{displaymath} (192)

Nommons les séquences
$\displaystyle t=0,\cdots,2N-1$ $\textstyle :$ $\displaystyle x_{2N}(t)=x(t)$ (193)
$\displaystyle n=0,\cdots,N-1$ $\textstyle :$ $\displaystyle x_{N}^o(n)=x(2n)$ (194)
$\displaystyle n=0,\cdots,N-1$ $\textstyle :$ $\displaystyle x_{N}^i(n)=x(2n+1)$ (195)
$\displaystyle k=0,\cdots,2N-1$ $\textstyle :$ $\displaystyle X_{2N}(k)=X(k)$ (196)

Avec ces notations, l'eq. (192) devient
\begin{displaymath}
X_{2N}(k)=\sum_{n=0}^{N-1}x_{N}^o(n)\exp(-2\pi j \frac{k.n}...
...}^i(n)\exp(-2\pi j \frac{k.n}{N})\exp(-2\pi j \frac{k}{2N})
\end{displaymath} (197)

Dans la deuxième sommation du membre de droite de l'équation (197), le facteur $\exp(-2\pi j \frac{k}{2N})$ ne dépend pas de $n$. On a donc l'écriture Pour $k=0,\cdots,2N-1$
\begin{displaymath}
X_{2N}(k)=\left[\sum_{n=0}^{N-1}x_{N}^o(n)\exp(-2\pi j \fra...
...um_{n=0}^{N-1}x_{N}^i(n)\exp(-2\pi j
\frac{k.n}{N})\right]
\end{displaymath} (198)

Si
\begin{displaymath}
0\le k \le N-1,
\end{displaymath} (199)

on reconnait dans les deux expressions entre crochets les transformées de Fourier discrètes des séquences des échantillons de numéro pair $x_{N}^o(n)$ et des échantillons de numéro impair $x_{N}^i(n)$ que nous nommons $X_{N}^o(k)$ et $X_{N}^i(k)$ Pour $k=0,\cdots,N-1$
\begin{displaymath}
X_{2N}(k)=X_{N}^o(k)
+\exp(-\pi j \frac{k}{N})X_{N}^i(k)
\end{displaymath} (200)

Lorsque $N\le k \le 2N-1$, on peut écrire
\begin{displaymath}
k=\ell+N
\end{displaymath} (201)

et remarquer que
\begin{displaymath}
\exp(-\pi j \frac{k}{N})=-\exp(-\pi j \frac{\ell}{N})
\end{displaymath} (202)

L'équation (198) devient alors Pour $\ell=0,\cdots,N-1$
$\displaystyle X_{2N}(\ell+N)=\left[\sum_{n=0}^{N-1}x_{N}^o(n)\exp(-2\pi j
\frac{(\ell+N).n}{N})\right]$     (203)
$\displaystyle +\exp(-2\pi j \frac{\ell+N}{2N})\left[\sum_{n=0}^{N-1}x_{N}^i(n)\exp(-2\pi j
\frac{(\ell+N).n}{N})\right]$      

et, en remarquant que
\begin{displaymath}
\exp(-2\pi j \frac{(\ell+N).n}{N})=\exp(-2\pi j \frac{\ell.n}{N})
\end{displaymath} (204)

en tenant compte de (200), on a une écriture analogue à l'éq. (200) Pour $\ell=0,\cdots,N-1$
\begin{displaymath}
X_{2N}(\ell+N)=X_{N}^o(\ell)
-\exp(-\pi j \frac{\ell}{N})X_{N}^i(\ell)
\end{displaymath} (205)

On peut changer le nom de la variable $\ell$ en $k$ et regrouper les deux équations (200) et (205) Pour $k=0,\cdots,N-1$
$\displaystyle X_{2N}(k)=X_{N}^o(k)
+\exp(-\pi j \frac{k}{N})X_{N}^i(k)$     (206)
$\displaystyle X_{2N}(k+N)=X_{N}^o(k)
-\exp(-\pi j \frac{k}{N})X_{N}^i(k)$     (207)

Les calculs correspondants sont représentés dans la figure 53.

Figure 53: Schéma de l'enchaînement des calculs de la transformée de Fourier rapide
\begin{figure}
\begin{picture}(156,76)
% thinlines
\put(-17,0){
\drawthickdo...
...
\drawcenteredtext{64.0}{10.0}{$x_{N}^i(N-1)$}
}
\end{picture}
\end{figure}

Cette formulation se traduit directement par une implémentation récursive. Toutefois la programmation de la plupart des processeurs est fondée sur une implémentation différente. On commence par effectuer toutes les opérations de réarrangement des données : Pour un vecteur de longueur $T$, construction d'un tableau de données d'adresse paire et d'un tableau de données d'adresse impaire de longueur $T/2$, ce rangement étant reproduit pour les deux moitiés de tableau de taille $T/2$, puis les quatre quarts de tableau de taille $T/4$, etc... Ceci revient à ranger la données $x(t)$ à l'adresse obtenue en lisant le code binaire de $t$ en sens inverse comme on peut le voir dans la table 1.

Tableau 1: Réordonnancement des données préalable dans le calcul de la transformée de Fourier rapide
abcd bcda cdba dcba
0000 0000 0000 0000
0001 0010 0100 1000
0010 0100 1000 0100
0011 0110 1100 1100
0100 1000 0010 0010
0101 1010 0110 1010
0110 1100 1010 0110
0111 1110 1110 1110
1000 0001 0001 0001
1001 0011 0101 1001
1010 0101 1001 0101
1011 0111 1101 1101
1100 1001 0011 0011
1101 1011 0111 1011
1110 1101 1011 0111
1111 1111 1111 1111

On effectue ensuite la même opération sur chacun des deux tableaux. Ensuite on effectue séquentiellement les multiplications par les nombres complexes de la forme $exp 2\pi j\frac{kn}{N}$ pour calculer les $T/2$ transformées de Fourier de taille 2, puis les $T/4$ transformées de taille 4, et ainsi de suite jusqu'à obtenir les 2 transformées de Fourier de taille $T/2$ et finalement la transformée de Fourier de taille $T$.

Sous-sections
next up previous contents
suivant: Calcul du nombre d'opérations monter: La transformée de Fourier précédent: La transformée en cosinus   Table des matières
Leroux Joel
2000-11-14