FFT & Analyseur de spectre - Page 2

Tu parles de quel algo ? LA FFT ou celui de Godzil ?
Le fait d'utiliser la convolution discrète telle quelle ne fait pas que l'algo marche plus rapidement, au contraire puisqu'un convolution c'est du O(n²). En revanche, si on réorganise la FFT en la faisant récursive, on obtient du O(n ln(n))

Heu mon besoin n'a strictement aucun rapport avec les TIs hein

Je mettrais le code en question bientot

Mon code (qui a 1ans 1/2 qui date d'un projet foireux : )

/**************************************
** DFT                               **
**                                   **
** TransformÈ de fourier discrËte    **
In:
	- s   : Pointeur vers une structure signal
Out:
	- Nothing
**************************************/
TANGUY_DLL_API void DFT(Signal *s /* int MAX_TRIG */)
{
	double PtsA[MAX_TRIG], PtsB[MAX_TRIG];
	double Ap,Bp,A,Phi;

	char tmp[10];

	int i,j;

	if ( TableInited == 0 )
	{ /* Si non gÈnÈrÈ : */
		j = 0;
		/* gÈnÈration des table sin et cos */
		for ( i = 360 ; i > 0 ; i -= (360 / MAX_TRIG) )
		{
			tCos[j] = Round( cos(Deg2Rad(i)) , 10000 );
			tSin[j++] = Round( sin(Deg2Rad(i)) , 10000 );
		}
		TableInited = 1;
	}

	/* On efface la zone d'affichage */
	clear_bitmap(Buffer);

	hline(Buffer,0,ScreenHeight-20,ScreenWidth,255);
	vline(Buffer,0,0,ScreenHeight,255);

	for ( i = ScreenHeight - 20 ; i > 0 ; i -= 30 )
		putpixel(Buffer,1,i,255);

	for ( i = 1 ; i < MAX_TRIG ; i ++ )
	{
		j = i*(ScreenWidth/MAX_TRIG);
		putpixel(Buffer,j,ScreenHeight-19,255);
		sprintf(tmp,"%d",i);
		textout_centre(Buffer, font, tmp, j,ScreenHeight-18,255);
	}
		
	for ( i = 0 ; i < MAX_TRIG ; i ++ )
	{
		/* i : harmonique a tester 
		   0 = fondamentale
		*/

		/* Selection des points a utiliser */			
		for ( j = 0 ; j < MAX_TRIG ; j ++ )
		{
			PtsA[j] = tSin[(j*(i+1))%MAX_TRIG];
			PtsB[j] = tCos[(j*(i+1))%MAX_TRIG];
		}

		Ap = 0; Bp = 0;
		for ( j = 0 ; j < MAX_TRIG ; j ++ )
		{
			Ap += PtsA[j%MAX_TRIG] * s->sign[j];
			Bp += PtsB[j%MAX_TRIG] * s->sign[j];
		}
		
		Ap /= MAX_TRIG;
		Bp /= MAX_TRIG;

		
		A = sqrt(pow(Ap,2)+pow(Bp,2)) * 2; // A/2 = racine(A'? + B'?)

		/*
		B' = A/2 sin(Phi)

		donc

		(A/2) / B' = sin(Phi)

		donc

		Phi = asin((A/2)/B')
		*/

		Phi = asin((A/2.0)/Bp);

		j = i*(ScreenWidth/MAX_TRIG);
		line(Buffer,j,ScreenHeight-19,j,ScreenHeight-19-(int)(30*A),4);

	}
	AfficheBuffer();
}

Une vraie DFT
Maintenant, fait une FFT et tu verras que ton code va beaucoup s'accélérer.

Oui mais mon code, tel qu'il est (et meme si il est a mon avis assez rapide pour mon besoin) ne me donne pas les fréquences, mais juste le coeff des harmoniques. Enfin ça doit être moi qui suis a la masse

Attends... Tu peux réexpliquer exactement ce que tu veux stp ?

Dans ton code i=0 c'est la composante continue, pas la fondamentale (c'est i=1 pour la fondamentale )

Et si tu calcules pas certaines composantes ça va empêcher ton code d'être récursif, et comme dit Miles tu gagnerais quasiment rien de toute façon ^^ (à moins que tu sois à l'octet près niveau consommation de RAM, mais ça m'étonnerait...)

ex-Miles :
au contraire puisqu'un convolution c'est du O(n²).

Sauf si tu passes par une FFT

Pollux: ben heu, m'en fou moi qu'il soit recursif ou pas mon code, et certe oui c'est i=1 la fondamentale et pas i=0, mais c'est une déformation C-iène

ah nan j'avais pas vu mais tu as un (i+1) dans PtsA[] donc i=0 c'est bien la fondamentale, Autan pour moi (et i=MAX_TRIG-1 la composante continue, hyper-logique )

