Convolution FFT algorithme

Bonjour à tous,

Je travail actuellement sur du traitement du signal. Je cherche à réaliser une opération de convolution sur un signal "infini". Pour cette opération de convolution je transforme mon signal d'entrée ( f ) (selon une fenetre de taille fixe) dans le domaine fréquentiel via une FFT. Et je transforme mon impulse ( h ) dans le domaine fréquentiel. Puis une multiplication entre les deux et enfin une FFT inverse sur le résultat avant de resortir le son.

Le principe utilisé est celui du fenetrage. Imaginons une fenetre de taille 2048.
Je me pose des questions sur la mise en place de l'algorithme. Si mon impulse est plus petite que 2048 qu'est ce que je fais ? Si elle est plus grande ?

Je suis ouvert à toute l'aide que vous pourrez me founir, tous les documents.
Merci beaucoup.

On note souvent h(t) la réponse impulsionnelle et H(f) la réponse fréquentielle.

Est-ce ce que vous voulez dire en parlant de h l'impulse ?

Quelques pistes : http://miles.developpez.com/tutoriels/algo/fft/
Donc si tu regardes bien, si tu as un signal fenêtré de taille 1024, ton impulsion ne devrait pas être plus grande que 1025 échantillons.

Citation:

---

On note souvent h(t) la réponse impulsionnelle et H(f) la réponse fréquentielle.

---

H(f) = FFT ( h(t) ) ?

Je ne suis pas sur du vocabulaire employé en fait ?

Après reflexion je pense que la meilleure solution est de mettre une fenetre relativement grande de telle facon que les impulses soient toujours plus courtes et compléter par des 0 jusqu'a atteindre la taille de la fenetre.

Merci pour le tuto. Je vais le décortiquer.

Citation:

---

Envoyé par samtheh

H(f) = FFT ( h(t) ) ?

Je ne suis pas sur du vocabulaire employé en fait ?

---

Oui c'est tout à fait ça. A une multiplication dans le domaine des fréquences correspond une convolution dans le domaine des temps.

Mais il vaut mieux pratiquer une convolution, la réalisation de la FFT rajoute du temps de calcul car il faut ensuite revenir dans le domaine des temps.

Seulement,

f O g (t) = IFFT( FFT (f (t)) * FFT(g(t)) )

Et le calcul coté fréquentiel est moins complexe que coté temporel. D'un point de vue algorithmie en tout cas.

Il y a complexité algorithmique et temps de calcul.

Tu veux dire que le temps de calcul serait inférieur dans le domaine temporel ??

Est ce bien sur ? dans tous les cas ?

Si le filtre est petit devant la taille de l'image, une FFT n'est pas rentable.
Millie en parle dans son tutoriel sur la FFT appliqué au traitement d'image, si je me souviens bien.

Je ne travaille pas sur des images mais sur du son, musique.

Mon filtre (impulse) est plutot petit devant le fichier appliqué puisque considéré comme infini....

Je ne sais pas. Si vous connaissez la FFT, vous avez celle du système en mémoire, ça fait une FFT pour le signal, une multiplication terme à terme des deux vecteurs, avec stockage, et une FFT inverse, qui vaut pour une FFT.

Je ne connais pas d'algorithme de convolution, mais il faut faire la comparaison.

il y a 1024x1024 produits + 1024 sommes pour un algorithme de convolution discrète "brut"

La FFT optimise aussi beaucoup les calculs, mais avec une TF classique, ça fait 2x1024x1024 +1024 produits plus 2048 sommes, ce qui est plus important qu'une convolution "brut"

Je ne sais pas vraiment dans quelle mesure la FFT optimise le temps de calcul.

Convolution = algorithme en N²
FFT = algorithme en Nlog(N)

Pas besoin de faire le calcul maintenant, tu as les chiffress.

...
Avant de raconter ça, programme une FFT...

fftw ? :aie: Je peux le mettre dans le pic directement ? C'est surtout ça que j'aimerai savoir. En fait, je ne connais pas le fonctionnement d'une récursion en terme d'exécution sur la machine, et ça m'avait paru un peu "magique" en cours. Donc je me posais des questions.

PS : j'ai déjà réalisé un algorithme de fft avec matlab. Juste que je me pose des questions sur les dsPIC, comment ils fonctionnent...:question: Désolé

Tu es donc au courant que même si la FFT peut être écrite récursivement, son implémentation n'est jamais récursive mais itérative ?

Donc c'est bien ce qu'il me semblait il est plus rapide et moins complexe de passer dans le domaine frequentiel que de réaliser l'opération dans le domaine temporel. C'est bien ca ?

euhh ... non je n'étais pas au courant.

Alors l'algorithme récursif du calcul de la factorielle est itératif en fait, il fait simplement appel à une valeur stockée en mémoire déjà calculé ? C'est juste une manière plus commode de l'écrire ? Désolé de mon ignorance :oops:

samthet > c'est plus rentable si la taille du filtre est au moins du même ordre que celle du signal analysé, cf message précédent. Le point exact de changement doit être testé.
kromartien > La démonstration est récursive, mais l'implémentation est itérative, c'est facile à modifier.

Désolé de rouvrir ce sujet après tant d'année
Mais samtheh, est-ce que tu as réussi à mettre une convolution de signal dans ton dsPic ?
Car c'est un sujet qui me trotte en tête depuis quelques temps, et si qq1 l'a déjà fait, autant ne pas réinventer la roue 8-)