Home :: Articles :: Fourier Primer

Abstract Why does the Fourier transform show us the frequency components of a signal? The fundamentals lie in a more basic construct called the Fourier series. Traditionally used for periodic functions, they can be extended into arbitrary domains to give us an honest representation of any (“nice” enough) function. Theorems in linear algebra tell us why that can be done. A few definitions later, and the Fourier transform is born. This article does not attempt to explain discrete Fourier methods (such as the discrete and discrete-time Fourier transforms), because to maintain the rigor of this article I would need to provide a thorough introduction to signal processing. This topic has been overdone anyway. Instead, the article takes a more intuitive, mathematical approach, which may not appear in your favorite book on digital signal processing. This article grew out of a series of shorter articles on the Fourier series and transform I wrote while in high school. Those, in turn, can be attributed to articles in Mathworld, Wikipedia, and chapters in Lay’s Linear Algebra, Karniadakis et al.’s Parallel Scientific Computing in C++ and MPI, as well as other similar publications. They were originally written for myself, but eventually became something I could share with my microelectronics classmates. Over the summer between high school and college, I compiled them into this article, hoping that it would help others, particularly in engineering, use and, most importantly, understand the mechanics of all things Fourier. It should be accessible to a first-year calculus student, although parts rely on techniques of linear algebra.

This article is also available as a pdf.

Contents

1 Fourier Series

1.1 Fourier Series on a Specific Domain

1.1.1 Definition

If we have an integrable¹ function f(θ) that is defined² everywhere on θ [-π, π], then it can be expressed³ as

(1)

over this domain, where the coefficients a_n and b_n are

(2)

(3)

1.1.2 Verification

To see why the definition is true, let’s substitute (1) into (2) and evaluate the right side to see if we come up with a_n:

(4)

To “do” the tough trigonometric integral (4), it’s easier to first investigate the properties of the simpler family of integrals

(5)

where k and n are integers (k, n Z). In particular, we need to convince ourselves that both vanish to zero if k≠n or if k or n are zero⁴, and are equal to π if k = n, i.e. that

(6)

where δ_k,n is the Kronecker delta. We will do the first definite integral in (5) under these conditions here, and leave the second to the reader as an exercise.

First, if k is zero, then the integrand is an even sinusoidal periodic (cosine) function with period 2π/n, which is being integrated over the domain θ [-π, π]. This domain contains exactly = n periods of the cosine function. As such, the area over n periods is always zero. A similar situation holds for n = 0. Figure 1 shows plots of representative such cosine functions.

---

---

The general anti derivative

this means that

Whether or not k = n, the second term is automatically zero, because the argument to the sine function is an integer multiple of π. If k≠n, then the first term also vanishes for the same reason. But if k = n, then we have a indeterminate form, which we will correct by using the rule of my good friend G. de l’Hôpital⁵:

Returning to (4), we expand and distribute to get the integral

(7)

In the case n = 0, (7) becomes

In the case n ≥1, (7) becomes

The first term in the sum we have already computed in (6). Thus, ∫ _-π^πa_kcos(kθ) cos(nθ)dθ = a_kπ for k = n, and zero otherwise. Convince yourself that the second term in the sum ∫ _-π^πb_ksin(kθ) cos(nθ) = 0 for all k, n Z. This leaves us with

By similar labor, we can substitute (1) into (3) to complete our verification of the Fourier series. ■

1.1.3 Derivation

Here we employ concepts from linear algebra to derive a formula for the Fourier series. By computing (6), we showed that for , the subset

of sinusoids in C[-π, π] (the vector space of all continuous functions on the domain θ [-π, π]) is orthogonal with respect to the inner product

that is, every member of S is orthogonal to every other member, except itself. We can therefore enforce an orthogonal coordinate system on a subset W = Span of C[-π, π] using S as a spanning set. All that remains is to find the corresponding weights on each basis function such that a generic function f(θ) C[-π, π] is approximated as closely as possible in W-space. This will give us an arbitrary approximation to f(θ) using elements of S. Then, to extend this to an exact representation of f(θ), we need to increase the dimensionality of W to ∞ (by letting n →∞), showing that the approximation error →0. This is equivalent to the statement W →C[-π, π] as n →∞.

First, we will find the weights for a finite n. Since S is orthogonal, the best approximation to f(θ) using S as the spanning set is the orthogonal projection of f(θ) onto W. The standard formula for orthogonal projections shows that the coefficients for k ≥1

By “doing” the inner products, we get the familiar results

which are equivalent to (2) and (3). The coefficient of the element 1 of S is

