Définition de la Transformée de Fourier






Jean-François COLONNA
www.lactamme.polytechnique.fr
jean-francois.colonna@polytechnique.edu
CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641, Ecole Polytechnique, CNRS, 91128 Palaiseau Cedex, France
france telecom, France Telecom R&D

[Site Map, Help and Search [Plan du Site, Aide et Recherche]]
[The Y2K bug [Le bug de l'an 2000]]
[Croyez-vous que les Nombres Réels existent dans un ordinateur et que les calculs flottants sont sûrs ?]
[N'oubliez pas de visiter Une Machine Virtuelle à Explorer l'Espace-Temps où vous trouverez plus de 5400 images à la frontière de l'Art et de la Science]
(Site WWW CMAP28 : cette page a été créée le 24/01/2001 et mise à jour le 28/01/2014 15:04:36 -CET-)



/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        D E F I N I T I O N   D E   L A   T R A N S F O R M E E   D E   F O U R I E R  :                                           */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Cas mono-dimensionnel :                                                                                                    */
/*        ---------------------                                                                                                      */
/*                                                                                                                                   */
/*                    Soit une fonction "discrete" 'f'                                                                               */
/*                  connue aux points (0,1,2,...,N-1),                                                                               */
/*                  ce qui signifie que l'on connait les                                                                             */
/*                  valeurs (f(0),f(1),f(2),...,f(N-1)).                                                                             */
/*                  Designons par T (f,u) la transformee de                                                                          */
/*                                 N                                                                                                 */
/*                  Fourier "discrete" de la fonction 'f'                                                                            */
/*                  au point 'u' et calculee pour 'N' points.                                                                        */
/*                  Elle est definie par :                                                                                           */
/*                                                                                                                                   */
/*                            n=N-1                                                                                                  */
/*                            _____                u                                                                                 */
/*                            \           -(2.i.p.---.n)                                                                             */
/*                  T (f,u) = /     f(n).e         N        ou 'p' designe 'pi' et                                                   */
/*                   N        -----                         'i' la racine de -1.                                                     */
/*                             n=0                                                                                                   */
/*                                                                                                                                   */
/*                  'u' est appelee "frequence spatiale",                                                                            */
/*                  et varie dans [0,N-1], tout comme la                                                                             */
/*                  variable 'n'.                                                                                                    */
/*                                                                                                                                   */
/*                    L'algorithme dit de "transformee                                                                               */
/*                  rapide" (ou 'FFT" en anglais), repose                                                                            */
/*                  sur le raisonnement suivant :                                                                                    */
/*                                                                                                                                   */
/*                  posons, en supposant 'N' pair, et                                                                                */
/*                  meme une puissance de 2 (a cause                                                                                 */
/*                  de la dichotomie que l'on va mettre                                                                              */
/*                  en evidence) :                                                                                                   */
/*                                                                                                                                   */
/*                       N                                                                                                           */
/*                  M = ---,                                                                                                         */
/*                       2                                                                                                           */
/*                                                                                                                                   */
/*                  on a alors :                                                                                                     */
/*                                                                                                                                   */
/*                            m=M-1                                                                                                  */
/*                            _____                   u                           u       u                                          */
/*                            \              -(2.i.p.---.m)             -(2.i.p.(---.m + ---))                                       */
/*                  T (f,u) = /     [f(2.m).e         M     + f(2.m+1).e          M       N   ]                                      */
/*                   N        -----                                                                                                  */
/*                             m=0                                                                                                   */
/*                                                                                                                                   */
/*                            m=M-1                                        m=M-1                                                     */
/*                            _____                  u                 u   _____                    u                                */
/*                            \             -(2.i.p.---.m)    -(2.i.p.---) \               -(2.i.p.---.m)                            */
/*                  T (f,u) = /     f(2.m).e         M     + e         N  ./     f(2.m+1).e         M                                */
/*                   N        -----                                        -----                                                     */
/*                             m=0                                          m=0                                                      */
/*                                                                                                                                   */
/*                  soit donc :                                                                                                      */
/*                                                                                                                                   */
/*                                                      u                                                                            */
/*                                             -(2.i.p.---)                                                                          */
/*                  T (f,u) = T (f.paire,u) + e         N  .T (f.impaire,u),                                                         */
/*                   N         N                             N                                                                       */
/*                            ---                           ---                                                                      */
/*                             2                             2                                                                       */
/*                                                                                                                                   */
/*                  avec :                                                                                                           */
/*                                                                                                                                   */
/*                  T (f,u) = f(du_point_unique), quel que soit 'u'.                                                                 */
/*                   1                                                                                                               */
/*                                                                                                                                   */
/*                  ou 'f.paire/impaire,u' signifie que l'on                                                                         */
/*                  ne conserve que les coefficients pairs et                                                                        */
/*                  impairs de la fonction 'f' respectivement.                                                                       */
/*                  Ainsi, on divise par 2 exactement le nombre                                                                      */
/*                  de points sur lesquels faire les calculs,                                                                        */
/*                  tout en arrivant a une definition recursive                                                                      */
/*                  de la transformee de Fourier...                                                                                  */
/*                                                                                                                                   */
/*                    Le cout de l'algorithme de transformee                                                                         */
/*                  de Fourier rapide mono-dimensionnelle est                                                                        */
/*                  donc en N.Log(N).                                                                                                */
/*                                                                                                                                   */
/*                    En ce qui concerne les periodes de la                                                                          */
/*                  frequence spatiale 'u', on peut dire la                                                                          */
/*                  chose suivante :                                                                                                 */
/*                                                                                                                                   */
/*                                           u                                                                                       */
/*                  pour T (f,u), on trouve ---, on peut donc                                                                        */
/*                        N                  N                                                                                       */
/*                  considerer que la periode de 'u' est 'N',                                                                        */
/*                  et donc 'u' est a considerer dans [0,N-1].                                                                       */
/*                  Alors que pour T (f.paire,u) et T (f.impaire,u),                                                                 */
/*                                  N                N                                                                               */
/*                                 ---              ---                                                                              */
/*                                  2                2                                                                               */
/*                             u                                                                                                     */
/*                  on trouve ---, on peut donc considerer que                                                                       */
/*                             M                                                                                                     */
/*                  la periode de 'u' est alors 'M' (ou 'M' est                                                                      */
/*                  la moitie de 'N') ; 'u' est alors a considerer                                                                   */
/*                  dans [0,M-1].                                                                                                    */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Cas bi-dimensionnel :                                                                                                      */
/*        -------------------                                                                                                        */
/*                                                                                                                                   */
/*                    Soit une fonction "discrete" 'f'                                                                               */
/*                  connue aux points (0,1,2,...,N-1)x(0,1,2,...,N-1),                                                               */
/*                  ce qui signifie que l'on connait les                                                                             */
/*                  valeurs (f(0,0),f(0,1),f(0,2),...,f(0,N-1),...,f(N-1,0),f(N-1,1),f(N-1,2),...,f(N-1,N-1)).                       */
/*                  Designons par T(f,u,v) la transformee de                                                                         */
/*                  Fourier "discrete" de la fonction 'f' aux points 'u' et 'v'.                                                     */
/*                  Elle est definie par :                                                                                           */
/*                                                                                                                                   */
/*                             y=Y-1  x=X-1                                                                                          */
/*                             _____  _____                   u       v                                                              */
/*                             \      \             -[2.i.p.(---.x + ---.y)]                                                         */
/*                  T(f,u,v) = /      /     f(x,y).e          X       Y                                                              */
/*                             -----  -----                                                                                          */
/*                              y=0    x=0                                                                                           */
/*                                                                                                                                   */
/*                  ou (u,v) E [0,X-1]x[0,Y-1], 'p' designe 'pi' et 'i' la racine de -1.                                             */
/*                                                                                                                                   */
/*                  Comme on le verra dans la programmation                                                                          */
/*                  qui suit, la 'FFT' bi-dimensionnelle peut                                                                        */
/*                  se ramener au calcul de 'FFT' mono-                                                                              */
/*                  dimensionnelles "orthogonales".                                                                                  */
/*                                                                                                                                   */
/*                    Le cout de l'algorithme de transformee                                                                         */
/*                  rapide de Fourier bi-dimensionnelle est donc                                                                     */
/*                  en 2N.N.Log(N) ; en effet, on effectue 'N'                                                                       */
/*                  transformees horizontales, puis 'N' trans-                                                                       */
/*                  formee verticales (d'ou le '2N'), chacune                                                                        */
/*                  etant en N.Log(N)... On notera que :                                                                             */
/*                                                                                                                                   */
/*                                 2             2      2                                                                            */
/*                  2N.N.Log(N) = N .2.Log(N) = N .Log(N ).                                                                          */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Transformees inverses :                                                                                                    */
/*        ---------------------                                                                                                      */
/*                                                                                                                                   */
/*                    Pour obtenir en mono- et bi-dimensionnel                                                                       */
/*                  la transformee inverse, il suffit de changer                                                                     */
/*                  le signe de l'exposant dans l'exponentielle :                                                                    */
/*                                                                                                                                   */
/*                             u=N-1                                                                                                 */
/*                             _____                 n                                                                               */
/*                          1  \              2.i.p.---.u                                                                            */
/*                  f(n) = --- /     T (f,u).e       N      ou n E [0,N-1], 'p' designe 'pi' et                                      */
/*                          N  -----  N                     'i' la racine de -1.                                                     */
/*                              u=0                                                                                                  */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*                                v=Y-1  u=X-1                                                                                       */
/*                                _____  _____                   x       y                                                           */
/*                            1   \      \               2.i.p.(---.u + ---.v)                                                       */
/*                  f(x,y) = ---- /      /     T(f,u,v).e        X       Y                                                           */
/*                             2  -----  -----                                                                                       */
/*                            N    v=0    u=0                                                                                        */
/*                                                                                                                                   */
/*                  ou {x,y} E [0,X-1]x[0,Y-1], 'p' designe 'pi' et 'i' la racine de -1.                                             */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*************************************************************************************************************************************/


(Nota : les lignes d'explications qui précédent sont des commentaires extraits des programmes ayant été utilisés pour calculer les images correspondantes. Ce programme en est un exemple parmi des centaines.)


Copyright (c) Jean-François Colonna, 2001-2014.
Copyright (c) France Telecom R&D and CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / Ecole Polytechnique, 2001-2014.