MA4705 Aircraft Navigation and

Flight Computers
3A Fourier Transforms
Introduction to DSP Series
Ed Ang
School of Mechanical and Aerospace Engineering
Nanyang Technological University
 Introduction

• The Fourier Series (FS) is useful for decomposing a signal into

different sinusoids or complex exponentials.

• FS is applicable for infinite length periodic signals.

• Real world signals are using finite in length and they may not be
periodic. We adapt FS to these sorts of signals – the result is the
Fourier Transform.
 Finite length discrete time signal
• We CANNOT directly describe a
finite length discrete signal (a)
using the Fourier Series because it
is not infinite & periodic.

• To overcome this problem,

we duplicate the signal and force it
to be periodic, repeating every N
samples (b).

Ref: Section 5.1.1 Development of the Discrete Time Fourier Transform

 Discrete Fourier Series 1
• The Fourier series coefficients (Analysis equation) can be re-
expressed as follows.

• Notice the discrete summation

rather than the continuous integral?

• This is because x[n] is a discrete

signal.
 Discrete Fourier Series 2
• We define the function below – Inverse Discrete Fourier Series
(IDFS).

• Substitute the expression into the synthesis equation.

 Discrete Time Fourier Transform (DTFT)
• As N -> ∞, the signal becomes aperiodic and becomes exactly like
the original finite length signal x[n]. Therefore, we take limits …

• As N becomes larger, w0 becomes smaller, so the discrete

summation becomes an integral.
 Discrete Fourier Series 3
•We have proven that a finite length discrete signal can be
expressed as a continuous integral of its IDFS.

•Continuous integrals are not ideal because there is an

infinite number of points in the signal that needs to
be summed.

•Revisit IDFS.
•x[n] has a period of N.

•e-jkw0n has a period of 2π. If k is an integer

between 0 and N-1 and w0 = 2π/N, then there
are N distinct values for e-jkw0n.

•Therefore, it is only necessary to sum from 0 to N-1,

rather than from -∞ to ∞.
 Discrete Fourier Series FINAL
• Since the Fourier series is also discrete, we replace e-jkw0 with index k, resulting in a part of forward
and reverse transforms.
• Note that both x[n] and X[k] are both periodic functions with period N, with k varying from -∞, …, -1, 0, 1, … ∞.
 Discrete Fourier Transform
• Note that the DFS & IDFS still apply to periodic signals only.

• Since both DFS & IDFS repeat after period N, we can obtain all of the information by
considering indices k and n from 0 … N-1. This is known as the Discrete Fourier Transform
(DFT). The transform pair is shown here.

Discrete Fourier Transform (DFT)

Continuous Time Fourier Transform (CTFT)
 Discrete Fourier Transform (DFT) Example

We take DFT of a signal x[n], getting the transform, X[k].

• We consider the case where m=k (left exponential term).

 Discrete Fourier Transform (DFT) Example

• For m ≠ k, we obtain a closed expression using the Geometric Progression summation formula.
Discrete Fourier Transform (DFT) Example
The right exponential term can be analysed in the same way, and you can then obtain a final expression
for X[k] shown here.

• The right exponential term can be analysed in

the same way, and you can then obain a final
expression for X[k] shown here.

• Note that the frequency axis as indices of k. If

its expressed as Hz, it will be in terms
of kw0, between -π and π, instead of -
N/2+1 to N/2.
 Discrete Fourier Transform (DFT) Examples
• Instead of choosing the range –N/2+1 to N/2 (or -π to π), we can
choose the range 0 to N (or 0 to 2π).

• Can you prove that the Fourier transform of a Sine wave is as

follows?
 Circle
• For a fixed length sequence, x[n], where n=0, 1, 2, …, 7.

• There is a corresponding 8-point DFT, varying from 0 to 2π, in steps of 2π/8. Since the DFT is periodic,
moving beyond 2π is akin to moving in a circle.

• The unrolled version of the circle is shown on the right.

Discrete signal frequency domain

• The DFT converts a finite length, real N-

point, discrete signal into the frequency space,
which is similarly N-point in length (Figure on
right).

• Notice that the DFT is conjugate symmetric

about π.

X[k] = X[N-k], k=0, …, N-1

Re{X[k]} = Re{X[N-k]}
Im{X[k]} = -Im{X[N-k]}
 Properties of Discrete Fourier Transform

• Linearity
• Consider 2 discrete waveforms, 2cos(3w0n), and 3sin(2w0n), consisting of 50 samples
each (N=50).
• F{h[]} refers to taking the Discrete Fourier Transform of function h.
• Individually:
• F{2cos(3w0n)} = 50[ [n - 3] + [n - 47]]
• F{3sin(2w0n)} = -75j[ [n - 2] - [n - 48]]
• When the input is x[n] = 2cos(3w0n) + 3sin(2w0n), the following is true.

