1
$\begingroup$

I have a basic understanding of the Fourier Transform, though I'm trying to use it in a program and I'm confused on the specifics. Based on source code I can find online, the DFT takes a set of samples/numbers, performs a summation for each term, and returns a set of these summations which is the same size as the input set. Suppose I have a periodic function. As I understand it, the output array should contain the amplitudes/weights of each frequency which sum to that function. What I can't figure out is how each frequency is encoded in the array as just an index. In each example I read, we just assign a summation at each iteration of the inner loop to the next consecutive index in the output array. How are these indices indicative of which frequency they correspond to?

I'm attaching the source code I'm referencing to the bottom of this in case the website I linked to ever goes down.

import cmath
def compute_dft_complex(input):
    n = len(input)
    output = []
    for k in range(n):  # For each output element
        s = complex(0)
        for t in range(n):  # For each input element
            angle = 2j * cmath.pi * t * k / n
            s += input[t] * cmath.exp(-angle)
        output.append(s)
    return output
Improve this question
$\endgroup$
16
  • 2
    $\begingroup$ Fourier Transform takes some functions defined in a locally compact Abelian group to functions defined in its Pontryagin dual. The Pontryagin dual of the real numbers is itself. So, the Fourier transform of functions on the reals give functions on the reals. When you have a periodic function, you can think of it as defined on the unit circle. The Pontryagin dual of the circle is the integers. The Fourier transform in this case is a function on the integers, a sequence. So, people talk about Fourier series in this case. $\endgroup$
    – plop
    Commented Aug 6, 2020 at 20:44
  • 1
    $\begingroup$ DFT is for functions on the remainders modulo $n$. In the case of the remainders modulo $n$, the Pontryagin dual is the integers modulo $n$. For functions on the remainders modulo $n$ the Fourier transform gives back functions on the remainders modulo $n$. So, to know the transform, you only need its $n$ values at the inputs $0,1,2,...,n-1$. $\endgroup$
    – plop
    Commented Aug 6, 2020 at 20:45
  • 1
    $\begingroup$ What I said above is to give you a rough idea of the relationship between Fourier transform, Fourier series and DFT. In what ways they are the same and in what ways they are different. They apply to functions with different domains. In the case of DFT the functions have domain $\mathbb{Z}/n\mathbb{Z}$, the remainders modulo $n$. So, the input is just the values of the function at $0,1,2,...,n-1$. The output happens to be also a function on (a group isomorphic to) $\mathbb{Z}/n\mathbb{Z}$. So to know the output function you only need its values at the points $0,1,2,...,n-1$. That's all. $\endgroup$
    – plop
    Commented Aug 6, 2020 at 21:00
  • 1
    $\begingroup$ If you want to interpret something as 'frequency', then you can think of $k/n$, $k=0,1,...,n-1$ as the 'frequencies'. The indexes of the output array would be the $k$. $\endgroup$
    – plop
    Commented Aug 6, 2020 at 21:01
  • 1
    $\begingroup$ The main reason why think you needed to know about the bigger picture is because you said "Suppose I have a periodic function." You can think of DFT as inputting periodic function, but periodic functions on the integers (so actually sequences), with period $n$. Contrast this to the input to Fourier series, which you can see as periodic function on the reals. They are really functions on the unit circle. And finally the input to the classical Fourier transform are functions on the reals. $\endgroup$
    – plop
    Commented Aug 6, 2020 at 21:17

1 Answer 1

Reset to default
1
$\begingroup$

Let us denote the input signal by $x(0),\ldots,x(n-1)$ and the output signal by $y(0),\ldots,y(n-1)$. Your program is using the following formula: $$ y(k) = \sum_{t=0}^{n-1} e^{-2\pi i tk/n} x(t). $$ We also have $$ x(t) = \frac{1}{n} \sum_{k=0}^{n-1} e^{2\pi i tk/n} y(k). $$ In other words, any input signal can be represented as a linear combination of the functions $\chi_k(t) = e^{2\pi i tk/n}$, and the output signal gives the coefficients of this representation (up to a normalization factor).

The parameter $k$ is analogous to frequency. You can see the analogy more clearly if you write $$ \chi_k(t) = \cos \frac{2\pi k}{n} t + i \sin \frac{2\pi k}{n} t. $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.