Skip to content Skip to navigation

Connexions

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

Navigation

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.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • OrangeGrove display tagshide tags

    This module is included inLens: Florida Orange Grove Textbooks
    By: Florida Orange GroveAs a part of collection:"Signals and Systems"

    Click the "OrangeGrove" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • SHN CNX Workshop display tagshide tags

    This module is included inLens: Stategic Horizon Network Workshop on Alternative Couseware -- Connexions Session
    By: Connexions

    Comments:

    "This module shows the use of sections and subsections to divide content logically, and shows extensive use of math, equations, and proofs. It also uses callout notes."

    Click the "SHN CNX Workshop" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

  • richb's DSP display tagshide tags

    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.

    Click the tag icon tag icon to display tags associated with this content.

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. E-mail the authors

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

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.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

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.
(a) Periodic Function (b) Function on the interval 0T 0 T
Figure 1(a) (fanal1.png)Figure 1(b) (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 .
(a) Periodic Function (b) Function on the interval 0T 0 T
Figure 2(a) (fanal3.png)Figure 2(b) (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.
(a) n=0 n 0 (b) n=1 n 1 (c) n=2 n 2
Figure 5(a) (fanalcir2.png)Figure 5(b) (fanalcir3.png)Figure 5(c) (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
(a) N=7 N 7 (b) Here we have a plot of ℜⅇⅈ2π7n 2 7 n .
Figure 6(a) (fcirN1.png)Figure 6(b) (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
(a) N=7 N 7 (b) Here we have a plot of ℜⅇⅈn n .
Figure 7(a) (fcirN2.png)Figure 7(b) (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 π.
(a) (b)
Figure 8(a) (fanal_neg1.png)Figure 8(b) (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
(a) Harmonic sinusoid with k=0 k 0 (b) Imaginary part of sinusoid, ℑⅇⅈ2πN1n 2 N 1 n , with k=1 k 1 (c) Imaginary part of sinusoid, ℑⅇⅈ2πN2n 2 N 2 n , with k=2 k 2
Figure 10(a) (hsin1.png)Figure 10(b) (hsin2.png)Figure 10(c) (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.

Content actions

Give Feedback:

E-mail the module authors | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

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 (?)

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.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks