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!

Optimizing a DFT

  1. Aug 1, 2008 #1
    1. The problem statement, all variables and given/known data
    Given a discrete Fourier transform, create a fast Fourier transform.

    2. Relevant equations
    The DFT:
    [tex]X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n} \quad \quad k = 0, \dots, N-1[/tex]

    3. The attempt at a solution
    I've heard about split-radix and Cooley-Tukey, but I'm missing the underlying principle. There are a lot of redundant calculations somewhere in the DFT. Where are they? How do I go about optimizing this darn thing? By the way, this isn't really a HW question.
  2. jcsd
  3. Aug 1, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Since we are taking sines and cosines of the expression


    the redundancies are the values of k and n where

    k1*n1 (mod N) = k2*n2 (mod N)

    It's covered in a chapter of Numerical Recipes in C (or Pascal, or Fortran) by Press, Flannery, Teukolsky and Vetterling.
  4. Aug 4, 2008 #3
    Can you tell me what is meant by (mod N)?

    It also appears as though there could be more redundancies when

    k1*n1/N = k2*n2/N+M

    where M is an integer.
  5. Aug 4, 2008 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    It's explained here:

    Yes, exactly. Or equivalently,

    k1*n1 = k2*n2 + M*N

    In other words, k1*n1 and k2*n2 differ by an integer multiple of N. This can also be written as I did before, in terms of (mod N) notation.

    There are even more redundancies, for example

    \cos[2 \pi \ k1 \ n1 \ / \ N] = \cos[2 \pi (N - k1 \ n1) \ / \ N] \ \rightarrow \ k2 \ n2 = N - k1 \ n1

    \cos[2 \pi \ k1 \ n1 \ / \ N] = -\cos[2 \pi \ ( N/2 \pm k1 \ n1 ) \ / \ N] \ \rightarrow \ k2 \ n2 = N/2 \ \pm \ k1 \ n1

    I.e. each value of cos(...), or it's negative, occurs 4 times during each period. And similarly for sin(...)

    And that's not all:

    \cos[2 \pi \ k1 \ n1 \ / \ N] = \sin[2 \pi \ (N/4 - k1 \ n1) \ / \ N ] \ \rightarrow \ k2 \ n2 = N/4 - k1 \ n1

    I.e. there are redundancies between the sin(...) and cos(...) terms as well.

    Essentially, you just need to evaluate cos(...) for 1/4 of a period, and all other cos(...) and sin(...) terms will appear in that list.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Optimizing a DFT
  1. DFT of cosine (Replies: 1)

  2. 2d dft (Replies: 3)

  3. Optimization Problem (Replies: 3)

  4. Optimal Frequency (Replies: 1)

  5. Optimization problem (Replies: 10)