STC.UNM v. Intel Corporation

Filing 112

DECLARATION re 110 Brief of Brian Ferrall by Intel Corporation (Attachments: # 1 Exhibit 1, # 2 Exhibit 2, # 3 Exhibit 3, # 4 Exhibit 4, # 5 Exhibit 5, # 6 Exhibit 6, # 7 Exhibit 7, # 8 Exhibit 8, # 9 Exhibit 9)(Atkinson, Clifford)

Exhibit 6

An Introduction to Fourier Theory
by Forrest M. Hoffman

Introd uction
Linear transforms, especially Fourier and Laplace transforms, are widely used in solving

problems in science and engineering. The Fourier transform is used in linear systems analysis,

antenna studies, optics, random process modeling, probability theory, quantum physics,
and boundary-value problems (Brigham, 2-3) and has been very successfully applied to
restoration of astronomical data (Brault and White). The Fourier transform, a pervasive

and versatile tool, is used in many fields of science as a mathematical or physical tool to alter
a problem into one that can be more easily solved. Some scientists understand Fourier theory
as a physical phenomenon, not simply as a mathematical tool. In some branches of science,
the Fourier transform of one function may yield another physical function (Bracewell, 1-2).

The Fourier Transform
The Fourier transform, in essence, decomposes or separates a waveform or function

into sinusoids of different frequency which sum to the original waveform. It identifies or
distinguishes the different frequency sinusoids and their respective amplitudes (Brigham, 4).
The Fourier transform of f (x) is defined as
F(s) = ¡: f(x)e-i27rxSdx.

Applying the same'transform to F(s) gives
f(w) = ¡: F(s)e-i27rxSdx.

If f(x) is an even function of x, that is f(x) = f(-x), then f(w) = f(x). If f(x) is an odd
function of x, that is f(x) = -f(-x), then f(w) = f(-x). When f(x) is neither even nor

odd, it can often be split into even or odd parts.
To avoid confusion, it is customary to write the Fourier transform and its inverse so that
they exhibit reversibility:
F(s) = ¡: f(x)e-i27rxSdx

f(x) = ¡: F(s)ei27rxSdx
so that

f(x) = ¡: (¡: f(x)e-i27rXSdX) ei27rSds

as long as the integral exists and any discontinuities, usually represented by multiple integrals
of the form! ¡j(x+) + f(x-)J, are finite. The transform quantity F(s) is often represented
as 1(s) and the Fourier transform is often represented by the operator § (Bracewell, 6-8).

i

There are functions for which the Fourier transform does not exist; however, most physical functions have a Fourier transform, especially if the transform represents a physical

quantity. Other functions can be treated with Fourier theory as limiting cases. Many of the
common theoretical functions are actually limiting cases in Fourier theory.
Usually functions or waveforms can be split into even and odd parts as follows
f(x) = E(x) + O(x)

where
1

E(x) = 2" ¡j(x) + f(-x)J
1

O(x) = 2" ¡j(x) - f(-x)J

and E(x), O(x) are, in general, complex. In this representation, the Fourier transform of
f( x) reduces to
2 1000 E(x) cos (21rxs) dx - 2i 1000 O(x) sin (21rxs) dx

It follows then that an even function has an even transform and that an odd function has
an odd transform. Additional symmetry properties are shown in Table 1 (Bracewell, 14).

Table 1: Symmetry Properties of the Fourier Transform
real and odd

transform
real and even
imaginary and odd

imaginary and even

imaginary and even

complex and even

complex and even

function
real and even

complex and odd

complex and odd

real and asymmetrical

complex and asymmetrical
complex and asymmetrical

imaginary and asymmetrical

real
imaginary
even
odd

real even plus imaginary odd
real odd plus imaginary even
even
odd

An important case from Table 1 is that of an Hermitian function, one in which the real

part is even and the imaginary part is odd, i.e., f(x) = f*(-x). The Fourier transform of
an Hermitian function is even. In addition, the Fourier transform of the complex conjugate
of a function f(x) is F*( -s), the reflection of the conjugate of the transform.

The cosine transform of a function f( x) is defined as
cos 21rSX dx.

Fc(s) = 2 1000 f(x)

This is equivalent to the Fourier transform if f (x) is an even function. In general, the even
part of the Fourier transform of f(x) is the cosine transform of the even part of f(x). The
cosine transform has a reverse transform given by
2

f(x) = 2 1000 Fc(s) cos 21rsX ds.

Likewise, the sine transform of f( x) is defined by
sin 21rSX dx.

Fs(s) = 2 1000 f(x)

As a result, i times the odd part of the Fourier transform of f (x) is the sine transform of

the odd part of f(x).
Combining the sine and cosine transforms of the even and odd parts of f(x) leads to the
Fourier transform of the whole of f(x):
§f(x) = §cE(x) - i§sO(x)
where §, §c, and §s stand for -i times the Fourier transform, the cosine transform, and

the sine transform respectively, or

1 1.

F(s) = iFc(s) - izFs(s)

17-18).
Since the Fourier transform F( s) is a frequency domain representation of a function

