As I told last time, I’m going to present a small project I’ve done to exercise sound card use on Linux, sound processing with Fourier transform, Discrete Fourier Transform(DFT) and Fast Fourier Transform (FFT). All of these are used to make a practical LRC-meter able to measure inductors, resistors, capacitors.
The math behind:
It is not the idea of this article to present the full math theory behind Fourier transform but only to present the application of the theory. Good books that present theory in detail are on the market, e.g. “Discrete-time signal processing” by Oppenheim and Schafer.
Suppose we have a discrete signal represented as
The Fourier representation of the x[n] is a function of the form:
The above formula is an analysis formula.
The inverse Fourier transform (which is an synthesis formula) is like this:
A Fourier transform translates the signal from time domain to frequency domain in which it represents the signal as a superposition of sine waves each having a coeficient given by the Fourier transform.
Now to make a long story short, a LTI (Linear Time Invariant) system could be analised by using the Fourier transform. The relationship between the Fourier transform of a signal and the characteristics of the system could be explained as follows:
For LTI system: where h[k] is the impulse response of the system to unit step.
If we choose then
If we define:
then we have
– frequency response of the system
Comparing the latest formula with the Fourier transform formula we could see that:
meaning that the frequency response of a LTI system is the Fourier transform of impulse response.
The above equality is very important to practical needs just because if you have the frequency response of a LTI system then you could calculate the response to unit step by using the inverse Fourier transform:
Discrete Fourier Transform (DCT):
The Fourier transform formula of a discrete signal gives a continue function. Depending on the signal, the sum could be calculated easily or not because of the infinite number of harmonics taken into consideration.
If we consider the signal is periodic with period N so that then we could take into consideration a finite number of samples for
The Fourier representation in this case is a superposition of complex exponentials with frequencies that are multiple of fundamental frequency .
Therefore DFT will use two formulas:
Therefore, one could calculate direct/inverse DFT series easily by using a finite length N vector of respective .
Fast Fourier Transform (FFT):
To calculate DFT with equations above you’ll have complexity . It is called FFT, the algorithms that strives to calculate DFT efficiently other than doing the sums above. There are couple such algorithms variations that goes to a complexity of .