Thus, the nth approximation f_n(θ) to f(θ) is

The error Δ_n of this approximation can be quantified in Euclidean-like terms as the norm of the difference between the approximation f_n(θ) and f(θ):

The square of this error (Δ_n²) is termed the mean-square error. The direct computation of this Lebesgue integral is difficult without employing some high-power theorems. You now have my permission to choose one of a couple options:

1. Chant whatever magic you like, so long as you conclude that lim _n→∞Δ_n² = 0. Actually “doing” this limit is, of course, left as an exercise to the reader.
2. Change the little n at the top of the little ∑ sign in the partial sum equation (8) to ∞ and don’t tell anyone that you cheated.
3. Employ your “get out of proof free” card⁶.

By convincing ourselves that the limit of the mean-square error as n →∞ is zero, we conclude that the set S is a complete orthogonal system over the domain θ [-π, π], spanning the complete inner product space W. This has important ramifications in the study of Hilbert spaces, but for us it means that almost all functions f(θ) can be approximated exactly over our domain by an infinite Fourier series. Thus, we establish the relations (1), (2), and (3). ■

1.1.4 Example

Now that we’ve gained insight into the truth of the Fourier series, an example is in order. Let’s find the Fourier series representation of the periodic sawtooth function seen in Figure 2.

---

---

The function is periodic with period 2π, defined everywhere on θ [-π, π], of bounded variation – the whole nine yards. It is a simple one with which to start, because it does not require a change of variables to extend the domain over which the function is periodic. In the domain θ [-π, π], the function f(θ) = θ. Beyond that, the function is periodic. Let’s compute the Fourier coefficients a_n and b_n using (2) and (3):

Since n is an integer, the expression for b_n can be simplified to b_n = . Note that we do not have to worry about the case n = 0, because the only Fourier coefficient that requires n = 0 is a₀ according to (1), and we have already shown that a_n = 0 for all n. Now let’s substitute our expressions for the Fourier coefficients into (1) to get the Fourier series for f(θ).

(9)

Note that (9) consists only of sines, and that both f(θ) and sin(θ) are odd functions. This is not a coincidence, but rather a direct consequence of a Fourier expansion. Now let’s get an intuitive look at the convergence of (9) by truncating the series at 2, 5, and 10 terms (Figure 3).

---

---

It appears that as the number of terms →∞, the Fourier series approaches the periodic function. Note how we only used the value of the function f(θ) = θ on the interval θ [-π, π], and the series became periodic on the entire domain θ [-∞, ∞]. This means that we only need information about one period of the function we are approximating to write the Fourier series for it. What happens when we have information about only half of a period? Easy. Make up the rest. Set it all to zero, or do what is called an “even” or “odd” extension by reflecting the function through the y-axis or the origin. Granted, the information you didn’t have doesn’t magically appear, but the part of the period you did have is faithfully reproduced in every period of the approximation. Try doing that with a Taylor series!

1.2 Fourier Series on a General Domain

1.2.1 Definition

In Section 1.1.4 , we found the Fourier series representation of a nice sawtooth function with a convenient period of 2π and defined over the specific domain θ [-π, π]. But with a simple change of variables, we can extend (1), (2), and (3) to a generic function f(t) defined on the domain t [t₀ -T, t₀ + T], where the new period is 2T, and the new center point is t₀. This allows us to glean a Fourier series for an arbitrary-period function that was shifted laterally in any fashion. Let t = t₀ + θ. Then dt = dθ. With this substitution, the definitions become

1.2.2 Example

With the extended definition, let’s express the general square wave with period 2T depicted in Figure 4 as a Fourier series.

---

---

Though we can set t₀ = 0, evaluating (11) and (12) on the domain t [-T, T], we’ll make our calculations more instructive by using the information on t [0, 2T], thereby setting t₀ = T. Since f(t) is odd, the even (cosine) coefficients are zero⁷, meaning a_n = 0. Here we define the single period of f(t) piecewise as

where A is the amplitude. Substituting the relevant information into (12) to calculate b_n, we get

Therefore,

---

---

Figure 5 shows how this series converges to the square wave. For a square wave with period 2π (that is, T = π) and amplitude π/4, the expansion for f(t) takes on a pattern that makes it easier to see that odd harmonics add to make a square wave:

2 Fourier Transform

2.1 Definition

A wonderful and accessible tutorial on the Fourier transform is available through Mathworld’s “Fourier Transform” page. Subscribing to Mathworld’s notation, we will define the forward (13) and inverse (14) Fourier transforms on the function f(x) as

where j is the imaginary unit⁸. By virtue of this symmetric definition,

