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

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.

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:$a_1, a_2, x_1[n], x_2[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.

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.