Real DFT Recap

Up to this point, we've seen the definition of the real discrete fourier transform (DFT). For a signal x with N samples, we take K = floor(N/2)+1 frequencies, starting at a frequency that goes through 0 cycles, all the way up to a frequency that goes through K-1 cycles over the interval of N samples. Let k be the number of cycles that a frequency goes through over this interval. Then we measure the cosine component of this frequency with the following dot product:

\[ c_k = \sum_{n = 0}^{N-1} x[n] \cos(2 \pi k n / N) \]

And we measure the sine component of this frequency with the following dot product:

\[ s_k = \sum_{n = 0}^{N-1} x[n] \sin(2 \pi k n / N) \]

As we saw, the phase of a sinusoid at frequency index k can be computed as

\[ \phi_k = \tan^{-1}(s_k/c_k) \]

And the amplitude can be extracted as

\[ A_k = \sqrt{c_k^2 + s_k^2} \]

However, it is cumbersome to have to store two separate variables for every frequency, and there is also a more elegant way to represent both amplitude and phase if we switch to complex numbers.

Euler's Formula

Now that we've been introduced to complex numbers, we can use an amazing fact about them known as Euler's formula. Recalling that the complex number i is defined as the square root of -1, we have the following relation:

\[ e^{i \theta} = \cos(\theta) + i \sin(\theta) \]

This actually gives us an incredibly elegant way to represent the general sinusoid

\[ f(t) = A \cos(2 \pi f t - \phi) = A\cos(\phi) \cos(2 \pi f t) + A\sin(\phi) \sin(2 \pi f t) \]

If we recognize that every sinusoid can be split up this way into a sine and a cosine, we'll just let the cosine part tag along with the real component of a complex number and the sine part tag along with the complex part of an imaginary number. In this way, the same sinusoid can be written as

\[ A e^{i(2 \pi f t + \phi)} \]

which is known as a phasor. The magnitude/absolute value of this complex number (its length when thought of as a vector in 2D) is the amplitude of the sinusoid, and the instantaneous phase comes out in the ratio between the imaginary and real components. This is all there is to it! But now this allows us to think about sinusoids as living on a circle, which will be extremely helpful when think about some of the subsequent concepts.

Deriving The Complex DFT

You will now derive an expression for the discrete fourier transform using phasors. You should setup a sum so that the cosine component of a sinusoid ends up in the real part and the sine component ends up in the imaginary part.