FFT & PIC18

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From French to

Threaded View
bonjour a tous,
je connais pas grand chose (voir rien!) dans le calcul FFT et j'aimerai  
l'implementer dans un pic18.
en fait j'ai une suite de valeurs (128 en tout) sur 8 bits qui  
represente le signal dans des cases memoires contigus.(de 0 a 127 par  
exemple)
j'aimerai en retour avoir la magnitude seulement (rien a faire de la  
phase) sur 8 bits egalement.(dans les cases 129 a 255 par exemple)
quelqu'un a deja fait cela ou bien a t'il un point de depart, je connais  
tres bien l'assembleur et je suis tres vaillant :-)
merci et bonne soiree et bon WE.
laurent.

Re: FFT & PIC18
On 2012-10-27 22:10:23 +0200, laurent said:

Quoted text here. Click to load it

notre ami robert lacoste l'a fait en 2003, et l'a mis en acces libre
chance non ?
tout est ici :  
http://www.alciom.com/fr/telechargements/ressources-gratuites/198-fftpic.html


--  

Jean-Yves.


Re: FFT & PIC18
Le 27/10/2012 22:56, jeanyves a écrit :

Quoted text here. Click to load it
merci beaucoup.
a priori c'est sur 16b mais bon, je regarde :-)

Re: FFT & PIC18
On 27 oct, 22:10, laurent :

Quoted text here. Click to load it

| Le 27/10/2012 22:56, jeanyves a écrit :
| notre ami robert lacoste l'a fait en 2003,
| et l'a mis en acces libre chance non ?
| http://www.alciom.com/fr/telechargements/ressources-gratuites/198-fftpic .
html

Quoted text here. Click to load it

Veux-tu juste un algo de FFT,
ou veux-tu en plus comprendre comment cela fonctionne ?

Dans le second cas, voici un PDF (léger: 98 K) qui
détaille la TF puis le passage de la DFT à la FFT :

http://cjoint.com/?0JCoPgWDaRy


Re: FFT & PIC18
Le 28/10/2012 14:47, Jean-Christophe a écrit :

Quoted text here. Click to load it

bonjour,
en effet j'aimerais bien comprendre comment ca fonctionne et si possible  
le faire moi meme, c'est plus "formateur" et j'aime ca plutot que de  
faire un #include... qui n'apprend rien de plus :-)
je connais les complexes (niveau bac) et j'espere comprendre un peu, je  
regarde ton pdf et on verrat bien, c'est pas gagner ;-)
j'aime bien re-inventer la roue pour comprendre le pourquoi du comment,  
je ne suis pas un tres grand electronicien mais je me debrouille avec ce  
que je sais.
encore merci JC
laurent.

Re: FFT & PIC18
On 28 oct, 15:51, laurent :

Quoted text here. Click to load it

Dans ce cas je suggère de commencer d'abord par bien
comprendre et assimiler sur le papier ce qu'est (et ce que fait)
la Transformée de Fourier (l'intégrale complexe continue)
puis passer au discret avec la DFT (Transformée Discrète de Fourier)
en implémentant toi-même en soft une DFT sur ton uC (en C ou en ASM)

Parce-que t'attaquer directement à comprendre la FFT
sans avoir d'abord compris la DFT, c'est pas gagné.

Quoted text here. Click to load it

Si l'Anlais te gène, sur le net il y a des docs en Francais,
par exemple ci-dessous avec explications et algo FFT :
http://cermics.enpc.fr/polys/oap/node86.html

Et si tu as des questions, n'hésite pas à
les poster sur ce newsgroup TRES SYPMA :o)

& bon courage à toi.

Re: FFT & PIC18
Le 28 octobre 2012, Jean-Christophe a écrit :

Quoted text here. Click to load it

La série de Fourier devrait suffire, non ?

Quoted text here. Click to load it

C'est sûr, quoiqu'on puisse considérer la FFT comme un algo qui implémente  
la série de Fourier vue comme une formule magique.

