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

Periodic Function Function on the interval 0 T We will just consider one interval of the periodic function throughout this section. A periodic, discrete-time signal (with period N) 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 : … 3 2 -2 1 3 … We can represent this signal as either a periodic signal or as just a single interval as follows:

Periodic Function Function on the interval 0 T Here we can look at just one period of the signal that has a vector length of four and is contained in 4 . The set of discrete time signals with period N equal 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

Complex sinusoid with frequency ω 0

Complex sinusoid with frequency ω 4

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 which tells that our complex sinusoid only takes values on the unit circle. As for the angle, the following statement holds true: ∠ ω n w n As n increases, we can picture ω n equaling the values we get moving counterclockwise around the unit circle. See for an illustration:

n 0 n 1 n 2 These images show that as n increases, the value of ω n moves around the unit circle counterclockwise. For ω n to be periodic, we need ω N 1 for some N. For our first example let us look at a periodic signal where ω 2 7 and N 7 .

N 7 Here we have a plot of 2 7 n . Now let us look at the results of plotting a non-periodic signal where ω 1 and N 7 .

N 7 Here we have a plot of n .

Aliasing Our complex sinusoids have the following property: ω n ω 2 n Given this property, if we have a sinusoid with frequency ω 2 , then this signal "aliases" to a sinusoid with frequency ω. Each ω n is unique for ω 0 2

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

Plot of our complex sinusoid with a frequency greater than . 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 ω . Rotating counterclockwise by w is the same as rotating clockwise by 2 ω . Let us plot our complex sinusoid, ω n , where we have ω 5 4 and n 1 .

The above plot of our given frequency is identical to that of one where ω 3 4 . This plot is the same as a sinusoid with "negative" frequency 3 4 . It makes more physical sense to chose as the interval for ω . Remember that ω n and ω n are conjugates. This gives us the following notation and property: ω n ω n 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 N. Find a set of vectors n n 0 … N 1 b k ω k n such that b k are a basis for ℂ n In answer to the above question, let us try the "harmonic" sinusoids with a fundamental frequency ω 0 2 N : Harmonic Sinusoid 2 N k n

Harmonic sinusoid with k 0 Imaginary part of sinusoid, 2 N 1 n , with k 1 Imaginary part of sinusoid, 2 N 2 n , with k 2 Examples of our Harmonic Sinusoids 2 N k n is periodic with period N and has k "cycles" between n 0 and n N 1 . If we let n n 0 … N 1 b k n 1 N 2 N k n where the exponential term is a vector in N , then k 0 … N 1 b k is an orthonormal basis for N . First of all, we must show b k is orthonormal, i.e. b k b l δ k l 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 1 N n N 1 0 2 N l k n If l k , then b k b l 1 N n N 1 0 1 1 If l k , then we must use the "partial summation formula" shown below: n N 1 0 α n n 0 α n n N α n 1 1 α α N 1 α 1 α N 1 α 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 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 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 1 k l 0 k l Therefore: b k is an orthonormal set. b k is also a basis, since there are N vectors which are linearly independent (orthogonality implies linear independence). And finally, we have shown that the harmonic sinusoids 1 N 2 N k n form an orthonormal basis for ℂ 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 ) f n , we can write: f n 1 N k N 1 0 c k 2 N k n c k 1 N n N 1 0 f n 2 N k n Note: Most people collect both the 1 N terms into the expression for c k . Here is the common form of the DTFS with the above note taken into account: f n k N 1 0 c k 2 N k n c k 1 N n N 1 0 f n 2 N k n This what the fft command in MATLAB does.