What is Fourier transform?

The algorithm used to convert a sequence to its Discrete Fourier transform (DFT) is known as the Fast Fourier transform. It can be used for both DFT and IDFT (Inverse DFT) transformation.

A transform used to change the domain of the input signal to frequency domain is known as Fourier series transform. When the input signals are periodic in nature, signal processing cannot be done with ease. Hence, changing the domain to frequency domain enables wavelet processing and Fourier transform is widely used.

Periodic functions will have time or space domains. The Fourier transform will decompose the original input signal based on its spatial or temporal frequency. The magnitude of the Fourier transform represents the absolute value of frequency that was depicted in the input function. The argument of Fourier transform will be phase offset value. This relationship between time and frequency domain is studied under harmonic analysis.

The inverse Fourier Transformers are used to convert the frequency domain to the time domain.

Fourier transform in signal processing

Signal processing involves synthesizing input signals and analyzing them. The process involves detecting various components of the input signal add measuring them to create an output. Multiple instruments and mathematical methods are used in signal processing. While the instruments help the user to filter and take the components of the input signal, the mathematical methods especially the transform theory are used to convert one form of signal into another for easier calculations.

Transform theories involve Laplace transform, Fourier transform, Hankel transforms, Z-transform, Mellin transform and Joukowsky transform.

Fourier Transform is mainly used in decomposing a signal into its oscillatory components and this process is known as Fourier analysis. Fourier synthesis represents rebuilding a particular signal from its oscillatory components. Main applications cover the processing of signals and digital images, mathematics, and structure analysis. In signal processing, the input signal is taken in the continuous-time domain, and decomposition of the function by taking oscillatory sinusoidal parts is done to convert the signal to the frequency domain. This type of Fourier analysis is known as Discrete Fourier Analysis.

Discrete Fourier transform

The most important Fourier transform that is practically used in digital signal processing is the discrete Fourier transform (DFT). Signals in the time domain have various underlying factors that keep on fluctuating with time. These disturbances will be reflected as noise in the output signal and hence signal processing cannot be done in the time domain. Discrete Fourier transform (DFT) will convert the input function sequence into an output sequence which is a complex-valued function in the frequency domain. This method of transforming from time to frequency domain is known as Discrete-time Fourier transform (DTFT). The frequency spectra will be based on the time domain variables themselves.

DTFT deals with discrete data points that are samples of continuous function. It handles a sequence of input signals and is invertible.

Fast Fourier transform

DTF and IDTF computations can be computed using fast Fourier transform algorithms. It was first introduced by Carl Friedrich Gauss in 1805. Later on, it was developed throughout the 19^th century. It takes the approach of Danielson-Lanczos Lemma to divide the data sets into successively smaller problems, not by factors of 2, but by whatever small prime factors happen to divide N-point. It is invertible in the form of inverse fast Fourier transform (IFFT).

FFT Algorithm

Cooley–Tukey algorithm

The algorithm is based on the divide and conquer method. The DFT is broken down into smaller sizes. The division of the data sets is based on radix-2 cases where the transform is divided into two smaller pieces at the middle, after every step. The basic concept is of breaking down a DFT into sections that can be considered as micro DFTs.

The division is done to make parts of size N-point=N-1 N-2, in the case of a two-dimensional DFT.

Prime factor Fast Fourier Transform

With similarities to mixed radix method of Cooley-Tukey algorithm, Prime factor algorithm (PFA). The algorithm is used when N1 and N2 are relatively prime numbers. PFA required reindexing of the data samples and this property is a disadvantage to the algorithm.

Bruun’s Fast Fourier Transform

The algorithm uses the recursive polynomial factorization method to compute the DFT of the input data. It was developed by G. Bruun in 1978 and was modified throughout the 19^th century. It is also known as Bruun factorization.

Bluestein’s Fast Fourier Transform

It is a type of chirp Z- transform (CZT). It was invented by Leo Bluestein in 1968. It uses the convolution theorem to receive an output.

Hexagonal Fast Fourier Transform

With hexagonal sampling, Hexagonal FFT is used on two-dimensional signals. The transform uses the hexagonal efficient coordinate system for efficient outcomes. It was invented by Mersereau. It uses linear transforms to two-dimensional samples of data, to create subarrays.

Rader’s Fast Fourier Transform

The cyclic convolution is used in the algorithm to express the divided parts. The algorithm is based on the periodic nature of DFT.

Applications

The main application of the FFT algorithm is digital signal processing. In 1965, the application of FFT was introduced in O(N log N). Applications range from nuclear tests to national security. Material analysis and processing use FFT as an indispensable part.  

Context and Applications

• Bachelors in Technology (Computer Science)
• Masters in Technology (Computer Science)
• Bachelors in Science (Electronics)
• Masters in Science (Electronics)

Practice Problems

Q1. Which of the following is the main application of Fast Fourier transform?

1. Digital signal processing
2. Material analysis
3. Spectral analysis
4. All of the above

Answer: Option d

Explanation: Fast Fourier transform (FFT) is mainly used in digital signal processing, material analysis, and spectral analysis.

Q2. Bluestein’s Fast Fourier Transform is a type of which of the following transform?

1. FFTPACK
2. Bruun's FFT
3. Chirp Z- transform
4. None of these

Answer: Option c

Explanation: Bluestein’s fast Fourier transform is a type of Chirp Z- transform.

Q3. Which of the following algorithms uses cyclic convolution?

1. Bruun’s fast Fourier transform
2. Rader’s fast Fourier transform
3. Prime factor fast Fourier transform
4. None of these

Answer: Option b

Explanation: Rader’s Fast Fourier transform uses cyclic convolution.

Q4. What is the use of inverse fast Fourier transform?

1. Converts time domain to frequency domain
2. Converts frequency domain to time domain
3. Both a and b 
4. None of these

Answer: Option b

Explanation: Inverse fast Fourier transform is used to convert frequency domain to time domain.

Q5. What is the basis of the division of sets in the Cooley-Tukey FFT algorithm?

1. Convolution
2. Polymerization
3. Radix-2
4. None of these

Answer: Option c

Explanation: Cooley-Tukey FFT algorithm uses radix-2 method for division of sets.

Common Mistakes

Fourier transform is an intricate mathematical process that requires precision and concentration. Mistakes are commonly made while selecting the sample size, dissecting the signal, and during computation. Such mistakes can lead to improper data processing. Mistakes made in simple integration and complex multiplications can cause multiple discrepancies throughout the process.

Choosing the right method of FFT is an important part of the process.

Related Concepts

• Digital signal processing
• Audio signal processing
• Image processing
• Short-time Fourier transform
• Functional relations
• N-dimensional functions