помогите с фурье

z_m
Сообщения: 5
Зарегистрирован: 29 ноя 2010, 19:51

помогите с фурье

Сообщение z_m »

здравствуйте, не могу никак разобраться с фурье, читал статью на этом сайте, объясните, пожалуйста, почему на этом графике
Изображение
все коэффициенты в нижней полуплоскости, когда на тригонометрическом круге, например 3pi/8 находится в первой четверти(вверху слева)?
Изображение
коэффициенты я преобразую по Эйлеру так:
W^p = cos(2pi*p/N) -isin(2pi*p/N)
где N- длина ДПФ.
Спасибо.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: помогите с фурье

Сообщение Бахурин Сергей »

Вы взяли рисунок из статьи по быстрому преобразованию Фурье. Wn^k = exp(-j*2*pi*k/N), причем k = 0..N/2-1. Поэтому если вы подставите для фиксированного N в свое выражение W^p = cos(2pi*p/N) -isin(2pi*p/N) все значения p = 0..N/2-1, то увидите, что мнимая часть W^p всегда отрицательная (у вас же -i*sin(2pi*p/N) ). Поэтому все поворотные к-ты при вычислении БПФ лежат в нижней полуплоскости. Но если вы возьмете дискретное преобразование то там поворотные к-ты будут по всему кругу.

z_m
Сообщения: 5
Зарегистрирован: 29 ноя 2010, 19:51

Re: помогите с фурье

Сообщение z_m »

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

входные данные- массив {0,1,2,3,4,5,6,7} в бит-реверсивном порядке {0,4,2,6,1,5,3,7}
W^k считаю по формуле cos(2*pi*k/N)-sin(2*pi*k/N)
вроде по такой формуле всё делаю,но ничего не выходит

Изображение

Stage 0; halfsize: 1; groups: 4
group[0]node[0]k[0]N[2]W[1.000] 4.00=0.00 + (1.000 * 4.00)
group[0]comp[1]k[0]N[2]W[1.000] -4.00=0.00 - (1.000 * 4.00)

group[1]node[2]k[0]N[2]W[1.000] 8.00=2.00 + (1.000 * 6.00)
group[1]comp[3]k[0]N[2]W[1.000] -4.00=2.00 - (1.000 * 6.00)

group[2]node[4]k[0]N[2]W[1.000] 6.00=1.00 + (1.000 * 5.00)
group[2]comp[5]k[0]N[2]W[1.000] -4.00=1.00 - (1.000 * 5.00)

group[3]node[6]k[0]N[2]W[1.000] 10.00=3.00 + (1.000 * 7.00)
group[3]comp[7]k[0]N[2]W[1.000] -4.00=3.00 - (1.000 * 7.00)

Stage 1; halfsize: 2;groups: 2;
group[0]node[0]k[0]N[4]W[1.000] 12.00=4.00 + (1.000 * 8.00)
group[0]comp[2]k[0]N[4]W[1.000] -4.00=4.00 - (1.000 * 8.00)
group[0]node[1]k[0]N[4]W[1.000] -8.00=-4.00 + (1.000 * -4.00)
group[0]comp[3]k[0]N[4]W[1.000] 0.00=-4.00 - (1.000 * -4.00)

group[1]node[4]k[2]N[4]W[-1.000] -4.00=6.00 + (-1.000 * 10.00)
group[1]comp[6]k[2]N[4]W[-1.000] 16.00=6.00 - (-1.000 * 10.00)
group[1]node[5]k[2]N[4]W[-1.000] 0.00=-4.00 + (-1.000 * -4.00)
group[1]comp[7]k[2]N[4]W[-1.000] -8.00=-4.00 - (-1.000 * -4.00)

Stage 2; halfsize: 4; groups: 1
group[0]node[0]k[0]N[8]W[1.000] 8.00=12.00 + (1.000 * -4.00)
group[0]comp[4]k[0]N[8]W[1.000] 16.00=12.00 - (1.000 * -4.00)
group[0]node[1]k[1]N[8]W[0.000] -8.00=-8.00 + (0.000 * 0.00)
group[0]comp[5]k[1]N[8]W[0.000] -8.00=-8.00 - (0.000 * 0.00)
group[0]node[2]k[2]N[8]W[-1.000] -20.00=-4.00 + (-1.000 * 16.00)
group[0]comp[6]k[2]N[8]W[-1.000] 12.00=-4.00 - (-1.000 * 16.00)
group[0]node[3]k[3]N[8]W[-1.414] 11.31=0.00 + (-1.414 * -8.00)
group[0]comp[7]k[3]N[8]W[-1.414] -11.31=0.00 - (-1.414 * -8.00)

spectrize out:
8.000000
-8.000000
-20.000000
11.313708
16.000000
-8.000000
12.000000
-11.313708

хотя я ожидаю такой спектр
28.000000
5.656853
0.000000
-2.343146
-4.000000
-5.656854
-8.000000
-13.656854

спасибо.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: помогите с фурье

Сообщение Бахурин Сергей »

ошибка на втором этапе. На втором этапе используется 2 поворотных к-та:
Изображение

Исходные данные:
S00[0] = group[0]node[0]k[0]N[2]W[1.000] 4.00=0.00 + (1.000 * 4.00)
S00[1] = group[0]comp[1]k[0]N[2]W[1.000] -4.00=0.00 - (1.000 * 4.00)

S01[0] = group[1]node[2]k[0]N[2]W[1.000] 8.00=2.00 + (1.000 * 6.00)
S01[1] = group[1]comp[3]k[0]N[2]W[1.000] -4.00=2.00 - (1.000 * 6.00)

Тогда на втором этапе
S0[0] = S00[0] + W4^0 * S01[0] = 4+W4^0 * 8 = 4+8 = 12;
S0[1] = S00[1] + W4^1 * S01[1] = -4+W4^1 *(-4) = -4+j*4;
S0[2] = S00[0] - W4^0 * S01[0] = 4-W4^0 * 8 = -4;
S0[3] = S00[1] - W4^1 * S01[1] = -4-W4^1 * (-4) = -4-j*4;

аналогично для второй половины. И третий этап аналогично только будет 4 поворотных к-та:
Изображение

z_m
Сообщения: 5
Зарегистрирован: 29 ноя 2010, 19:51

Re: помогите с фурье

Сообщение z_m »

оказывается я вообще неправильно с комплексными числами работал, заподозрил, что все операции производятся в комплексной области, когда вы написали
S0[3] = S00[1] - W4^1 * S01[1] = -4-W4^1 * (-4) = -4-j*4;
отличные статьи у вас тут, спасибо!)

Закрыто