离散傅立叶变换 [英] Discrete Fourier transform

问题描述

我目前正在尝试编写一些傅立叶变换算法.我从数学定义中介绍的简单DFT算法入手:

public class DFT {
    public static Complex[] Transform(Complex[] input) {
        int N = input.Length;

        Complex[] output = new Complex[N];

        double arg = -2.0 * Math.PI / (double)N;
        for (int n = 0; n < N; n++) {
            output[n] = new Complex();
            for (int k = 0; k < N; k++)
                output[n] += input[k] * Complex.Polar(1, arg * (double)n * (double)k);
        }
        return output;
    }
}

所以我用以下代码测试了该算法:

    private int samplingFrequency = 120;
    private int numberValues = 240;

    private void doCalc(object sender, EventArgs e) {
        Complex[] input = new Complex[numberValues];
        Complex[] output = new Complex[numberValues];

        double t = 0;
        double y = 0;
        for (int i = 0; i < numberValues; i++) {
            t = (double)i / (double)samplingFrequency;
            y = Math.Sin(2 * Math.PI * t);
            input[i] = new Complex(y, 0);
        }

        output = DFT.Transform(input);

        printFunc(input);
        printAbs(output);
    }

转换工作正常，但仅当numberValues是sampleFrequency的倍数时(在这种情况下:120、240、360等).那就是我的240个值的结果:

转换工作正常.

如果我要计算280个值，我会得到以下结果:

如果更改计算值的数量，为什么会得到不正确的结果? 我不确定我的问题是代码问题还是对DFT的数学定义的误解.无论哪种方式，有人可以帮助我解决我的问题吗?谢谢.

解决方案

您遇到的情况称为光谱泄漏.

这是由于傅立叶变换的基础数学假设从-无限到+无限的连续函数引起的.因此，您提供的样本范围实际上可以无限次重复.如果您在窗口中没有完整的波形周期数，则两端将不会对齐，并且会出现不连续现象，这表现为它的自身表现为频率涂抹到任一侧.

处理此问题的正常方法称为 Windowing .但是，这确实会带来不利的一面，因为它会导致振幅略有下降.这是将要处理的样本的整个窗口乘以某个函数的过程，该函数在窗口的两端趋于0，导致端点对齐，但振幅有所失真，因为此过程会降低总信号功率./p>

因此，总结一下，您的代码中没有错误，并且结果符合预期.可以使用窗函数来减少伪像，但是这会影响幅度的准确性.您将需要调查并确定最适合您的项目要求的解决方案.

I am currently trying to write some fourier transform algorithm. I started with a simple DFT algorithm as described in the mathematical definition:

public class DFT {
    public static Complex[] Transform(Complex[] input) {
        int N = input.Length;

        Complex[] output = new Complex[N];

        double arg = -2.0 * Math.PI / (double)N;
        for (int n = 0; n < N; n++) {
            output[n] = new Complex();
            for (int k = 0; k < N; k++)
                output[n] += input[k] * Complex.Polar(1, arg * (double)n * (double)k);
        }
        return output;
    }
}

So I tested this algorithm with the following code:

    private int samplingFrequency = 120;
    private int numberValues = 240;

    private void doCalc(object sender, EventArgs e) {
        Complex[] input = new Complex[numberValues];
        Complex[] output = new Complex[numberValues];

        double t = 0;
        double y = 0;
        for (int i = 0; i < numberValues; i++) {
            t = (double)i / (double)samplingFrequency;
            y = Math.Sin(2 * Math.PI * t);
            input[i] = new Complex(y, 0);
        }

        output = DFT.Transform(input);

        printFunc(input);
        printAbs(output);
    }

The transformation works fine, but only if numberValues is a multiple number of the samplingFrequency (in this case: 120, 240, 360,...). Thats my result for 240 values:

The transformation just worked fine.

If i am trying to calculate 280 values I get this result:

Why I am getting a incorrect result if I change the number of my calculated values? I am not sure if my problem here is a problem with my code or a misunderstanding of the mathematical definition of the DFT. In either way, can anybody help me with my problem? Thanks.

解决方案

What you are experiencing is called Spectral Leakage.

This is caused because the underlying mathematics of the Fourier transform assumes a continuous function from -infinity to + infinity. So the range of samples you provide is effectively repeated an infinite number of times. If you don't have a complete number of cycles of the waveform in the window the ends won't line up and you will get a discontinuity which manifests its self as the frequency smearing out to either side.

The normal way to handle this is called Windowing. However, this does come with a downside as it causes the amplitudes to be slightly off. This is the process of multiply the whole window of samples you are going to process by some function which tends towards 0 at both ends of the window causing the ends to line up but with some amplitude distortion because this process lowers the total signal power.

So to summarise there is no error in your code, and the result is as expected. The artefacts can be reduced using a window function, however this will effect the accuracy of the amplitudes. You will need to investigate and determine what solution best fits the requirements of your project.

这篇关于离散傅立叶变换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！