Calculating DFT for specific polynomial

  • #1
aka mor
1
0
Hello everyone,

This seems like a simple problem but I get the impression that I'm missing something.

1. Homework Statement

Given the values ## v_1,v_2,...,v_n ## such that DFTn ## (P(x)) = (v_1, v_2, \ldots, v_n) ## and ##deg(P(x)) < n##, find DFT2n## P(x^2)##

Homework Equations

The Attempt at a Solution



My attempt:
Let [itex]P(x) = \sum\limits_{i=0}^{k} a_ix^i[/itex] .
First, expand ##P(x^2)## :
[tex]P(x^2) = a_0 + a_1x^2 + a_2x^4 + \ldots + a_kx^{2k}[/tex]
Let's denote by ##W^j_n## the j'th root of unity of order n.
We have:
[tex]W^j_{2n} = e^{\frac{2\pi i j}{2n}} = e^{\frac{\pi i j}{n }}[/tex]
Using this information, let's expand a term p of ##P(x^2)## on ##W^j_{2n}##:
[tex]a_p(x^2) = a_p(e^\frac{\pi ij}{n})^{2p} = a_p(e^{2\pi i}) ^\frac{jp}{n} = a_p[/tex] (since ##e^{2\pi i} = 1## ).
So, when evaluating any term of the compound polynomial on some unity root of order 2n we get ##\sum\limits_{i=0} ^k ak## and therefore the final answer is:
[tex](\sum\limits_{i=0} ^k ak, \sum\limits_{i=0} ^k ak,\ldots, \sum\limits_{i=0} ^k ak)[/tex].

This doesn't seem right, I didn't even use the information about ## (v_1, \ldots, v_n) ## (answer should be in terms of those?).

Any help would be appreciated.
 
Last edited by a moderator:

Similar threads

Replies
3
Views
3K
Replies
2
Views
1K
Replies
2
Views
12K
Replies
1
Views
1K
Replies
1
Views
2K
Replies
4
Views
1K
Replies
6
Views
2K
Replies
2
Views
2K
Back
Top