Discrete fourier tranforms -help

[rainbowings]

discrete Fourier tranforms -help!

How does one write the orthogonality condition for discrete Fourier tranforms - alternatley, how does one express the kronecker delta as a sum over exp(i k x) kind of thing. One last thing - what is the mormalization constant in front of the sum (analogous to the 1/2 pi for the Fourier resolution of the dirac delta function)?

 

[rbj]

i would suggest posting to comp.dsp your question. i can maybe deal with it here if you could be a bit more specific.

do you want to know why the basis functions are orthogonal to each other? is that your first question?

the kronecker delta is not periodic, so a sum of exp(i k x) would have to be an integral instead. the inverse DFT of a sequence all having 1 for coefficients is a repeated delta, but i wouldn't call that a kronecker delta.

usually the forward DFT has not normalization constant in front and the inverse DFT has a 1/N in front. but that could be switched, or you could have 1/sqrt(N) in front of both.

 

[Hurkyl]

Are you just asking for the DFT formula?

$$\hat{f}(s) = \frac{1}{N} \sum_{t=0}^{N-1} \omega^{-st} f(t)$$

Or maybe it's +st, not -st, I forget.

ω is your favorite (primitive) N-th root of unity. exp(2 π i / N) is usually a good choice.

 

[rainbowings]

Thanks rbj and Hurkyl. Two more questions - what does DFT stand for and how would i derive this? what happens if "s" is a vector?

 

[Hurkyl]

Then the sum is over the whole vector space (change the normalization appropriately), and the exponent is a dot product.

(P.S. I think I might have made an assumption in that formula...)

 

[rbj]

Two more questions -

well it's not exactly the question(s) you started with. and it looks like you have three.

what does DFT stand for

that's kinda funny when i look at the title you gave the thread.

and how would i derive this?

it's in textbooks. it might be a little much to derive here. there's a hint below.

what happens if "s" is a vector?

i don't get where "s" comes from at all. using the language of Electrical Engineers (who are the folks i think that deal with the DFT the most), the most common expression of the DFT:

DFT:

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N}$$

inverse DFT:

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N}$$

[ i deleted some text because it made the math rendering break. ] ... essentially the DFT maps a periodic sequence of period N to another periodic sequence of period N.

you can define one equation arbitrarily and, given that, prove the other is true by noting

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = 0$$

when $k \ne m$ (both are integers) and

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = N$$

when $k = m$.

the rest is plug and chug.

r b-j

 

[rbj]

DFT:

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N}$$

inverse DFT:

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N}$$

because we use the symbol i for electic current, EEs use the symbol $j = \sqrt{-1}$ for the imaginary unit. n, k, and N are integers. usually $0 \le n \le N-1$ and $0 \le k \le N-1$ in the DFT, but it doesn't have to be since the DFT effectively periodically extends the data given it. essentially the DFT maps a periodic sequence of period N to another periodic sequence of period N.

you can define one equation arbitrarily and, given that, prove the other is true by noting

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = 0$$

when $k \ne m$ (both are integers) and

$$\sum_{n=0}^{N-1} e^{-j 2 \pi n (k-m)/N} = N$$

when $k = m$.

boy, i don't know what wrong with this thing, but i can't get the tex to come out right at all, so i am giving up trying. hey PF folks, your tex rendering is a little bit schitz.

r b-j

 

[rainbowings]

thanx r-b-j ... that helped. and yes, i thought of density functional theory but not the title of my own thread when i saw DFT - sometimes one does overlook the obvious!

adi

 

[rbj]

thanx r b-j ... that helped. and yes, i thought of density functional theory but not the title of my own thread when i saw DFT - sometimes one does overlook the obvious!

did the hint help you derive the validity of the inverse transform (assuming the forward DFT definition)? you have to look at the 2nd post where i quote myself because the stupid tex rendering doesn't work right.

r b-j