标签: fft

I've been reading a lot about Fast Fourier Transform and am trying to understand the low-level aspect of it. Unfortunately, Google and Wikipedia are not helping much at all.. and I have like 5 different algorithm books open that aren't helping much either.

我试图找到像矢量[1,0,0,0]那样简单的FFT.当然我可以将其插入Matlab,但这无助于我理解底层正在发生的事情.另外,当我说我想找到一个向量的FFT时,就像说我想用一个更有效的算法找到一个向量的DFT一样吗？

我试图在oder中实现重叠和添加方法,以在实时上下文中应用过滤器.但是,似乎有一些我做错了,因为结果输出的误差比我预期的要大.为了比较我的计算的准确性,我创建了一个文件,我在一个块中处理.我将此与重叠和添加过程的输出进行比较,并将得到的比较作为计算准确性的指标.所以这是我的重叠过程并添加:

• 我从输入信号中取出一大块长度为L.
• 我用零填充块长度L*2
• 我将该信号转换为频域
• 我将频域中的信号与我在频域中的长度为L*2的滤波器响应相乘(滤波器响应实际上是通过在UI中插入控制点来创建的 - 所以这不是从时域转换的.但是使用长度L*2 in频域应类似于使用长度为L的接收时域信号填充到L*2)
• 然后我将结果信号转换回时域并将其添加到输出流中,重叠为L.

这个程序有什么问题吗？在阅读了很多不同的论文和书籍之后,我已经非常不确定哪种方法可以解决这个问题.

以下是我运行的测试中的更多数据:

我创建了一个由三个余弦波组成的信号

我在时域中使用此过滤器功能进行过滤.(它是对称的,因为它应用于FFT的整个输出,对于实际输入信号也是对称的)

IFFT的输出如下所示:可以看出低频在中频范围内衰减的频率高于频率.

对于重叠添加/保存和窗口处理,我将输入信号分成8个256个样本的块.重新组装后,它们就像那样.(样本490 - 540)

输出信号重叠并添加:

输出信号重叠并保存:

使用带Hanning窗口的STFT输出信号:

可以看出,重叠添加/保存过程与块放在一起的点处的STFT版本不同(样本511).这是比较窗口化过程和重叠添加/保存时导致不同结果的主要错误.然而,STFT更靠近输出信号,输出信号已在一个块中处理.几天后我几乎陷入困境.这有什么不对？

这是我的来源

    // overlap and add

// init Buffers
for (UInt32 j = 0; j<samples; j++){
    output[j] = 0.0;
}


