1. Introduction
2. What’s the Fourier Rework?
   2.1 Time Area
   2.2 Frequency Area
   2.3 The Fourier Rework: A Mathematical Perspective
3. The Limitation of the Conventional Discrete Fourier Transformation Calculation
4. The FFT Algorithm
5. The Matrix View
6. The Backside Line

Word: All the code file used on this article is offered on the following repository: https://github.com/namanlab/FFT_Algorithm_Code

The very foundations of the world round us, from the habits of quantum particles to the motion of enormous celestials are in all probability ruled by algorithms. Because the silent architects of our digital cosmos, they’re just like the gods of the fashionable period sculpting the contours of our technological actuality. Algorithms are all-powerful, as they command the intricacies of actuality with unmatched precision and understanding. They manifest an omnipresence, quietly shaping our experiences, guiding all of expertise, and influencing the very cloth of our interconnected world. Lastly, additionally they exhibit an omniscient prowess as they assist mankind decipher complicated patterns and navigate the huge realms of information buried inside our nature.

An algorithm isn’t only a technique or a method of doing one thing, it’s additionally about doing it effectively in a approach that saves us time and area, the 2 constraints that mainly led to your entire subject of their research. On this article, we are going to discover some of the good algorithms of the century: the Quick Fourier Rework (FFT) algorithm. The FFT algorithm helped us clear up one of many greatest challenges in audio sign processing, particularly computing the discrete Fourier rework of a sign in a approach that isn’t solely time environment friendly but additionally extraordinarily stunning. I hope that by the top of this text, it is possible for you to to understand the sheer magnificence of this revolutionary algorithm. Let’s start!

Word: In the event you’re already aware of the idea of a Fourier rework, you might skip this part and proceed to the subsequent one, the place I’ll discuss in regards to the want for the FFT algorithm and the way it works.

The Fourier transformation is actually a mathematical method that enables us to transform a sign from its time area to its frequency area. However what do you even imply by time and frequency area? To know this, first allow us to take into consideration the basic query: what’s a sign?

Within the easiest sense, a sign is only a variation in a bodily amount. This bodily amount could possibly be something measurable: pace, voltage, present, stress, vitality, you identify it. Indicators might be broadly categorized into two domains: time area and frequency area.

Time Area

Within the time area, a sign is represented as a operate of time. In different phrases, which means that we will plot/characterize the sign’s habits with respect to time, and also you observe the way it modifications over a particular time interval.

For instance, if you’re measuring the voltage throughout a resistor in {an electrical} circuit, the sign within the time area would present you the way the voltage varies at totally different cut-off dates. Equally, the time area illustration of a sound simply exhibits how the amplitude of the sound wave (which is simply the extent of air stress) varies over time. The sign could possibly be represented mathematically as a operate:

x(t) = 2t² + 2t − 1

That is the continual illustration of the sign x as a direct operate of time, t (in seconds). Nevertheless, for many sensible purposes, we don’t know the true purposeful type of the sign. All we now have is a discrete pattern of the sign (at totally different factors of time) that could possibly be represented as a easy vector equivalent to this:

The vector simply exhibits the worth of x at 8 totally different (equally spaced) intervals of time. The spacing between the time intervals known as the time interval, T of the sign. So, if the sign was sampled at intervals of two seconds every, the time interval can be T = 2 seconds.

Frequency Area

Within the frequency area, a sign is represented as a operate of frequency. As an alternative of analyzing how a sign modifications over time, the main target is on its frequency parts or the totally different frequencies current within the sign. This can be a bit extra obscure, so let’s spend some extra time speaking about this with an instance of sound waves. Think about you’re listening to a chunk of music on the radio. Within the time area, you expertise the music unfolding over time — how the melody progresses, the rhythm of the beats, and the length of every observe.

Now, let’s change to the frequency area. Consider the frequency area as should you’re trying on the music from a unique perspective. As an alternative of specializing in how the music evolves over time, you’re within the particular person tones or pitches that make up the general sound. Think about you may isolate the particular musical notes, such because the deep bass, the mid-range tones, and the high-pitched parts. How cool would that be? Take into consideration what constitutes the music: the person devices and the singers. Every instrument and voice current within the music has a singular signature within the frequency area. The bass guitar may dominate within the decrease frequencies, the vocals could cowl a broad vary, and the cymbals and excessive hats contribute to the upper frequencies. That’s the place the frequency area steps in as a superhero of types; it means that you can break down the complicated combination of sounds into its constituent elements. In essence, it gives a unique viewpoint, specializing in the constructing blocks of a sign’s sound somewhat than its development over time.

