Ambiguity about roots of unity in discrete Fourier transform

Join the discussion
Registration is free. Start your own thread to ask a follow-up.
1 reply · 3K views
CantorSet
Messages
44
Reaction score
0
Hi everyone, I have a question on the discrete Fourier transform. I already know its a change of basis operator on [itex]C^N[/itex] between the usual orthonormal basis and the "Fourier" basis, which are vectors consisting of powers of the [itex]N[/itex] roots of unity.

But if i recall correctly from complex analysis, the root of a complex number is not unique. So for example, if we look at the first entry of the first Fourier basis vector, it is [itex]e^{\frac{2 \pi i }{N}}[/itex]. But there are N solutions here. Which one is the actual first entry in the first Fourier basis vector?
 
Physics news on Phys.org
We do not use the usual complex analysis in the calculus of discrete Fourier transformations. Instead finite fields are used, that is we consider only one cycle on the circle and do not circulate, which makes it unique. If temporary or final results do circle, then additional information from the application is needed to determine which one.