Извлечение коэффициентов многочлена из ДПФ с использованием обратного ДПФ

Я пытаюсь умножить два многочлена, используя ДПФ, и я не знаю, как получить последний бит из ДПФ их умножения.

Итак, p (x) = x - 4, dft -3, i-4, -5, -i-4 и q (x) = x ^ 2-1, dft 0, -2, 0, -2

степень (pq) = 3

Итак, мы получаем 4-й корень из единицы 1, i, -1, -i

dft для pq равно 0, 8-2i, 0, 8+2i.

Может ли кто-нибудь сказать мне, как теперь получить коэффициенты для pq из его dft?

Спасибо!


discrete-mathematics fft dft
person Sorin Cioban    schedule 18.03.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Первое, что нужно понять, это то, что умножение двух многочленов аналогично свертке коэффициентов.

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 кажутся неправильными)

person Mark Borgerding    schedule 19.03.2013
comment
Почему мои коэффициенты ДПФ неверны? Разве вы не используете корни из единицы для вычисления ДПФ для каждого многочлена, затем выполняете поточечное умножение, а затем инвертируете ДПФ, чтобы получить результат? Как вы делаете обратное ДПФ? - person Sorin Cioban; 20.03.2013