Fast Fourier Transform (FFT)

The Fast Fourier Transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, and it’s used for analysing and processing signals and data in the frequency domain. FFT is widely used in various fields and applications where signal processing or frequency analysis is necessary.

MatDeck Fast Fourier Transform FFT options

• Simple and Fast FFT functions used in MD documents and formulas on canvas
• MD FFT functions used as Python library in Python Scripts
• Python FFT library used in MD Python IDE
• FFT functions as mathematical formula template for MD document can transfer to PDF document
• GPU Fast Fourier Transform (FFT) ArrayFire supports CUDA and NVIDIA
• Other Spectral functions
• Build FFT App with MD GUI Designer
• MD hardware devices for FFT applications

Using Python Fast Fourier Transform FFT libraries in MD Document and IDEs

MatDeck’s FFT functions can easily be used in Python alongside popular libraries like SciPy and NumPy in both the MatDeck Document and Python Scripts. With MatDeck’s Python Bindings, MD Python, you can now use the simplicity of Python with 1600+ MatDeck functions which allow you utilize incredibly intricate and crucial functions. NumPy and SciPy functions such as

• fft()
• ifft()
• fft2()
• ifft2()

are already available in MD Python with much simpler syntax and arguments, this make FFTs much simpler and minimizes the chances of the mistake.

MatDeck FFT functions

MatDeck’s fft1() function rapidly calculates the DFT of the input sequence, with speed comparable to other leading mathematical software, achieving 0.5 sec for a sequence length equal to one million samples. This speed is achieved using the “Build and Run Exe” option to execute the fft1() function. The ffti1 function () is used to compute the inverse discrete Fourier transform, and to move from the frequency domain to the time domain. ffti1() also uses a very efficient algorithm as well. All MatDeck functions that rely on fft1() or ffti1() are extremely efficient in algorithmic sense. MatDeck’s fft2() function is used to determine the two-dimensional Fourier transform in an efficient manner.

MatDeck’s function fft1() rapidly calculates the DFT of the input sequence, with speed comparable to other leading mathematical software achieving 0.5 sec for the sequence length equal to one million samples.

Fast Fourier Transform (FFT) templates

This speed is MatDeck’s templates are shown below. The red boxes show where to find Fast Fourier Transform FFT templates and functions. Templates are ready-made pieces of code that need very little editing to be used of advanced and needed applications.

Fast Fourier Transform FFT GPU Acceleration

MatDeck allows user to set GPU modes with ArrayFire. The better video card you use, the more noticeable the difference in execution time will be. This is clearly visible when you have larger matrices, Fast Fourier Transform FFT, convolution and more. ArrayFire supports all CUDA –capable NVIDIA video cards and OpenCL devices such as AMD video cards. The function that is used for MatDeck’s fft1() function is the ArrayFire afp_fft() function, which is part of the AF plugin. The corresponding two-dimensional function is afp_fft2(). There are also functions for inverse Fast Fourier Transform transforms afp_ifft(), and afp_ifft2(). Several other functions rely on the efficient implementation of afp_fft(), such as: afp_fft_convolve() and afp_fft_convolve,2 which are used for convolution as well as afp_fft_c2r() that is used for complex to real Fourier transform.

In the example below, we can see how CUDA is used to speed up the execution of the code, the same can also be done with OpenCL, using ArrayFire functions.

Fast Fourier Transform Basics

Essentially, the Fourier Transform is a mathematical algorithm that facilities the transform of signals in the space/time domain into signals in the frequency domain. If we use the frequency of sound for this example, the air pressure recorded from a sensor or microphone will be a raw combination of various signals and frequencies. Fast Fourier Transform can be applied to convert the different waves combined into terms of frequency. This gives users the unique opportunity to separate individual signals and frequencies which is fundamentally crucial for Digital Signal Processing.

What is Discrete Fourier Transform (DFT)?

The formal strict mathematical definition of Fast Fourier Transform is rather limited in how it can be applied to real world scenarios and projects. It is computationally difficult and simply rare to find signals in terms of functions and signals tend to be recorded and stored instead as discrete values and recordings. The important aspect here is that these signals are finite. This where the Discrete Fourier Transform is compromised where instead of a function, the Fourier transform is treated as a translation applied over a discrete finite set of values.

Convolution Theorem and Fast Fourier Transform – FFT

Fast Fourier Transforms truly show the complexity of the algorithm when separating specific signals from a mix of signals (Noise).            This mix of multiple signals combining to create a new mutated signal is called convolution where in our above example, two signals combine to create a new 3^rd signal. With FFTs and DFTs, being able to mathematically convolute signals and the inverse may be the single most important founding block of Digital Signal Processing. It is almost used and applied in every algorithm and proof for DSP engineers.

