THE DISCRETE FOURIER TRANSFORM
CLASSICAL NOTATION
$$ \mathrm{DFT}[k] = \sum_{n=0}^{N-1} \mathrm{x}[n] \cdot e^{-\varphi\mathrm{i}} \\ where \quad \varphi = k \frac{n}{N} 2\pi $$
Illustration 1. Caricature of Joseph Fourier by Julien-Léopold Boilly
Note the Pythagorean doodle in the upper left and the Phasor doodle to the right. 		Equation 1. The Discrete Fourier Transform1
Don't panic.


Although the classical notation of the Discrete Fourier Transform isn’t terribly approachable for learning purposes, it is a beautifully compact representation. It contains everything you need to know in order to implement and encode the transform. I personally think that it’s important to feel comfortable with the classical notation because you’ll continually encounter it when reading any paper or book related to signal processing. Most practicing scientists and engineers communicate with one another using these funny glyphs and symbols, so if you want to join in on the discussion you must be able to interpret the symbolic notation and relate it to your own mental models.2 In the next two sections we'll spend some time unpacking the classical notation and relating it to the concepts that we’ve already learned.

$$\mathrm{DFT[k]}$$
DFT is a list of N complex numbers. It’s the output of the Discrete Fourier Transform. A complex number is composed of a real and imaginary number. Each complex number in the DFT list encodes the amplitude and phase of a single phasor. More on complex numbers in the next section.
$$\mathrm{x}[n]$$
x[n] Is an arbitrary time-domain signal with a length of N samples. It’s the input to the Discrete Fourier Transform. It's written as x and not signal or input because mathematicians are enamored with abstraction and brevity.
$$e^{-\varphi\mathrm{i}}$$
e-φi Is a compact way of describing a pair of sine and cosine waves. Beyond being succinct, this representation is exceptionally fascinating, and relates to Euler’s formula. More on that later.
$$\sum_{n=0}^{N-1} x[n] \cdot y[n]$$
Is a dot-product. The dot product lies at the the heart of the Discrete Fourier Transform, and we’ll spend a fair amount of time with it after learning about complex numbers.
$$\varphi = k \frac{n}{N} 2\pi$$
Is just a way of describing the phase and frequency of a sine wave. There’s really no need to get hung up on this. This construction should become clear once we begin to see the transform in action.
1. You’ll often see this written with the phi (φ) term inline. I find that a bit hard to read (it's just too smushed up and crowded), so I've extracted the phi term from the exponent. Don't get thrown if you see a slightly different formulation when you look into the literature.

























2. If you're like me, you might wonder if Mathematicians themselves actually use these sorts of representations to do their work. Do most mathematicians really get this stuff at a deep, intuitive level? What sort of mental models and representations do mathematicians use for thinking? Jacques Hadamard asked these very sorts of questions, and it's worth watching this video of Alan Kay discussing the topic of symbolic representation and Hadamard's work. This article is also interesting. It's titled, "How Did Einstein Think?"