(Bracewell,

f(x), the s characterizes the frequency of the decomposed cosinusoids and sinusoids and is

equal to the number of cycles per unit of x (Bracewell, 18-21). If a function or waveform
is not periodic, then the Fourier transform of the function wil be a continuous function of
frequency (Brigham, 4).

The Two Domains
It is often useful to think of functions and their transforms as occupying two domains.
These domains are referred to as the upper and the lower domains in older texts, "as if
functions circulated at ground level and their transforms in the underworld" (Bracewell,

135). They are also referred to as the function and transform domains, but in most physics
applications they are called the time and frequency domains respectively. Operations performed in one domain have corresponding operations in the other. For example, as wil

be shown below, the convolution operation in the time domain becomes a multiplication

operation in the frequency domain, that is, f(x) @ g(x) f- F(s) G(s). The reverse is also
true, F(s) @ G(s) f- f(x) g(x). Such theorems allow one to move between domains so that

operations can be performed where they are easiest or most advantageous.

Fourier Transform Properties
Scaling Property
If § U(x)) = F(s) and a is a real, nonzero constant, then
3

§ U(ax)) = ¡: f(ax)ei27rsXdx
= ~ roo f(ß)ei27r%ß dß

la11-00
= 1~IF (~).
From
this, the time scaling property, it is evident that if the width of a function is decreased
while its height is kept constant, then its Fourier transform becomes wider and shorter. If
its width is increased, its transform becomes narrower and taller.

A similar frequency scaling property is given by

§ t i~if (~) 1 = F(as).

Shifting Property
If § U( x)) = F( s) and Xo is a real constant, then

§ U(x - xo)) = ¡: f(x - xo)ei27rsXdx

. = ¡: f(ß)ei27rs(ß+xo)dß

= é27rxos ¡: f(ß)ei27rsß dß

= F( s )ei27rxos.

This time shifting property states that the Fourier transform of a shifted function is just

the transform of the unshifted function multiplied by an exponential factor having a linear
phase.
Likewise, the frequency shifting property states that if F( s) is shifted by a constant so,
its inverse transform is multiplied by ei27rxsO

§ ff(x)ei27rXSo) = F(s - so).

Convolution Theorem
We now derive the aforementioned time convolution theorem. Suppose that g( x) =
f(x) @ h(x). Then, given that § -(g(x)) = G(s), § U(x)) = F(s), and § -(h(x)) = H(s),
4

G(s) = § U(x) @ h(x))

= § r¡: f(ß)h(x - ß) dß 1
= ¡: (¡: f(ß)h(x - ß) dßJ e-i27rSXdx
= ¡: f(ß) (¡: h(x - ß)e-i27rSXdx J dß

= H(s) ¡: f(ß)e-i27rsßdß
= F(s) H(s).

This extremely powerful result demonstrates that the Fourier transform of a convolution is
simply given by the product of the individual transforms, that is

§ U(X) @ h(x)) = F(s) H(s).
Using a similar derivation, it can be shown that the Fourier transform of a product is
given by the convolution of the individual transforms, that is

§ U(x) h(x)) = F(s) @ H(s).
This is the statement of the frequency convolution theorem (Gaskil, 194-197; Brigham,

60-

65).

Correlation Theorem
The correlation integral, like the convolution integral, is important in theoretical and
practical applications. The correction integral is defined as
h(x) = ¡: f(u)g(x + u)du