Convolution theorem states that the convolution of two signals in real-time is equal to the product of their equivalent Fourier transformations within the frequency domain. This simple theorem is crucial and useful as it simplifies a plethora of calculations. Convolutions naturally are hard to deal with and utilise mathematically however, become much more linear when dealing with them as Fourier transforms and multiplications.

Fourier Transform Symmetries

Symmetry is a useful property in mathematics and algorithm building thus, where found, symmetry should be exploited to minimize problems and their respective solutions. One way symmetry is present in Fourier Transforms is through the representation of a periodic function in terms of phase and magnitude. Fourier transforms naturally produce complex values for magnitude. The example two-sided spectrum shows how amplitude of a Fourier transform series would look when plotted on a axis of infinitely negative and positive frequency.

Readers will be able to tell that the reason it’s aptly named a two-sided spectrum is because both negative and positive frequencies are plotted.

Important and useful deductions that will reduce the number of computational cycles needed can be inferred from the representation above.

Since Cn that is plotted above is a complex number (composed of real and imaginary parts), complex conjucation can be applied to make useful changes.

The amplitude spectrum of the Fourier transform series can be seen mathematically and visually to be symmetrical about the vertical axis present at 0hz. However, analysis of the phase spectrum aspect shows us that the phase spectrum of a Fourier Transform series is anti-symmetrical.

Example 1 – Applying DFT to a discrete signal

For our example below, we will look through the steps taken to apply the DFT version of the Fast Fourier Transform (FFT) algorithm when we have a discrete signal. Below is the discrete signal we will work with.

To find the FFT of this signal, first we define the signal which has been already defined for us above. To calculate the FFT we will use the DFT formula which is defined in MatDeck already.

The formula above is the defined DFT formula that will be used. As the signal we are using is discrete and finite, naturally the Discrete Finite Transform formula will be used instead of the FFT formula. As touched on before, the FFT formula is incredibly important but has limited application within the real world as not every signal can be dealt with periodically and infinitely.

where:

• N is the length of the signal.
• k is the frequency index.
• j is the imaginary unit.

Our discrete signal has 4 data points in it so N=4 and the DFT formula will be applied to each data point thus k=0, k=1, k=2, k=3. Keen users will notice that the range of the sigma function in the DFT is n=0 to N-1, meaning each n passed to the DFT formula will consecutively count to N(length)-1.

Below are two iterations that were created in MatDeck showcasing how the FFT of each discrete data point is calculated.  

Once all the iterations from 0-3 are complete, you will have the transformed FFT values for each point within the signal. Below are the results for each point.

These complex numbers represent the amplitude and phase of sinusoidal components at different frequencies in the original signal. The magnitude and phase of these complex numbers can be used to analyse the frequency content of the signal. In short, the magnitude gives the amplitude of the corresponding frequency component, and the phase gives the phase shift.

Discrete Fourier Matrices

A Fourier Series in essence is a periodic function or a sum of functions of different frequencies. As explained before, the Discrete Fourier Transform is the missing piece that is used in the decomposition of Fourier Transforms by breaking infinite sets of data or signals into groups of finite and discrete transforms.  This applies as well when we begin to use the Fourier Matrix.

When using Fourier transform and related components, complex numbers and their properties are extremely common and present in most applications. For the Fn matrix above, all values used are on the unit circle in the complex plane and the columns of the matrix are orthogonal. Another important distinction that will help in representing the Fourier matrix is that each value within the matrix raised to the power of n is 1 and

Knowing these two equivalences for our matrix values we can convert our matrix into another representation by using 4 as our value of n. By using 4, we can create a Fourier matrix that can be used to transform vectors with four components(n). This is simply done by multiplying the given vector with our Fourier matrix.

Example 2 – Applying a Fourier Transform Matrix to an impulse

To illustrate how the Fourier Transform matrix can be applied, we will use an impulse described by the matrix below and apply the transform.

As mentioned above, this vector has 4 components so the Fourier Transform matrix defined beforehand will be left-multiplied with the given vector.

As our vector example is a single impulse, all the frequencies will be transformed in equal amounts. To inverse the transform and return inputs to their original states, multiply the matrix by Fn again and divide by the scalar n.

Example 3 – Converting From Coefficient Form to Point Form

For this illustration, we will look at how to implement two n-degree polynomials being multiplied in Fast Fourier Transform – FFT form. An important definition we will be using throughout is the division of our polynomial in even and odd parts. Here, applying the transform to the odd and even parts respectively will prove more viable than applying the transform sequentially on all coefficients of A(X).

Now we split A(X) in terms of even and odd-indexed coefficients as such.

