0

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$.

$\deg(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!

M47145
  • 4,106
Sorin Cioban
  • 349

1 Answers1

1

You've already finished couple of steps but I'll repeat them here.

  1. Get the DFT of each polynomial.
  2. Multiply the coefficients.
  3. inverse-DFT of the result.

That's all. Based on your result, $IDFT\{[0, 8-2i, 0, 8+2i]\} = [4, -1, -4, 1]$.