The discrete Fourier transform (DFT) is a basic but very versatile algorithm for digital signal processing (DSP). This article will explain each step of how to implement the algorithm from scratch. It also provides the resulting code in multiple programming languages. The DFT is a function that maps a vector of nn complex numbers to another vector of nn complex numbers. Using 0-based indexing, let x(t)x(t) denote the tthtth element of the input vector and let X(k)X(k) denote the kthkth element of the output vector. Then the basic DFT is given by the following formula: The interpretation is that x represents the signal level at various points in time and X represents the signal level at various frequencies. The signal level at frequency k is equal to the sum of {the signal level at each time t multiplied by a complex exponential}. With basic knowledge of summation notation, complex numbers, and computer programming, it is straightforward to convert the description above into computer code. The purpose of this article is to guide you through the translation process step by step. We will use the Java programming language to illustrate. The first part of the description says that the DFT takes an input vector of n complex numbers and calculates an output vector of n complex numbers. Since Java does not have a native complex number type, we will manually emulate a complex number with a pair of real numbers. A vector is a sequence of numbers, which can be represented by an array. Instead of returning the output arrays, we will have them passed in by reference as an argument. Let’s write a skeleton method: Summation notation, while it might look intimidating, is actually easy to understand. The general form of a finite sum just means this: The multiplication of complex numbers is slightly harder, using the distributive law and the identity i2=−1: Euler’s formula tells us that exi=cosx+isinx, for any real number x. Furthermore, cosine is an even function so cos(−x)=cosx, and sine is an odd function so sin(−x)=−(sinx). By substitution: Let Re(x) be the real part of x and let Im(x) be the imaginary part of x. By definition, x=Re(x)+iIm(x). Therefore: The result of this DFT tutorial is available in multiple languages for your convenience, and the code is placed in the public domain: Notes: Python and MATLAB both have built-in support for complex numbers, which makes our job much easier and the resulting DFT implementation much simpler. Each implementation respects the naming convention, formatting style, and code idioms of its own language – they’re not meant to imitate the tutorial’s Java implementation as closely as possible. The code on this page covers a basic, correct, but slow DFT algorithm with Θ(n2) running time. For real-world use, please see my page Free small FFT in multiple languages which features a fast Θ(n log n) implementation. Source.