Discussion :

[Mat 74]

salut a tous,
voila depuis un petit moment je vois pamal de site qui parle de la transformée de fourier, en plus je crois que l'on peut faire des multiplication entre des grands nombre plus rapidement grâce à elle.
mais le problème c'est que je ne sais pas du tout de quoi il s'agit et je n'arrive pas à comprendre le concept.
vous allez me dire google. oui mais sur google je ne trouve que des sites qui en parle comme si on connaissait déjà, je n'ai pas trouver de site qui explique le principe très clairement et le plus simplement possible.
donc si qq1 a une url ... ou veux bien m'expliquer ...

merci
@+

[Neo82]

Salut

tu veux une explication sur la transformée de fourier?

Essaie de rechercher des cours de traitement du signal...

Si jamais tu ne trouves rien (j'en doute) je pourrai t'expliquer. Par contre je ne connais pas le rapport avec la multiplication des grands nombres

@+

[ceugniet]

Pour Neo82

Lorsque tu veux calculer un produit de deux nombres A et B dont la décomposition en base c est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
A = Somme (pour i=0 à n) de a[i]*c**i
B = Somme (pour j=0 à n) de b[j]*c**j

Alors le produit est donné par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
C = A * B =   [Somme (pour i=0 à n) de a[i]*c**i]  * [Somme (pour j=0 à n) de b[j]*c**j]
          = Somme (pour i=0 à n et j=0 à n) de a[i]*c**i * b[j]*c**j
          = Somme (pour i=0 à n et j=0 à n) de a[i]*b[j] * c**(i+j)

Il est alors naturel de regrouper les termes correspondant à des puissances égales de c :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
C = A * B = Somme (pour somexp=0 à 2n) de c**somexp * somme (pour i=0 à somexp) de a[i]*b[somexp-i]

Or l’expression

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

somme (pour i=0 à somexp) de a[i]*b[somexp-i]

ressemble fort à une convolution qui, on le sait est faite beaucoup plus rapidement avec une transformée de Fourier.

Bien sûr, il y a des tas de détails à régler, que je ne peux expliquer ici, mais je pense que tu peux ainsi voir au moins le rapport entre la multiplication de grands nombres et la transformée de Fourier.

Par ailleurs, il est illusoire de faire des calculs exacts avec la transformée de Fourier « normale » c’est à dire avec des sinus et des cosinus qui ne sont jamais exacts. Mais il existe d’autres algorithmes qui prennent modèle sur la transformée de Fourier et qui travaillent exactement,
car en nombres entiers. En effet, l’unique propriété qui permet l’algorithme de FFT (Fast Fourier Transform) est le fait que exp(2*pi*i) = 1 (avec i*i=-1) (j’écrirai plutôt [exp(2*pi*i/n)]**n = 1). C’est aussi l’unique propriété qui permet de transformer le calcul d’une convolution en trois transformées de Fourier : deux transformées aller, une multiplication terme à terme, et une transformée retour.

L’astuce (géniale) de l’inventeur de cet algorithme, est d’avoir créé des ensembles d’entiers où une puissance de dix, k, joue un rôle particulier et tels que k**n = 1.

Chaque nombre A et B est décomposé selon une base b qui est une puissance de dix. On crée un ensemble où précisément b**n = 1. Et on peut appliquer du même coup toute la théorie des transformées de fourier, FFT, convolution etc…

C’est comme cela qu’un japonais a il y a une vingtaine d’année battu le record du nombre de décimales de pi calculées (je n’ignore pas que ce record a dû être battu à nouveau de nombreuses fois depuis, mais je serais bien étonné que tous ses challengers n’aient pris cet algorithme pour modèle depuis son invention).

En relisant, je m’aperçois que mon explication n’est pas réellement lumineuse… Navré, je n’ai pas pu faire mieux, mais j’espère qu’elle aura un peu débrousaillé le terrain. Il faut dire que c'est quand même assez compliqué à mettre en oeuvre...

@+

[Mac LAK]

En (très très) gros, la transformée de Fourier d'un signal, c'est le spectre de ce signal. Si tu veux voir très rapidement ce que ça peut représenter, c'est très simple : tu prends ton player MP3 favori (mettons WinAmp), et tu regardes les visualisations.
En général, tu en as au moins deux accessibles :
- Oscilloscope : ça te montre le signal audio d'origine, c'est à dire la représentation visuelle des ondes sonores qui seront générées par les haut-parleurs.
- Analyseur de spectre (Spectrum Analyser) : c'est le graphe avec les barres verticales, en général les basses à gauche, les aigus à droite. Tu as le même sur ta chaîne Hi-Fi, certainement.

La différence entre les deux ? Simplement une transformée de Fourier (et une représentation graphique un peu différente), c'est tout.

C'est très utilisé en traitement du signal, bien sûr, mais également dans d'autres domaines moins "évidents", comme les compressions de type JPEG ou MPEG (y compris MPEG audio, MP3, etc...).

Reposes des questions après avoir fait quelques recherches sur le net, si des trucs ne sont pas clairs.

[Mat 74]

voila je viens de faire des recherches
mais y a un truc que je capte pas
la transforméé de fourier sert a transformé des fonctions ( sinusoïdale )
alors c'est quoi le rapport avec une suite de nb fois des puissance ?
et c'est quoi une convolution ?

[Mac LAK]

la transforméé de fourier sert a transformé des fonctions ( sinusoïdale )

Pas que sinusoïdales.... On peut même calculer la TF d'une impulsion de Dirac (fonction valant 0 sur R, sauf en un seul et unique point où elle vaut 1).

alors c'est quoi le rapport avec une suite de nb fois des puissance ?

Heu... As-tu réellement fait des maths ? L'expression de la TF continue est une intégrale... Et réputée (quasiment) incalculable pour la plupart des fonctions, qui plus est. Or, d'après toi, comment approche-t-on une intégrale, ce qui revient à dire "comment calcule-t-on une intégrale sur un ordinateur" ??
D'où l'expression de la Transformée de Fourier Discrète (TFD).

et c'est quoi une convolution ?

Je n'ai plus l'expression mathématique exacte d'une convolution sous la main : dans mon propre domaine, je n'utilisais que les convolutions de matrices.
En gros, c'est l'application d'une matrice sur une autre, on s'en sert beaucoup en analyse d'images pour appliquer par exemple des filtres (comme le lissage, ou les filtres de flou) ou pour calculer le gradient d'une image (sa "dérivée", permettant de détecter les contours).
Bien sûr, ça a beaucoup d'autres applications.
On demande un matheux "pur jus" pour compléter, svp... ;-)

