**Ursinus CS 372: Digital Music Processing, Spring 2023**

## Week 6: Euler's Formula And The Complex DFT

### Chris Tralie

## 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.