In its frequency area, the sign could possibly be represented as a operate (steady) like y(f) = 2f² + 3 or as a easy vector (akin to the time area) equivalent to this:

The vector simply exhibits the amplitude/extent of the presence of the totally different frequency parts. The primary aspect (1) may characterize the amplitude of the bottom frequency part (say 1 Hz, Hz is the unit of frequency). Likewise, the second aspect (2) may characterize the amplitude of the subsequent frequency part, and so forth.

The Fourier Rework: A Mathematical Perspective

Now that we now have some concept of how the sign might be represented, visualize the Fourier Transformation as a magical lens that means that you can change your view between the 2 representations of alerts. . It acts as a bridge between the time and frequency domains, permitting us to research and perceive alerts in each time and frequency views.

Now, we analyze what I simply stated utilizing some math. The Fourier transformation is a operate that takes the sign in its time area as enter and decomposes it right into a sum of sine and cosine waves of various frequencies having their amplitude and part. The ensuing illustration is nothing however the frequency area (or what we additionally name the spectrum) of the sign. Mathematically, the Fourier rework of a steady sign in its time area x(t) is outlined as follows:

the place i = √(-1) is the imaginary quantity. Sure, the Fourier transformation yields a posh output in consequence that features each a posh part and magnitude. However, in lots of sensible situations, our focus is totally on the magnitude of the transformation, and we frequently disregard the accompanying part. Provided that digitally processed sign is discrete, we will set up the discrete Fourier rework (DFT) as its analogous counterpart:

Right here we now have merely changed the integral with sum as we could solely have discrete time samples and the true purposeful type of the sign could also be unknown to us. As an alternative of an infinite variety of samples, suppose we now have a finite variety of samples, name it N: the variety of time samples or the size of the vector representing the sign. Then we get the so-called short-term Fourier rework of the sign:

the place T is the time interval. The above operate might be computed for any worth of f and its magnitude simply exhibits us the extent to which that exact frequency part is current / energy of that frequency part. For example, given the next vector illustration, we could compute the Fourier rework at f = 0.5 and f = 0.25:

Suppose the values of x are measured in intervals of T = 1 second every. Then,

The above calculation requires using some primary complicated quantity properties, largely the Euler’s id: exp{πi} = −1. The output, primarily permits us to check the presence of various frequency parts. This leads us to the subsequent query: what values of f will we take into account? Theoretically, we may acquire the worth of the Fourier rework for any worth of f, thus it turns into crucial to search out the suitable vary of values of f, for which the Fourier Rework offers a great image of the underlying sign and can also be interchangeable i.e., it may be used to acquire the time area again. For many sensible purposes, we solely take into account frequency bins which might be an integral a number of of 1/(TN) the place TN is the overall length of the sign (the variety of samples N occasions the length of every pattern, T) we now have. The rationale for that is carefully associated to the idea of sampling and the Nyquist-Shannon sampling theorem, an concept that isn’t significantly related to this text. However should you’re interested in it, be at liberty to confer with this web page.

Earlier than transferring ahead, let’s take a second to summarise all the things we’ve coated to this point: a sign is only a variation in a bodily amount that may be expressed as a operate of time (time area) or as a operate of frequency (frequency area). Each these representations are equal (i.e., one may give us the opposite) and the Fourier rework is the strategy for changing one illustration to a different. The Fourier Rework of a steady sign is represented as a steady operate within the frequency area. Nevertheless, after we work with digital alerts (discrete-time alerts), we pattern the continual sign at discrete factors. This offers us the next system for computing the short-term discrete Fourier rework of a sign:

Since we solely take into account frequencies which might be an integral a number of of 1/N, we get the next:

the place i is the complicated quantity √(-1), j is the index of the pattern within the sign and okay is the index of the frequency bin for which we’re computing the facility. Because it’s cumbersome to jot down y(okay/(NT)) once more, we merely outline a brand new operate:

And that my buddies, is the equation for the Fourier Rework that we generally encounter in textbooks. In the event you’re nonetheless uncertain about how and why this works, right here’s a superb rationalization of Fourier transforms. For the subsequent part of this text, we are going to put in some actual information to calculate the whole Fourier Rework of a sign, write up some code, and uncover the constraints of the normal strategy to computing the Fourier Rework of a sign. It will ultimately lead us to the core of this text: the FFT algorithm.

Let’s begin this part by calculating the Fourier Transformation of a easy sign consisting of simply 8 samples:

As we will see from the system, we don’t care in regards to the time interval i.e., the intervals at which the amount is measured so long as it’s sampled uniformly. Now, we could proceed to search out the Fourier rework by plugging within the values into the system for various values of okay (starting from okay = 0 to okay = N — 1 = 7). Consequently, we have to calculate the next:

Allow us to simplify the calculations by taking α = exp{-2πi/N}. Thus, all we’d like is:

and so forth for all 8 values of okay. That is fairly a prolonged calculation. Can we do higher? After all, we will use a easy Python program to do the job for us. Right here’s a conventional (known as the brute power) strategy that primarily goes by each each aspect within the vector and computes the required time period for all values of okay from 0 to N — 1:

import numpy as np
def simple_dft(sign):
# Get the variety of samples within the sign
N = len(sign)
# Initialize an empty record to retailer the end result (DFT coefficients)
res = []
# Iterate over every frequency bin (okay)
for okay in vary(N):
# Initialize the present DFT coefficient for the given frequency bin
cur_value = 0
# Iterate over every pattern within the sign (j)
for j in vary(N):
# Calculate the complicated exponential time period and accumulate
cur_value += sign[j] * np.exp(-2 * np.pi * 1j * j * okay / N)
# Append the end result for the present frequency bin to the record
res.append(np.spherical(cur_value, 5))
# Return the record of DFT coefficients
return res
simple_dft([1, 2, 0, 5, 9, 2, 0, 4])
# Output: [(23+0j), (-8.70711-0.70711j), (10+5j), (-7.29289-0.70711j), 
# (-3-0j), (-7.29289+0.70711j), (10-5j), (-8.70711+0.70711j)]

Utilizing this operate, we simply get the 8 DFT coefficients required. We will additionally confirm our calculations utilizing the fft operate supplied by numpy:

# Compute the FFT utilizing NumPy's fft operate
a = np.fft.fft([1, 2, 0, 5, 9, 2, 0, 4])
# Compute the DFT utilizing our simple_dft operate
b = simple_dft([1, 2, 0, 5, 9, 2, 0, 4])
# Verify if the outcomes are element-wise shut inside a tolerance
print(np.allclose(a, b))
# Output: True

Cool, we will get the end result accurately! However, is the strategy of calculating actually environment friendly? What do you suppose is the time complexity of this operate? It includes two nested for loops every iterating over your entire vary of values from 0 to N — 1. Thus, the time complexity is of the order O(N²). This may occasionally not appear too dangerous, however for many sensible purposes, an O(N²) time complexity may imply extraordinarily sluggish time to get the outcomes. Let’s put this to numbers.

Suppose we’re computing the Fourier rework of an audio pattern that’s simply 10 minutes lengthy. For many conventional purposes, we frequently pattern at a fee of 22050 i.e., we measure 22050 samples at each second (this may occasionally appear loads, but it surely actually isn’t, that is the sampling fee that’s mostly used to take care of the standard of the audio pattern). Because of this we now have about 10*60*22050 = 13230000 samples. To take the DFT of this pattern, we are going to subsequently want no less than N² = 13230000² = 175032900000000 variety of computations, and that’s loads! In the event you’re utilizing one thing like C++ (which is likely one of the most effective programming languages), the max you are able to do is probably 2 × 108 computations per second. This implies, that calculating the DFT of a brief 10-minute audio would take 175032900000000/200000000 = 2875164.5 seconds or about 10 days! This could make it virtually not possible to compute the DFT of enormous alerts, rendering the appliance of the Fourier rework fairly restricted. However concern not! Enter the Quick Fourier Rework (FFT), the magical algorithm that swoops in, making DFT computations lightning-fast. It helps cut back the time complexity of DFT calculation from O(N²) to mere O(N log N). For the 10-minute pattern, we might now require solely 13230000*log(13230000) = 216945507 floating level operations. This interprets to a mere 1.08 seconds, rather more environment friendly than the normal DFT algorithm. This implies we’re not simply restricted to small alerts — FFT unleashes the facility of Fourier Transforms on huge datasets. Cool, proper? However how does the algorithm even work and what makes it so environment friendly? This leads us to the subsequent part of this text: the FFT algorithm!

