1.    Basics of Fourier Transform

Fourier transform is a process to convert a spatial domain signal (i.e., time domain signal) into a frequency domain signal. Oppositely, the inverse Fourier transform is a process to convert the frequency domain signal to the primary time domain signal.

 

Fourier transform

The Fourier transform of a time-domain signal is defined as follows

X(ω) = ωt) dt

 

**x(t) denotes the signal in the time domain, denotes the signal in the frequency domain and is the angular frequency.

 

Inverse Fourier transform

x(t) = ωt) dt

 

Discrete Fourier Transform (DFT)

For digital systems, the Fourier transform is realized by

For complex numbers x₀, x₁, x₂, x₃, … , x_n-1

X[k] = W_N^kn ,  where k=1,2,3,..,N-1

Where W_N  is the n^th root of unity given by

W_N = exp(-j(2 )

 

**DFT Algorithms are at the end of this article

 

Fast Fourier Transform (FFT)

The basic idea of a fast Fourier transform is to break up a transform of length N into two transforms of length N/2.

For complex numbers x[n] where, n = 1, 2, 3, …, n-1

X[k] = W_N^kn = e^-j2πk(2r)/N + e^{-j2πk(2r+1)/N}

**In the above transform of length N is broken into two transforms of length N/2 and on the other hand, they pick up even and odd samples of x[n] separately

= e^-j2πk(2r)/N + e^-j2πk/N e^-j2πk(2r)/N

= e^{-j2πkr/(N/2)} + e^-j2πk/N e^{-j2πkr/(N/2)}

In the above diagram {X[0], X[1], X[2], X[3], X[4], X[5], X[6], X[7]} is the Fourier transform of {x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]}

 

**FFT algorithms are at the end of this article

 

2.    Advantages of FFT over DFT

To compute the DFT of an N-point sequence it take O(N²) multiplies and adds. The FFT algorithm computes the DFT using O(N log N) multiplies and adds.

The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for N points from 2N² to 2Nlog₂N.

 

3.    Properties of Fourier Transform

1. Linearity

The Fourier Transform satisfies linearity & principle of superposition

Consider two functions x₁(t) & x₂(t)

If F(x₁(t)) = X₁(ω),  F(x₂(t)) = X₂(ω)

Then F[a₁x₁(t) + a₂x₂(t)] = a₁X₁(ω) + a₂X₂(ω) 

 

 

2. Scaling

F(x(t)) = X(ω)

If ‘a’ is real constant then

 F(x(at)) = X(ω), 

 

3. Symmetry

When x(t) is real and even then X(ω) = X^*(-ω)

When x(t) is real and odd then X(ω) = X(-ω)

 

4. Convolution

Fourier transform makes the convolution of 2 signals into the product of their Fourier Transform. There are two types of convolutions, one for time domain and other for frequency domain.

1. Time domain convolution

F(x₁(t)) = X₁(ω),  F(x₂(t)) = X₂(ω)

Then F(x₁(t)* x₂(t)) = X₁(ω) . X₂(ω),    [‘*’ – convolution sign)]

 

2. Frequency domain convolution

F(x₁(t) . x₂(t)) = 1/2.X₁(ω) * X₂(ω)      [‘*’ – convolution sign)]

 

5. Shifting Property

F(x(t – t₀)) = e^-jωt0 X(ω)

As a consequence, transforms leave the Fourier spectrum | X(ω)|² unchanged.

 

6. Duality

F(x(t) =  X(t) = 2 x(-ω)

 

7. Differentiation

F( ) = jωX(ω)

 

8. Integration

F(t) dt) = X(ω)/jω

When a function (i.e., x(t)) is not an energy function and hence the Fourier transform of (t) dt] includes an impulse function.

F(t) dt) = X(ω)/jω + X

 

9. Modulation Property

F{x(t)cosat} = ½ {X(ω + a) + X(ω - a)}

F{x(t)sinat} = ½ {X(ω + a) - X(ω - a)}

 

10. If the Fourier transform of f(x) is F(k), then f^*(x) <=>  F^*(-k)

As a consequence Fourier transform of a real function must satisfy the symmetry relation.

F(k) = F^*(-k), meaning that the Fourier transform is symmetric about the origin in k-space. |F(k)|² = |F(-k)|²

 

11.  Parseval’s theorem

Energy = (t)|²dt = 1/2 (ω)|²dω

