Быстрое преобразование Фурье - Умножение полиномов?

Question

Я просто не понимаю, как выполнить БПФ над двумя полиномами, такими как X ^ 2 + 1 и X + 1 ... Может кто-нибудь шаг за шагом пройти со мной этот процесс?

Большое спасибо

Answer 1

Просто используйте ваши полиномиальные коэффициенты в качестве входных данных для FFT:

octave:16> poly1=[1 0 1 0]
poly1 =

   1   0   1   0

Примечание: это означает, что x ^ 2 + 1

octave:17> poly2=[1 1 0 0]
poly2 =

   1   1   0   0

octave:18> ifft( fft(poly1).*fft(poly2))
ans =

   1   1   1   1

Это результат. Интерпретировать как x ^ 3 + x ^ 2 + x + 1, который является произведением двух полиномов.

Answer 2

Но на самом деле здесь происходит свертка.

ifft (fft (poly1). * Fft (poly2))

является эквивалентом свертки (правильно дополнен). И свертка может быть интерпретирована как умножение двух полиномов. Посмотрите на определение свертки (это очень просто) и разработайте его вручную на бумаге. Я ожидаю, что это даст вам много света ...

Пол
Программное обеспечение CenterSpace