Godzil :
Pollux: ben heu, m'en fou moi qu'il soit recursif ou pas mon code

bah oué mais tu t'en fous peut-être pas que ça soit en O(n.ln(n)) et pas O(n^2) ? ou alors tu t'en fous mais alors je sais pas quelle est ta question (et j'ai la flemme de chercher dans les posts d'avant pour savoir, re-)

la question c'est et re-

problème résolu #tricrobug#

spa l'cas

oulah ça devient trop subtil pour moi ^^

moi je parlais de ca: FFT rapide

http://cermics.enpc.fr/polys/oap/node86.html

et au fait les cowboys.., j'ai trouvé la transformée de Fourier la plus rapide de l'ouest... (Fastest Fourier Transform in the West)
http://www.fftw.org/

#42: il a dit qu'il ne voulait pas de fftw.

onur > on lui propose la FFT depuis longtemps...

Godzil > implémente une FFT et puis c'est bon. Tu peux même faire du sur place si ça te saoûle d'utiliser 2 fois plus de mémoire.

Perso l'utilisation mémoire je m'en fou bcp

Miles: si tu pouvait m'expliquer comment je récupere la fréquence ? pasque moi avec mon code (qui est un dft oui) je n'ai que la "puissance' des harmoniques, et pas la valeur de la fréquence fondamentale ??

Enfin si je suis completement a la masse tu peut le dire aussi hein ^^

Moi je ne pige pas, suffit de modifier un peu le code que tu avais de Visual Basic et là tu auras ce que tu demandes. Moi j'ai fait des retouches pour que cette FFT soit appliquée sur des échantillons audios avec des fenêtres qui se recoupaient. FFT ne te donne pas de façon brutes les fréquences mais seulement leur amplitude. C'est à partir de tes fenêtres que tu trouves les fréquences.


J'avais étudié la reconnaissance vocale lors de mon dernier TPE et j'ai fait un dossier assez détaillé expliquant ma démarche.
http://www.tigen.org/pws/forum/index.php?action=sujet&forum=8&cat=12&topic=1741&page=1#0

Ah oui je te conseil de faire un petit tour ici http://perso.wanadoo.fr/philippe.baucour/pratiquer/fft/fft1.html

La valeur de la fréquence fondamentale ? Tu prends l'harmonique dont l'amplitude est la plus importante, si tu as n points pris en 1 seconde, la fréquence est n / k avec k l'harmonique sus-décrite.

C'est bien ça.

geogeo
: Moi j'ai fait des retouches pour que cette FFT soit appliquée sur des échantillons audios avec des fenêtres qui se recoupaient. FFT ne te donne pas de façon brutes les fréquences mais seulement leur amplitude. C'est à partir de tes fenêtres que tu trouves les fréquences.

Je ne vois pas le rapport entre les fenêtres et les fréquences ???

J'aurais dû dire à partir des fenêtres d'échantillons.

ex-Miles :
La valeur de la fréquence fondamentale ? Tu prends l'harmonique dont l'amplitude est la plus importante, si tu as n points pris en 1 seconde, la fréquence est n / k avec k l'harmonique sus-décrite.

Je suis con

Merci

j'ai encore les binaires d'une super fft en C pour 92+ que j'avais faite pour mon TIPE (marchait jusqu'à 1024 éléments sur la ti, après, plus de mem!)
et j'ai plus de link, donc macache pour le trouver!

sinon ça marchait bien, 1 minute pour analyser un tableau de 1024 nombres (une heure avec le code de vince en basic, c'était saoulant)

Plus de RAM après ???

10 octets Re + 10 octets Im * 1024 = 20KB mais en fait ca c'est la mémoire malloccée dans mon prog. En fait y'a aussi la RAM pour passer la liste sur l'ESTACK et les données en retour. ça doit bien faire 20KB chaque truc aussi Oui, c'est codé comme un chien, je sais (même si j'archivais les listes avant de les lui filer la ti les recopie sur l'estack avant de lancer le prog, je suppose)

Ah oui, effectivement, si tu as dès le départ 10 octets pour la partie réelle... Si tu veux doubler tes capacités -> Bergland.

en fait j'ai codé ça y'a un moment alors j'ai utilisé des doubles BCD de la TI avec bcd_add et les copaings. y'a le support des floats IEEE maintenant non?

Pas obligé de prendre des doubles, avec des long, on peut faire une excellent précision à condition de diviser par 2 à chaque étage - pour tenir compte de la constante différente entre la transformation et son inverse -, je ne sais vraiment plus comment ça s'appelle cette méthode, et pourtant c'est l'enfance de l'art #nawak#

> y'a le support des floats IEEE maintenant non?
Non, car je ne crois pas que le support FFP pour 68000 de Motorola, qui est disponible dans des libs, soit IEEE. En ASM, bcd_add et autres restent la seule solution. En C, c'est plus sympa à écrire.