The total energy in the time domain signal, x(t) [i.e., the left integral] can be easily calculated from the frequency domain signal, X(ω) [i.e., from the right integral]

 

12. Time reversal

F(x(-t)) = X(-ω)

 

4.    Fourier Transform of some common signals
   1.           Fourier Transform of a delta function

If x(t) = 𝛅(t), then Fourier transform,

X(ω) = (t)e^-jωt dt

= (t)e^-jωt dt

= e^-jω0 dt

= 1

Thus Fourier transform of a delta/impulse is a constant equal to 1, independent of frequency. Remember that derivation is used the shifting property of the impulse to eliminate the integral.

 

2.           Fourier transform of a unit step function

 

γ (t) = 0 for t<0

                                                            = 1 for t ≥1

We know that a unit-step function is an integration of a delta function. So for a unit step function,

γ (t) =  (t) dt

So, X(ω) = F() + F() 

[See the property of integration above]

           = +       [as F()= F()=1]

When a function (i.e., x(t)) is not an energy function and hence the Fourier transform of (t) dt] includes an impulse function.

 

3.           Fourier Transform of a unit pulse function

A pulse function can be represented as,

x(t)=Π(t) = γ (t + ½) - γ(t - ½)

For a function rect(t) = Π(t) = 1 for |t| ≤ ½

                                             = 0 otherwise

Given that

x(t) = Π(t)

Hence from the definition of the Fourier transform we have

F (Π(t)) = X() = e ^-jωt dt

                           =  e ^-jωt dt     [as Π(t) = 1 for |t| ≤ ½]

                            =  [(e ^–jωt)/-jω]_-1/2^1/2

                                           = [e ^–jω/2 - e ^jω/2] / -jω

                            = [e ^jω/2 - e ^-jω/2] / jω

                            = 2/ω . {[e ^jω/2 - e ^-jω/2] / 2j}

                            = 2/ω . sin(ω/2)

                            = {sin(ω/2) / (ω/2)}

                           = {sin((ω/2)) / ((ω/2))}

                            = sinc(ω/2)

 

For the above case, the rectangular function has a pulse width value of 1 over the interval of [-½, ½]; 0 otherwise.

Now we’ll discuss a rectangular pulse that has a width of T

Then,    rect(t/T) = Π(t/T) = 1 for |t| ≤ T/2

                                             = 0 otherwise

Given that

x(t/T) = Π(t/T)

Hence from the definition of the Fourier transform we have

F (Π(t/T)) = e ^-jωt dt

                           =  e ^-jωt dt     [as Π(t/T) = 1 for |t| ≤ T/2]

                            =  [(e ^–jωt)/-jω]_-T/2^T/2

                                           = [e ^–jωT/2 - e ^jωT/2] / -jω

                            = [e ^jωT/2 - e ^-jωT/2] / jω

                            = 2/ω . {[e ^jωT/2 - e ^-jωT/2] / 2j}

                            = 2/ω . sin(ω(T/2))

                            = {sin(ω(T/2)) / (ω/2)}

                            = {sin(ωT/2)) / (ω/2))}

                            = {sin(ωT/2)) / (ωT/2))}.T

                            = T. sinc(ωT/2)

 

 

4.           Fourier Transform of a unit triangle pulse

A unit triangle pulse is simply the convolution of a unit pulse function with itself.

Here, Λ(t) = Π(t) * Π(t)               

[Π(t) is a unit pulse function & ‘*’ denotes convolution]