and like the convolution integral, it forms a Fourier transform pair given by

§ -(h(x)) = F(s)G*(s).
This is the statement of the correlation theorem. If f( x) and g( x) are the same function,
the integral above is normally called the autocorrelation function, and the crosscorrelation if

they differ (Brigham, 65-69). The Fourier transform pair for the autocorrelation is simply

§ r¡: f(u)f(x + u)du 1 = 1F12 .

Parseval's Theorem
Parseval's Theorem states that the power of a signal represented by a function h(t) is
the same whether computed in signal space or frequency (transform) space; that is,
5

¡: h2(t)dt = ¡: IH(J)12 df

(Brigham,

23). The power spectrum, P(J), is given by
P(J) = IH(J)12 , -00 :: f:: +00.

Sampling Theorem
A bandlimited signal is a signal, f(t), which has no spectral components beyond a frequency B Hz; that is, F( s) = 0 for Is I ? 21r B. The sampling theorem states that a real
signal, f(t), which is bandlimited to B Hz can be reconstructed without error from samples
taken uniformly at a rate R ? 2B samples per second. This minimum sampling frequency,
Fs = 2B Hz, is called the Nyquist rate or the Nyquist frequency. The corresponding sampling
interval, T = 21 (where t = nT), is called the Nyquist interval. A signal bandlimited to B

Hz which is sampled at less than the Nyquist frequency of 2B, i.e., which was sampled at
an interval T ? 21, is said to be undersampled.

Aliasing
A number of practical diffculties are encountered in reconstructing a signal from its
samples. The sampling theorem assumes that a signal is bandlimited. In practice, however,
signals are timelimited, not bandlimited. As a result, determining an adequate sampling
frequency which does not lose desired information can be diffcult. When a signal is undersampled, its spectrum has overlapping tails; that is F( s) no longer has complete information

about the spectrum and it is no longer possible to recover f(t) from the sampled signaL. In
this case, the tailing spectrum does not go to zero, but is folded back onto the apparent
spectrum. This inversion of the tail is called spectral folding or aliasing (Lathi, 532-535).
As an example, Figure 1 shows a unit gaussian curve sampled at three different rates.

The FFT (or Fast Fourier Transform) of the undersampled gaussian appears flattened and
its tails do not reach zero. This is a result of aliasing. Additional spectral components have
been folded back onto the ends of the spectrum or added to the edges to produce this curve.

The FFT of the oversampled gaussian reaches zero very quickly. Much of its spectrum
is zero and is not needed to reconstruct the original gaussian.
Finally, the FFT of the critically-sampled gaussian has tails which reach zero at their
ends. The data in the spectrum of the critically-sampled gaussian is just suffcient to recon-