The core concept of FFT lies within the inherent symmetry of the Fourier Transformation that helps us cut back among the redundant calculations. FFT works by harnessing the symmetry of the DFT computation and feeding it into a sublime recursive divide and conquer mannequin successfully lowering time complexity from O(N²) to O(N log N). However, what is that this symmetry we’re speaking about? Recall the system for the DFT computation:

What occurs if we use this system for N + okay as an alternative of okay? Let’s see:

By the properties of complicated numbers, e−2πij = 1 for any worth of j. Thus,

In different phrases, the worth merely repeats itself after okay = N. Thus, F(1) = F(N + 1); F(2) = F(N + 2) and so forth. That is the explanation, why we solely compute the Fourier rework as okay ranges from 0 to N — 1. The values merely carry on repeating afterward. Extra typically by easy induction, we now have that for any nonnegative integer s ∈ Z≥0,

That is the symmetric property that we’re going to use to provide you with the a lot quicker (as is claimed in its identify), the FFT algorithm. However how will we provide you with a divide-and-conquer technique that makes use of this symmetry? The concept is to separate up the phrases into odd and even phrases and have a look at the DFT for every of them individually:

Within the above formulation, we’ve break up the DFT phrases into two teams: one with even indices (j = 2m) and the opposite with odd indices (j = 2m + 1). As you may see, this offers us two separate DFTs, one computed solely on the even phrases of the sign, whereas the opposite computed on the odd phrases. However, does this assist us cut back the variety of operations? Not but, as we nonetheless want to judge all N/2 phrases for all values of okay from 0 to N — 1 for each odd and even phrases i.e., nonetheless 2*N*(N/2). Or do we have to? Right here’s after we use the symmetric property of FFT! Suppose we will consider the above expression for some integral worth a that lies between 0 and N/2–1. Thus,

Utilizing simply the worth of F₁(a) and F₂(a) (and the symmetric property proven earlier), we will simply calculate the worth of F(a + b) = F(c) for some integral worth c that lies between N/2 and N — 1:

