Fft (transformée de fourier rapide)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 42 111 fois - Téléchargée 30 fois

Contenu du snippet

Comme promis, voici le code de la FFT commenté. Il n'est pas optimisé, mais tourne bien (d'autres versions de cette méthode à suivre).
Bonne lecture !

Source / Exemple :


public double[] Calcul_FFT(double[] donnees)
{
	nb_donnees	= donnees.Length;		// longueur tableau de données
	fft		= new double[nb_donnees];	// Tableau final.
	indices_fft	= new int[nb_donnees];	// tableau d'indices du Reverse Carry

	indices_fft	= Reverse_Carry(nb_donnees); // Fonction de calcul du Rev Carry

	fft_r = new double[nb_donnees];		// tableau d'indices Réels.
	fft_i = new double[nb_donnees];		// tableau d'indices Imaginaires.

	// création des tableaux Réels / Imaginaires
	for(int cptr_mixage = 0 ; cptr_mixage < nb_donnees ; cptr_mixage++)
	{
		fft_r[cptr_mixage] = Variables.donnees[indices_fft[cptr_mixage]];
		fft_i[cptr_mixage] = 0;
	}

	// rang de l'algorithme (Papillon) - ici, 9 pour 1024 données
	for(int rang_fft = 0, cptr_resultat = 0 ; rang_fft < 10 ; rang_fft++)
	{
		omega_fft	= Math.PI/(Math.Pow(2, rang_fft));	// calcul de Omega
		cptr_resultat	= 0;			// compteur de tableau après calcul - Initialisation

		while(cptr_resultat < 1024)		// Parcours du tableau
		{
			for(int largeur = 0 ; largeur < (int) Math.Pow(2, rang_fft) ; largeur++, cptr_resultat++)
			{
				bn_fft_ind	= cptr_resultat + (int) Math.Pow(2, rang_fft);	// Calcule l'indice des impairs
				
				fac_cos		= Math.Cos(omega_fft*largeur);	// Calcule le Cosinus
				fac_sin		= Math.Sin(omega_fft*largeur);		// Calcule le Sinus

				an_fft_r		= fft_r[cptr_resultat];			// a(n) - PAIR / REEL
				an_fft_i		= fft_i[cptr_resultat];			// a(n) - PAIR / IMAGINAIRE
				bn_fft_r		= fft_r[bn_fft_ind];			// b(n) - IMPAIR / REEL
				bn_fft_i		= fft_i[bn_fft_ind];			// b(n) - IMPAIR / IMAGINAIRE

				fft_r[cptr_resultat]	= an_fft_r + bn_fft_r*fac_cos + bn_fft_i*fac_sin;	// Partie réelle de A(k) - (somme)
				fft_i[cptr_resultat]	= an_fft_i + bn_fft_i*fac_cos - bn_fft_r*fac_sin;	// Partie imaginaire de A(k) - (somme)
				fft_r[bn_fft_ind]		= an_fft_r - bn_fft_r*fac_cos - bn_fft_i*fac_sin;	// Partie réelle de B(k) - (différence)
				fft_i[bn_fft_ind]		= an_fft_i - bn_fft_i*fac_cos + bn_fft_r*fac_sin;	// Partie imaginaire de B(k) - (différence)
			}
			cptr_resultat = bn_fft_ind+1;	// Après la fin de chaque trame (2, 4, 8, 16...), passe à la suivante
		}
	}

	//----------------------------------------------------------------------------------------------------------------------
	for(int cptr_fft = 0 ; cptr_fft < nb_donnees ; cptr_fft++)		// Boucle de calcul des Amplitudes totales.
	{
		fft[cptr_fft] = Math.Pow(fft_r[cptr_fft], 2) + Math.Pow(fft_i[cptr_fft], 2);
	}

	return fft;
}

A voir également

Ajouter un commentaire

Commentaires

cs_apach
Messages postés
8
Date d'inscription
jeudi 23 septembre 2004
Statut
Membre
Dernière intervention
28 mars 2005
-
Qu'est ce que, et comment fonctionne la la fonction Reverse_Carry?
supernaz
Messages postés
9
Date d'inscription
mardi 29 mars 2005
Statut
Membre
Dernière intervention
14 janvier 2008
-
pas d'include...
pas de connaissances des librairies a utiliser....
le Reverse_Carry, il a été cherché ou?
le Variables pareil...

pas plus d'explications? :s
dommage, la methode semblait interessante...
Nils_Reco_Vocale
Messages postés
7
Date d'inscription
mercredi 26 novembre 2003
Statut
Membre
Dernière intervention
16 janvier 2008
-
La fonction Reverse Carry sert à organiser les valeurs dans un ordre spécial, de manière à retrouver un arbre qui facilite les calculs.
L'objectif étant de retrouver un tableau qui soit divisé en deux : une première partie ne prenant que les indices pairs, puis la seconde, les impairs.
Je peux t'envoyer l'algo si tu es intéressé, même si je découvre que ce n'est pas le cas de tout le monde... un peu "naze" comme réaction.
Aida_81
Messages postés
2
Date d'inscription
dimanche 12 novembre 2000
Statut
Membre
Dernière intervention
30 mars 2005
-
Bonjour,

J ai lu votre algorithme et ca m interesse de le comprendre.
J ai vraiment fait l effort, mais je me suis bloquée au niveai de la boucle for a l interieur du while, je ne vois pas l utilité de chaque instruction, parce que je n ai pas l algorithme, si tu peux m envoyer STP l algorithme ca serait gentil, pour que je puisse comprendre les etapes, ca d une part.
D autre part, je veux que tu me parles de la complexité de ton algorithme, parce que un algorithme naif fera n*n, donc le tien fera n lg n, mais vraiment je ne vois pas la division du probleme initial, si tu peux m exliquer un petit peu, ou bien si tu vois que tu vas m envoyer fera l affaire, ca ne serait pas necessaire.
Mon courriel est: chami_aida@yahoo.fr
J attends ta reponse.
Merci.
Aida.
toutiwai
Messages postés
4
Date d'inscription
samedi 6 mars 2004
Statut
Membre
Dernière intervention
6 août 2005
-
Moi aussi je suis intéressé par ce "ReverseCarry" même si pense savoir ce que c'est!
Par contre j'ai une question: comment interpréter les résultats de la FFT ? Je comprendsbien qu'on recoit un tableau de la même taille que celui fourni en entrée, j'ai cru comprendre que chaque valeur correspond à l'amplitude en fonction de la fréquence (qui dépend sans doute du n° de la case dans le tableau)...
Pouvez-vous m'expliquer la signification des valeurs pour les cases 0 et 1 du tableau résultat pour, par exemple un fichier son 16bits 44100Hz avec une FFT sur 1024 bits ?
Merci d'avance!

Johan

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 (Nils_Reco_Vocale)