FAST FOURIER ALGORITHM, RADIX-2 FFT ALGORITHMS
Table of Contents
FAST FOURIER ALGORITHM
Fast Fourier Transformation (FFT)
In the field of measuring audio and acoustics, the “Fast Fourier Transform” (FFT) is a crucial measurement technique. So It breaks down a signal into its individual spectral components, giving frequency information about the signal in the process. FFTs are used for machine or system condition monitoring, quality control, and fault analysis. This article explains the operation of an FFT, the pertinent parameters, and how they affect the measurement outcome.
The FFT is technically a “Discrete Fourier Transformation” (DFT) implementation algorithm that has been optimized. A signal is divided into its frequency components after being sampled over time. So Each of these elements is a single sinusoidal oscillation with a unique frequency, amplitude, and phase. The diagram that follows shows how this transformation happens. The signal contains 3 distinct dominant frequencies over the measured time period.
FAST FOURIER ALGORITHM
DFT calculations are necessary for many applications, including filtering, correlation analysis, and spectrum analysis. Direct DFT computation, however, necessitates numerous calculations, keeping the processor busy. Therefore, special algorithms known as Fast Fourier Transforms (FFT) are created to quickly compute DFT.
The divide and conquer strategy is the foundation of the radix-2 FFT algorithms. This technique breaks down the N-point DFT into smaller DFTs one at a time. There are fewer computations as a result of this decomposition.
RADIX-2 FFT ALGORITHMS
DECIMATION IN TIME (DITFFT)
There are three properties of twiddle factor WN
Two N/2 point data sequences, f1(n) and f2(n), are created from the N point sequence x(n). Even numbered samples of x(n) are found in f1(n), and odd numbered samples are found in f2(n). Decimation is the name for this split operation. It is known as “Decimation in Time” because it is performed in a time domain sequence. Thus
f1(m)=x(2m) where n=0,1,………….N/2-1
f2(m)=x(2m+1) where n=0,1,………….N/2-1
N point DFT is given as
Since the sequence x(n) is divided into samples with even and odd numbers,
Fig 1 shows that 8-point DFT can be computed directly and hence no reduction in computation.