fft - 高速フーリエ変換 - 多項式の乗算?

Question

X^2+1 と X+1 などの 2 つの多項式で FFT を実行する方法がわかりません。このプロセスを段階的に実行できる人はいますか?

どうもありがとう

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

これが結果です。2つの多項式の積であるx^3 + x ^ 2 + x+1として解釈します。

Answer 2

しかし、実際にここで起こっているのは畳み込みです。

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

畳み込みと同等です（適切にパディングされます）。畳み込みは、2 つの多項式の乗算として解釈できます。畳み込みの定義を調べて (非常に単純です)、紙に手書きで書き込んでください。私はそれがあなたのためにこれについて多くの光を当てることを期待しています...

ポール
センタースペース ソフトウェア