F{x[n]} = 50[ [n - 3] + [n - 47]] - 75j[ [n - 2] - [n - 48]]

F{x[n] + y[n]} = F{x[n]} + F{y[n]}

 Properties of Discrete Fourier Transform

• Time shifting
• Shifting an input in time implies a phase shift in the Fourier transform.

F{x[n – m]} = e-jmw0X[k]

• To illustrate this, lets assume that the DFT is a sequence, X[k] = ak. ak is
generally a complex number that can be described in polar form.

e-jmw0X[k] = e-jmw0[|ak|ejφ] = |ak|ej(φ-mw0) , X[k]= |ak|ejφ

 Properties of Discrete Fourier Transform
• Convolution
• The Fourier transform of the convolution of 2 discrete signals is
equivalent to the product of their Fourier transforms.

• This is an extremely important property of DFT.

• Assuming that DFT is a very efficient operator. How
many multiplications are involved in convolution & simply taking the
product of the 2 sequences x[n] & y[n]?
 Properties of Discrete Fourier Transform

• Frequency shift
• A shift in the frequency domain implies a product of a sequence with a
complex exponential.
F{x[n]ejmw0} = X[k - m]

• Notice the similarity with time shifting, and the negation of the exponent?

• Time reversal
• Reversing in time has a similar effect in the frequency space.

F{x[-n]} = X[-k]
 Properties of Discrete Fourier Transform

• Differentiation
• Differentiation in frequency implies multiplication in time by 'time'.

• Parserval's relation
• Conservation of energy between the time & frequency domain.
 Conclusion

• A finite length sequence can be described by the Discrete Fourier Series (DFS) after
replicating and shifting infinite copies of it.

• The Discrete Time Fourier Transform (DTFT) can be found, as a limit (infinite period) of
the DFS.

• To avoid continuous integrals, we make use of the Discrete Fourier Transform (DFT).

• The DFT is a symmetric sequence, with a period of 2π, with N samples for an N-point
sequence.

• The DFT of the convolution of 2 sequences is the product of the DFT of individual
sequences.
MA4705 Aircraft Navigation and
Flight Computers
3B Fourier Transforms
Introduction to DSP Series
Ed Ang
School of Mechanical and Aerospace Engineering
Nanyang Technological University
The Fourier Story 1
The Fourier Story 2
DFT: Periodic in Frequency
Sampling & Aliasing

• A system processing the signal

will reconstruct the signal from
the discrete samples (top figure).

• There are many curves that

will fit these points (2 options
shown here – middle, bottom).

• Reconstruction modules
will always pick the lowest
frequency (f = 0.6 Hz).

• What happens if the original

signal actually has a higher
frequency i.e. f = 9.4 Hz?
 Generalising Aliasing

• For a Cosine waveform varying at frequency f, it has an infinite

number of aliases, defined here, where fs is the sampling
frequency and N = 0, ±1, ±2, ....

Cos(2π(f + Nfs)t)

• When fs=10 Hz, f=0.6 Hz, aliases include 9.4 Hz (N = -1), 10.6 Hz
(N = 1), 20.6 Hz (N = 2), ...
 Moral of the story ...

• When you carry out sampling, ensure that the sampling frequency
is at least 2X of the highest frequency component in the original
continuous signal.
Nyquist Frequency: fs/2 ≥ fsignal
Aliasing visualised in Frequency space
 Reality

• Often, the maximum frequency of the input system isn't known.

• Eg. A mobile device that is exposed to different types of electrical
noise – Aliasing distortion from noise is NOT acceptable.
 DFT efficiency

• Recall that we talked about convolution and FFT.

• Convolution is an expensive operation. For a signal of duration N, number

of multiplications is proportional to N2 i.e. O(N2).
• If we can replace that with the product of Fourier transform, this makes it more
efficient.
• Unfortunately, the original version of DFT also have a complexity of O(N2).
 Fast Fourier Transform (FFT)

• By removing redundant operations in DFT, the FFT algorithm is

created.
• The FFT has a complexity of O(NlogN).
 Conclusion

• The development of the DFT from Fourier Series.

• The DFT of a signal is a periodic signal over 2π.
• Aliasing occurs when the highest frequency in a signal is higher
than ½ the sampling frequency.
• In a DFT, π corresponds to the Nyquist frequency and 2π
corresponds to the sampling frequency.
• An anti-aliasing filter should be used before the sampling module to
prevent aliasing.
• The FFT is an efficient implementation of DFT, and is
very commonly used.