Autotune

GitHub

As a simple signal processing project, I build an autotune program from scratch. The key implementation here is a manual implementation of the Fast Fourier Transform. This program allows the user to speak into their computer microphone and apply an autotune onto their voice.

Theoretical Background

Fourier Analysis in Signal Processing

We are given some audio signal $∣ x ⟩ = ϕ$ and wish to decompose it into the different frequencies making it up. We can do this by representing this signal vector in the orthonormal basis of frequencies $∣ k ⟩ = exp (ik x)$ , for integers $k$ . We get

∣ x ⟩ = \int_{- \infty}^{\infty} \hat{ϕ} (k) ∣ k ⟩ d k

The Fourier Transform allows us to solve for the coefficients by mapping the function $ϕ$ from the time domain to the frequency domain $\hat{ϕ}$ .

The Fourier Transform is defined as:

\hat{ϕ} (k) = \int_{- \infty}^{\infty} ϕ (x) exp (- ik x) d x = ⟨ x ∣ k ⟩

Here, $⟨ x ∣ k ⟩$ represents the inner product of our audio samples with the $k$ -th frequency mode.

And the Inverse Fourier Transform is defined similarly, reversing the mapping back to the time domain.

The Numerical Approach: Discrete Fourier Transform

We sample discrete points from the continuous signal $ϕ (x)$ according to the Nyquist-Shannon Sampling Theorem.

The Discrete Fourier Transform is:

X_{k} = n = 0 \sum N - 1 x_{n} exp (- \frac{i 2 π}{N} k n)

The job of performing a Fourier Transform comes down to computing the coefficient $X_{k}$ for all frequencies $k$ . If there are $N$ and (?) $N$ samples, each frequency computation requires $N$ multiplications, and thus the runtime of this procedure is $O (N^{2})$ .

Cooley-Tukey Algorithm for Fast Fourier Transform

The computational cost of the naive DFT approach is very expensive. Fast-Fourier-Transform exploits the fact that the twiddle factors $W_{N}^{n} = exp (- \frac{i 2 π}{N} k n)$ are periodic to perform the same transformation in $O (N lo g N)$ time. Notice $W_{N}^{n + N /2} = - W_{N}^{n}$ .

X_{k} = n = 0 \sum N - 1 x_{n} exp (- \frac{i 2 π}{N} k n) = n even \sum x_{n} exp (- \frac{i 2 π}{N} k n) + n odd \sum x_{n} exp (- \frac{i 2 π}{N} k n) = m = 0 \sum N /2 - 1 x_{2 m} exp (- \frac{i 2 π}{N /2} k m) + exp (- \frac{i 2 π}{N} k) m = 0 \sum N /2 - 1 x_{2 m + 1} exp (- \frac{i 2 π}{N /2} k m)