Fourier transform and signal processing (part 2)

Uncategorized

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 x[n] for -\infty < n < \infty

The Fourier representation of the x[n] is a function of the form:

X(e^{j\omega})=\sum_{n=-\infty}^{n=\infty}x[n]e^{-j\omega n}

The above formula is an analysis formula.

The inverse Fourier transform (which is an synthesis formula) is like this:

x[n] = \frac{1}{2\pi}X(e^{j\omega})e^{j\omega n}d\omega

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: y[n] = \sum_{k=-\infty}^{\infty}h[n-k]x[k] where h[k] is the impulse response of the system to unit step.

If we choose x[n] = e^{j\omega n} then y[n] = e^{j\omega n}(\sum_{k=-\infty}^{\infty}h[k]e^{-j\omega k})

If we define: H(e^{j\omega}) = \sum_{k=-\infty}^{\infty}h[k]e^{-j\omega k}

then we have y[n] = H(e^{j\omega})e^{j\omega n}

H(e^{j\omega}) – frequency response of the system

Comparing the latest formula with the Fourier transform formula we could see that:

X(e^{j\omega}) = H(e^{j\omega}) 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:

h[n] = \frac{1}{2\pi}\int_{-\pi}^{\pi}X(e^{j\omega})e^{j\omega n}d\omega

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 x[n] = x[n + rN] then we could take into consideration a finite number of samples for X(e^{j\omega})

The Fourier representation in this case is a superposition of complex exponentials with frequencies that are multiple of fundamental frequency \frac{2\pi}{N}.

Therefore DFT will use two formulas:

Analysis equation: X[k] = \sum_{n=0}^{N-1}x[n]W_N^{kn}

Synthesis equation: x[n] = \frac{1}{N}\sum_{k=0}^{N-1}X[k]W_N^{-kn}

whre W_N = e^{-j(2\pi/N)}

Therefore, one could calculate direct/inverse DFT series easily by using a finite length N vector of x[n] respective X[k].

Fast Fourier Transform (FFT):

To calculate DFT with equations above you’ll have complexity O(N^2). 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 O(Nlog(N)).

3 thoughts on “Fourier transform and signal processing (part 2)”

  1. Hello i try to open your blog in safari and its looks funny, i tink that the problem is from your hosting ,or maybe from me but still you have a nice setup for the ads, i writing in this post because you will see it when you are validating comments, Keep up the good work Andrei from Romania

  2. Doesnt seem to be working on my IE7. Just thrashes incessantly, refreshing the address bar non-stop. View source shows about 6 lines of curious JavaScript. I can be from may laptop but the page its ok on Mozila, i cant undestend someting im on alexa now and your rank is verry big, i found you blog on second page of google .Andrei from Italy

Leave a Reply

Your email address will not be published. Required fields are marked *