--  
LL

Re: FFT & PIC18
On 29 oct, 10:20, Lucas Levrel :

Quoted text here. Click to load it

| La série de Fourier devrait suffire, non ?

Je généralisais.

Quoted text here. Click to load it

| C'est sûr, quoiqu'on puisse considérer la FFT
| comme un algo qui implémente la série
| de Fourier vue comme une formule magique.

J'ai connu quelques programmeurs qui 'écrivaient'
leur soft à grands coups de copié/collé depuis le net
puis trituraient le tout jusqu'à ce que ca 'marchotte'.
Mais lorsqu'ils doivent faire évoluer les algos,
ou débugger, ils ne savent pas par où commencer.
Quand c'est pour des trucs maison ca n'a pas de conséquence,
mais quand c'est professionnel ca fait froid dans le dos.

De la même facon que quelqu'un qui n'y connait rien en
électronique peut acheter un truc en kit puis le monter
lui-même en suivant aveuglément les instructions, il suffit
de savoir lire et d'être soigneux pour que ca fonctionne.
Mais il ne saura toujours pas *comment* cela fonctionne,
et n'aura pas goûté au plaisir de l'avoir conçu lui-même.
C'est bien aussi, mais il n'aura rien appris de plus.

A l'opposé, Laurent a explicitement dit qu'il voulait
*comprendre* comment fonctionne le principe de la FFT,
c'est pourquoi je trouve son attitude trés positive.

Re: FFT & PIC18
Le 29/10/2012 18:41, Jean-Christophe a écrit :

Quoted text here. Click to load it

