The Fourier Transform has been employed from the beginning of this text, however it is commonly used in the continuous “analog” domain.  When we are dealing with discrete data however, some of the details are different.  We will start with the basic definitions of what is known as the Discrete Fourier Transform (DFT), establishing some of its basic properties.  Moving on we will do a couple application of the DFT, such as the filtering of data and the analysis of data.  Another important part of will be the computation of the DFT using what is known as the Fast Fourier Transform (FFT).

Section A) DFT Basics

The DFT is actually a process of approximating a function by a weighted sum of basis functions.  The basis function that has proven to be the most effective, not just in the discrete domain but in all forms, is the complex exponential.  If we are analyzing a signal that is N points long, this basis function looks like

[latex]b_k (n) = e^{j \frac{2 \pi}{N} k n }[/latex]

An implied assumption that is

We can then approximate a function x(n) as

[latex]\hat x(n) = \sum_{k=0}^ {N-1} X(k) b_k(n)[/latex]

or

[latex]\hat x(n) = \sum_{k=0}^{N-1} X(k) e^{j \frac{2 \pi}{N} k n}[/latex]

To solve for the term X(k), which represents the weighting of each function b_k(n) we will work to minimize the Lease Squared Error.  The first step is to write the error expression as

[latex]\epsilon = \sum_{n=0}^{N-1} | x(n) - \hat x(n) |^2[/latex]

assuming x(n) could be complex we would have

[latex]\epsilon = \sum_{n=0}^{N-1} ( x(n) - \hat x(n) ) (x(n) - \hat x(n) )^*[/latex]

Substituting in the definition of [latex]\hat x(n)[/latex] we have

[latex]\epsilon = \sum_{n=0}^{N-1} ( x(n) - \sum_{k=0}^{N-1} X(k) e^{j \frac{2 \pi}{N} k n} ) (x^*(n) - \sum_{m=0}^{N-1} X^*(m) e^{-j \frac{2 \pi}{N} m n} )[/latex]

Completing the product of the two equations under the sum and then distributing the sum we have

[latex]\epsilon = \sum_{n=0}^{N-1} | x(n) |^2 - \sum_{k=0}^{N-1} X(k) \sum_{n=0}^{N-1} x^*(n) e^{-j \frac{2 \pi}{N} k n} - \sum_{m=0}^{N-1} X^*(m) \sum_{n=0}^{N-1} x(n) e^{j \frac{2 \pi}{N} m n}  + \sum_{k=0}^{N-1} X(k) \sum_{m=0}^{N-1} X^*(m) \sum_{n=0}^{N-1} e^{j \frac{2 \pi}{N} (k-m) n} )[/latex]

Now this is rather long and tedious, but if we look at the last sum, it can be shown to be a geometric series which has a solution of

[latex]\sum_{n=0}^{N-1} e^{j \frac{2 \pi}{N} (k-m) n}  = \frac{1-e^{j(k-m) \frac{2 \pi}{N} N}}  {1-e^{j(k-m) \frac{2 \pi}{N}}}[/latex]

[latex]\sum_{n=0}^{N-1} e^{j \frac{2 \pi}{N} (k-m) n}  = \frac{1-e^{j{2 \pi} (k-m)}}  {1-e^{j \frac{2 \pi}{N}(k-m) }}[/latex]

[latex]\sum_{n=0}^{N-1} e^{j \frac{2 \pi}{N} (k-m) n}  = \frac{1-(1^{ (k-m)})}  {1-e^{j \frac{2 \pi}{N}(k-m) }}[/latex]

if k = m

[latex]\sum_{n=0}^{N-1} e^{j \frac{2 \pi}{N} 0 n}  =\sum_{n=0}^{N-1} 1 = N [/latex]

Otherwise we have

[latex]\sum_{n=0}^{N-1} e^{j \frac{2 \pi}{N} (k-m) n}  = \frac{1-1}  {1-e^{j \frac{2 \pi}{N}(k-m) }} = \frac{0}  {1-e^{j \frac{2 \pi}{N}(k-m) }} = 0[/latex]

This is commonly called the orthogonality property.  Thus the two sums at the end of the previous equation collapse to one, since the sum under them is zero, except when k = m. 

