CODEWITHSUNDEEP
fftdiscrete-mathematicsdft
Sorin Cioban
Sorin Cioban

Reputation: 2225

Retrieving coefficients of polynomial from DFT using inverse DFT

I am trying to multiply two polynomials using DFT and I don't know how to get the last bit from the DFT of their multiplication.

So there's p(x) = x - 4, dft -3, i-4, -5, -i-4 And q(x) = x^2-1, dft 0, -2, 0, -2

degree(pq) = 3

So we get the 4th roots of unity 1, i, -1, -i

dft for pq is 0, 8-2i, 0, 8+2i.

Could someone please tell me how to get the coefficients for pq now from its dft?

Thanks!

Upvotes: 1

Views: 480

Answers (1)

Mark Borgerding
Mark Borgerding

Reputation: 8476

The first thing to understand is that multiplying two polynomials is the same as convolving the coefficients.

octave:1> p=[0 0 1 -4];
octave:2> q=[0 1 0 -1];
octave:3> conv(p,q)
ans =
    0   0   0   1  -4  -1   4

Secondly, understand the conditions under which circular convolution is equivalent to linear convolution.

(Also, your DFT coeffs seem to be wrong)

Upvotes: 1

Related Questions