1. Accueil
  2. Tous les snippets
  3. Snippets C / C++ / C++.NET
  4. La transformée de fourier rapide à une dimension

La transformée de fourier rapide à une dimension

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 606 fois - Téléchargée 33 fois

Commenter

Contenu du snippet

La transformée de Fourier rapide qui réduit l'algorithme de Fourier en 2 log(2) au lieu de 2^N. elle peut etre utiliser en traitement du signal ou autre application mathématique

Source / Exemple : 


bool FFT(int dir,int m,double *x,double *y)
{
	long nn,i,i1,j,k,i2,l,l1,l2;
	double c1,c2,tx,ty,t1,t2,u1,u2,z;

	/* Calculate the number of points */
	nn = 1<<m;

	/* Do the bit reversal */
	i2 = nn >> 1;
	j = 0;
	for (i=0;i<nn-1;i++) {
		if (i < j) {
			tx = x[i];
			ty = y[i];
			x[i] = x[j];
			y[i] = y[j];
			x[j] = tx;
			y[j] = ty;
		}
		k = i2;
		while (k <= j) {
			j -= k;
			k >>= 1;
		}
		j += k;
	}

	/* Compute the FFT */
	c1 = -1.0;
	c2 = 0.0;
	l2 = 1;
	for (l=0;l<m;l++) {
		l1 = l2;
		l2 <<= 1;
		u1 = 1.0;
		u2 = 0.0;
		for (j=0;j<l1;j++) {
			for (i=j;i<nn;i+=l2) {
				i1 = i + l1;
				t1 = u1 * x[i1] - u2 * y[i1];
				t2 = u1 * y[i1] + u2 * x[i1];
				x[i1] = x[i] - t1;
				y[i1] = y[i] - t2;
				x[i] += t1;
				y[i] += t2;
			}
			z =  u1 * c1 - u2 * c2;
			u2 = u1 * c2 + u2 * c1;
			u1 = z;
		}
		c2 = sqrt((1.0 - c1) / 2.0);
		if (dir == 1)
			c2 = -c2;
		c1 = sqrt((1.0 + c1) / 2.0);
	}

	/* Scaling for forward transform */
	if (dir == 1) {
		for (i=0;i<nn;i++) {
			x[i] /= (double)nn;
			y[i] /= (double)nn;
		}
	}

   return true;
}

A voir également

Ajouter un commentaire Commentaires
Late2201
Messages postés
3
Date d'inscription
mercredi 16 septembre 2009
Statut
Membre
Dernière intervention
17 septembre 2009
17 sept. 2009 à 13:47
C'est pour le traitement d'un signal electrique
nonoRed
Messages postés
4
Date d'inscription
mercredi 21 mai 2003
Statut
Membre
Dernière intervention
17 septembre 2009
17 sept. 2009 à 10:48
faudrait me donner le contexte précis de ton exo, parceque là ca remonte à deux ans,
c'est dans une image? ou un signal electrique?
Late2201
Messages postés
3
Date d'inscription
mercredi 16 septembre 2009
Statut
Membre
Dernière intervention
17 septembre 2009
17 sept. 2009 à 09:45
D'accord, mais on m'avait conseillé de faire une FFT et de "ne sélectionner que le composant correspondant a 50 Hertz, (en dimensionnant subtilement mes fenêtres d'analyses...".

Mais je ne vois pas comment faire ça avec cet algo, à moins que cela ne soit a faire apres...
nonoRed
Messages postés
4
Date d'inscription
mercredi 21 mai 2003
Statut
Membre
Dernière intervention
17 septembre 2009
16 sept. 2009 à 17:07
late2201 : c'est ecrit un peu plus haut au dessus "* m est egale à log2 ( nn ) (environs deux heures pour le comprendre....) "

loicus : euh il me veut quoi le gamin ?
Late2201
Messages postés
3
Date d'inscription
mercredi 16 septembre 2009
Statut
Membre
Dernière intervention
17 septembre 2009
16 sept. 2009 à 16:55
Salut,

Voila je m'interesse depuis peu a la transformée de Fourier dans le but de faire un filtre numérique.

Certains l'ont deja demandé mais ils n'ont pas eu de réponse alors je réessaie :p

Serait-il possible d'avoir plus de détails sur l'algo en lui-même ?

A quoi correspond le paramètre m, et comment influence-t-il l'algo ?

Merci d'avance.
Afficher les 31 commentaires
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (lpikachu58)