1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...