БПФ - не получается...

[oleg777]

БПФ - не получается...
Взялся программировать быстрое преобразование Фурье и наткнулся на противоречие, с которым не могу разобраться.

Не понимаю, почему почему формула для простого дискретного преобразования Фурье дает не тот же результат, что итерации по методу БПФ.


Пример:

$N = 4$, тогда по методу БПФ получаем:

$X_0 = x_0 + x_2 + x_1 + x_3$

$X_1 = x_0 - x_2 - i (x_1 - x_3)$

$X_2 = x_0 + x_2 - x_1 - x_3$

$X_3 = x_0 - x_2 + i (x_1 - x_3)$ , где маленькие $x$ - входящий сигнал, большие $X$ - результат.


А формула вот для расчета каждого $X_k$ "втупую":

$$X_k = \sum_{n=0}^{N} x_n \exp\left(\frac {-i \cdot 2 \pi k n} {N} \right) $$

Подставлял на вход $x = ( 0, 1, 2, 3 )$ (с 0-й мнимой частью).
На выходе получил в первом случае вектор с такой действительной частью: $\operatorname{Re} X = ( 6, -2, -2, -2 )$. Во втором случае получил $\operatorname{Re} X = ( 6, -2, -3, 0.707 )$.


В чем подвох?

[Xaositect]

Покажите код для расчета "втупую". $[6,-2,-2,-2]$ - это правильный ответ.

[oleg777]

Xaositect в сообщении #727499 писал(а):

Покажите код для расчета "втупую". [6,-2,-2,-2] - это правильный ответ.

Например, для $k = 2$:

$$X_2 = 0 + 1 \cdot \cos\left(\frac {2 \pi \cdot 2 \cdot 1} {4}\right) + 2 \cdot \cos\left(\frac {2 \pi \cdot 2 \cdot 2} {4}\right) + 3 \cdot \cos\left(\frac {2 \pi \cdot 2 \cdot 3} {4}\right) = 0 - 1 + 1 + 3 \cdot (-1) = -3$$

А должно быть -2.

[Xaositect]

$0 - 1 + \textbf{2} - 3$

[oleg777]

Только вот для $N = 8$ у меня все равно не получается!

Собственно, для $N = 8$ я полдня проверял, потом решил написать на форуме про $N = 4$ и ступил.

Какой будет правильный ответ для входного сигнала $x = ( 0, 1, 2, 3, 4, 5, 6, 7 )$ (с 0-й мнимой частью)?

При расчете по формуле преобразования Фурье выходит (для $k=1$) $X_1 = -4$ , а по БПФ получается $X_1 = -9.656$ .

Вот как это выглядит при расчете вручную:

1. "Простая" формула для ДПФ:

$$\operatorname{Re} X_1 = 0 + 1 \cdot \cos\left(\frac {2 \pi \cdot 1 \cdot 1} {8}\right) + 2 \cdot \cos \left(\frac {2 \pi \cdot 1 \cdot 2} {8}\right) + 3 \cdot \cos\left(\frac {2 \pi \cdot 1 \cdot 3} {8}\right) + $$

$$ + 4 \cdot \cos\left(\frac {2 \pi \cdot 1 \cdot 4} {8}\right) + 5 \cdot \cos\left(\frac {2 \pi \cdot 1 \cdot 5} {8}\right) + 6 \cdot \cos\left(\frac {2 \pi \cdot 1 \cdot 6} {8}\right) + 7 \cdot \cos\left(\frac {2 \pi \cdot 1 \cdot 7} {8}\right) = $$

$$ = 0 + 0.707 + 0 - 3 \cdot 0.707 - 4 - 5 \cdot 0.707 + 0 + 7 \cdot 0.707 = -4$$

2. Результат итераций по БПФ:

$$\operatorname{Re} X_1 = \operatorname{Re}(0 - 4 + w \cdot (2 - 6) + w \cdot (1 - 5 + w \cdot (3 - 7))) = 0 - 4 + 0.707 \cdot (2 - 6 + 1 - 5) = -9.656$$

где $ w = \exp(\frac {-i \cdot 2 \pi \cdot 1 \cdot 1} {8}) $ , $ \operatorname{Re} w^2 = 0 $

А у Вас что получается? Посмотрите? Очень надо понять, почему у меня АЧХ, посчитанная по БПФ, выходит "кривая"...

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

oleg777, наберите все формулы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[GAA]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»