bonjour,
je pense que j'ai été un peu vite en disant "comprendre", vu mon niveau  
en math et vu les quelques lectures que j'ai pu faire :-)
je comprend la représentation temporelle et fréquentielle mais le  
passage de l'un vers l'autre .... c'est une autre histoire.
par contre j'ai trouvé un bout de code en C sur le net et j'ai essaye de  
comprendre comment ca fonctionne (le programme surtout et un peu l'algo  
quand même)
je suis nul en C alors j'ai refais tout ca en vb.net et en fait ca donne  
ca : http://cjoint.com/?0JDw2UdrsJk
c'est un algorithme qui fait le "miroir" dans les indices du tableau  
puis qui fait la FFT sur le tableau.(c'est l'algo de cooley tukey, c'est  
bien ca ?)
a priori ca fonctionne pas trop mal pour du 8 bits, la seul petite  
chose, meme si ce n'est pas un probleme ce sont les petites "raie" sur  
le "planché", c'est du a quoi ?
j'ai une petite idee mais bon, en fait ce n'est pas vb.net qui calcul le  
sinus mais les valeurs sont calculées, arrondies et placees dans un  
tableau en 8 bits (exactement comme quand ce sera dans le pic car un  
sinus avec un pic .... je suis comme la fosse, ...septique! quoi que  
j'ai deja fait de la multiplication 32x32 dans un 16F)
enfin bon, passer d'une variable double precision a une variable  
"integer" sur 8 bit, la precision est plutot mediocre et je pense que  
c'est du a ca mais bon, je ne suis pas un grand specialiste de la FFT ;-)
si quelqu'un peu m'eclairé un peu et me dire ce qu'il en pense
merci et bonne soiree a tous,
laurent

Re: FFT & PIC18
On 29 oct, 23:20, laurent :

Quoted text here. Click to load it

Ce que je soulignais c'est l'opposition entre le désir
de comprendre (qui induit plus de savoir au fur et à mesure)
et l'attitude mécanique du copié/collé (qui ne mène à rien)
(sans parler des 'têtes bien pleines' et des 'têtes bien faites')


Quoted text here. Click to load it

Tout est dans l'expression mathématique de la TF.
Tu vois bien que l'expression  e^(-i.2.pi.f.t)
correspond à un point situé sur un cercle,
ce point parcourant le cercle quand 'f.t' va de zéro à un,
c'est-à-dire quand 't' va de zéro à '1/f' ...
(en théorie 't' va de -infini à +infini, mais bon)
Donc, pour une fréquence 'f' donnée, si l'oscillation
de l'exponentielle complexe est trés différente de 'f'
alors la somme des valeurs (l'intégrale) s'annule
(oscillation symétrique avec parties positives et négatives)
Par contre si la fréquence 'f' est proche de celle de l'oscillation
de l'exponentielle complexe alors la somme sera constructive
et donnera une composante spectrale non nulle à la fréquence 'f'.

Intuitivement, la transformation temps/fréquence correspond à
une rotation; imagine un repère à 3 dimensions (X,Y,Z) avec :

 Z orienté vers le 'haut' qui correspond à l'amplitude.
 X orienté 'gauche/droite' qui correspond au temps.
 Y orienté en 'profondeur' qui correspond aux fréquences.

Vu 'de face' on voit la représentation temporelle (X,Z)
Si on fait une rotation de 90° autour de l'axe (Z)
on obtient la représentation fréquentielle (Y,Z)
(la transformée inverse correspond à une rotation de
-90° qui permet le passage inverse fréquence/temps)
C'est juste une facon de voir les choses,
mais qui permet de s'en faire une image.

Quoted text here. Click to load it

L'allure du signal temporel que tu utilises montre un mélange
de fréquences un peu bordélique ... pas trés parlant pour
vérifier si ton algo de FTT a été correctement implémenté.
Au début c'est mieux d'utiliser des signaux-tests
dont le spectre est déja bien connu, du genre :
- Sinus pur => une seule raie
http://cjoint.com/data/0JEso2ijQ7K_0s.jpg
- Rectangulaire => raies d'harmoniques impaires 1,3,5, etc
  et d'amplitudes 1/1, 1/3, 1/5, etc.
http://cjoint.com/data/0JEspRSqVuv_0c.jpg
- Triangle, rampe, etc ...
http://cjoint.com/data/0JEsqhZrByA_0t.jpg
- Idem avec une seule impulsion carrée => sinus cardinal
http://cjoint.com/data/0JEsqIUPlbv_0i.jpg
Etc ... voir sur le net les spectres de
divers signaux puis comparer avec les tiens.


Quoted text here. Click to load it

C'est sûr que 8 bits c'est pas le top de la précision,
( aussi bien pour le signal que pour la table sinus )
mais c'est déja un début, et une fois que tu as un algo béton,
rien ne t'empêche de l'implémenter ensuite en 16 ou 24 bits.

Remarque que ton spectre est symétrique : le zéro est au centre,
les fréquences positives à droite et les fréquences négatives à
gauche.
Le signal temporel étant réél, la puissance du spectre est symétriq
ue
de part et d'autre du zéro Hertz, donc tu peux te contenter
des fréquences positives uniquement (pour l'affichage par exemple)
d'autant plus que tu as dit ne pas t'intéresser au spectre de phase.

Re: FFT & PIC18
Le 30/10/2012 18:27, Jean-Christophe a écrit :
Quoted text here. Click to load it

je ne dirais pas que j'ai une tete bien faite ou bien pleine, ce n'est  
pas a moi de juger mais quand je fais quelque chose, en electronique ou  
autre, j'aime bien comprendre ce que je fais c'est tout.
pour ce qui est du copier/coller, c'est bien facile ... quand ca  
fonctionne mais quand ca "bug" hou lala.



Quoted text here. Click to load it

merci beaucoup pour les explications, ca éclaircit quelques peu mes  
lectures :-)

pour l'image, j'ai utilise 3 frequences differentes et a priori ca  
fonctionne pas trop mal, j'ai essayé avec differentes formes de signaux  
et ca donne "a peu pres" de bon resultats mis a part le rapport de  
puissance entre chaques raies qui n'est pas tout a fait bon mais c'est  
du aux differentes "reductions" de donnees pour rester toujours sur 8  
bits, mais ce n'est pas tres grave, ca resterat du 8 bits car  
l'aquisition est en 8 bits alors...

par contre il faut que je prenne 256 valeurs pour avoir un spectre sur  
128 valeurs a cause des frequences positives et negatives mais ce n'est  
pas un probleme car je compte faire oscilloscope egalement et avec le  
declenchement en auto ca permettra faire une sorte de "tempo" avant un  
declenchement sans synchro.

en tout ca, merci beaucoup et si j'ai encore quelques problemes ... je  
reviens ici ;-)

Re: FFT & PIC18

Quoted text here. Click to load it

Pas nécessairement. Si les données d'entrées sont 256 nombres réels alors on  
peut exécuter une FFT complexe sur 128 points et non sur 256 points. Le  
principe est d'entrelacer les données réelles à l'entrée de la FFT. Le  
résultat est 128 valeurs complexes (fréquences positives et négatives). Un  
post-traitement permet de retrouver les résultat de la FFT équivalente de  
ces résultats, et d'en déterminer  les amplitudes et phases des 128  
fréquences positives. Voir par exemple ici :

http://processors.wiki.ti.com/index.php/Efficient_FFT_Computation_of_Real_Input

C'est le principe qu'on avait utilisé dans la librairie PICFFT que quelqu'un  
a eu la gentillesse de citer plus haut. Le gros intéret est surtout pour la  
mémoire, puisqu'on n'utiliser que 50% de la RAM qui serait sinon  
nécessaire...

Cordialement,
Robert Lacoste
www.alciom.com


Re: FFT & PIC18
On 31 oct, 12:13, laurent :

Quoted text here. Click to load it

Qu'affiches-tu pour ce spectre ?

Le spectre étant calculé en complexe, il contient deux
 nombres de la forme [ x + i.y ] qui donnent à la fois
 le spectre de puissance [ puissance = sqrt(x^2 + y^2) ]
 et le spectre de phase [ angle = arctg(y/x) ]

 ( que tu utilises ou non le spectre de phase, il est
   déja potentiellement présent dans le résultat de la
   FFT alors ce serait dommage de ne pas l'exploiter )

Mais qu'affiches-tu pour le spectre en fréquence :
  est-ce [x] , [y] , ou bien [ sqrt(x^2 + y^2) ] ?

Re: FFT & PIC18
Le 03/11/2012 17:24, Jean-Christophe a écrit :

Quoted text here. Click to load it

bonjour,
j'avais un peu oublier la racine ;-)
haaa Pythagore .... quand tu nous tient.
autre petite questions:
y a t'il un moyen de calculer la magnitude sans faire la racine?
calculer une racine avec un pic18, c'est faisable mais c'est pas simple,  
hein !


Re: FFT & PIC18
On 5 nov, 13:14, laurent :

| Le 03/11/2012 17:24, Jean-Christophe :
| qu'affiches-tu pour le spectre en fréquence :
| est-ce [x], [y], ou [ sqrt(x^2 + y^2) ] ?

Quoted text here. Click to load it

C'est peut-être pour ca que les amplitudes
des raies du spectre n'étaient pas correctes.


Quoted text here. Click to load it

Au lieu de calculer la puissance P = sqrt(x^2 + y^2)
( et graduer l'axe des ordonnées en 'P' )
tu peux te contenter de Q = P^2 = x^2 + y^2
( et graduer l'axe des ordonnées en 'P^2' )
mais ca risque d'être un peu ... exotique.


Quoted text here. Click to load it

Je vois au moins 3 solutions :

[1]
Puisque le résultat est sur 8 bits
le plus simple (pour l'implémentation)
et le plus rapide (pour la vitesse)
est d'implémenter une table de 256 valeurs
directement indexée par le produit (x^2 + y^2)


[2]
Pour de la bonne artillerie, vois du côté des
packages flottants (genre IEEE) sous formes
de librairies à inclure dans ton code :
http://www.microchip.com/search/searchapp/searchhome.aspx?id=2&q=floati
ng%20point
Ou encore :
http://picfloat.sourceforge.net/
(...etc...)


[3]
Il existe des algorithmes spécifiques (plus ou moins rapides)
pour calculer la racine carrée d'entiers en base 2
( à adapter à la taille des registres de ton uC )
http://www.google.com/search?as_q=binary+square+root+algorithm


Ci-dessous, deux exemples au hasard :

//---------------------------------------
unsigned int sqrt( unsigned int x )
{
unsigned int y = 0,
 p = 1 << ( (sizeof(int)<<2) - 1 );

  for(;  p;  p >>= 1 )
  { y += p;
    if( y*y > x ) y -= p;
  }

  return y;
}

//---------------------------------------
short isqrt(short num)
{
short res = 0,
bit = 1 << 14;

 while (bit > num)
   bit >>= 2;

 while (bit != 0)
 {
   if(num >= res + bit)
   { num -= res + bit;
     res = (res >> 1) + bit;
   }
   else res >>= 1;

   bit >>= 2;
 }

 return res;
}

//---------------------------------------

Re: FFT & PIC18
Le 05/11/2012 18:48, Jean-Christophe a écrit :

Quoted text here. Click to load it
je pense que ce serat beaucoup plus simple et rapide (pour moi et le  
processeur) :-)

en fait j'ai un ancien kit velleman K7105 qui fonctionne parfaitement et  
j'essai de voir si on ne peut pas implementer tout ca dans un autre µC.
d'origine c'est un 16C65 que je n'ai meme pas essayer de relire car il  
doit etre protege.
j'ai commander un autre µC compatible 18F46K22 que j'attend (presque un  
mois deja) et j'aimerais bien implementer la FFT et peut etre d'autres  
fonctions si jamais.

Re: FFT & PIC18
On 5 nov, 19:25, laurent :

| Puisque le résultat est sur 8 bits
| le plus simple (pour l'implémentation)
| et le plus rapide (pour la vitesse)
| est d'implémenter une table de 256 valeurs
| directement indexée par le produit (x^2 + y^2)

Quoted text here. Click to load it

Dans la mesure où c'est sur 8 bits et
que tu n'as pas besoin d'autres fonctions
que la racine carrée, ca se justifie.


Quoted text here. Click to load it

Ca m'a l'air plutôt bien parti.


Quoted text here. Click to load it

Alors tu *pourrais* avoir besoin d'autres
fonctions ( autres que les 4 opérations )
et dans ce cas l'usage d'un package de calcul
en flottant IEEE ( gratuit ) serait justifié ...

Par exemple, une fois que le signal temporel
a subi une conversion analogique/numérique
suivi d'une FFT, tu *pourrais* effectuer
une transformation arbitraire sur ce spectre,
suivi d'une conversion numérique/analogique
pour sortir un signal temporel analogique.
Il y a beaucoup de manips à faire, surtout sur de
l'audio si le uC et les ADC/DAC sont assez rapides.

Re: FFT & PIC18
Le 05/11/2012 19:40, Jean-Christophe a écrit :

Quoted text here. Click to load it

en fait le kit est un oscilloscope portable 1MHz (750KHz a -3db) donc  
pas de sortie ana, seulement un CAN 8b a 40MHz mais l'horloge est  
generée par le pic (d'origine a 20MHz donc 5MHz interne) soit une  
horloge a 1MHz maxi et ca ne laisse pas beaucoup de place dans le  
programme j'imagine (5 instructions maxi entre chaques fronts)
bien sur il n'y a pas de sortie ana donc a par faire quelques calculs  
"simple" du genre Vpp, Vrms, Vmin, Vmax, ... rien d'extraordinaire quoi.
bonne soiree et merci pour tout a tous.
laurent

ps: si j'ai besoin d'autres chose, je reviens demandé ici ;-)

Site Timeline