Discrete Fourier Transform from scratch — Part 1

Introduction

The discrete Fourier transform (DFT) is a mathematical function that performs the operation of breaking down a digitally represented signal, such as a digitally recorded sound, into its spectrum: a set of scalars on a set of sinusoidal components.

Jean Baptiste Fourier (1768–1830)

More precisely, the DFT takes a waveform (a digitally sampled signal) as input and produces a set of coefficients that can be used to scale a set of sine waves equally spaced between 0 Hz and the sampling rate f, Hz. If the scaled functions are added together, the original waveform is reconstructed. For example in the figure below: If we add all the senoids in blue, we get the function represented in red.

Signal Decomposition

Before we continue with the explanation of the DFT, let’s remember the mathematical bases that will help us to understand it.

Complex Numbers

A complex number z is defined as a sum of a real part and an imaginary part. Then z can be represented as x + jy where x and y are real. We also sometimes use the notations Re{z} = x (“real part of z equals x”) and Im{z} = y (“imaginary part of z equals y”). We can plot complex numbers in a plane (called the complex plane) as ordered pairs (x, y).

We can also express complex numbers in terms of polar coordinates as an ordered pair (R, θ) where R = |z| is the magnitude of z and θ= z is the angle of z. Using simple trigonometry, we can convert from rectangular coordinates (x, y) to polar coordinates (R, θ) and vice versa.

Note that z = x + jy is an algebraic representation of z in terms of its rectangular coordinates.Similarly, there is an algebraic representation of z in terms of polar coordinates:

Thus any complex number can be broken down into a cosinusoidal and a sinusoidal component. Another representation of z exists in terms of polar coordinates. In order to define it, we must introduce Euler’s identity (proof):

With Euler’s identity, we gain the alternative algebraic representation of z in terms of polar coordinates:

This representation simplifies the mathematics of the DFT greatly, since simple rules of exponents can now be used in place of difficult trigonometric identities.

A complex number multiplied by its conjugate is equal to its magnitude squared:

Or, in polar coordinates:

In part 2, we will study complex sine waves.See you.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store