struct the originaL. This gaussian was sampled at the Nyquist frequency.
Figure 1 was generated using IDL with the following code:
i !P.Multi=(0,3,2J
2 a=gauss (256,2.0,2) ; undersampled

3 fa=fft(a,-1)
4 b=gauss(256 ,2. 0,0.1) oversampled
5 fb=fft(b,-1)
6 c=gauss(256,2.0,0.8) critically sampled
7 fc=fft(c,-1)
8 plot, a, ti tle=' ! 6Undersampled Gaussian'

9 plot,b,title=' !60versampled Gaussian'
10 plot,c, title=' !6Critically-Sampled Gaussian'
shift
(abs
(fa) ,128), title=' ! 6FFT of Undersampled Gaussian'
12 plot, shift (abs (fb) ,128) , ti tle=' ! 6FFT of Oversampled Gaussian'

II plot ,

13 plot ,shift (abs(fc), 128), title=' ! 6FFT of Critically-Sampled Gaussian'
6

The gauss function is as follows:
I function gauss,dim,fwhm,interval
2

3
4

gauss - produce a normalized gaussian curve centered in dim data
points with a full width at half maximum of fwhm sampled
with a periodicity of interval

5

6

dim = the number of points

7
8
9
10
11
12
13
14
15
16
17

fwhm = full width half max of gaussian
interval = sampling interval
.

center=dim/2.0 ; automatically center gaussian in dim points
x=f indgen (dim) -cent er

sigma=fwhm/sqrt(8.0 * alog(2.0)) ; fwhm is in data points
coeff=1.0 / ( sqrt(2.0*!Pi) * (sigma/interval) )
data=coeff * exp( -(interval * x)-2.0 / (2.0*sigma-2.0) )

data

return,

end

Undersampled Gaussian
1.0

0.8

0.030

0.4

0.020

0,2

Critically-Sampled Gaussian

0.40

0.040

0,8

Oversampled Gaussian
"

0.050

0,010

0,30

0,20

0,10

J

0.000

0.0
60

0

100

160

200

260

300

0

60

100

0.00
160

200

260

30D~

°

50

100

160

200

260

300

60

100

150

200

250

300

FFT of Oversampled Gaussian

FFT of Undersampled Gaussian

0,0040

0,0060

0,0040
0.0030

0.0030

0.0020

0,0020

0,0010

0.0010

0.0030

0,0020

0.0010

,

0,0000

0.0000
0

50

100

150

200

250

300

°

60

0,0000
100

150

200

260

300

0

Figure 1: Undersampled, oversampled, and critically-sampled unit area gaussian curves.

Discrete Fourier Transform (DFT)
Because a digital computer works only with discrete data, numerical computation of the
Fourier transform of f(t) requires discrete sample values of f(t), which we wil call fk' In

addition, a computer can compute the transform F( s) only at discrete values of s, that is, it
can only provide discrete samples of the transform, Fr. If f(kT) and F(rso) are the kth and
7

rth samples of f(t) and F(s), respectively, and No is the number of samples in the signal in

one period To, then

fk = Tf(kT) = ~f(kT)
and
Fr = F(rso)

where
21r

so = 21rFo = -.
To

The discrete Fourier transform (DFT) is defined as
No-l
Fr = L fke-irnok
k=O

where no = ~. Its inverse is
No-l
!k = ~ L Freirnok.
No r=O

These equations can be used to compute transforms and inverse transforms of appropriatelysampled data. Proofs of these relationships are in Lathi (546-548).

Fast Fourier Transform (FFT)
The Fast Fourier Transform (FFT) is a DFT algorithm developed by Tukey and Coo-

ley in 1965 which reduces the number of computations from something on the order of
N'6 to No log No. There are basically two types of Tukey-Cooley FFT algorithms in use:
decimation-in-time and decimation-in-frequency. The algorithm is simplified if No is chosen

to be a power of 2, but it is not a requirement.

Summary
The Fourier transform, an invaluable tool in science and engineering, has been introduced and defined. Its symmetry and computational properties have been described and the
significance of the time or signal space (or domain) vs. the frequency or spectral domain has

been mentioned. In addition, important concepts in sampling required for the understanding
of the sampling theorem and the problem of aliasing have been discussed. An example of
aliasing was provided along with a short description of the discrete Fourier transform (DFT)
and its popular offspring, the Fast Fourier Transform (FFT) algorithm.

8

References
Blass, Wiliam E. and Halsey, George W., 1981, Deconvolution of Absorption Spectra, New

York: Academic Press, 158 pp.
Bracewell, Ron N., 1965, The Fourier Transform and Its Applications, New York: McGraw-

Hil Book Company, 381 pp.
Brault, J. W. and White, O. R., 1971, The analysis and restoration of astronomical data via
the fast Fourier transform, Astron. & Astrophys., 13, pp. 169-189.
Brigham, E. Oren, 1988, The Fast Fourier Transform and Its Applications, Englewood Cliffs,

NJ: Prentice-Hall, Inc., 448 pp.
Cooley, J. W. and Tukey, J. W., 1965, An algorithm for the machine calculation of complex
Fourier series, Mathematics of Computation, 19, 90, pp. 297-301.
Gabel, Robert A. and Roberts, Richard A., 1973, Signals and Linear Systems, New York:

John Wiley & Sons, 415 pp.
Gaskil, Jack D., 1978, Linear Systems, Fourier Transforms, and Optics, New York: John
Wiley & Sons, 554 pp.
Lathi, B. P., 1992, Linear Systems and Signals, Carmichael, Calif: Berkeley-Cambridge

Press, 656 pp.

9