// process multiple chunks of data
for (UInt32 i = 0; i < (float)div * 2; i++){

    for (UInt32 j = 0; j < chunklength/2; j++){
        // copy input data to the first half ofcurrent buffer
        inBuffer[j] = input[(int)((float)i * …

有没有人知道是否有任何免费和开源的库以matlab中的方式实现这两个功能？

谢谢

John Feminella 在回答这个问题时说:

如果您真的很喜欢,可以通过将每个整数表示为位向量并执行快速傅立叶变换来实现这种子二次方,但这超出了本答案的范围.

解决该问题中描述的问题的渐近最优方法是什么？

灵感来自Herb Sutter引人注目的讲座不是你父亲的C++,我决定再使用微软的Visual Studio 2010来看看最新版本的C++.我特别感兴趣的是Herb断言C++"安全而快速",因为我写了很多性能关键代码.

作为基准,我决定尝试用各种语言编写相同的简单FFT算法.

我想出了以下使用内置complex类型和vector集合的C++ 11代码:

#include <complex>
#include <vector>

using namespace std;

// Must provide type or MSVC++ barfs with "ambiguous call to overloaded function"
double pi = 4 * atan(1.0);

void fft(int sign, vector<complex<double>> &zs) {
    unsigned int j=0;
    // Warning about signed vs unsigned comparison
    for(unsigned int i=0; i<zs.size()-1; ++i) {
        if (i < j) {
            auto t = zs.at(i);
            zs.at(i) = zs.at(j);
            zs.at(j) = t;
        }
        int m=zs.size()/2;
        j^=m; …

更新2016-03-15

请看一下这个项目:https://github.com/ooper-shlab/aurioTouch2.0-Swift.它已被移植到Swift并包含您正在寻找的每个答案,如果你在这里.

我做了很多研究,并学到了很多关于FFT和Accelerate Framework的知识.但经过几天的实验,我有点沮丧.

我想在图表中播放期间显示音频文件的频谱.对于每个时间间隔,它应该在X轴上通过FFT计算的每个频率(在我的情况下为512个值)显示Y轴上的数值(由红色条显示).

输出应如下所示:

我用1024个样本填充缓冲区,仅为开头提取左侧通道.然后我做所有这些FFT的东西.

到目前为止,这是我的代码:

设置一些变量

- (void)setupVars  
{  
    maxSamples = 1024;

    log2n = log2f(maxSamples);  
    n = 1 << log2n;  

    stride = 1;  
    nOver2 = maxSamples/2;  

    A.realp = (float *) malloc(nOver2 * sizeof(float));  
    A.imagp = (float *) malloc(nOver2 * sizeof(float));  
    memset(A.imagp, 0, nOver2 * sizeof(float));

    obtainedReal = (float *) malloc(n * sizeof(float));  
    originalReal = (float *) malloc(n * sizeof(float));

    setupReal = vDSP_create_fftsetup(log2n, FFT_RADIX2);  
}

做FFT.FrequencyArray只是一个包含512个浮点值的数据结构.

- (FrequencyArry)performFastFourierTransformForSampleData:(SInt16*)sampleData andSampleRate:(UInt16)sampleRate   
{  
    NSLog(@"log2n %i n %i, …

在iOS上从音频流(音乐)获取Hz频率值的最佳方法是什么？Apple提供了哪些最好,最简单的框架.提前致谢.

我正在使用C++/C对某些数据执行前向和反向FFT,这些数据应该是激光器的脉冲输出.

我们的想法是获取输出,使用正向FFT转换到频域,对相位应用线性最佳拟合(首先展开它),然后从相位信息中减去这个最佳拟合.

然后将得到的相位和幅度转换回时域,最终目标是通过相位补偿压缩脉冲.

我试图在MATLAB中不成功地做到这一点,结果转而使用C++.前向FFT工作正常,我从C++中的数字配方中获取了基本配方,并使用函数对复杂输入进行修改,如下所示:

void fft(Complex* DataIn, Complex* DataOut, int fftSize, int InverseTransform, int fftShift)
{

        double* Data  = new double[2*fftSize+3];
        Data[0] == 0.0;


        for(int i=0; i<fftSize; i++)
        {
                Data[i*2+1]  = real(DataIn[i]);
                Data[i*2+2]  = imag(DataIn[i]);
        }

        fft_basic(Data, fftSize, InverseTransform);

        for(int i=0; i<fftSize; i++)
        {
                DataOut[i] = Complex(Data[2*i+1], Data[2*i+2]);
        }

        //Swap the fft halfes
        if(fftShift==1)
        {
                Complex* temp = new Complex[fftSize];
                for(int i=0; i<fftSize/2; i++)
                {
                        temp[i+fftSize/2] = DataOut[i];
                }
                for(int i=fftSize/2; i<fftSize; i++)
                {
                        temp[i-fftSize/2] = DataOut[i];
                }
                for(int i=0; …

考虑一个函数f(t),我如何计算连续的Fouriertransform g(w)并绘制它(使用numpy和matplotlib)？

如果不存在傅里叶积分的解析解,则出现这个或反问题(g(w)给出,f(t)未知的图).

我在网上找到了许多用于在iOS中处理音频的例子,但是大多数都已经过时了,并不适用于我想要完成的任务.这是我的项目:

我需要从两个来源捕获音频样本 - 麦克风输入和存储的音频文件.我需要对这些样本执行FFT以产生整个剪辑的"指纹",以及应用一些额外的过滤器.最终目标是构建一种类似于Shazam等的歌曲识别软件.

在iOS 8中捕获单个音频样本以执行快速傅里叶变换的最佳方法是什么？我想最终会有大量的这些,但我怀疑它可能不会像那样.其次,如何使用Accelerate框架处理音频？它似乎是在iOS中对音频执行复杂分析的最有效方式.

我在网上看到的所有例子都使用旧版本的iOS和Objective-C,但我无法将它们成功转换为Swift.iOS 8是否为这类东西提供了一些新的框架？