Fft

[Ravaner]

Bjr à tous, je cherche un algorithme de calcul "style FFT" pour des panneaux de tailles qcq ( non puissances de 2 )
D'avance merci
-----

[invitead065b7f]

Bonjour,

La technique généralement utilisée consiste à ajouter artificielement des 0 devant les nombres à multiplier, de façon à utiliser la FFT

Amicalement,
Moma

[invite986312212]

La technique généralement utilisée consiste à ajouter artificielement des 0 devant les nombres à multiplier, de façon à utiliser la FFT

ou alors à répéter les données (conventions de tore).

[Ravaner]

Merci pour ta réponse, bien évidemment j'avais imaginé cette solution, mais je me demandais s'il existait un version aussi astucieuse que celle de la fft pour calculer en fait la dft, un classement, un ordonnancement particulier des data.

[A voir en vidéo sur Futura]

[Evil.Saien]

Bonjour,

La technique généralement utilisée consiste à ajouter artificielement des 0 devant les nombres à multiplier, de façon à utiliser la FFT

Amicalement,
Moma

Ah bon ??? Connaissais pas, et je doute pas de ce que tu dis, mais ca doit quand-meme bien fausser les resultats...

En traitement d'image on fait la chose suivante: inaginons qu'on ait une image 2000 x 2000, alors on selectione une zone d'interet 1024 x 1024 si on peut se le permettre, sinon on rajoute 24 pixels (bien choisis) sur chaque bords (miroir ou periodiquement).

++

[invite6de5f0ac]

Bonjour,

J'ai parfois utilisé ce bouquin: Fast Algorithms for Digital Signal Processing, de Richard E. Blahut, chez Addison Wesley.

Il y a plein d'exemples de FFT avec des facteurs composites plus exotiques les uns que les autres... style 19x13 par exemple!

-- françois

[invite3d7be5ae]

Ah bon ??? Connaissais pas, et je doute pas de ce que tu dis, mais ca doit quand-meme bien fausser les resultats...

Ca ne fausse pas les résultats, ça en donne de nouveaux.
Tu ne peux pas comparer 8 nb complexes et 16 autres.
Et puis de toutes façons on est obligé.
Je rappelle l'algorithme pour multiplier :
1) On calcule la FFT du premier nb.
2) On calcule la FFT du deuxième nb.
3) On fait un produit terme à terme des 2 FFT obtenues précédemment.
4) On calcule la FFT inverse du produit terme à terme.
5) On fait toutes les retenues.

A l'étape 5, on se retrouve avec un nb d'une taille égale à : taille d'un nombre+taille de l'autre - 1 (ou -0).
Il faut donc chercher le plus petit n tel que 2^n-1>taille approchée du produit. 2ⁿ sera la taille de la FFT.


Pourrait-on décrire la convention du tore?

Pole.

[Evil.Saien]

Tu viens de decrire le principe de la convolution !

Je confirme que ca fausse bel et bien les resultats, puisque la fft n'est pas le seul moyen de calculer la dft, nous ne somme pas "oblige" de le modifier.
Ca va ajouter artificiellement des composantes basses frequences au signal, eventuellement modifier la moyenne...

Personellement, dans un soucis d'exactitude des resultats, j'avais utilise une dft lorsque ca s'averait vraiment necessaire bien que ca ralonge considerablement le temps de calcule.

[invitead065b7f]

salut,

Je rappelle l'algorithme pour multiplier :

Il parle ici de la multiplication de deux grands entiers il me semble.

Pour revenir au traitement des signaux, je n'y connais rien, mais n'est-il pas possible de se débrouiller pour avoir de toute façon une puissance de 2 comme nombre de point ? Je ne me rappelle plus du tout du principe de la DFT

Amicalement,
Moma

[invite986312212]

Pourrait-on décrire la convention du tore?

Pole.

conventions de tore: une expression un peu pédantesque pour une idée simple: en analyse d'image, on peut par exemple pour chaque pixel être amené à calculer une moyenne des 8 pixels voisins. Mais au bord de l'image, il manque 3 pixels (et au coin 5). Au lieu de les remplacer par zéro, on peut prendre les 3 pixels du bord opposé de l'image, comme si celle-ci était repliée en cylindre. comme on fait ça pour les quatre bords, ça revient à supposer que l'image est un tore déplié. En dimension 1 on devrait dire: convention de cercle.

[Evil.Saien]

Oui ou encore "periodisation des donnees"