Preface

---

Discrete Fourier Transform

---

We noted above that Fourier Series requires the calculation of integrals, (an infinite number of them), and that is not always feasible. The Discrete Fourier Transform (DFT) addresses this problem by creating a simple and wonderfully structured matrix which can be used on basic finite signals. Suppose that you have a function f(t) on some interval, and you want to represent it with N samples at discrete time points t_n, where n = 0, 1, … , N − 1. We will refer to this vector as ∣f≫_N = {f(t_n)}_n=0^N.

The Discrete Fourier Transform actually samples the cosine and sine terms, so the vector representing cos(t) would be cos(2πn/N), where n = 0, 1, … , N −1. Note that this vector cos(2πn/N) goes through one cycle of the cosine just as cos(t) would go through one cycle on [0, 2π]. We then use these sine and cosine vectors to construct the Fourier matrix F_N, where N represents the number of points in our sampled function. By doing this carefully, we can then write the vector ∣f≫_N that we sampled from our function f(t) as a multiple of these cosine and sine vectors, or in the form

where c are the coefficients of our sampled sines and cosines. We will also set this up, so F has a simple inverse or so that we can easily find c with the formula

The obvious advantage of this approach is that we do not have to calculate integrals. We can simply use Linear Algebra. A bonus is that we can decompose the matrix F_N in a special way which will make the Linear Algebra extremely fast. This is a crucial enabling factor in the digital world in which we live.

There are several questions and problems that we must address to utilize this approach: (1) How often do we sample, or how close do the points t_n have to be so that we can accurately study the behavior of f(t) from a finite number of samples f(t_n)? (2) Do we utilize the above matrix on short portions of the function, or long portions? (3) Will the way we use this represent the real frequency content of the original function? (4) Can we calculate these expansions quick enough to be useful in applications such as real-time communication systems? These are all questions which have answers, but they are not all solvable in a simple way.

 

References

 

Return to Mathematica page
Return to the main page (APMA0340)
Return to the Part 1 Matrix Algebra
Return to the Part 2 Linear Systems of Ordinary Differential Equations
Return to the Part 3 Non-linear Systems of Ordinary Differential Equations
Return to the Part 4 Numerical Methods
Return to the Part 5 Fourier Series
Return to the Part 6 Partial Differential Equations
Return to the Part 7 Special Functions