[latex]\epsilon = \sum_{n=0}^{N-1} | x(n) |^2 - \sum_{k=0}^{N-1} X(k) \sum_{n=0}^{N-1} x^*(n) e^{-j \frac{2 \pi}{N} k n} - \sum_{m=0}^{N-1} X^*(m) \sum_{n=0}^{N-1} x(n) e^{j \frac{2 \pi}{N} m n}  + \sum_{k=0}^{N-1} X(k) X^*(k) N [/latex]

We now take the partial derivative of the error [latex]\epsilon[/latex] with respect to one of the weights X(k).

[latex]\frac{\partial{ \epsilon }}{\partial{X(L)} } = 0 - \sum_{n=0}^{N-1} x(n) e^{-j\frac{2 \pi}{N}L n} - \sum_{n=0}^{N-1} x^*(n) e^{j\frac{2 \pi}{N}L n} + N X^*(L) + N X(L)  = 0[/latex]

Note that the first sum is not a function of X(L) so is zero, and the next to sums disappear except for the case of the sum index equal to L.  The last sum is only true when k = L and is then separated into its two parts.  It is sufficient to recognize that the sum

[latex]X(L) = \frac{1}{N} \sum_{n=0}^{N-1} x(n) e^{-j \frac{2 \pi}{N} L n}[/latex]

is a solution to partial derivative equation above.

Returning to the original definition we have an approximation of x(m) as

[latex]\hat x(m) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{j \frac{2 \pi}{N}k m}[/latex]

Substituting in the solution to our derivation above we have

[latex]\hat x(m) = \frac{1}{N} \sum_{k=0}^{N-1} \sum_{n=0}^{N-1} x(n) e^{-j \frac{2 \pi}{N} m n} e^{j \frac{2 \pi}{N} m k}[/latex]

Reordering the finite sums, we have

[latex]\hat x(m) = \frac{1}{N} \sum_{n=0}^{N-1} x(n) \sum_{k=0}^{N-1} e^{-j \frac{2 \pi}{N} k (m-n)} [/latex]

Note that the sum on the right hand side of the previous equation is the orthogonality property and is equal to N if and only if m = n.  Thus

[latex]\hat x(m) = \frac{1}{N} x(m) N = x(m) [/latex]

This leads us to the final point, in that we have a DFT pair of

[latex]X(m) = \sum_{k=0}^{N-1} x(k) e^{-j \frac{2 \pi}{N} m k}[/latex]

[latex]x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{j \frac{2 \pi}{N}k n}[/latex]

The [latex]\frac{1}{N}[/latex] is moved to the inverse strictly by convention.  And we need to be aware that the transform from x to X, uses the conjugate of the basis function ( [latex]e^{-j \frac{2 \pi}{N} m k}[/latex] ) and the inverse transform uses the basis function ( [latex]e^{j \frac{2 \pi}{N} m k}[/latex] ) .

Section A.1) Hidden Assumptions in the DFT.

One of the most important “hidden” assumptions about the DFT is that it assumes the sequence that we are analyzing is periodic with a period of N.  The term N is the number of points we have been given in the sequence.  This periodicity can be validated by

[latex]x(n+N) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{j \frac{2 \pi}{N}k (n+N)}[/latex]

Factoring the term [latex]e^{j \frac{2 \pi}{N} k (n+N) }[/latex] into [latex]e^{j \frac{2 \pi}{N} k n} e^{j \frac{2 \pi}{N} N }[/latex] and noting that the N’s cancel in the second term we have [latex]e^{j \frac{2 \pi}{N} k n} e^{j 2 \pi }[/latex] and [latex]e^{j 2 \pi } = 1[/latex] thus

[latex]x(n+N) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{j \frac{2 \pi}{N}k n} = x(n)[/latex]

This property / assumption will affect many of the algorithms we will use the DFT for, so please keep it in mind.

Section B) Properties of the DFT.

Again we start with the DFT pair.

[latex]X(m) = \sum_{k=0}^{N-1} x(k) e^{-j \frac{2 \pi}{N} m k}  = DFT"{" x(n) "}"[/latex]

[latex]x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{j \frac{2 \pi}{N}k n} = IDFT"{" X(k) "}"[/latex]

Then we will start with some basic properties of the DFT

1) Linearity

DFT{ a x(n) + b y(n) } = a DFT{ x(n) } + b DFT{ y(n) }

2) Time and phase shifts

DFT{ x(n – i) }  => X(k) [latex]e^{-j \frac{2 \pi}{N} k i }[/latex]

