是否有使用对数分频的FFT? [英] Is there an FFT that uses a logarithmic division of frequency?

问题描述

Wikipedia的小波文章包含以下文本:

Wikipedia's Wavelet article contains this text:

对于快速傅里叶变换.这种计算优势不是变换固有的，而是反映了与FFT等距间隔的频分形成对比的对数分频选择.

The discrete wavelet transform is also less computationally complex, taking O(N) time as compared to O(N log N) for the fast Fourier transform. This computational advantage is not inherent to the transform, but reflects the choice of a logarithmic division of frequency, in contrast to the equally spaced frequency divisions of the FFT.

这是否意味着还存在一种类似FFT的算法，该算法使用对数分频而不是线性分频?也是O(N)吗?对于许多应用程序，这显然是更可取的.

Does this imply that there's also an FFT-like algorithm that uses a logarithmic division of frequency instead of linear? Is it also O(N)? This would obviously be preferable for a lot of applications.

推荐答案

是.是的.不.

它称为对数傅立叶变换.它具有O(n)时间.但是，它对于随域/横坐标增加而缓慢衰减的功能很有用.

It is called the Logarithmic Fourier Transform. It has O(n) time. However it is useful for functions which decay slowly with increasing domain/abscissa.

请参考维基百科的文章:

Referring back the wikipedia article:

主要区别在于小波 在时间和地点都本地化 频率，而标准傅立叶 转换仅本地化 频率.

The main difference is that wavelets are localized in both time and frequency whereas the standard Fourier transform is only localized in frequency.

因此，如果只能在时间(或空间，对横坐标进行解释)中进行局部定位，则小波(或离散余弦变换)是一种合理的方法.但是，如果您需要不断进行下去，那么就需要进行傅立叶变换.

So if you can be localized only in time (or space, pick your interpretation of the abscissa) then Wavelets (or discrete cosine transform) are a reasonable approach. But if you need to go on and on and on, then you need the fourier transform.

在 http://homepages.dias.ie/~上了解有关LFT的更多信息. ajones/publications/28.pdf

这里是摘要:

我们给出了对数采样的函数的傅立叶变换的精确和解析表达式.与快速傅立叶变换(FFT)相比，该程序在计算函数或测得的响应时会效率更高，这些函数或测量的响应随横坐标值的增加而缓慢衰减.我们以电磁地球物理学为例来说明所提出的方法，该方法的标度通常是应应用对数傅立叶变换(LFT)的结果.对于所选择的示例，我们能够在短1.0e2的时间内获得与FFT一致的结果，误差在0.5％以内.我们的LFT在地球物理学中的潜在应用包括将宽带电磁频率响应转换为瞬态响应，冰川加载和卸载， 含水层补给问题，地震学中的正常模式和大地潮研究以及脉冲冲击波模拟.

We present an exact and analytical expression for the Fourier transform of a function that has been sampled logarithmically. The procedure is significantly more efficient computationally than the fast Fourier transformation (FFT) for transforming functions or measured responses which decay slowly with increasing abscissa value. We illustrate the proposed method with an example from electromagnetic geophysics, where the scaling is often such that our logarithmic Fourier transform (LFT) should be applied. For the example chosen, we are able to obtain results that agree with those from an FFT to within 0.5 per cent in a time that is a factor of 1.0e2 shorter. Potential applications of our LFT in geophysics include conversion of wide-band electromagnetic frequency responses to transient responses, glacial loading and unloading, aquifer recharge problems, normal mode and earth tide studies in seismology, and impulsive shock wave modelling.

这篇关于是否有使用对数分频的FFT?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！