Overview
The discrete fourier transform for a sequence of numbers {% f_1,f_2,...,f_N %} is given by
{% X_n = \sum_{k=1}^N x_k \frac{exp[-2\pi i kn/N]}{\sqrt{2 \pi}} %}
The sequence of numbers can be viewed as the output of a function {% f %} that is
sampled
at a fixed frequency, that is,
the points are equally spaced apart. Viewed this way, the discrete fourier transform can be shown to be equivalent
to the following approximation to the
fourier transform
{% \displaystyle \int_{0}^{T} dt \frac{exp[-i \omega_n t]}{\sqrt{2 \pi}} x(t) %}
where this integral is approximated by using the
Trapezoid rule for integration.
Alternate Formulations
{% X[n] = \sum_{-\infty}^{\infty} x[n]e^{-j\omega n} %}
This formulation makes the following changes to the above definition
- It uses the engineering notation that {% j = \sqrt{-1} %} -this is just notation, but is common in engineering literature
- The limits of the sum are changed to {% \infty %}. This can be used assuming that the signal is a finite energy signal.
- It removes the {% \omega = 2\pi k/N %}