fft - 使用逆 DFT 从 DFT 中检索多项式系数

Question

我正在尝试使用 DFT 将两个多项式相乘，但我不知道如何从它们相乘的 DFT 中获得最后一位。

所以有 p(x) = x - 4, dft -3, i-4, -5, -i-4 和 q(x) = x^2-1, dft 0, -2, 0, -2

度（pq）= 3

所以我们得到统一 1, i, -1, -i 的第 4 个根

pq 的 dft 为 0, 8-2i, 0, 8+2i。

有人可以告诉我现在如何从它的 dft 中获取 pq 的系数吗？

谢谢！

Answer 1

首先要理解的是，将两个多项式相乘与对系数进行卷积相同。

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

其次，了解循环卷积等价于线性卷积的条件。

（另外，你的 DFT 系数似乎是错误的）