Now we need to apply to both even and odd-indexed parts respectively some derivations can be made.

Thereforewould require:

,…,

Extending this logic to and, we can say that the andwould require,…, _≡,…, as the points on which they should be evaluated.

Now users will be able to notice that evaluating the even and odd-indexed parts of A(x) at

,…,

is actually just recursively solving the problem in two equal parts. In other words, this would be the same as evaluating A(x).

Where is FFT used

The Fast Fourier Transform FFT algorithm is most commonly used for:

• Signal Processing: For tasks like filtering, convolution, and spectral analysis.
• Audio Processing: Transforming audio signals for compression, equalization, and spectral analysis.
• Image Processing: For filtering, compression, and frequency content analysis.
• Communications: Modulating, demodulating, and channel estimation.
• Scientific Research: Analysing experimental data and extracting information from spectra.
• Computer Graphics: Texture mapping, image synthesis, and rendering.
• Finance: In financial modelling, option pricing, risk assessment, and time series analysis.
• Seismology: Analysing seismic data and identifying wave frequencies.
• Medical Imaging: Processing MRI and CT scans for analysis.
• Vibration Analysis: Studying vibrations and frequency responses in engineering.

Fast Fourier Transform FFT in Signal Processing

Fast Fourier Transform FFT is used widely throughout signal processing an does not have one specific area where it is used, but its main areas of use are:

• Frequency Analysis: Decomposing signals into their constituent frequencies to identify dominant components and analyse harmonic content.
• Filtering: Efficiently removing noise and unwanted frequency components by designing and applying frequency-domain filters.
• Convolution: Accelerating operations like smoothing, modulation, and system analysis through frequency domain conversions.
• Spectral Analysis: Calculating power spectral density to understand signal power distribution across frequencies.
• Signal Compression: Transforming signals to the frequency domain for compression by discarding or quantizing high-frequency components.
• Equalization: Adjusting frequency response to achieve desired spectral balance.
• Transient Detection: Identifying transient events and anomalies by examining their frequency content.
• Time-Frequency Analysis: Combining time and frequency domain analysis for studying how signal frequency components change over time using techniques like STFT and Wavelet Transform.

Fast Fourier Transform FFT in Audio Processing

The Fast Fourier Transform FFT is a fundamental tool in audio processing, with versatile applications:

• Spectrum Analysis: Breaks audio signals into constituent frequencies for component identification and harmonic analysis.
• Filtering: Removes noise and unwanted frequencies via frequency-domain filters.
• Convolution: Speeds up operations like modulation and system analysis.
• Spectral Analysis: Calculates power spectral density for power distribution insights.
• Signal Compression: Prepares audio for compression by transforming it into the frequency domain.
• Equalization: Adjusts frequency response for desired spectral balance.
• Transient Detection: Identifies transient events by examining their frequency content.
• Time-Frequency Analysis: Combines time and frequency analysis for tasks like tempo estimation and speech analysis.

Fast Fourier Transform FFT in Image Processing

Similar to Signal and Audo processing, Fast Fourier Transform FFT is a versatile tool in image processing, and is crucial for several reasons:

• Frequency Analysis: Decomposes images to identify patterns and textures by their constituent frequencies.
• Filtering and Noise Removal: Efficiently eliminates noise and unwanted features by applying frequency-domain filters.
• Convolution and Image Enhancement: Speeds up operations like smoothing and edge detection.
• Texture Analysis: Calculates power spectral density for understanding texture distribution.
• Image Compression: Transforms images for efficient compression.
• Image Equalization: Adjusts frequency response for improved visual quality.
• Edge and Anomaly Detection: Identifies edges and anomalies by analysing frequency content.
• Spatio-Frequency Analysis: Combines time and frequency analysis for tasks like texture recognition.

The History of Fast Fourier Transform FFT

The history of the Fast Fourier Transform (FFT) is a story of mathematical progress and computational innovation. It traces its origins to Joseph Fourier’s work in the 18th century, where he laid the groundwork for understanding the decomposition of complex signals into simpler sinusoidal components.

The modern FFT, as we know it, emerged in the 1960s with the Cooley-Tukey algorithm, developed by American mathematicians Cooley and Tukey. This algorithm revolutionized the computation of the Discrete Fourier Transform (DFT) by significantly reducing its computational complexity. This breakthrough marked the birth of the Fast Fourier Transform.

Since then, Fast Fourier Transform has played a pivotal role in signal processing, image analysis, and various other fields. Its historical journey, from Fourier’s foundational work to the algorithmic innovations of Cooley and Tukey, highlights its enduring importance in scientific and technological advancements.

Examples

• FFT 1
• Vibration Analysis of a Car Engine
• IIR filter implementation