Fast Fourier Transform - Moltiplicare polinomi?

StackOverflow https://stackoverflow.com/questions/776719

  •  13-09-2019
  •  | 
  •  

Domanda

Ho appena non capisco come eseguire una FFT su due polinomi come X ^ 2 + 1 e X + 1 ... qualcuno può passo per passo passare attraverso il processo con me?

Grazie molto

È stato utile?

Soluzione

Basta usare i vostri coefficienti polinomiali come input per la FFT: 

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

   1   0   1   0

Nota: questo significa che 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

Questo è il risultato. Interpretare come x ^ 3 + x ^ 2 + x + 1, che è il prodotto di due polinomi.

Altri suggerimenti

Ma in realtà quello che sta succedendo qui è circonvoluzione.

  

IFFT (FFT (POLY1). * FFT (poly2))

è l'equivalente di convoluzione (opportunamente riempito). E convoluzione può essere interpretata come la moltiplicazione di due polinomi. Andare a cercare la definizione di convoluzione (è molto semplice) e lavorare a mano su carta. Mi aspetto che sarà versato un sacco di luce su questo per te ...

Paul
CenterSpace Software

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top