Fast Fourier Transform, or FFT, is a mathematical algorithm used to transform data from time or space into the frequency. It is widely used in various fields, such as signal processing, image processing, data compression, and communication systems. The development of the FFT algorithm can be traced to Carl Friedrich Gauss's unpulished work in 1805, however James Cooley and John Tukey are generally credited for the invetion of the modern generic FFT algorithm published in 1965, and since then, it has become an essential tool for processing digital signals.

What is FFT?

FFT is an algorithm that allows us to analyze the frequency components of a signal. In other words, it is a way to convert a signal from the time domain to the frequency domain. This is useful for a variety of applications, such as filtering, noise reduction, and compression.

How does FFT work?

The FFT algorithm works by dividing a signal into smaller segments and performing the Fourier Transform on each segment. These smaller segments are combined to form the overall frequency spectrum of the signal.

The FFT algorithm is based on the fact that the Fourier Transform of a signal is periodic. This property is exploited to reduce the number of computations required to compute the Fourier Transform.

The FFT algorithm can be implemented using various techniques, such as the Cooley-Tukey algorithm, the Radix-2 algorithm, and the Bluestein algorithm. Each of these techniques has its own advantages and disadvantages and is suitable for different types of signals.

Applications of FFT

The FFT algorithm has a wide range of applications, some of which are listed below:

1. Signal Processing: FFT is used in signal processing to analyze signals in the frequency domain. It is used for filtering, noise reduction, and compression of signals.

2. Image Processing: FFT is used in image processing to analyze the frequency components of an image. It is used for tasks such as image enhancement, filtering, and compression.

3. Audio Processing: FFT is used in audio processing to analyze the frequency components of an audio signal. It is used for tasks such as equalization, filtering, and compression.

4. Communication Systems: FFT is used in communication systems for tasks such as modulation and demodulation of signals.

5. Data Compression: FFT is used in data compression to compress data by reducing the amount of redundant information in the signal.

Python Cooley-Tukey implementation of the FFT

# General-purpose FFT method
def fft(vals, modulus, domain, add, multiply, neg):
    if len(vals) == 1:
        return vals
    L = fft(vals[::2], modulus, domain[::2], add, multiply, neg)
    R = fft(vals[1::2], modulus, domain[::2], add, multiply, neg)
    o = [0 for i in vals]
    for i, (x, y) in enumerate(zip(L, R)):
        y_times_root = multiply(y, domain[i])
        o[i] = add(x, y_times_root)
        o[i+len(L)] = add(x, neg(y_times_root))
    return o

Here, vals is a of coefficients representing a polynomial in the time domain, modulus is the modulus used for arithmetic operations, domain is a list of domain values and a domain in the context of the Cooley-Turkey FFT is a complex number that is typically chosen to be root of unity in the modulus field, which works almost in the same way as normal mathematics but instead of dealing with all of the numbers you calculate the equality based on the remainder of the division of numbers, this reduces the number of possible points from all possible numbers into full numbers (int), for example, if the modulus field is the complex numbers with modulus 1 (i.e., the unit circle in the complex plane), then the domain values would be the complex numbers of the form exp(2pii*k/N), where k is an integer and N is the length of the input sequence. These values are the Nth roots of unity in the complex plane, and they have the property that when they are multiplied together, they generate all possible phase shifts of the input sequence.add and multiply are functions that do what they say but in the modulus field and neg is a function that returns the additive inverse of a value in the modulus field.

If there is only one coefficient then it returns it, that's the base case on:

if len(vals) == 1:
    return vals

in this step:

L = fft(vals[::2], modulus, domain[::2], add, multiply, neg)
R = fft(vals[1::2], modulus, domain[::2], add, multiply, neg)

The vals[::2] operator gets the even coefficients of the sequence and the vals[1::2] gets the odd based on the index of the list not the value of the coefficient itself, so you are essentially breaking down the original polynomial coefficients into left and right sections separating the odd ones from the even ones.

Recursion can be hard to understand but think about it like this, when the algo gets to this point:

o = [0 for i in vals]
for i, (x, y) in enumerate(zip(L, R)):

'o' is going to be a list of the same length of values that will be used to calculate the output of each coefficient, when it gets to the loop the previous recursive calls will have returned a bunch of lists of one element each containing the respective value of the coefficient based on it´s odds and evens in the sequence, this means the loop will run for each one of them at a time...

y_times_root = multiply(y, domain[i])
o[i] = add(x, y_times_root)
o[i+len(L)] = add(x, neg(y_times_root))

this operations refer to turning the coefficient into the domain based on the modular field for each coefficient, which is the point of the algorithm. Here is an example using example parameters:

vals = [1, 2, 3, 4]
modulus = 5
domain = [1, 4, 1, 4]
add = lambda x, y: (x + y) % modulus
multiply = lambda x, y: (x * y) % modulus
neg = lambda x: (modulus - x) % modulus

Then, after the first recursive call, L and R would be:

L = [1, 3]
R = [2, 4]

After the second recursive call, L and R would be:

L = [1]
R = [3]

and

L = [2]
R = [4]

Finally, the loop would be executed twice, producing the output:

o = [0, 3, 0, 2]

which corresponds to the DFT of the input sequence [1, 2, 3, 4].

It's also worth mentioning that the types of function used in this algorithm depend on the field you are perform the algorithm on, in the case of this example it is a finite field of modulo 5, but the functions can vary depending on the purpose of the algorithm and the field chosen. So the purpose of the algorithm is to compute the Discrete Fourier Transform or DFT of a sequence of complex numbers, which can be represented as a polynomial in the time domain, the DFT can be defined mathematically as a linear transformation that maps a sequence of N complex numbers x[n] to another sequence of N complex numbers X[k], where n and k are integers that range from 0 to N-1. The transformation can be expressed using a matrix multiplication as follows:

X[k] = sum from n=0 to N-1 of (x[n] * exp(-2*pi*i*n*k/N))

where i is the imaginary unit, and exp is the exponential function. This formula calculates the contribution of each input sample x[n] to the output sample X[k], taking into account the phase relationship between the input and output frequencies.

Conclusion

The Fast Fourier Transform (FFT) is a powerful mathematical algorithm used to transform data from the time or spatial domain to the frequency domain. It has numerous applications in various fields, such as signal processing, image processing, data compression, and communication systems. The FFT algorithm is based on the Fourier Transform, which was introduced by Jean-Baptiste Joseph Fourier in the early 19th century. The FFT algorithm is a fast version of the Fourier Transform that can efficiently compute the discrete Fourier Transform of a signal. It is widely used in many applications and has become an essential tool for processing digital signals.