Right here’s the important thing concept! We don’t must calculate F(c) over again, this protects us about N/2*N operations each time. All we have to do is calculate F1(a) and F2(a) for each integral worth a between 0 and N/2–1 (which takes a complete of (N/2)*(N/2) = N²/4 operations for each the even and odd phrases. Doing this and making use of some easy symmetric logic will permit us to calculate the worth of F(okay) for all integral values of okay between 0 and N — 1, successfully lowering the variety of operations from N² to 2 × (N/2) × (N/2) = N²/2 i.e, an element of half. Isn’t it simply wonderful?

Now, it could appear that we simply diminished the time complexity by half, isn’t it nonetheless O(N²) on the finish of the day? That’s true provided that we break up up the sign as soon as. However, nothing stops us from splitting it additional! We will proceed this chain:

If we assume, that N is an influence of two, we will repeat this course of for a complete r occasions such that:

Every particular person analysis takes O(N) time to compute, and we do that for r = log2(N) occasions, giving us a time complexity of O(Nr) = O(N log N) (we will ignore the bottom of the logarithm when describing time complexities). For these of you who’d wish to see this when it comes to the recurrence relation, it’s given by:

Right here, T(N) represents the time complexity of fixing an issue of measurement n. Within the case of FFT, it’s the variety of parts within the enter sign, and O(N) represents the time required for combining the outcomes of smaller sub-problems.

The recurrence relation signifies that to unravel an issue of measurement N, the FFT algorithm recursively divides the issue into two sub-problems of measurement N/2 (one for the odd phrases, and the opposite for the even phrases), computes the options for these sub-problems in a complete of 2T(N/2) time, after which combines the ends in O(N) time. Fixing this recurrence relation additionally leads us to the O(N log N) time complexity proven earlier.

Every part appears to be like good in idea! However does this even work? Let’s try it out by writing a easy Python operate that calculates the DFT utilizing the FFT algorithm as an alternative. Right here’s the code:

import numpy as np
def nice_fft(sign):
# Get the variety of samples within the sign
N = len(sign)
# Base case: if the sign has just one samples, use simple_dft
if N == 1:
return simple_dft(sign)
else:
# Initialize an empty record to retailer the end result (DFT coefficients)
res = []
# Separate the sign into even and odd phrases
even_terms = sign[::2]
odd_terms = sign[1::2]
# Recursively compute FFT for even and odd phrases
f1 = nice_fft(even_terms)
f2 = nice_fft(odd_terms)
# Mix the outcomes utilizing the Cooley-Tukey FFT algorithm
for okay in vary(N):
# Calculate the complicated exponential time period
mult = np.exp(-2 * np.pi * 1j * okay / N)
# Decide the index for the even and odd phrases
INDEX = (okay % int(N / 2))
# Mix the outcomes for the present frequency bin
dft_value = f1[INDEX] + mult * f2[INDEX]
# Append the end result for the present frequency bin to the record
res.append(np.spherical(dft_value, 5))
# Return the record of DFT coefficients
return res
nice_fft([1, 2, 0, 5, 9, 2, 0, 4])
# Output: [(23+0j), (-8.70711-0.70711j), (10+5j), (-7.29289-0.70711j), 
# (-3-0j), (-7.29289+0.70711j), (10-5j), (-8.70711+0.70711j)]

And it offers the identical outcomes as earlier than, however a lot quicker! The above code follows a recursive strategy primarily based on the divide-and-conquer technique mentioned. Word that this code works just for alerts whose size is an influence of two for simplicity. For alerts with a size that isn’t an influence of two, we will merely append 0s firstly or the top to get the specified end result. To check our two capabilities (easy dft and good fft), we will attempt to generate a random array of a measurement equivalent to a big energy of two and measure the time taken:

import timeit
# Generate a random array of measurement 2^14 (16384)
random_array = np.random.rand(2**14)
# Measure the execution time for simple_dft
time_simple_dft = timeit.timeit(lambda: simple_dft(random_array), quantity=1)
# Measure the execution time for nice_fft
time_nice_fft = timeit.timeit(lambda: nice_fft(random_array), quantity=1)
# Print the outcomes
print(f"Time taken for simple_dft: {time_simple_dft:.5f} seconds")
# Output: Time taken for simple_dft: 149.81244 secondss
print(f"Time taken for nice_fft: {time_nice_fft:.5f} seconds")
# Output: Time taken for nice_fft: 1.28395 seconds

That’s an enormous enchancment. To get a greater view of the time variations, we will additionally make a line plot (log scale) displaying the distinction within the period of time taken for arrays of various sizes:

# Outline array sizes to check
array_sizes = [2**n for n in range(5, 14)]  # Sizes from 2^5 to 2^14
# Measure execution time for every array measurement
time_simple_dft = []
time_nice_fft = []
for measurement in array_sizes:
random_array = np.random.rand(measurement)
time_simple_dft.append(timeit.timeit(lambda: simple_dft(random_array), quantity=1))
time_nice_fft.append(timeit.timeit(lambda: nice_fft(random_array), quantity=1))
# Plotting
import matplotlib.pyplot as plt
plt.determine(figsize=(10, 6))
plt.plot(array_sizes, time_simple_dft, label='simple_dft')
plt.plot(array_sizes, time_nice_fft, label='nice_fft')
plt.xlabel('Array Dimension')
plt.ylabel('Time (seconds)')
plt.title('Execution Time for simple_dft and nice_fft')
plt.legend()
plt.present()

Isn’t it cool how a easy concept of symmetry nested throughout the elegant framework of divide and conquer produced such an exquisite algorithm?

On this article, we began with the formulation of the Fourier Rework and easily manipulated the expression by splitting the odd and even phrases to reach on the FFT algorithm. There’s one other technique to view it: by the lens of matrix manipulation. The concept is to think about the Fourier rework as merely multiplying the enter sign with a matrix (known as the Fourier matrix). Recall the definition of the Fourier rework:

As you may see, every of the person DFT is calculated by merely taking a linear mixture of the sign measurements. We will take α = exp{-2πi/N}, and we get:

This permits us to characterize the sign and the transformation utilizing a easy notation of vectors and matrices:

The entire of DFT boils right down to discovering that massive N × N matrix F (known as the Fourier matrix) and multiplying it with the enter sign. Utilizing the FFT algorithm, we will decompose the Fourier matrix as a product of three sparse matrices:

Now it could appear overwhelming, however on the root, it’s simply expressing our earlier divide and conquer utilizing matrices. The I_{N/2} is simply the id matrix of N/2 rows/columns, recognized to us. D_{N/2} is just the diagonal entries of the primary N/2 × N/2 partition of the N × N Fourier matrix F . This may be calculated simply in O(N) because it solely requires us to calculate the values of 1, α, α⁴, …., α^{(N/2–1)²}, which simply corresponds to the multiplier time period in our authentic formulation.

The F_{N/2} corresponds to the recursive sub-problem, the Fourier matrix of measurement N/2 × N/2. Lastly, P is a permutation matrix (a matrix crammed with all 0s besides for only one 1 in each row/column). The aim of P is to segregate the odd and even phrases of the enter sign, by bringing the even phrases to the highest and the odd phrases to the underside. The remainder of the matrix manipulation follows as earlier than. We will hold repeating this course of many times, breaking the Fourier matrix F_{N/2} constantly till we attain the bottom case when N = 1. As earlier than the time complexity stays O(N log N), it’s only a extra elegant technique to write down the equations with out the messy summations!

The Quick Fourier Rework (FFT) stands as a testomony to the fantastic thing about simplicity and magnificence in algorithmic design. It has revolutionized sign processing, information evaluation, and numerous scientific disciplines and its significance lies not solely in its computational effectivity, as evidenced by the exceptional pace beneficial properties over na ̈ıve approaches, but additionally in its versatility, enabling breakthroughs in numerous fields equivalent to telecommunications, picture processing, and quantum computing. From audio compression algorithms to medical imaging strategies, the FFT underpins a myriad of purposes which have turn into integral to our day by day lives.

As we mirror on the journey from a easy concept to a groundbreaking algorithm, it’s awe-inspiring to understand how a elementary understanding of symmetry, coupled with modern algorithmic design, can yield options of profound significance. The FFT, with its magnificence and effectivity, encapsulates the essence of ingenuity in pc science. So, subsequent time you marvel on the readability of a digital picture or benefit from the constancy of a music stream, simply do not forget that behind these technological marvels stands the exceptional FFT — a real testomony to the facility of easy but ingenious concepts.

Hope you loved studying this text! In case you’ve gotten any doubts or ideas, do reply within the remark field. Please be at liberty to contact me by way of mail.

In the event you favored my article and need to learn extra of them, please comply with me.

Word: All photos (aside from the quilt picture) have been made by the writer.

1. cs.cornell.edu. https://www.cs.cornell.edu/~bindel/class/cs5220-s10/slides/FFT.pdf. [Accessed 05–01- 2024].
2. The Quick Fourier Rework (FFT): Most Ingenious Algorithm Ever? — youtube.com. https://www.youtube.com/watch?v=h7apO7q16V0. [Accessed 05–01–2024].
3. Shaw Talebi. The Quick-Fourier Rework (FFT) — medium.com. https://medium.com/swlh/ the-fast-fourier-transform-fft-5e96cf637c38#:~:textual content=Thepercent20FFTpercent20ispercent20anpercent20efficient,the% 20Permutationpercent20matrixpercent2Cpercent20usedpercent20above. [Accessed 05–01–2024].
4. Jake VanderPlas. Understanding the FFT Algorithm — Pythonic Perambulations — jakevdp.github.io. https: //jakevdp.github.io/weblog/2013/08/28/understanding-the-fft/. [Accessed 05–01–2024].