Y at-il une FFT qui utilise une division logarithmique de la fréquence?

Question

Wavelet article contient ce texte:

  

La transformée en ondelettes discrète est également moins complexe prenant calcul, O (N) fois par rapport à O (N log N) pour le transformée de Fourier rapide . Cet avantage de calcul n'est pas inhérent à la transformation, mais reflète le choix d'une division logarithmique de la fréquence, contrairement aux divisions de fréquence équidistants de la FFT.

Est-ce que cela implique qu'il ya aussi un algorithme de FFT semblable qui utilise une division logarithmique de la fréquence au lieu de linéaire? Est-il aussi O (N)? Ce serait évidemment préférable pour un grand nombre d'applications.

Answer 1

Oui. Oui. Non.

Elle est appelée la transformée de Fourier transformation logarithmique. Il a O (n). Cependant, il est utile pour les fonctions qui se désintègrent lentement avec l'augmentation de domaine / abscisse.

Pour revenir l'article wikipedia:

  

La principale différence est que les ondelettes   sont localisés dans le temps et   alors que la fréquence de Fourier norme   transformer est uniquement localisée   fréquence.

Donc, si vous pouvez être localisée seulement dans le temps (ou l'espace, choisissez votre interprétation de l'abscisse) puis (ou Ondelettes transformée en cosinus discrète) sont une approche raisonnable. Mais si vous avez besoin d'aller sur et et, alors vous devez la transformée de Fourier.

En savoir plus sur LFT http://homepages.dias.ie/~ ajones / publications / 28.pdf

Voici le résumé:

  

Nous présentons une expression exacte et analytique pour la transformée de Fourier d'une fonction qui a été échantillonné de façon logarithmique. La procédure est nettement plus efficace que la transformation informatiquement de Fourier rapide (FFT) pour transformer les fonctions ou les réponses mesurées qui se désintègrent lentement avec l'augmentation de la valeur abscisse. Nous illustrons la méthode proposée par un exemple de levés géophysiques électromagnétiques, lorsque l'échelle est souvent telle que notre Fourier transformation logarithmique (LFT) doit être appliqué. Pour l'exemple choisi, nous sommes en mesure d'obtenir des résultats qui concordent avec ceux d'une FFT à 0,5 pour cent dans un temps qui est un facteur de 1.0e2 plus court. Les applications potentielles de notre LFT géophysiciens comprennent la conversion des réponses en fréquence électromagnétique large bande à des réponses transitoires, le chargement et le déchargement glaciaire,   aquifère, recharge des problèmes en mode normal et les études des marées de la terre dans la sismologie et la modélisation impulsive d'onde de choc.

Answer 2

Pour faire ce que vous voulez, vous devez mesurer différents temps de Windows, ce qui signifie les basses fréquences moins souvent obtenir la mise à jour (inversement proportionnelle à des puissances de 2).

Vérifier ici LINGERIE POUR TOUTOU: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf

Cela signifie que les fréquences plus élevées sont mis à jour plus souvent, mais vous avez toujours la moyenne (moyenne mobile est bonne), mais peut aussi le laisser se déplacer plus rapidement. Bien sûr, si le plan sur l'utilisation de la FFT inverse, vous ne voulez pas tout cela. En outre, d'avoir une meilleure précision (bande passante plus faible) à des fréquences plus basses, signifie ceux-ci doivent mettre à jour beaucoup plus lentement, comme 16k de Windows (1/3 m / s).

Oui, un signal basse fréquence se déplace naturellement lentement, et donc bien sûr, il faut beaucoup de temps pour les détecter. Ce n'est pas un problème que les mathématiques peuvent corriger. Il est un commerce naturel de, et vous ne pouvez pas avoir une grande précision une fréquence plus basse et une réponse rapide.

Je pense que le lien que je fournis clarifiera certaines de vos options ... 7 ans après avoir posé la question, malheureusement.

Answer 3

EDIT: Après avoir lu ce que je pense que cet algorithme est pas vraiment utile pour cette question, je vais donner une description de toute façon pour d'autres lecteurs

.

Il y a aussi l'algorithme de Filon une méthode basée sur la qudrature de Filon qui se trouve dans Recettes numérique cette [thèse] [1]. L'échelle de temps est log espacé tout comme l'échelle de frequeny résultant.

Cet algorithme est utilisé pour les données / fonctions qui cariées à 0 dans l'intervalle de temps observé (ce qui est probablement pas votre cas), un exemple simple typique serait une décroissance exponentielle.

Si vos données est noté par des points (x_0, y_0), (x 1, y_1) ... (x_i, y_i) et que vous voulez calculer le spectre A (f) où f est la fréquence de permet de dire f_min = 1 / x_max à F_max = 1 / x_min  log espacés. La partie réelle pour chaque fréquence f est alors calculée par:

A (f) = somme de i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - X_i) * [cos (2 * pi * f * t_i + 1) - cos (2 * pi * f * t_i)] / ((2 * pi * f) ^ 2)}

La partie imaginaire est:

A (f) = y_0 / (2 * pi * f) + somme de i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - x_i) * sin [(2 * pi * f * t_i + 1) - sin (2 * pi * f * t_i)] / ((2 * pi * f) ^ 2)}

[1] Blochowicz, Thomas:. large bande Spectroscopie Diélectrique dans Neat et binaire verre moléculaire Formeurs Université de Bayreuth, 2003, chapitre 3.2.3