# Fourier Transform

## The Frequency Domain

Many physical objects have a frequency range over which they perform most of their work. Your ears for instance, can generally only hear frequencies between 20Hz and 20 kHz. Your own voice when speaking normally, concentrates most power in the range of 500 to 2000Hz. You can think of these as the bandwidth of their operation. Other real world sources have their own bandwidths of operation. A tuning fork has a very narrow bandwidth tuned to a single note. An organ pipe, or harp string is tuned to only release a specific frequency and its higher order harmonics. A Hi-Fi amplifier has to have a very wide operating bandwidth to allow it to amplify your music uniformly across all frequencies in the audible range. The loud-speakers in your car that turn the analog signal into sound waves are usually designed to work only on low, medium or higher frequencies in the audible range.

Your Wi-Fi modem has to operate equally well across a wide range of electromagnetic frequencies in the 2.4GHz and the 5GHz bands of the electromagnetic spectrum. The sun generates electromagnetic radiation across an enormous bandwidth that includes infra-red radiation we feel as heat, visible light, ultra-violet rays that damage our skin as well as X-Rays and Gamma rays. Thankfully, most of the energy that the sun releases is green visible light instead of the destructive X-rays and Gamma rays that fly out of other stars!

All of the objects and systems we have been talking about above, have a bandwidth of operation and a specific behavior in the *frequency domain*.

Analyzing objects in the frequency domain is a fundamental tool in mathematics that *simplifies* and provides insight into the analysis and design of electronics, control systems, communications systems, structural engineering, mechanical engineering, statistics and many other disciplines!

## The Fourier Transform

Any signal that varies with time can be referred to as a time-domain signal. All time-domain signals have a corresponding frequency-domain representation. The frequency-domain description tells us about the frequency-components that make up the total energy of the signal. You can describe any continuous time-domain signal as a sum of sinusoidal waves of increasing frequency and varying amplitude. The mathematical method to do this is called the Fourier transform. Here is a great picture that explains the Fourier transform really well in a visual way!

## Forms of the Fourier Transform

I am not going to dig into the details of how the Fourier Transform works in a blog. However, it does seem sensible to understand the various forms of the Fourier Transform and the contexts in which we make use of them!

### Fourier Transform – Integral

The Fourier transform as I was taught it with respect to time-domain signal f(t), has the following form:

This form of the Fourier transform is great for continuous time-domain signals that we want to analyze from a mathematical perspective, but this form does not easily lend itself to solution by digital computers.

### Discrete-Time Fourier Transform

The Discrete Time Fourier Transform is applied to signals that are not continuous in time and is useful for analyzing a sampled signal. The signal x(nT) is an infinitely long series of very short pulses of continuous, varying amplitude. It should be noted that the Discrete-Time Fourier Transform has a practical weakness in that the input is an infinitely long pulse train, and the output X(Ω) is a continuous function of the frequency variable and cannot be represented exactly by digital computers.

### Discrete Fourier Transform

This is the form of the Fourier transform used by digital computers. The output is a discrete function of the frequency variable and this can easily be represented by a computer!

To calculate the DFT and generate the discrete frequencies of the output samples, we have to start with a finite number of discrete-time samples of the input signal, we denote the number of samples as N.

In the Signals & Systems textbook I have, they write: “Let us choose the value of N sufficiently large, so that our set of samples adequately represents all of x[n]”. In the digital communications world, this would translate to all the sample values of the last received symbol.

We select our discrete angular frequencies as Ω = 2πk/N where k is some integer value between 0 and N-1.

In this case, where N is the number of time domain samples we have collected, and k is the current frequency sample we are calculating for, the discrete Fourier Transform is:

To figure out the frequency each discrete frequency k represents, recall:

### Fast Fourier Transform (FFT)

This is the method used by modern computers and radio receivers to calculate the Discrete Fourier Transform of a received time-domain signal and retrieve the symbol information encoded inside it. The Fast Fourier transform implements an algorithm to reduce the number of computational steps in calculating the Discrete Fourier Transform.

The complexity of calculating the DFT is easily seen to rise in proportion with the square of the total number of time-domain samples, N. That means that for a 1024 sample signal, a 1024 sample DFT will result, requiring in excess of 1 million complex multiplications! The Fast Fourier Transform enables the same calculation to be carried out using many fewer complex multiplications as shown in the table below:

# Samples | Complex Multiplications Required | Size required by Wi-Fi Standards | |

DFT | FFT | ||

2 | 4 | 1 | |

4 | 16 | 4 | |

8 | 64 | 12 | |

16 | 256 | 32 | |

32 | 1,024 | 80 | |

64 | 4,096 | 192 | 802.11ac (m) |

128 | 16,384 | 448 | 802.11ac (m) |

256 | 65,536 | 1,024 | 802.11ac (m) 802.11ax (m) |

512 | 262,144 | 2,304 | 802.11ac (opt) 802.11ax (m) |

1,024 | 1,048,576 | 5,120 | 802.11ax (m) |

2,048 | 4,194,304 | 11,264 | 802.11ax (m) |

=N^{2} |
=(N/2)log_{2}(N) |

### Further Reading:

Here are the resources I have found on the topic:

- http://www.thefouriertransform.com/
- https://www.princeton.edu/~cuff/ele201/kulkarni_text/frequency.pdf
- http://www.eie.polyu.edu.hk/~enpklun/EIE327/DFT.pdf
- http://math.mit.edu/~gs/cse/websections/cse41.pdf
- http://www.cse.salford.ac.uk/physics/gsmcdonald/H-Tutorials/Fourier-series-tutorial.pdf
- https://web.stanford.edu/class/ee102/lectures/fourtran
- http://www.lehman.edu/faculty/dgaranin/Physics_of_Sound/PHY140-Spring-2007-04-Synthesis_and_Analysis_of_complex_waves.pdf

If you are looking for a single, comprehensive source that will take you from basic mathematics all the way to the Fourier transform, I found this to be a fantastic, free resource (click on the picture!)

—

That’s all for now

Rob