Quelles données dois-je utiliser pour tester une implémentation FFT et à quelle précision dois-je m'attendre?

14

Je suis impliqué dans un effort pour implémenter un algorithme FFT, et je suis curieux de savoir quels sont les conseils recommandés pour les données de test d'entrée à utiliser - et pourquoi! - et quelle précision attendre.

Sur les entrées de test, j'ai trouvé quelques conseils dans les anciens messages Usenet que je posterai comme réponse, mais ce ne sont que les suggestions d'une personne sans beaucoup de justification - je n'ai rien trouvé qui ressemble à une réponse solide.

Sur la précision, Wikipedia dit que l'erreur devrait être O (e log N), mais quelle est une attente raisonnable en termes absolus?

Modifier pour ajouter: Les tests réels sont sous une forme où j'ai stocké des tableaux de données d'entrée et des données de sortie «de référence» précalculées à comparer, donc je n'ai pas nécessairement besoin de quelque chose avec une solution sous forme fermée.

Brooks Moses
la source

Réponses:

12

Si vous voulez vérifier l' exactitude d' un algorithme FFT , dans le sens où il exécute la fonction souhaitée qui a les propriétés connues de la transformée de Fourier discrète , alors vous pouvez utiliser l'approche proposée dans:

Ergün, Funda. (1995, juin). Test des fonctions linéaires multivariées: surmonter le goulot d'étranglement du générateur. Dans Proc. Vingt-septième Ann. ACM Symp. Théorie de l'informatique . (p. 407–416).

Le document ci-dessus est référencé par les fabricants de FFTW comme leur méthode de choix pour vérifier qu'une implémentation FFT particulière fait ce qu'elle devrait. La technique proposée distille la fonction en trois composants principaux qui sont vérifiés avec des tests séparés:

  • Linéarité: La DFT (ainsi que ses autres transformées cousin dans la famille de Fourier) est un opérateur linéaire , de sorte que pour toutes les valeurs d' , l'équation suivante doit être vérifiée:a1,a2,x1[n],x2[n]

FFT(a1x1[n]+a2x2[n])=a1FFT(x1[n])+a2FFT(x2[n])
  • DFT de l'impulsion unitaire: un signal du domaine temporel égal à la fonction delta de Kronecker est appliqué à l'entrée de l'algorithme FFT et la sortie est vérifiée par rapport à la DFT connue de la fonction impulsion unitaire (il se transforme en une valeur constante dans toutes les sorties bacs). Si l'algorithme FFT fournit un IFFT, il peut être testé en sens inverse pour montrer qu'il donne à nouveau la fonction d'impulsion unitaire.

  • Décalage temporel: deux ensembles de données sont appliqués à l'entrée de l'algorithme FFT; la seule différence entre les deux dans le domaine temporel est un décalage temporel constant. Sur la base des propriétés connues de la DFT, cela devrait effectuer un déphasage linéaire connu entre les représentations du domaine fréquentiel des deux signaux, où la pente du déphasage est proportionnelle au décalage temporel.

Les auteurs de l'article affirment que ces tests sont suffisants pour valider l'exactitude d'une implémentation FFT. Je n'ai pas utilisé cette technique dans le passé, mais cela semble logique, et je ferais confiance aux auteurs de la FFTW (qui ont produit un excellent logiciel gratuit) en tant qu'autorités crédibles sur les bonnes approches du problème de validation.

Jason R
la source
Merci! Les auteurs ont-ils une suggestion pour les valeurs de a1, a2, x1 [n] et x2 [n] à utiliser dans le test de linéarité (ou affirment-ils que cela n'a pas beaucoup d'importance)? Et, d'ailleurs, pour les ensembles de données à utiliser pour le test de décalage temporel?
Brooks Moses
3
Après avoir lu l'article, je peux répondre à ma propre question: les auteurs ne décrivent pas comment on effectue le test de linéarité, mais supposent plutôt que l'on l'a fait suffisamment pour prouver qu'il est vrai pour "la plupart des entrées". En outre, cet article décrit une preuve d'exactitude exacte en supposant une arithmétique exacte; il ne décrit pas un moyen de caractériser l'erreur numérique dans un programme approximatif (comme cela résulte nécessairement de l'utilisation de l'arithmétique de précision finie).
Brooks Moses
Je vais continuer et marquer cela comme accepté, car c'est certainement la meilleure réponse jusqu'à présent - mais je suis toujours très intéressé par d'autres réponses qui couvrent les jeux de données d'entrée de test à utiliser (et pourquoi), ou les détails de la précision attendue . Merci!
Brooks Moses
2
Il y a vraiment deux composantes à votre question sur la validation d'un algorithme FFT: valider son exactitude et mesurer sa précision numérique. Ma réponse ne concernait que la première. Il est difficile de faire des déclarations sur la précision numérique à laquelle s'attendre, car elle est intrinsèquement dépendante de l'implémentation. Le type d'arithmétique (par exemple, fixe par rapport à virgule flottante), la structure utilisée pour implémenter l'algorithme, la longueur de la FFT (c'est-à-dire le nombre d'étapes utilisées pour décomposer le problème), les raccourcis pris pour améliorer la vitesse d'exécution, etc. joueront tous un sont difficiles à généraliser.
Jason R
Bon point; J'aurais probablement dû poser ces questions séparément.
Brooks Moses
5

Comme mentionné dans la question, j'ai trouvé un ensemble de suggestions dans les articles comp.dsp Usenet archivés ( http://www.dsprelated.com/showmessage/71595/1.php , article de "tdillon"):

A.Single FFT tests - N inputs and N outputs
 1.Input random data
 2.Inputs are all zeros
 3.Inputs are all ones (or some other nonzero value)
 4.Inputs alternate between +1 and -1.
 5.Input is e^(8*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
 6.Input is cos(8*2*pi*i/N) for i = 0,1,2, ...,N-1.
 7.Input is e^((43/7)*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
 8.Input is cos((43/7)*2*pi*i/N) for i = 0,1,2, ...,N-1.

B.Multi FFT tests - run continuous sets of random data
 1.Data sets start at times 0, N, 2N, 3N, 4N, ....
 2.Data sets start at times 0, N+1, 2N+2, 3N+3, 4N+4, ....

Le fil suggère également de faire deux sinus, l'un avec une grande amplitude et l'autre avec une petite amplitude.

Comme je l'ai dit dans la question principale, je ne sais pas s'il s'agit d'un ensemble de réponses particulièrement bon, ou s'il est très complet, mais je le mets ici pour que les gens puissent voter et commenter.

Brooks Moses
la source
1
Que révélerait «1. Saisie de données aléatoires»?
Dilip Sarwate
1
@DilipSarwate: les tests Fuzz peuvent être utiles pour révéler les plantages. Et, selon le type d'entrée de bruit (disons, bruit rose ou bruit blanc), pourrait être utile pour vérifier que la distribution d'énergie globale est conforme aux attentes.
smokris
2
@Dilip - Mon "test de fumée" fft est que ifft (fft (random_stuff)) ~ = random_stuff.
hotpaw2
NCN(0,1)99%N CN(0,1)
2
@Dilip: Je suis un gars du matériel. Je voulais quelque chose qui pourrait basculer un pourcentage élevé de tous les bits dans tous les multiplicateurs et CSA.
hotpaw2