Skip to content Skip to navigation

Connexions

You are here: Home » Content » Fourier Analysis in Complex Spaces

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the authors

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

This content is ...

In these lenses

  • richb's DSP

    This module is included inLens: richb's DSP resources
    By: Richard BaraniukAs a part of collection:"Signals and Systems"

    Comments:

    "My introduction to signal processing course at Rice University."

    Click the "richb's DSP" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.

Fourier Analysis in Complex Spaces

Module by: Michael Haag, Justin Romberg

Summary: This modules derives the Discrete-Time Fourier Series (DTFS), which is a fourier series type expansion for discrete-time, periodic functions. The module also takes some time to review complex sinusoids which will be used as our basis.

Introduction

By now you should be familiar with the derivation of the Fourier series for continuous-time, periodic functions. This derivation leads us to the following equations that you should be quite familiar with:

ft=∑n c n ⅇⅈ ω 0 nt f t n n c n ω 0 n t (1)
c n =1T∫nftⅇ-ⅈ ω 0 ntdt=1T<f,ⅇⅈ ω 0 nt> c n 1 T t n f t ω 0 n t 1 T f ω 0 n t (2)
where c n c n tells us the amount of frequency ω 0 n ω 0 n in ft f t .

In this module, we will derive a similar expansion for discrete-time, periodic functions. In doing so, we will derive the Discrete Time Fourier Series (DTFS), or the Discrete Fourier Transform (DFT).

Derivation of DTFS

Much like a periodic, continuous-time function can be thought of as a function on the interval 0T 0 T

Figure 1: We will just consider one interval of the periodic function throughout this section.
Subfigure 1.1: Periodic Function Subfigure 1.2: Function on the interval 0T 0 T
Subfigure 1.1 (fanal1.png)Subfigure 1.2 (fanal2.png)

A periodic, discrete-time signal (with period NN) can be thought of as a finite set of numbers. For example, say we have the following set of numbers that describe a periodic, discrete-time signal, where N=4 N 4 : …32-213… … 3 2 -2 1 3 … We can represent this signal as either a periodic signal or as just a single interval as follows:

Figure 2: Here we can look at just one period of the signal that has a vector length of four and is contained in ℂ4 4 .
Subfigure 2.1: Periodic Function Subfigure 2.2: Function on the interval 0T 0 T
Subfigure 2.1 (fanal3.png)Subfigure 2.2 (fanal4.png)

note:

The set of discrete time signals with period NN equal ℂN N .
Just like the continuous case, we are going to form a basis using harmonic sinusoids. Before we look into this, it will be worth our time to look at the discrete-time, complex sinusoids in a little more detail.

Complex Sinusoids

If you are familiar with the basic sinusoid signal and with complex exponentials then you should not have any problem understanding this section. In most texts, you will see the the discrete-time, complex sinusoid noted as: ⅇⅈωn ω n

Example 1

Figure 3: Complex sinusoid with frequency ω=0 ω 0
Figure 3 (csin1.png)

Example 2

Figure 4: Complex sinusoid with frequency ω=π4 ω 4
Figure 4 (csin2.png)

In the Complex Plane

The complex sinusoid can be directly mapped onto our complex plane, which allows us to easily visualize changes to the complex sinusoid and extract certain properties. The absolute value of our complex sinusoid has the following characteristic:

∀n,n∈ℝ:|ⅇⅈωn|=1 n n ω n 1 (3)
which tells that our complex sinusoid only takes values on the unit circle. As for the angle, the following statement holds true:
∠ⅇⅈωn=wn ∠ ω n w n (4)

As nn increases, we can picture ⅇⅈωn ω n equaling the values we get moving counterclockwise around the unit circle. See Figure 5 for an illustration:

Figure 5: These images show that as n n increases, the value of ⅇⅈωn ω n moves around the unit circle counterclockwise.
Subfigure 5.1: n=0 n 0 Subfigure 5.2: n=1 n 1 Subfigure 5.3: n=2 n 2
Subfigure 5.1 (fanalcir2.png)Subfigure 5.2 (fanalcir3.png)Subfigure 5.3 (fanalcir4.png)

note:
For ⅇⅈωn ω n to be periodic, we need ⅇⅈωN=1 ω N 1 for some NN.

Example 3

For our first example let us look at a periodic signal where ω=2π7 ω 2 7 and N=7 N 7 .

Figure 6
Subfigure 6.1: N=7 N 7 Subfigure 6.2: Here we have a plot of ℜⅇⅈ2π7n 2 7 n .
Subfigure 6.1 (fcirN1.png)Subfigure 6.2 (fplot1.png)
Example 4

Now let us look at the results of plotting a non-periodic signal where ω=1 ω 1 and N=7 N 7 .

Figure 7
Subfigure 7.1: N=7 N 7 Subfigure 7.2: Here we have a plot of ℜⅇⅈn n .
Subfigure 7.1 (fcirN2.png)Subfigure 7.2 (fplot2.png)

Aliasing

Our complex sinusoids have the following property:

ⅇⅈωn=ⅇⅈω+2πn ω n ω 2 n (5)
Given this property, if we have a sinusoid with frequency ω+2π ω 2 , then this signal "aliases" to a sinusoid with frequency ωω.
note:
Each ⅇⅈωn ω n is unique for ω∈ 02π ω 0 2

"Negative" Frequencies

If we are given a signal with frequency π<ω<2π ω 2 , then this signal will be represented on our complex plane as:

Figure 8: Plot of our complex sinusoid with a frequency greater than π.
Subfigure 8.1Subfigure 8.2
Subfigure 8.1 (fanal_neg1.png)Subfigure 8.2 (fanal_neg2.png)

