Summer 2015-16

Course Information and Outline

**See canvas for course announcements, lecture notes, assignments and discussions. This page only includes the course syllabus.**

**Lectures**: MW 10:30 - 12:20; Skilling Auditorium

**Course web site**: Through Canvas. If you are registered on AXESS you are automatically registered on the course website as well. The course material (problem sets, etc.) will be posted on Canvas. Students are welcome to initiate and participate in discussions on Canvas.

**This is an SCPD course and the lectures will be taped for online viewing this quarter.**

**Instructor**:

Aditya Siripuram

: staditya@stanford.edu

: Packard 268

: Monday, Tuesday, Thursday 3-4pm

**Course Assistant**:

Leighton Pate Barnes

: lpb@stanford.edu

: Packard 268

: TBD

**Administrative Assistant**:

Marie Hamel

email: mhamel@stanford.edu

Office: Packard 217

Phone: 721-1060

The Fourier transform has it all. As a tool for applications it is used in virtually every area of engineering and science. In chemistry and molecular biology it is used to understand the crystal structures of molecules. In electrical engineering, methods based on the Fourier transform are used in all varieties of signal processing, from communications and circuit design to the analysis of imaging systems. In mathematics, Fourier series and the Fourier transform are cornerstones of the broad area known as harmonic analysis, and applications range from number theory to the modern formulation of the theory of partial differential equations. Lurking not so far beneath the surface are deep connections to groups and symmetry. Particularly widely used in practical applications is the discrete Fourier transform computed via the FFT (Fast Fourier Transform) algorithms – it is not an exaggeration to say that much of the digital world depends on the FFT.

Historically, Fourier analysis developed from employing sines and cosines to model periodic physical phenomena. This is the subject matter of Fourier series, and here we learn that a complicated signal can be written as a sum of these much simpler sinusoidal components. Borrowing from musical terminology, where pure tones are single sinusoids and the frequency is the pitch, the component sinusoids are often called the harmonics. Complicated tones are sums of harmonics where the frequencies that occur are integer multiples of the frequency of the lowest harmonic. In this way, with a periodic signal we associate a discrete set of frequencies – its spectrum – along with the amount that each harmonic contributes to the total signal. If we know the spectrum and the amounts that each harmonic contributes then we know the signal, and vice versa; we analyze the signal into its component parts and we synthesize the signal from its component parts.

The Fourier transform arose in turn as a way of analyzing and synthesizing nonperiodic signals. The spectrum becomes a continuum rather than a discrete set of numbers. Through the Fourier transform, and its inverse, we now understand that *every signal has a spectrum, and that the spectrum determines the signal*. This maxim surely ranks as one of the major secrets of the universe. A signal (often a time varying function, thus a representation in the “time domain") and its Fourier transform (a function depending on the spectrum, thus a representation in the “frequency domain") are equivalent in that one determines the other and one can pass back and forth between the two. The signal appears in different guises in the time domain and in the frequency domain, and this enhances the usefulness of both representations.

“Two representations for the same quantity” will be a steady refrain in our work. In signal processing, “filtering in the frequency domain” is an example of this, where operations are carried out in the frequency domain to produce a signal in the time domain having desired properties. Further important examples of the use of the dual representations are the sampling theorem, which is fundamental in passing from an analog to a digital signal, and the Wiener-Khinchine theorem on the spectral power density. In optics, examples are diffraction and interference phenomena, in physics an example is the Heisenberg Uncertainty Principle. In mathematics, celebrated identities in number theory come from Rayleigh’s identity, which, in physics, says that the energy of a signal can be computed in either the time domain or the frequency domain representation.

Underlying much of this development and wide applicability is the notion of *linearity*. The operations of *analyzing* a signal *into* its component parts (taking the Fourier transform) and *synthesizing* a signal *from* its component parts (taking the inverse Fourier transform) are *linear operations*, namely integration. The principle of superposition applies to many systems – the sum of inputs produces a sum of outputs – and one can thus work with a complicated signal by working with linear combinations, sums or integrals, of simpler signals. This is fundamental to all signal processing. Furthermore, the ideas extend to signals that depend on a spatial variable, e.g., images, so the ideas generalize to two dimensions and higher.

The desire to extend the applicability of Fourier series and the Fourier transform led not only to an increasing array of real-world applications but also to purely mathematical questions. Investigations on many fronts led to a better understanding of approximation and of limiting processes, the nature of integration, linear systems, eigenfunctions, and orthogonality. In extending the range of the mathematical methods it became necessary to move beyond classical ideas about functions and to develop the theory and practice of distributions, also known as generalized functions. The need for such objects was recognized earlier by engineers for very practical applications, and by physicists for computations in quantum mechanics.

We’ll see some of all of this, but with such a panorama we have to be selective. The goals for the course are to gain a facility with *using* the Fourier transform, both specific techniques and general principles, and learning to recognize when, why, and how it is used. Together with a great variety the subject also has a great coherence, and my hope is that you will appreciate both.

A course reader is available at the Stanford Bookstore and will also be posted on the course website.

Here are the main topics for the course, listed more or less chronologically. Though I’ve separated them out to make a list, many will be mixed together and will come up in several contexts.

Periodicity and Fourier series in one-dimension

Orthogonality

Applications to partial differential equations

Definition and basic examples of Fourier transforms

Classical transforms of common signals

Shifts, scaling, modulation, differentiation

Fourier inversion and duality

Convolution

Applications to filtering, differential equations, probability

Distributions (generalized functions)

Delta functions, generalized Fourier transforms, the

*I**I**I*distributionApplications to diffraction

Sampling and the Nyquist theorem

Aliasing

Linear systems

Eigenfunctions, eigenvalues, impulse response, transfer functions

The discrete Fourier transform and the FFT algorithm

Discrete convolution and digital filters

The two-dimensional Fourier transform

Two dimensional harmonics and Fourier series

Examples and properties of two-dimensional transforms, circularly symmetric transforms

Lattices and 2D sampling

Crystallography

Line impulses, the Radon transform, the projection slice theorem

Medical imaging

The majority of the students in 261 are EEs but not everyone is, and collectively you all bring a variety of backgrounds and interests. Students new to the subject are introduced to a set of tools and ideas that are used by engineers and scientists in an astonishing assortment of areas. Students who have seen bits and pieces of Fourier techniques in other courses benefit from a course that puts it all together – I frequently hear this from people who have taken the class. It bears repeating that the subject has an intellectual coherence that is especially attractive. Students also benefit by seeing a greater variety of applications at a deeper level. Keep in mind the different backgrounds and interests of your fellow students, and keep an open mind to the variety of the material.

There will be weekly problem sets and a final exam. The problem sets will be assigned on Wednesdays and due the following Wednesday. Most problem sets will include a problem using Matlab.

Grades for the course will be based on:

Problem sets: 50%

Final: 50%

The final exam is scheduled by the Registrar’s office for

**Saturday, August 13 from 8:30 - 11:30 AM**.

Students who may need an academic accommodation based on the impact of a disability must initiate the request with the Office of Accessible Education (OAE). Professional staff will evaluate the request with required documentation, recommend reasonable accommodations, and prepare an Accommodation Letter for faculty dated in the current quarter in which the request is made. Students should contact the OAE as soon as possible since timely notice is needed to coordinate accommodations. The OAE is located at 563 Salvatierra Walk; Phone: 723-1066, URL http://studentaffairs.stanford.edu/oae

Be sure you are familiar with Stanford’s Honor Code and Fundamental Standard. You can find the statements via the Registrar’s web page, or directly at

https://communitystandards.stanford.edu/student-conduct-process/honor-code-and-fundamental-standard