[ceugniet]

voila je viens de faire des recherches
mais y a un truc que je capte pas
la transforméé de fourier sert a transformé des fonctions ( sinusoïdale )
alors c'est quoi le rapport avec une suite de nb fois des puissance ?
et c'est quoi une convolution ?

La convolution de f(i) avec g(j), c'est la fonction h(k) définie par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
h(k)= somme (pour tous les i possibles) de f(i)*g(k-i)

En d'autres termes, h(k) c'est la somme de tous les produits f(i)*g(j) tels que i+j = k

Vu comme cela, ça a l'air tombé du ciel, mais on s'en sert constamment en physique.

J'ai l'impression que tu n'as pas lu attentivement mon petit baratin

alors c'est quoi le rapport avec une suite de nb fois des puissance ?

Il me semble qu'il répond exactement à cette question. Que faire de plus ? Bon ! Un petit exemple pour illustrer de manière concrète :

On multiplie 823 par 732, par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
823 * 732 = (8*100 + 2*10 + 3*1) * (7*100 + 3*10 +2*1)
                = 8*100* (7*100 + 3*10 +2*1)
                + 2*10 * (7*100 + 3*10 +2*1)
                + 3*1* (7*100 + 3*10 +2*1)
 
                = 8*100* 7*100
                + 8*100* 3*10
                + 8*100* 2*1
                + 2*10 * 7*100
                + 2*10 * 3*10
                + 2*10 * 2*1
                + 3*1 * 7*100
                + 3*1 * 3*10
                + 3*1 * 2*1
 
                = 8*7*10000
                + 8*3*1000
                + 8*2*100 
                + 2*7*1000
                + 2*3*100
                + 2*2*10
                + 3*7*100
                + 3*3*10
                + 3*2*1

soit, en regroupant les puissances de dix égales

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
                = 8*7*10000
                + 8*3*1000
                + 2*7*1000
                + 8*2*100 
                + 2*3*100
                + 3*7*100
                + 2*2*10
                + 3*3*10
                + 3*2*1
 
                = 8*7*10000
                + (8*3+2*7)*1000
                + (8*2+ 2*3+ 3*7)*100 
                + (2*2+ 3*3)*10
                + 3*2*1

Quand tu poses une multiplication, tu ne fais pas autre chose :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 
          823
       *  732
          ___
            6
           4x
         16xx
           9x
          6xx
        24xxx
         21xx
        14xxx
       56xxxx
      _______
       602436

Ainsi, regrouper les puissances de 10 égales lorsque l'on fait une multiplication revient à faire une convolution, d'où le rapport avec la transformée de Fourier et son utilisation pour faire rapidement des multiplications sur des nombres gigantesques.

Petite précision sur la transformée de Fourier.

Initialement, celle-ci est définie comme une intégrale de moins l'infini à plus l'infini. Ça sert pour ceux qui font des maths pour toutes sortes de fonctions... En physique au contraire, le plus souvent ça sert à transformer des fonctions PÉRIODIQUES en somme de fonctions sinusoïdales. Et pour réaliser effectivement des calculs, on est bien obligé de passer par des fonctions discrètes : au lieu de raisonner sur une fonction définie continuement sur un intervalle réel, on raisonne sur une fonction discrète définie en n points f(i), i=0 à n-1, fonction qui est censée représenter le mieux possible la fonction continue. Les matheux ont défini l'équivalent dans le domaine discret de la transformée de Fourier : la transformée de Fourier discrète. Et là dessus Cooley et Tuckey ont inventé leur fameux algorithme FFT (Fast Fourier Transform) qui a remplacé un algorithme quasiment infaisable pour cause de temps de calcul trop grand, en un algorithme accessible.

Le rapport entre la FT et la multiplication est uniquement cette similitude entre l'algorithme de la multiplication et la convolution. On se contente de profiter de cette similitude pour pouvoir appliquer ce génial algorithme de FFT qui fait gagner un temps fou...

[Neo82]

Merci bien pour m'avoir éclairci sur le rapport entre la FFT (enfin transformée de Fourier pardon..., c'est l'habitude) et la multiplication

Si j'avais réfléchi qq minutes j'aurai pu trouver je pense :D

@+

[ceugniet]

A ton service...