(15)

The property (15) is very important, because it allows us to analyze the same function in two equivalent forms.

By performing the forward Fourier transform on a signal as a function of time, we can view the signal as a function of frequency. Hence, we transform into the frequency domain. This point of view allows for recognition of its spectral structure – harmonics, noise components, beats – and results in frequency power data that can naturally be split into frequency channels.

By performing the inverse Fourier transform on the frequency data, we can transform back into the time domain.

2.2 Example and Discussion

To get a feel for the Fourier transform, let’s find _x, since (13) is easily computed for this function. Using ∫ _-∞^∞e^-x2 dx = , you should see that _x= F(k) = e^-k2π2 . Then, by substituting F(k) back into (14), we get _k^-1[F(k)] = e^-x2 , showing (but not proving) that, in fact, ^-1[[f(x)]] = f(x). □

But what if we wanted to take the Fourier transform of a function like f(x) = cos(2πk₀x)? It appears that (13) does not converge. In particular, ∫ _-∞^∞e^-2πjkxdx does not appear to converge.

To solve this problem, we have to use a little complex arithmetic and the Dirac delta function δ(x), which turns out to be

in such a way, that

(16)

It is easier to think of δ(x) as a limit of a sequence of vanishingly thin, normalized Gaussian functions, rather than a true function. However, it can also be thought of as a limit of a sequence of vanishingly thin, scaled “sinc” functions, or any such sequence termed a “delta sequence,” so long as the normalization condition (16) holds (Figure 6).

---

---

By convention, a Dirac delta function is drawn as a vertical arrow (Figure 7) emanating from the origin and ending at 1 (representing its area), even though at zero, the value of the delta function is ∞. This way, when the Dirac function is multiplied by a constant, this constant can be easily inferred from the point at which the arrow representing the function ends.

---

---

A vital property of the Dirac delta function is

(17)

In this sense, the Dirac delta function is known as an impulse, or sampling function, because it defines the mathematical notion of sampling a function g(x) at x₀ in terms of convolutions⁹. In fact, (17) is central to the formulation of Nyquist’s sampling theorem. With that said, let’s compute ^-1[δ(k)]:

by using x₀ = 0 and x = k in (17). The above calculation tells us that ^-1[δ(k)] = 1. More importantly, because of the symmetry of the Fourier transform (15), it tells us that = [1] = δ(k). This means that we can define

and therefore be able to “do” the integral ∫ _-∞^∞e^-2πjkxdx wherever it appears¹⁰. Using this new found knowledge, we can perform _x[cos(2πk₀x)], using cos(u) = (e^ju + e^-ju)/2. Substituting for f(x), it now becomes easy to see that _x[cos(2πk₀x)] = [δ(k-k₀) + δ(k+ k₀)]. ■

---

---

But what does this mean? According to a plot of our result (Figure 8), the Fourier transform of a cosine function of frequency k₀ is a sum of two Dirac delta functions each centered at either of ±k₀, and normalized in such a way that the integral of the sum is 1. It tells us that there is a positive and a negative frequency component to our cosine function, and both components have the same magnitude. Notice how the arrows end at 1/2, rather than at 1, signifying that even though the value of the Fourier transform at ±k₀ is technically ∞, not all infinities are created equal.

Similar to the pattern seen in Fourier series, the plot of the Fourier transform of a function is even for an even function and odd for an odd function. Try doing a Fourier transform of f(x) = sin(2πk₀x), which is an odd function, to see what is meant.

It is important to note that the Fourier transform does not (generally) produce results that are immediately useful in digital signal processing. For example, there is no easy way to physically interpret negative frequencies or imaginary powers. This is why in actual signal analysis, magnitudes are generally used. That is, when the Fourier transform of a signal says that the relative power of the frequency 2.1 (frequency units) is (2.73 -3.2j)δ (power units), we generally simplify that to (power units)¹¹. But as soon as we take the magnitude of a frequency or power, we lose the imaginary and negative information of the Fourier transform that is crucial in reconstructing the original signal with the inverse Fourier transform. For example, a sine and a cosine wave of the same frequency have different exact Fourier transforms, but the same magnitudes and powers. Clearly, a sine and a cosine are different signals, even if they have the same amplitude and frequency. Therefore, any method that does not keep track of exact values, with all the requisite δ’s and imaginary components, is inherently lossy, and property (15) cannot be true. There are methods of correcting or even finessing this issue, but that is in the realm of signal processing.

Footnotes

 

References

Contents copyright (c) 2006-2008 by Ivan Papusha. Last modified: August 20, 2008. Hosted at 000webhost.