/*************************************************************************************************************************************/
/* */
/* 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) ∈ [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 ∈ [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} ∈ [0,X-1]x[0,Y-1], 'p' designe 'pi' et 'i' la racine de -1. */
/* */
/* */
/*************************************************************************************************************************************/
