Welcome to AE Resources

FAST FOURIER TRANSFORMS

Most engineering data however are not continuous functions, but consist of discrete points. Thus, an efficient methodology is needed to transform discrete data (DFT). This methodology is known as a Fast Fourier Transform (FFT). There are various FFT algorithms designed to compute the DFT, but one of most often used is the Sande-Tukey algorithm.

This algorithm deprecates or reduces the size of the FFT to reduce the cost. Consider the discrete Fourier transform (DFT)

ℱ_k = ^N − 1⎲⎳_i = 0F_ie^{− (2π ⁄ N)jik}

where k varies from 0 to N − 1 and ω = (2π)/(N). This equation can be written with a weighting function, w = e^− jω as

ℱ_k = ^N − 1⎲⎳_i = 0F_iw^ik

The number of points is divided into two summations, one for even (n = 2ℓ) and the other for odd values (n = 2ℓ + 1):

ℱ_k = ^{N ⁄ 2 − 1}⎲⎳_ℓ = 0F_2ℓe^{− (2πj ⁄ N)2ℓk} + ^{N ⁄ 2 − 1}⎲⎳_ℓ = 0F_2ℓ + 1e^{− (2πj ⁄ N)(2ℓ + 1)k}

where k is still over the range from 0 to N − 1. Using exponential math, this equation can be modified to

ℱ_k = ^{N ⁄ 2 − 1}⎲⎳_ℓ = 0F_2ℓe^{− (2πj ⁄ (N ⁄ 2))ℓk} + e^{− (2πj ⁄ N)k}^{N ⁄ 2 − 1}⎲⎳_ℓ = 0F_2ℓ + 1e^{− (2πj ⁄ (N ⁄ 2))ℓk}

or as one summation

ℱ_k = ^{N ⁄ 2 − 1}⎲⎳_ℓ = 0(F_2ℓ + e^{− (2πj ⁄ N)k}F_2ℓ + 1)e^{− (2πj ⁄ (N ⁄ 2))ℓk}

This reduces the number of operations significantly from the original summation. With some further manipulations (e.g., e^− jπk = ( − 1)^k), the equation can be expressed as

ℱ_2k = ^{N ⁄ 2 − 1}⎲⎳_ℓ = 0(F_ℓ + F_{ℓ + N ⁄ 2})W^2ℓk

for the even values and

ℱ_2k + 1 = ^{N ⁄ 2 − 1}⎲⎳_ℓ = 0(F_ℓ − F_{ℓ + N ⁄ 2})W^ℓW^2ℓk

using the weighting function, W, defined previously. Comparing these expressions to the definitions of the Fourier integrals, it is readily seen that these are the Fourier transforms of the even and odd factors over N ⁄ 2, so that only N ⁄ 4 outputs for the expression are needed.. Recalling that e^±jx = cos(x)±jsin(x) permits a computer code to be efficiently written.

Because the code computes the coefficients in this compact form, the coefficients must be unscrambled to form the appropriate sequence in the end. This algorithm is known as a butterfly network.

← Previous Page