From the above images, the value of our complex sinusoid on the complex plane may be more easily interpreted as cycling "backwards" (clockwise) around the unit circle with frequency 2π-ω 2 ω . Rotating counterclockwise by ww is the same as rotating clockwise by 2π-ω 2 ω .

Example 5

Let us plot our complex sinusoid, ⅇⅈωn ω n , where we have ω=5π4 ω 5 4 and n=1 n 1 .

Figure 9: The above plot of our given frequency is identical to that of one where ω=-3π4 ω 3 4 .
Figure 9 (fanal_neg3.png)

This plot is the same as a sinusoid with "negative" frequency -3π4 3 4 .

point:
It makes more physical sense to chose -ππ as the interval for ω ω.

Remember that ⅇⅈωn ω n and ⅇ-ⅈωn ω n are conjugates. This gives us the following notation and property:

ⅇⅈωn¯=ⅇ-ⅈωn ω n ω n (6)
The real parts of of both exponentials in the above equation are the same; the imaginary parts are negative of one another. This idea is the basic definition of a conjugate.

Now that we have looked over the concepts of complex sinusoids, let us turn our attention back to finding a basis for discrete-time, periodic signals. After looking at all the complex sinusoids, we must answer the question of which discrete-time sinusoids do we need to represent periodic sequences with a period NN.

Equivalent Question:

Find a set of vectors ∀n,n=0…N-1:bk=ⅇⅈ ω k n n n 0 … N 1 b k ω k n such that bk b k are a basis for ℂ n ℂ n
In answer to the above question, let us try the "harmonic" sinusoids with a fundamental frequency ω 0 =2πN ω 0 2 N :

Harmonic Sinusoid

ⅇⅈ2πNkn 2 N k n (7)

Figure 10: Examples of our Harmonic Sinusoids
Subfigure 10.1: Harmonic sinusoid with k=0 k 0 Subfigure 10.2: Imaginary part of sinusoid, ℑⅇⅈ2πN1n 2 N 1 n , with k=1 k 1 Subfigure 10.3: Imaginary part of sinusoid, ℑⅇⅈ2πN2n 2 N 2 n , with k=2 k 2
Subfigure 10.1 (hsin1.png)Subfigure 10.2 (hsin2.png)Subfigure 10.3 (hsin3.png)

ⅇⅈ2πNkn 2 N k n is periodic with period N N and has kk "cycles" between n=0 n 0 and n=N-1 n N 1 .

theorem 1

If we let ∀n,n=0…N-1: b k n=1Nⅇⅈ2πNkn n n 0 … N 1 b k n 1 N 2 N k n where the exponential term is a vector in ℂN N , then b k | k=0…N-1 k 0 … N 1 b k is an orthonormal basis for ℂN N .

Proof

First of all, we must show b k b k is orthonormal, i.e. < b k , b l >= δ k l b k b l δ k l < b k , b l >=∑n=0N-1 b k n b l n¯=1N∑n=0N-1ⅇⅈ2πNknⅇ-ⅈ2πNln b k b l n N 1 0 b k n b l n 1 N n N 1 0 2 N k n 2 N l n

< b k , b l >=1N∑n=0N-1ⅇⅈ2πNl-kn b k b l 1 N n N 1 0 2 N l k n (8)
If l=k l k , then
< b k , b l >=1N∑n=0N-1 1 =1 b k b l 1 N n N 1 0 1 1 (9)
If l≠k l k , then we must use the "partial summation formula" shown below: ∑n=0N-1αn=∑n=0∞αn-∑n=N∞αn=11-α-αN1-α=1-αN1-α n N 1 0 α n n 0 α n n N α n 1 1 α α N 1 α 1 α N 1 α < b k , b l >=1N∑n=0N-1ⅇⅈ2πNl-kn b k b l 1 N n N 1 0 2 N l k n where in the above equation we can say that α=ⅇⅈ2πNl-k α 2 N l k , and thus we can see how this is in the form needed to utilize our partial summation formula. < b k , b l >=1N1-ⅇⅈ2πNl-kN1-ⅇⅈ2πNl-k=1N1-11-ⅇⅈ2πNl-k=0 b k b l 1 N 1 2 N l k N 1 2 N l k 1 N 1 1 1 2 N l k 0 So,
< b k , b l >= 1ifk=l0ifk≠l b k b l 1 k l 0 k l (10)
Therefore: b k b k is an orthonormal set. b k b k is also a basis, since there are NN vectors which are linearly independent (orthogonality implies linear independence).

And finally, we have shown that the harmonic sinusoids 1Nⅇⅈ2πNkn 1 N 2 N k n form an orthonormal basis for ℂ n ℂ n

Discrete-Time Fourier Series (DTFS)

Using the steps shown above in the derivation and our previous understanding of Hilbert Spaces and Orthogonal Expansions, the rest of the derivation is automatic. Given a discrete-time, periodic signal (vector in ℂ n ℂ n ) fn f n , we can write:

fn=1N∑k=0N-1 c k ⅇⅈ2πNkn f n 1 N k N 1 0 c k 2 N k n (11)
c k =1N∑n=0N-1fnⅇ-ⅈ2πNkn c k 1 N n N 1 0 f n 2 N k n (12)
Note: Most people collect both the 1N 1 N terms into the expression for c k c k .

Discrete Time Fourier Series:

Here is the common form of the DTFS with the above note taken into account: fn=∑k=0N-1 c k ⅇⅈ2πNkn f n k N 1 0 c k 2 N k n c k =1N∑n=0N-1fnⅇ-ⅈ2πNkn c k 1 N n N 1 0 f n 2 N k n This what the fft command in MATLAB does.

Comments, questions, feedback, criticisms?

Send feedback