So, Λ(ω) = sinc(ω/2) . sinc(ω/2 = sinc²(ω/2

 

5.           Fourier Transform of a Sawtooth function

s(t) = 0, for t < 0 and t > 1

                                                  = 1, for 0 ≤ t ≤ 1

We can represent sawtooth as the integral of shifted unit pulse function (to give the ramp) and a negative impulse (delayed by one second) to give the discontinuity at the end of the ramp

 

s(t) = dt - dt =

y(t) = -

Now, we’ve to find the Fourier transform of y(t),

Y(ω) = sinc(ω/2)e^-jω/2 - e^-jω

We can now apply integral property with Y(0) = 0, to find S(ω)

S(ω) = F() = Y(ω)/jω - Y(0)(0) = Y(ω)/jω

= {(sinc(ω/2)e^-jω/2 - e^-jω) / jω}

= {((sin(π . ω/2) / (π . ω/2))e^-jω/2 - e^-jω) / jω}

=  (((sin(π . ω/2) / (π . ω/2))e^-jω/2) / jω) – (e^-jω / jω)

= (2(sin(ω/2)e^-jω/2) / jω²) – (je^-jω / j²ω)

= (2((e^jω/2 - e^-jω/2) / 2j)e^-jω/2) / jω²) + (je^-jω / ω)     [as j² = -1]

= (((e^jω/2 - e^-jω/2)e^-jω/2) / j²ω²) + (je^-jω / ω)

= (((e^-jω/2 - e^jω/2)e^-jω/2) / ω²) + (je^-jω / ω)

= (((e^-jω/2 - e^jω/2)e^-jω/2) / ω²) + (je^-jω / ω)

= ((((e^-jω/2 - e^jω/2)e^-jω/2) + jωe^-jω) / ω²)

= ((e^-jω - 1 + jωe^-jω) / ω²)

= ((e^-jω(1+jω) - 1) / ω²)

 

 

5.    Algorithms

For DFT & FFT

Look at the aforementioned formula for DFT. The term W^k_N  (= exp(-j(2 .k) ) can be represented as follows

 

In the above figure the values for N = 2, 4, and 8 are shown in the complex plain. Where ‘N’ denotes N point DFT.

 

For example,

For a 2 point DFT

W₂ = e^-2jπ/N = e^-2jπ/2 = e^-jπ = -1

Now, discrete Fourier transform for complex numbers a₁ and a₂ is

A_K = _n W₂^kn

      = _n (-1)^kn

      = a₀ (-1)^{k  .0}  + a₁ (-1)^{k  .1}

As K = 0 and 1 (for 2 point DFT)

So, A₀ = a₀  + a₁

And A₁ = a₀  -  a₁

 

Similarly for a 4-point DFT

W₄ = e^-2jπ/4 = e^-2jπ/4 = e^-jπ/2 = -j

Now, discrete Fourier transform for complex numbers a₁, a₂, a₃, and a₄ is

A_K = _n W₄^kn

     = _n (-j)^kn

     = a₀ (-j)^{k  .0}  + a₁ (-j)^{k  .1} + a₂ (-j)^{k  .2} + a₃ (-j)^{k  .3}

So, A₀ = a₀  + a₁ + a₂  + a₃

      A₁ = a₀  - ja₁ - a₂  + ja₃

      A₂ = a₀  - a₁ + a₂  - a₃

      A₃ = a₀  + ja₁ - a₂  - ja₃

 

To compute A quickly, we can pre-compute common sub-expressions:

      A₀ = (a₀ + a₂) + (a₁  + a₃)

      A₁ =  (a₀ - a₂) – j(a₁  - a₃)

      A₂ = (a₀  + a₂) - (a₁  + a₃)

      A₃ = (a₀  - a₂)  + j(a₁ - a₃)

 

Then we can diagram the 4-point like so,

Fig: Three stages in the computation of an N=8-point DFT

 

Fig: Three stages in the computation of an N=8-point DFT

 

Matrix Relations in DFT

The DFT samples defined by

 

W_N^kn  can be expanded as  NXN DFT matrix

In the matrix the elements in first row and first column all are W_N^.k.0 or W_N^.0=1. In the third row powers are multiplied by 2 and in the fourth row powers are multiplied by 3 and so on.

So,

 

Oppositely, to find inverse DFT we replace the ‘j’ with ‘-j’ in the matrix or we take complex conjugates of the matrix elements.

So,

The effective determinant of above is 1/4

 

For a 8-point FFT

The FFT is a fast algorithm for computing the DFT. If we take the 2-point DFT and 4-point DFT and generalize them to 8-point, 16-point, ..., 2^r-point, we get the FFT algorithm.

 

N=8-point radix-4   DIT-FFT

Where, -W⁴ = W⁰=1; -W⁵= W¹  = a  = (1-j)/2;  -W² = W⁶=j and -W³ = W⁷ = b  =  (1+j)/2

The above diagram is same as illustrated in section ‘Fast Fourier Transform’ under ‘Basics of Fourier Transform’

 

N=8-point radix-2   DIT-FFT

 

** W^x = W₈^x

 

6.    Applications

Fourier transform is used in circuit analysis, signal analysis, cell phones, image analysis, signal processing, and LTI systems. The Fourier transform is most probably the best tool to find the frequency in an entire field. This makes it a useful tool for LTI systems and signal processing. Partial differential equations reduce to ordinary differential equations in Fourier Transform.