Хобрук: Ваш путь к мастерству в программировании

Алгоритм FFT Cooley Tukey - не работает с несколькими числами

Я пытаюсь написать алгоритм Кули Тьюки для БПФ. Теперь алгоритм работает хорошо, но только для 2 чисел - больше ничего. Например, я использовал расчет онлайн-БПФ, ввел те же данные и получил те же результаты. Вот код алгоритма:

#include <iostream>
#include <math.h>
#include <vector>
#include <complex>

using namespace std;

#define pi 3.14159

void ComplexFFT(vector<float> &realData, vector<float> &actualData, unsigned long sample_num, unsigned int sample_rate, int sign)
{
    unsigned long n, mmax, m, j, istep, i;
    double wtemp,wr,wpr,wpi,wi,theta,tempr,tempi;

    // CHECK TO SEE IF VECTOR IS EMPTY;

    actualData.resize(2*sample_num, 0);

    for(n=0; (n < sample_rate); n++)
    {
        if(n < sample_num)
        {
            actualData[2*n] = realData[n];
        }else{
            actualData[2*n] = 0;
            actualData[2*n+1] = 0;
        }
    }

    // Binary Inversion
    n = sample_rate << 1;
    j = 0;

    for(i=1; (i< n); i+=2)
    {
        if(j > i)
        {
            swap(actualData[j - 1], actualData[i - 1]);
            swap(actualData[j], actualData[i]);
        }
         m = sample_rate;
         while (m >= 2 && j > m) {
          j -= m;
          m >>= 1;
         }
         j += m;
     }
     mmax=2;

     while(n > mmax) {

        istep = mmax << 1;
        theta = sign * (2*pi/mmax);
        wtemp = sin(0.5*theta);
        wpr = -2.0*wtemp*wtemp;
        wpi = sin(theta);
        wr = 1.0;
        wi = 0.0;

        for(m=1; (m < mmax); m+=2) {
            for(i=m; (i <= n); i += istep)
            {
                j = i + mmax;
                tempr = wr*actualData[j-1]-wi*actualData[j];
                tempi = wr*actualData[j]+wi*actualData[j-1];

                actualData[j-1] = actualData[i-1] - tempr;
                actualData[j] = actualData[i]-tempi;
                actualData[i-1] += tempr;
                actualData[i] += tempi;
            }
            wr = (wtemp=wr)*wpr-wi*wpi+wr;
            wi = wi*wpr+wtemp*wpi+wi;
        }
        mmax = istep;
    }

    // determine if the fundamental frequency
    int fundemental_frequency = 0;
    for(i=2; (i <= sample_rate); i+=2)
    {
        if((pow(actualData[i], 2)+pow(actualData[i+1], 2)) > pow(actualData[fundemental_frequency], 2)+pow(actualData[fundemental_frequency+1], 2)) {
            fundemental_frequency = i;
        }

    }
}
int main(int argc, char *argv[]) {

    vector<float> numbers;
    vector<float> realNumbers;

    numbers.push_back(50);
    numbers.push_back(10);
    numbers.push_back(50);
    numbers.push_back(10);
    ComplexFFT(numbers, realNumbers, 4, 8, -1);

    for(int i=0; (i < realNumbers.size()); i++)
    {
        cout << realNumbers[i] << ' ';
    }
}

Если я ввожу:

50, 10

Тогда результат будет:

60.00, 0.0
40.00, 0.0

И в калькуляторе точно так же.

Где будто я вошел:

60.00, 0.0
40.00, 0.0

Калькулятор возвращает результаты:

120.0, 0.0
0.0, 0.0
80.0, 0.0
0.0, 0.0

И мои результаты возвращаются:

60, 60
24.6446, -45.3553
90, -10.0001
4.64479, 45.3555

У кого-нибудь есть предложения?

P.S. Алгоритм работает только для двухзначных значений?

Спасибо :)

08.08.2012

Ответы:


1

В вашем коде есть ошибки:

         for(m=1; (m < mmax); m+=2) {
            for(i=m; (i <= n); i += istep)
            {
                j = i + mmax;      // !!! Here, j will be bigger than actualData.size() - 1 
                tempr = wr*actualData[j-1]-wi*actualData[j];
                tempi = wr*actualData[j]+wi*actualData[j-1];

                actualData[j-1] = actualData[i-1] - tempr;
                actualData[j] = actualData[i]-tempi;
                actualData[i-1] += tempr;
                actualData[i] += tempi;
            }
            wr = (wtemp=wr)*wpr-wi*wpi+wr;
            wi = wi*wpr+wtemp*wpi+wi;
        }
07.12.2012
Новые материалы

Создание кнопочного меню с использованием HTML, CSS и JavaScript
Вы будете создавать кнопочное меню, которое имеет состояние наведения, а также позволяет вам выбирать кнопку при нажатии на нее. Финальный проект можно увидеть в этом Codepen . Шаг 1..

Внедрите OAuth в свои веб-приложения для повышения безопасности
OAuth — это широко распространенный стандарт авторизации, который позволяет приложениям получать доступ к ресурсам от имени пользователя, не раскрывая его пароль. Это позволяет пользователям..

Классы в JavaScript
class является образцом java Script Object. Конструкция «class» позволяет определять классы на основе прототипов с чистым, красивым синтаксисом. // define class Human class Human {..

Как свинг-трейдеры могут использовать ИИ для больших выигрышей
По мере того как все больше и больше профессиональных трейдеров и активных розничных трейдеров узнают о возможностях, которые предоставляет искусственный интеллект и машинное обучение для улучшения..

Как построить любой стол
Я разработчик программного обеспечения. Я люблю делать вещи и всегда любил. Для меня программирование всегда было способом создавать вещи, используя только компьютер и мое воображение...

Обзор: Машинное обучение: классификация
Только что закончил третий курс курса 4 часть специализации по машинному обучению . Как и второй курс, он был посвящен низкоуровневой работе алгоритмов машинного обучения. Что касается..

Разработка расширений Qlik Sense с qExt
Использование современных инструментов веб-разработки для разработки крутых расширений Вы когда-нибудь хотели кнопку для установки переменной в приложении Qlik Sense? Когда-нибудь просили..