Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete fourier tranforms -help

  1. Apr 13, 2005 #1
    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)?
     
  2. jcsd
  3. Apr 13, 2005 #2

    rbj

    User Avatar

    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.
     
  4. Apr 13, 2005 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Are you just asking for the DFT formula?

    [tex]
    \hat{f}(s) = \frac{1}{N} \sum_{t=0}^{N-1} \omega^{-st} f(t)
    [/tex]

    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.
     
  5. Apr 13, 2005 #4
    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?
     
  6. Apr 13, 2005 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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...)
     
  7. Apr 13, 2005 #6

    rbj

    User Avatar

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

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

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

    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:

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

    inverse DFT:

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

    [ 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

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

    when [itex] k \ne m [/itex] (both are integers) and

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

    when [itex] k = m [/itex].

    the rest is plug and chug.

    r b-j
     
    Last edited: Apr 14, 2005
  8. Apr 13, 2005 #7

    rbj

    User Avatar

    boy, i dunno 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
     
  9. Apr 14, 2005 #8
    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
     
  10. Apr 14, 2005 #9

    rbj

    User Avatar

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Discrete fourier tranforms -help
Loading...