高速フーリエ変換 - 掛け算多項式？

私はちょうどX^2 + 1やX + 1のような2つの多項式に対してFFTを実行する方法を理解していません...誰でもステップバイステップで私と一緒に行くことができますか？高速フーリエ変換 - 掛け算多項式？

どうもありがとうございました

2009-04-22 KP65

たくさん

...それはあなたのためにこれに多くの光を当てることを期待、しかし、彼らは一緒に意味がありません。おそらく、あなたはそのフックに大きなワームが必要です.... –

ただ、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として解釈する。

2009-04-22 12:16:04 jpalecek

あなたの返事のためにこんにちは感謝、しかし、私はおそらく非常に愚かですが、どのように1 0 1 0 x^2 + 1の係数として得るのですか？これはマトリックスを使用するのと同じ方法ですか？ありがとう – KP65

最初はx^0の係数、x^1の2番目の係数などです。私はあなたが "それを行うためにマトリックスを使用する"ことが何を意味するのか分かりません。 – jpalecek

ああ、はい、申し訳ありません、私はそれを考え出しました。 fft（poly1）* fft（poly2）を実行するまで何をしたのか分かりますが、どうやって1 1 1 1の値を確定しますか？ – KP65

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

IFFT（FFT（POLY1）。* FFT（POLY2））は

畳み込み（適切にパディング）と同等です。畳み込みは2つの多項式の乗算として解釈できます。畳み込みの定義を調べて（それは非常に簡単です）、紙の上に手で取り除きます。私はポール
CenterSpaceソフトウェアはその質問に技術的な単語の

2009-10-27 06:41:31 Paul

答えて