Path: EDN Asia >> Design Centre >> IC/Board/Systems Design >> Fast Fourier Transform: Equations and history
IC/Board/Systems Design Share print

Fast Fourier Transform: Equations and history

27 Apr 2016  | Shayan Ushani

Share this page with your friends

The Fast Fourier Transform (FFT) is fairly regarded as the most important numerical algorithm of our lifetime. Whether it's used to monitor signals coming from the depths of the earth or search for heavenly life forms, the algorithm is widely used in all scientific and engineering fields. But what exactly is an FFT? Why does it matter in signal-processing projects?

Named after the late 18th century French mathematician Jean-Baptiste Joseph Fourier, the Fourier Transform is a mathematical operation that converts a signal from the time (spatial) domain to the frequency domain. According to Fourier theorem, a signal is a composition of a number of sinusoidal functions with given amplitude, frequency, and phase. The Fourier series equation formulates the theorem for a periodic signal, x(t):

In these equations, P stands for the signal's period and Cn is called the Fourier coefficients of the signal x(t). The coefficients are calculated by:

For a sine wave, there is only one coefficient. If, however, the signal contains an infinite number of frequencies, such as is the case for an ideal square wave, a finite N results in an error. Figures 1 and 2 compare the original signal with its representation based on Fourier series coefficients for N=3 (green signal) and N=15 (blue signal.) As we can see, the accuracy of the transformation depends on the nature of the signal and the number of terms in the series.

Figure 1: An ideal square wave function.

Figure 2: The Fourier series reconstruction of the square wave for N=3 and N=15. Plot calculated by:

Most signals, however, aren't periodic. Nonperiodic signals don't have a Fourier series. This fact greatly disappointed Fourier, who needed almost 20 years to develop a general formula that would work for any function. Now, any signal could be transformed from the time domain to the frequency domain by the following equation:

[Note that Ω is discrete frequency.]

1 • 2 Next Page Last Page

Want to more of this to be delivered to you for FREE?

Subscribe to EDN Asia alerts and receive the latest design ideas and product news in your inbox.

Got to make sure you're not a robot. Please enter the code displayed on the right.

Time to activate your subscription - it's easy!

We have sent an activate request to your registerd e-email. Simply click on the link to activate your subscription.

We're doing this to protect your privacy and ensure you successfully receive your e-mail alerts.

Add New Comment
Visitor (To avoid code verification, simply login or register with us. It is fast and free!)
*Verify code:
Tech Impact

Regional Roundup
Control this smart glass with the blink of an eye
K-Glass 2 detects users' eye movements to point the cursor to recognise computer icons or objects in the Internet, and uses winks for commands. The researchers call this interface the "i-Mouse."

GlobalFoundries extends grants to Singapore students
ARM, Tencent Games team up to improve mobile gaming

News | Products | Design Features | Regional Roundup | Tech Impact