Дискретное преобразование Фурье

В настоящее время я пытаюсь написать алгоритм преобразования Фурье. Я начал с простого алгоритма 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 является кратным числом частоты дискретизации (в данном случае: 120, 240, 360,...). Это мой результат для 240 значений:

Преобразование просто работало нормально.

Если я пытаюсь вычислить 280 значений, я получаю такой результат:

Почему я получаю неверный результат, если я изменяю количество вычисленных значений? Я не уверен, что моя проблема - это проблема с моим кодом или неправильное понимание математического определения ДПФ. В любом случае, кто-нибудь может мне помочь с моей проблемой? Благодарю.

Ответ 1

То, что вы испытываете, называется Spectral Leakage.

Это вызвано тем, что лежащая в основе математика преобразования Фурье предполагает непрерывную функцию от -инфекции до бесконечности. Таким образом, диапазон выборок, которые вы предоставляете, эффективно повторяется бесконечно много раз. Если у вас нет полного числа циклов формы сигнала в окне, то концы не будут выстраиваться в линию, и вы получите разрыв, который проявляет себя как размашивающую частоту с обеих сторон.

Обычный способ справиться с этим называется Windowing. Однако это происходит с недостатком, так как это приводит к тому, что амплитуды слегка отключаются. Это процесс умножения всего окна образцов, которые вы собираетесь обрабатывать, с помощью некоторой функции, которая стремится к нулю на обоих концах окна, заставляя концы выстраиваться в линию, но с некоторым искажением амплитуды, потому что этот процесс снижает общую мощность сигнала.

Итак, чтобы подвести итог, в вашем коде нет ошибки, и результат будет таким, как ожидалось. Артефакты могут быть уменьшены с помощью оконной функции, однако это будет влиять на точность амплитуд. Вам нужно будет исследовать и определить, какое решение наилучшим образом соответствует требованиям вашего проекта.

Ответ 2

Вы не получаете неверный результат для непериодической синусоиды. И это не просто "артефакты". Ваш результат на самом деле является более полным результатом DFT, который вы не видите с периодической синусоидой. Эти другие ненулевые значения содержат полезную информацию, которая может быть использована, например, для интерполяции частоты одиночной синусоиды с непериодическим в апертуре.

ДПФ можно рассматривать как свертку прямоугольного окна с синусоидальной волной. Это создает (что-то очень близкое) функцию Sinc, которая имеет бесконечную протяженность, НО просто оказывается равной нулю на каждой частоте буфера DFT, отличной от его центральной ячейки DFT, для любой синусоиды, центрированной точно на DFT-бункере. Это происходит только тогда, когда частота является точно периодической в апертуре FFT, а не для других. Функция Sinc имеет множество "горбов", которые все скрыты в вашем первом сюжете.