2 / 2 / 0
Регистрация: 27.09.2017
Сообщений: 9
1

Прямое и обратное БПФ

05.08.2018, 17:05. Показов 2784. Ответов 5

Здравствуйте­!
Стоит задача написать прямое и обратное быстрое преобразован­ие Фурье без помощи сторонних библиотек, только std.
Взял формулы, по которым работают функции fft() и ifft() в MathCAD, набрал их в Word для удобства и дополнительн­ой разгрузки мозга, что бы не держать всё в голове. (Формулы во вложении). И спокойно написал такой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <complex>
#include <vector> 
#include <conio.h>
#include <cmath>
using namespace std;
 
#define Pi acos(-1.)
 
vector<complex<double>> FFT(vector<double> signal)
{
    unsigned N = signal.size();
    unsigned K = N / 2 + 1;
    double real = 0;
    double imag = 0;
    double phase = 0;
    vector<complex<double>> output;
    for (unsigned k = 0; k < K; k++)
    {
        real = 0;
        imag = 0;
        for (unsigned n = 0; n < N; n++)
        {
            phase = (2 * Pi * n * k) / N;
            real += signal[n] * cos(phase);
            imag += signal[n] * sin(phase);
        }
        complex<double>temp(real, imag);
        temp /= sqrt(N);
        output.push_back(temp);
    }
    return output;
}
 
vector<double> IFFT(vector<complex<double>> fourier)
{
    unsigned K = fourier.size();
    unsigned N = (K - 1) * 2;
    double phase = 0;
    complex<double> temp;
    double result = 0;
    vector<double> output;
    for (unsigned n = 0; n < N; n++)
    {
        result = 0;
        for (unsigned k = 0; k < K; k++)
        {
            temp = conj(fourier[k]);
            phase = (2 * Pi * n * k) / N;
            result += cos(phase) * temp.real() - sin(phase) * temp.imag();
        }
        result /= sqrt(N);
        output.push_back(result);
    }
    return output;
}
 
int main()
{
    vector<double> signal;
    cout << "Input: 8" << endl;
    for (int i = 1; i < 9; i++)
    {
        signal.push_back(i);
        cout << signal.back() << endl;
    }
    vector<complex<double>> test = FFT(signal);
        cout << endl << "Length of fourier array: " << test.size() << endl;
    vector<double> final = IFFT(test);
    cout << endl << "Length of output: " << final.size() << endl << endl;
    for (unsigned i = 0; i < final.size(); i++)
    {
        cout << final[i] << endl;
    }
    _getch();
    return 0;
}
Вроде всё просто и ясно. Но он, как на зло, работает неправильно.
Вывод из консоли:
Input: 8
1
2
3
4
5
6
7
8

Length of fourier array: 5

Length of output: 8

2.5
3.5
3.5
4.5
4.5
5.5
5.5
6.5

В общем, нет равенства IFFT(FFT(V)) = V.
Может быть кто то знает, в чём может быть проблема?
Миниатюры
Прямое и обратное БПФ  
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.08.2018, 17:05
Ответы с готовыми решениями:

Прямое и обратное преобразование Хаара
Здравствуйте. Написал вейвлет-сжатие Хаара, чисто визуально все работало правильно. Для надежности...

Прямое и обратное преобразование функции
Всем привет! Нужно написать программу прямого и обратного преобразования функции (скорее всего...

Прямое и обратное преобразование чисел в Код Грея
Здравствуйте. Есть вот такая интересная задача, надо прямое и обратное преобразование чисел в Код...

Прямое и обратное отображение набранных символов в консоли
#include &lt;iostream&gt; using namespace std; int main() { string s; int i; cin&gt;&gt;s; while...

5
20 / 20 / 4
Регистрация: 18.01.2017
Сообщений: 80
05.08.2018, 18:13 2
Извините если глючу, а в 50-й строке у вас точно минус синус? Вроде бы один минус берётся из формулы и ещё один минус из i в квадрате (одно i в формуле и i * temp.imag() ), два минуса - плюс...
0
2 / 2 / 0
Регистрация: 27.09.2017
Сообщений: 9
05.08.2018, 18:54  [ТС] 3
Та вроде всё правильно,
C++
1
result += cos(phase) * temp.real() - sin(phase) * temp.imag();
, потому что в степени -i, и всё. Формула то у нас https://www.cyberforum.ru/cgi-bin/latex.cgi?{e}^{j\varphi } = cos(\varphi) + jsin(\varphi). И даже если поменять - на +, то меняется только порядок выходных чисел, а сами числа такие же типа 2.5, 3.5 и т.д.
0
2 / 2 / 0
Регистрация: 27.09.2017
Сообщений: 9
08.08.2018, 12:38  [ТС] 4
Вопрос решён: на выходе обычного ДПФ мы имеем спектр, симметричный относительно нуля по горизонтальн­ой оси. Выходной вектор нашего ДПФ имеет размер https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{m-1}+{1} из-за того, что мы берём правую часть спектра т. е. от 0 и до конца, а левую отбрасываем, она нам не нужна. При ОДПФ мы создаём вектор https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{m} путём воссоздания левой части за счёт правой, и склеиваем их в один вектор.
Может кому то пригодится..­.

Добавлено через 12 минут
И ещё, k = n = 0..N, во вложении на картинке диапазон k неверный.
1
636 / 444 / 208
Регистрация: 06.09.2013
Сообщений: 1,233
08.08.2018, 12:46 5
Цитата Сообщение от Romashka911 Посмотреть сообщение
Стоит задача написать прямое и обратное быстрое преобразован­ие Фурье
Только это у вас не быстрое преобразован­ие Фурье. У быстрого сложность O(NlogN).
0
2 / 2 / 0
Регистрация: 27.09.2017
Сообщений: 9
08.08.2018, 13:12  [ТС] 6
Это я знаю, но суть не в этом была.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.08.2018, 13:12
Помогаю со студенческими работами здесь

Прямое и обратное преобразования Фурье
Здравствуйте, нужна помощь. Требуется произвести прямое и обратное преобразования Фурье для...

Прямое и обратное преобразование Фурье
Добрый день. Суть проблемы такова: дана функция f(x)=sin(x)/x. Сначала пишу в mathcad sin(x)/x ,...

Прямое и обратное Фурье преобразование
есть исходный сигнал 'w5'. Пусть это звуковой импульс. Известно, что поглощение спектра этого...

Прямое и обратное включение транзистора
Добрый вечер! Что понимается под прямым и обратным включением транзистора? И когда и как оно...

Прямое и обратное преобразование Фурье в Java
Мне нужна библиотека для реализации прямого а затем обратного преобразования Фурье для...

Прямое и обратное преобразование Лапласа дробностепенной функции
Доброго времени суток. Мне нужно выполнить преобразование Лапласа функции:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru