La transformée de fourier rapide à une dimension

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 103 fois - Téléchargée 31 fois

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

lpikachu58
Messages postés
351
Date d'inscription
samedi 2 février 2002
Statut
Membre
Dernière intervention
6 mai 2004
2 -
Ah oui encore une précision c'est l'algorithme d'ashley et cohl qui utilise l'algo du papillon.
cs_LordBob
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
8 -
je suis contre les MFC, mais la je n'ai rien d'autre a dire que BRAVO !!!
excelente source !!!
lpikachu58
Messages postés
351
Date d'inscription
samedi 2 février 2002
Statut
Membre
Dernière intervention
6 mai 2004
2 -
merci mais la c'est du C tout a fait standart
cs_LordBob
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
8 -
excuse moi c'est parce que en fait je me suis trompé de source !!! (j'ai honte) désoler
lpikachu58
Messages postés
351
Date d'inscription
samedi 2 février 2002
Statut
Membre
Dernière intervention
6 mai 2004
2 -
pas de mal

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.