3) The DFT of a signal is Hermitian or has a Complex Conjugate Symmetry about its mid-point.

This is similar to the property of continuous Fourier Transforms (FT) where real of the FT is even and the imaginary part is odd.  ( real( X(f) ) = real( X(-f) ) and imaginary( X(f) ) = – imaginary( X(-f) ) )

For the DFT, let x(n), 0 < n < N be a real sequence, then

X^*(k) = X(N-k)  for  0 < k < N

Proof:

[latex]X(N-k) = \sum_{n=0}^{N-1} x(n) e^{-j \frac{2 \pi}{N} n (N-k) }[/latex]

Again we factor out the N and have

[latex]X(N-k) = \sum_{n=0}^{N-1} x(n) e^{j \frac{2 \pi}{N} n k } e^{-j \frac{2 \pi}{N} N n  }[/latex]

Since [latex]e^{-j \frac{2 \pi}{N} N n  } = e^{-j {2 \pi} n  } = 1^n[/latex], we have

[latex]X(N-k) = \sum_{n=0}^{N-1} x(n) e^{j \frac{2 \pi}{N} n k }  = X^*(k)[/latex]

Do note that the sign changed on the [latex]e^{j \frac{2 \pi}{N} n k }[/latex] due to the -k in X(N-k).

The next figure is intended to show the relationship in a graphical fashion.

Figure 6-1. Hermitian Symmetry Displayed.

4) If x(n) is real valued ( like most of the signals we deal with ) then X(0) is real valued

[latex]X(0) = \sum_{k=0}^{N-1} x(k) e^{-j \frac{2 \pi}{N} 0 k}  = \sum_{k=0}^{N-1} x(k) 1 = \sum_{k=0}^{N-1} x(k)[/latex]  which is thus real valued.

Also if N is even,

[latex]X(\frac{N}{2}) = \sum_{k=0}^{N-1} x(k) e^{-j \frac{2 \pi}{N} \frac{N}{2} k}  = \sum_{k=0}^{N-1} x(k) e^{-j  \pi  k}  = \sum_{k=0}^{N-1} x(k) (-1)^k[/latex]

which is again real valued.

5) X(k) is periodic as well

[latex]X(k) = X(N+k)[/latex]

This can be proven by writing out the definition

[latex]X(N+k) = \sum_{n=0}^{N-1} x(n) e^{-j \frac{2 \pi}{N} (N+k) n}[/latex]

Factoring out the N in the exponent, we have

[latex]X(N+k) = \sum_{n=0}^{N-1} x(n) e^{-j \frac{2 \pi}{N} k n} e^{-j \frac{2 \pi}{N} N n}[/latex]

Cancelling out the N, in the second exponent and we have

[latex]X(N+k) = \sum_{n=0}^{N-1} x(n) e^{-j \frac{2 \pi}{N} k n} e^{-j 2 \pi n}[/latex]

Then noting that [latex]e^{-j 2 \pi n} = 1^n = 1[/latex] we have

[latex]X(N+k) = \sum_{n=0}^{N-1} x(n) e^{-j \frac{2 \pi}{N} k n} = X(k) [/latex]

The properties listed here are just a small subset of the various properties that can be developed for the DFT.  However these are the ones that commonly come up when applying the DFT to filtering or data analysis.

The next section deals with using the DFT to filter data and the things to watch for.

Section C. DFT Applications.

As with the FT for continuous signals, the DFT can be used to filter and analyze discrete signals, however many of the properties of the DFT need to be kept in mind when applying the DFT.  The first property we will address the is the implied periodicity of the DFT.  Another property that will have to be considered is the symmetry of DFT, which will heavily affect the filters applied.  Finally we will look at how the DFT can be used to measure the underlying frequency in a signal.

Section C.1 DFT filtering

As with the continuous FT, a filter can be characterized by the relationship

[latex]Y( \omega ) = X( \omega )  H( \omega )[/latex]

where [latex]X( \omega )[/latex] is the FT of the input, and [latex]H( \omega )[/latex] is the frequency response of the filter.

Similarly the discrete version is

[latex]Y( k ) = X ( k )  H(k)[/latex]

where [latex]X( k )[/latex] is the DFT of the input, and [latex]H(k )[/latex] is the transfer function of the filter evaluated at

As was stated previously, when using the DFT to filter a signal, the periodicity and symmetry of the DFT must be kept in mind.