Citation
Multilevel discrete Fourier transforms

Material Information

Title:
Multilevel discrete Fourier transforms
Creator:
Hare, Michael Anne
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
62 leaves : illustrations ; 29 cm

Subjects

Subjects / Keywords:
Fourier transformations ( lcsh )
Fourier transformations ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaf 62).
Thesis:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Mathematical and Statistical Sciences.
Statement of Responsibility:
by Michael Anne Hare.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
20960313 ( OCLC )
ocm20960313
Classification:
LD1190.L62 1989m .H37 ( lcc )

Downloads

This item has the following downloads:


Full Text
MULTILEVEL DISCRETE FOURIER TRANSFORMS
by
Michael Anne Hare
B.S., University of Texas, 1982
(
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Department of Mathematics


This thesis for the Master of Science degree by
Michael Anne Hare
has been approved for the
Department of
Mathematics
by
Steven F. McCormick
Roland A. Sweet
Date

r


Hare, Michael Anne (M.S., Applied Mathematics)
Multilevel Discrete Fourier Transforms
Thesis directed by Professor William L. Briggs
in
In many applications of the Fast Fourier Transform (FFT) computations
are necessary in both the physical space and the transform space. By manipu-
lating the grid in one space, the grid in the other space is altered in a manner
consistent with the properties relating the two spaces. This change of grids in
the time domain (or physical space) which produces a new sequence of values
to be transformed may be accomplished in several ways, five of which are pre-
sented in this thesis. In each case, the resulting grid in the frequency domain
(transform space) is known and the values expected from the new transform
may be shown analytically. In some cases a change of grids in the time domain
results in a higher resolution grid in the frequency domain. Whether this higher
resolution grid actually provides new or insightful information about the fre-
quency spectrum of a function will be investigated. In other cases, resolution in
the frequency domain is not lost so we will investigate whether we have lost or
gained information contained in the frequency spectrum by transferring the in-
put sequence of data to another grid. Knowledge about multiple transform grids
and their related output may then be used to advantage to develop systems of
multilevel Fourier transforms.
The form and content of this abstract are approved. I recommend its publication.
Signed___________________________________________________________
Faculty member in dnarge of thesis


IV
CONTENTS
CHAPTER
I. INTRODUCTION .......................................... 1
1.1 The Fourier Transform................................ 1
1.2 DFT Properties........................................ 3
1.2.1 Linearity Property.............................. 3
1.2.2 Shift Properties................................ 3
1.2.3 Time vs. Frequency Domain....................... 4
1.2.4 Convolution..................................... 5
1.2.5 Properties of wjv............................... 5
1.2.6 Sampling Theorem............................... 6
1.3 The Fast Fourier Transform ........................... 9
II. DFTs ON MULTIPLE GRIDS.................................... 12
2.1 Grid Definitions..................................... 13
2.2 Case 1: Injection flT ......................... 15
2.3 Case 2: Extension (lN Q?N .................... 22
2.3.1 Periodic Extension............................. 22
2.3.2 Zero Extension ................................ 25
2.4 Case 3: Extension and Injection flN £lNc....... 33
2.4.1 Periodic Extension
37


V
2.4.2 Zero Extension .......................... 40
2.5 Summary ....................................... 51
III. FUTURE DIRECTIONS: MULTILEVEL
TRANSFORM SYSTEMS ................................. 52
3.1 Transform System I ............................ 52
3.2 Transform System II............................ 55
3.2.1 Periodic Extension ...................... 57
3.2.2 Zero Extension .......................... 58
IV. SUMMARY AND CONCLUSIONS........................... 60
BIBLIOGRAPHY ............................................. 62


VI
TABLES
Table
2.1 Multilevel Transform Results
51


vu
FIGURES
Figure
1.1 The Sampling Theorem ....................................... 7
2.1 Time and Frequency Domain Grids............................. 14
2.2 Q,N flT for x(t) = 8sin(t) + sm(16t)..................... 17
2.3 QN (1% for x(t) = Boxcar function ............... 18
2.4 flN for x(t) = e-,rt2 ............................................... 20
2.5 fiN y for x(t) = Triangle function............................................... 21
2.6 QN tt2N with Periodic Extension for
x(t) = 8sin(t) + sm(16<).................................... 24
2.7 QN fl2N with Periodic Extension for
x(t) = Boxcar function ..................................... 26
2.8 QN fl2N with Periodic Extension for x(f) = e~nt2. 27
2.9 ClN with Periodic Extension for
x(t) = Triangle function ................................... 28
2.10 flN Sl2N with Zero Extension for x(<) = 8sin(t) + sm(16i). 31
2.11 QN Cl2N with Zero Extension for x(t) = Boxcar function .. 32
2.12 F(f) on i\N and F{f) on A2N ................................ 34
2.13 QN > fl2N with Zero Extension for x(t) = e~nt2................................ 35
2.14 y with Zero Extension for x(t) = Triangle function . 36
2.15 QN y with Periodic Extension for
x(t) = 8sin(t) + sm(16t) ................................. 39


VUl
2.16 flNc with Periodic Extension for
i(t) = Boxcar function ..................................... 41
2.17 P(/) on and F(/) on ........................................ 42
2.18 flNc with Periodic Extension for x(<) = e~*t2........ 43
2.19 flN UNc with Periodic Extension for
x(t) = Triangle function ................................... 44
2.20 f £lNc with Zero Extension for
x{t) = 8 sin(t) + sin(16t).................................. 47
2.21 f1N + SlNc with Zero Extension for x(t) = Boxcar function .. 48
2.22 ClN flNc with Zero Extension for x(t) = e-,r<2.......... 49
2.23 ClN * ClNc with Zero Extension for x(t) = Triangle function . 50
3.1 Transform System I......................................... 54
3.2 Transform System II .......................................... 56


CHAPTER 1
INTRODUCTION
The fast Fourier transform (FFT) is a powerful and very efficient al-
gorithm for computing the discrete Fourier transform of a series of complex
numbers. The FFT has been widely applied in areas such as signal processing,
antenna and radio wave theory, data analysis, solutions of PDEs, and image
reconstruction. The work in this thesis was motivated by questions that arise
in multilevel image reconstruction algorithms. However, the results should be
applicable to a variety of other problems in which computation takes place in
both a physical space and a transform space. In problems of this nature, it is
generally possible to construct multiple grids in both spaces and use this sys-
tem of multiple transform grids to advantage. The purpose of this thesis is to
investigate such systems of grids.
1.1 The Fourier Transform
The Fourier transform identifies or distinguishes the different frequency
sinusoids and their respective amplitudes which combine to form an arbitrary
waveform. The Fourier transform of a continuous function x(t) is defined as
X{f) = r x{t)e2nift dt (1.1)
J CO
where x(t) is the waveform to be decomposed into its frequency components. If
the integral exists for every value of the parameter / then equation (1.1) defines
X(f), the Fourier transform of x(t).


2
The inverse transform allows the reconstruction of a function of time
from its Fourier transform. The inverse is defined as
*(<)= I" X(f)-2ifif (1.2)
*/oo
If the functions x(t) and X(f) are related by equations (1.1) and (1.2),
the two functions are termed a Fourier transform pair and their relationship is
indicated by
x(*) <=> X(f).
For computational reasons, it is necessary to discretize the Fourier trans-
form. The discrete Fourier transform (DFT) of a periodic sequence of N complex
numbers {x_jv, x_£+1, ..., x0, ..., X£_2,X£_i} is given by
2 1
Xk= £
__ N
nT
2irink N N
xne^r~ for < k < 1,
where {Xjt} is another sequence of N complex numbers. Its similarity to the
continuous form of the transform is readily visible. For notational ease, the
transform sequence may also be denoted
i£_i
xk = £ zu# for-y<* n=-%
where This relationship between the sequences {xn} and {X*} is
denoted
DFTN{xn] = {Xk}.
The elements of the sequence {xn} are considered to reside in the time
domain, while the sequence {X*} is associated with the frequency domain. Note
that the sequence {Xjt} also has a period of length N. The inverse DFT is
defined as
Xn =
jf E
K 2
2irmfc
N
2 ~ 2
(1.4)


3
The fact that equations (1.3) and (1.4) are inverses of each other may
be verified by substituting (1.3) into (1.4):

/
xk =
1 r% r^ 2jrnm
Jr £ £
AT , __ AT
fl \ 771 ^
\
__2>rinfc
e n
£t_i
1 2
JV ^

E2irinm _2jrink
e w e *
(1.5)
_ AT
77l=n=

~~ 2
This last summation in equation (1.5) equals j ^ otherwise ^us
proving that the right-hand side of (1.5) equals xk.
1.2 DFT Properties
The definition given above in equation (1.3) may be used to demonstrate
several properties of the DFT. This list of properties is by no means complete,
but rather includes only those properties that will be useful in the following
chapters.
1.2.1 Linearity Property
The linearity property states that the transform of the sum of two se-
quences is the sum of the transforms. If {xn} and {i/n} are two periodic sequences
with period N whose transforms are {X*} and {!*}, respectively, then
{in} + {j/n} <=> {-X*} + {K}-
1.2.2 Shift Properties
Shifting a sequence of values left or right in the time domain is equivalent
to a rotation in the frequency domain. Define Sm{xn} = {xn_m} to be the
sequence obtained by shifting {xn} to the right m units. Then the shift property


says that
4
0fTj*{Sm{*}} = Xk) for y < fc < y 1.
The proof of this property follows immediately by applying equation (1.3) to the
shifted sequence.
Similarly, a shift in the frequency domain corresponds to a rotation in
the time domain. If we define i2m{xn} = as the sequence obtained by
rotating {xn} in the complex plane in a counter-clockwise direction, then the
shift property in the frequency domain says that
DFTNiRrnixJ} = {Xk+m} for y < k < y 1.
1.2.3 Time vs. Frequency Domain
Define At to be the sampling interval of the N points that make up the
sequence {i} in the time domain and A/ to be the corresponding sampling
interval in the frequency domain. If we discretize the continuous form of the
Fourier integral, we have
X(kA/) £ x(nAt) e2winAtk*f for oo < k < oo.
ns-OO
However, over the finite interval 1, the DFT was defined as

= E xn e***,
n=-f
leading to the conclusion that At Af = This equation defines the relationship
between the sampling intervals of the time and frequency domains. If we also
define the length of the time domain as T, where T = NAt and the length of
the frequency domain as F, where F = NAf, then it follows that TF = N.


5
1.2.4 Convolution
Given two continuous functions of time, x(t) and z(t), the convolution
of x(t) and z{t) is defined as
y(t) = f x{r)z{t r)dr.
J OO
In the discrete case, the convolution of two sequences {xn} and {zn}, both of
which are periodic in N, is defined by the summation
2 1
Vk = £ **-
f
For convenience of notation, discrete convolution is normally written as
fan} = {*n} {*n}.
The discrete convolution theorem (Brigham [5]) states that the DFT of
the convolved sequence is the product of the transforms of the original sequences;
that is,
DFTN{xn*zn} = {XkYk}.
1.2.5 Properties of u>n
2iri
By the definition of u>n = , two properties may be quickly identified
which will be very helpful in later chapters:
.n k
iQ. 2ir iNk
WN
2jrink 2ni2nk
7rifc
= u = ui 2 (1.6)
_-r. 2ir iNk -H* e k = e =uN2 (1.7)


6
1.2.6 Sampling Theorem
The sampling theorem states that if the Fourier transform of a function
x(t) is zero for all frequencies greater than a certain cutoff frequency fc, i.e.
the frequency function is band-limited, then the continuous function x(t) can be
uniquely determined from a knowledge of its sampled values (Brigham [5]). A
graphical demonstration of this fact is worth presenting.
First assume we have a continuous function x(t) (Figure 1.1a) which
has been sampled in the time domain with sample spacing that does not exceed
At = This spacing will assure that the signal is sampled at a rate that is
twice the highest frequency (the cutoff frequency) and thus avoids aliasing of
any part of the signal. Sampling of the function x(t) amounts to multiplying the
original signal by the shah function:
III(t) = jr S(t-nAt)
n=oo
which is just a train of delta (or impulse) functions with sample spacing At.
III(t) and its transform, 111(f), are shown in Figure 1.1b. According to the
convolution theorem, this multiplication in the time domain,
x(t)III(t) = ^2 x(t)6(t nAt)
n=oo
is just the convolution of X(f) and 111(f) in the frequency domain:
x(t)III(t) <=* X(f) 111(f).
Since X(f) is band-limited and 111(f) is also a repeated delta function
with sample spacing 1/At = 2fc, their convolution produces a signal which is just
X(f) repeated every 2fc units, as shown in Figure 1.1c. Now we want to extract
only one of the repeated functions from X(f), so we multiply X(f) 111(f) by


2
X(t)
X(f)
o 0.(0
(d) |----
-1 -------------------1------
-4 -2 0 2 4
Figure 1.1
The Sampling Theorem


8
a boxcar function, Q(f), where
Q(f)
_ / 0 for |/| > fc
\ At for j/| < fc
Q(f) possesses the Fourier transform q(t), where
sin(2-!rfct)
q(t) =
2irfct
The function q(t) is also called the sine function, where
sin( 2tt fct)
sinc{2-K fct) =
2irfct
This transform pair (q(t) Q(f)) can be seen in Figure l.ld. The multipli-
cation of X(f) ///(/) by Q(f) in the frequency domain is just the convolution
of x{t)III{t) with q(t) in the time domain. Thus, we now have the transform
pair
[x(()/i/(()l ?(i) <=* W) *
which is shown in Figure l.le. This is then just an identity transformation that
produces the original transform pair that we started with in Figure 1.1a; that
is, [x{t)III{t)] q(t) = x(t).
It follows then that
x(f)
[x(t)III(t)\ ,(()
OO
y; [x(nAt)5(< nAt)] q(t)
n=soo
oo
y xnq(t nAt)
n=oo
oo
y xnsinc(2irfc(t nAt)).
n=oo
Therefore, if a function possesses a band-limited transform, the value of the
function at any point in the time domain may be uniquely determined from the
sampled values using the above equation.


9
Analogous to time domain sampling, there exists a sampling theorem
in the frequency domain. If a function x(t) is time-limited, that is x(t) = 0 for
\t\ > Tc, then its Fourier transform X(f) can be uniquely reconstructed from
equidistant samples of X(f). As a result of these operations, values of X(f) are
given by
X(f) = lX(f)III(f)]*Q(f)
= £ X(kAf)Q(f kAf)
k=- oo
= ^2 Xksinc(2irTc(f kAf)).
k=oo
According to Bracewell [2], this infinite sum may be reduced to a finite sum if
the coefficients are modified as follows:
Y( n v Y sin(2irTc(f ~ kAf))
U k*in(2*%(f-kAf))
(1.8)
1.3 The Fast Fourier Transform
A brief description of the FFT algorithm is in order here, for it will later
become an important aspect of understanding the DFTs of functions that are
shifted to multiple grids.
A sequence of N elements may be divided into two shorter sequences
of Nj2 elements each by placing the even-numbered elements into the first sub-
sequence and the odd-numbered ones into the second. These two subsequences
can then be stretched and shifted so that their resulting DFTs may be added
together to form the DFT of the original sequence. Bracewell^ shows how, for
example, we can write the eight point series {8 7 6 5 4 3 2 1} as the sum of the
two subsequences {8 6 4 2} and {7 5 3 1}. If
{8 6 4 2}<=> {A B C D}


10
then
{8 0 6 04 0 2 0} *=> {ABC D ABC D},
and if
{7 5 3 1 }*=>{PQ RS}
then
{7 0 5 0 3 0 1 0} <= {P Q R S P Q R S}.
If we then shift the odd series, giving
{0 7 0 5 0 3 0 1} <=* {P u8Q u\R ujjS w\P wjQ wfR u7S},
then the DFT of the entire sequence is just the sum of the transforms of the
even and odd subsequences {8 0 6 0 4 0 2 0} and {0 7 0 5 0 3 0 1}. If we define
{xn} to be the full sequence {8 7 6 5 4 3 2 1} and let {yn} and {zn} be the even
and odd subsequences, respectively, then we have
Xk = Yk+ ukNZk for 0 < k < N 1,
which is just the butterfly relation associated with the Cooley-Tukey version of
the FFT.
In general, we will adopt the notation that
Yk = DFT*{yn},
where yn = X2n for j < n < ^ and
Zk = DFTz{zn},
where = x2n+i for < n <
Similarly, this breaking down of each sequence may continue by splitting
the sequence into four shorter sequences of length N/4, and then eight sequences


11
of length JV/8, etc., until N sequences of length 1 are obtained. Since the trans-
form of a one-point sequence is itself, all that remains is to reconstruct the entire
transform from all its pieces.
This specific algorithm assumes the original sequence is of length N
where N is a power of 2, say N = 2m. If N ^ 2m a fast algorithm may still be
constructed.


CHAPTER 2
DFTs ON MULTIPLE GRIDS
The input sequence {x} is defined on a grid in the time domain and its
transform is defined on a grid in the frequency domain whose length and sample
spacing are determined by the equation AtAf = ^. In some Fourier transform
applications, it is necessary to interpolate the grid points in the frequency domain
in order to better resolve a functions frequency spectrum. But what if the
transform is very oscillatory? Interpolation in this case can only provide a very
crude estimate of the true transform. It is for this reason that we look at ways
of improving resolution in the frequency domain using only modifications of the
grid in the time domain.
The relationship At A/ = jj tells us that in order to double the reso-
lution in the frequency domain (i.e. to reduce the frequency sample spacing to
we must either double the sample interval in the time domain or double the
number of sample points to 2N: In either case we must construct a new grid in
the time domain; this requires that a new input sequence, {xn}, be constructed
in terms of {xn}. The resulting grid in the frequency domain is then known and
the transform of the new sequence may be determined analytically in terms of
the original transform. These analytical results will then tell us whether the new
transform has in fact provided valuable information at a higher resolution.
There are many ways to define how the original sequence of input data
{xn} is to be defined on a new grid with different length or sample spacing. This
chapter will explore some of those possiblities and their expected results.


13
2.1 Grid Definitions
We shall denote the physical grid on which the sequence {xn} is defined
by Q,N, where N is an even natural number. It is useful to regard the indices of
{xn} as actual coordinates on the grid VlN. We shall also assume that the grid
nN has spacing At between adjacent grid points, so the total length of grid is
T = NAt. The corresponding grid in the frequency domain will be defined as
A.N which has spacing Af and length F = NA/. The relationship between f
and A.N is shown in Figure 2.1a.
Case 1. The first type of grid transfer we consider consists of injecting
the even-numbered points from the original sequence on grid ft" to grid fl~,
where f)T has grid spacing 2At and length T. The frequency domain corre-
sponding to fiT will be defined as At, where grid spacing on At is still Af but
its length is (N/2)Af = F/2. Grids fiT and At are shown in Figure 2.1b.
Case 2. The next type of grid transfer involves extending the the original
sequence to 2N points without changing the sample interval. Hence, all of the
original data points will be retained and new ones added to make up the full 2N
points. Two methods of extending the sequence will be explored: periodic and
zero extension. This new grid, tt2N, thus will have sample spacing At and total
length 2NAt = 2T. In the frequency domain, grid A2N will then have sample
spacing Af/2, but the total grid length is once again (2N)(Af/2) = F. This
relationship between fl2JV and A2N is demonstrated in Figure 2.1c.
Case 3. The final type of grid transfer involves extension and injection
of the original sequence resulting in a sequence of N points with sample spacing
2At. This new coarser grid, f!^, will thus have length 2T. This doubling of the
sampling interval without halving the number of sample points, N, means that
the spacing on the frequency domain grid ANc will now be Af/2 and total grid


TIME DOMAIN
FREQENCY DOMAIN
T
F
nN
_n ri i
-N-N ... 0
2 2
f-H
N
02
2At
y
-N
4
+
0
Af
M-----1---(I
-N . 0 N
4 4
o
2N
At
IIP+
-N -N-1
A--------MM
0 N-2 N-1
(c)
Af
2
m-----------1--------hu
-N 0 N-1
2At
2T
l
At Af
TF
2.
N
N
Figure 2.1
Time and Frequency Domain Grids


15
length will be F/2. These grids are shown in Figure 2.Id. As in Case 2, periodic
and zero extension methods will be studied.
2.2 Case 1: Injection fl ^
As shown in the grids pictured in Figures 2.1a and 2.1b, sampling N/2
points produces a grid in the frequency domain that is half the length of the
original frequency grid, but with the same spacing between points, A/. We
would like to determine if this new grid, STt is in any way representative of the
original grid, ClN.
First it should be noted that on the frequency grid AN, coefficients with
indices in the interval 0 < |fc| < y correspond to low frequency components,
while the coefficients associated with y < |fc| < y correspond to high frequency
components. With this in mind, it seems clear that the transfer of grid points
from CtN to will extract the low frequency modes from the original series.
This is true simply because a lower sampling rate implies that higher frequency
components cannot be resolved.
N
The transform on grid fit may be written in terms of the original series
{xn} in the following way. Let {in} = {i_^, x_n+1, ..., x0, ..., xn_2, xn_1}
be obtained by sampling only the even points of {xn}. In that case, xn = x2n
for < n < 1 so the DFT of {xn} can be written
Xk = £ x2nuftk
= £
__ N
nT
_ , ,nk
X2ntjJN_
2
= DFTn{x 2n}
= Yk for-^ which is just the y-point DFT of the sequence of even points only.


16
We now consider a few functions and their transforms on grids and
nf
Function 1. We first consider the simple dual mode sine wave x(t) =
8sin(t) + sin(16t) on the interval [7r, 7r] with N = 256 on grid f1N. This input
signal has the two frequencies 1/2tt = .159 and 16/27T = 2.55. Figures 2.2a and
2.2b show the function x(t) and its transform F(f), respectively. In this and all
subsequent frequency domain plots, the transform is plotted on a frequency vs.
amplitude graph. Notice the spikes located at .159 and 2.55 on the frequency
axis which correspond to the frequencies of each of the modes composing the
function. (The fact that these are not true spikes, but more like very steep
triangles, is due to the plotting algorithm.)
Figure 2.2c shows the same function which has been injected from to
fiT and now consists of N/2 = 128 sample points over the same interval [7r, 7r].
N
Notice in Figure 2.2d, the plot of F(f) on At, that the two modes are retained
and only their amplitudes have changed.
Function 2. The second function we will consider is a shifted boxcar
function. We shift the typical boxcar function (which is zero everywhere except
on a small region in the center of the entire interval) one unit to the right and
examine the function on the interval [1,1] with N = 64. We will also assume
periodicity with this function so that one-half width of the original boxcar will
be present at both ends of the interval [1,1]. Define x[t) to be
( 1 for .75 < \t\ < 1.0
x(t) = <
[0 for 0 < |Z| < .75
as shown in Figure 2.3a.
The transform of x(t) is the sine function and is shown in Figure 2.3b.
(Remember that only amplitudes are plotted.) The frequency spectrum on A.N
has length F = 32 (given by the equation XF = N) and, hence, extends over


u -
5 -
0 -
5
0
-1
Or
5
0
5
0
-1
1500 r-
1000 -
500 -
0 -
-5 0 5 10 -10 -5 0
(a)
i---------r
(b)
1500
1000 -
500 -
0
-5 0 5 10 -10 -5 0 5
Figure 2.2
£lN for x(t) = 8sin(t) + sm(16<)
(a) x(t) on £lN (b) F(f) on AN (c) x(t) on (d) F(f) on
(<0
t-------------1-------- r


Figure 2.3
KT N U
flN ft 2" for x(t) Boxcar function
(a) i(<) on flN (b) F(f) on AN (c) x{t) on ft^ (d) F(f) on
ao


Figure 2.4
flN > fIt for x(t) = e_ir*2
(a) x(t) oh QN (b) F(f) on (c) x(t) on (d) F(f) on A ^
to
o


19
the interval [16,16].
Figure 2.3c displays the boxcar function which has been injected to grid
fl% where N = 32. Its transform, shown in Figure 2.3d, is also a sine function,
but the length of the interval has been cut in half. Only the low frequency
components from A.N are retained, that is, frequencies |/| < 8.
Function 3. The next function to be considered is the Gaussian curve
x(t) = e-**. This function was sampled at N = 256 points over the interval
[£, |], The Gaussian curve also has a known transform itself! The transform
pair x(t) +=+ F(f) is shown in Figures 2.4a and 2.4b. Notice that the plot of the
transform is not as smooth as the original function though, in theory, it should
be. This is due to the sample spacing in the frequency domain (A/ = £ .318)
and the use of piecewise linear plotting.
Although it is impossible to tell from Figure 2.4b, the frequency interval
on AN has length N/T = 81.49 and thus extends from -40.75 to +40.75; how-
ever, the majority of the signal is in the interval [1.5,1.5]. When the function
is injected to the grid Qt (Figures 2.4c and 2.4d), only the low frequency com-
ponents of the original transform are kept; but in this case, the entire spectrum
is in the low frequency range, so nothing is lost.
Function 4. The last function to be investigated is a triangle function
defined by
Ax + 4 for 1 < t < 0
x(t) = < Ax + 4 for 0 < t < 1
0 for 1 < |£| < 4
It will be sampled with N = 128 points.
This function also has a known transform: the.sine2 function. The
function x(t) and its transform F(f) can be seen in Figures 2.5a and 2.5b. The
length of the frequency spectrum on AN is 16 and thus extends over the interval


(a) x(t) on S1N (b) F(f) on \N (c) x(t) on ftT (d) F(f) on At


22
[-8,8].
Figures 2.5c and 2.5d show the function after it has been injected to grid
which consists of N = 64 sample points. Its transform again contains only
the low frequency components (|/| < 4) from the original grid.
2.3 Case 2: Extension Q.2N
We will now focus on keeping the same sample spacing, but extending
the original sequence of N input points to 2N points. This will produce values
in the frequency domain on a grid that is the same length as AN. However, this
new grid, A2N, has a finer sampling interval of A//2, so it remains to be seen
whether we have gained information about the original frequency spectrum on
AN.
2.3.1 Periodic Extension
We will perform the extension to grid ft2N in two ways. The first extends
the original sequence on fto {xn} periodically in the intervals N y 1 and y < n < N 1. Thus the new sequence of points, {xn}, is
{xn+N for -N xn fory xn_w for y < n < TV 1
Now we can show the relationship between {AT*} and {A*}:
N-l
Y
n=N
-£-l 2 1 ¥-> JV-1
E _ nk ^n+N^2N + E _ ,nk xn^2N + Y Xr i-N^2N
n=N N n T
£-1 2 1 -1
E* , Xn-rt)k n^>2N + E _ .nk xn^2 N + E . Jn+N)k 'nUJ2N
n=0 ny 71 T


23


-l
nT

N
nT
Xk ^2Nk E XnU2N + E XntjJ2N+ w2N E Xnul2N
n=0 n=-f
By equation (1.7), u= (l)fc so
^ = £ *W& + (-l)fc E **
f"1
= (l + (-l)fc) E
f
Note that when k is odd, AT* = 0. When k is even, say, k = 2p,
f-i
X2p = 2 2 for-f ,nfc
nT
, ."2p U2N rtp = Upf, SO

x2p = 2 2 xnu$
__ W
nT
= 2XV
= 2X*
2
for iV < k < N 1.
Therefore, on grid A2W we have
- f 0 if A: is odd
k ~~ | 2Xk if k is even
This says that the values of the even coefficients are twice their value
on the original grid (which is due to the fact that the DFT is not scaled by
JV), and the odd coefficients are all zeroes. Therefore, we have picked up no
new information at the interpolated values on grid A2N. Now we shall examine
these results graphically as applied to the same functions shown in the previous
section.
Function 1. Figures 2.6a and 2.6b show the original function x(t) =
8sin(t) -f sm(16<) and its transform F(f). Figures 2.6c and 2.6d show the


flN > £l2N with Periodic Extension for x(t) = 8sin(t) -f szn(16i)
(a) x(t) on nN (b) F(f) on AN (c) x{t) on Q2N (d) F(f) on A2N
to


25
new function extended to 2N points over the interval [2ir, 2tt] as well as its
transform. Because the modes of this sine wave occur at even values of k, the
zeroes at the odd points are not evident. However, notice the amplitude of each
of the modal peaks has been doubled, as predicted.
Function 2. The shifted boxcar again appears with its transform in
Figures 2.7a and 2.7b. The function has been extended periodically to grid 02jV,
shown in Figure 2.7c, and now has each of the boxcars within the interval instead
of at the ends of the interval. Its transform, pictured in Figure 2.7d, displays
exactly what is expected from the above analytical results. Odd coefficients are
now zero, while even coefficients are twice what they were in Figure 2.7b, making
this transform much more oscillatory than the original transform.
Function 3. The Gaussian curve (Figures 2.8a and 2.8b) displays many
of the same characteristics. The original function on grid QN has been extended
to grid n2N, as shown in Figure 2.8c, and now displays two Gaussian curves
shifted by 37T. The transform of the extended function (Figure 2.8d) again shows
a curve where every other point is zero, but this function can be enveloped by a
curve that is exactly twice the amplitude of the function on AN.
Function 4. Finally, the triangle function and its transform (Figures
2.9a and 2.9b) display the same characteristics when the points from grid Q,N
are extended to grid fl2N (Figure 2.9c). The new transform on grid A.2N (the
sine2 function) is highly oscillatory due to the alternating zeroes, but is still
enveloped by the function with twice the amplitude of that on grid A2N.
2.3.2 Zero Extension
We now consider extending the original sequence to 2N points by padding


2
Figure 2.7
Cl2N with Periodic Extension for x(t) = Boxcar function
(a) x(t) on (b) F(f) on AN (c) x(t) on f)2N (d) F(f) on A2N
to
Oi


Figure 2.8
flN n2N with Periodic Extension for x(t) = e~vt2
(a) x{t) on nN (b) F(f) on AN (c) x(t) on tl2N (d) F(f) on A2N


Figure 2.9
£lN Q2N with Periodic Extension for x[t) = Triangle function
(a) *(0 on UN (b) F(f) on AN (c) x(t) on 0,2N (d) F(f) on A2N
to
00


29
with zeroes at both ends. The sequence {xn} is then defined as
{0 for N xn fory 0 for y < n < N 1
The reason for expanding in this way is that it will take a signal that
has high amplitudes on both ends of the interval and make it a signal where the
high amplitude signal is now nearer to the center of the interval.
To again explore the relationship between {X*} and {Xk}, note as before
that the transform can be broken into the three intervals corresponding to the
original grid, giving
N-1
Xk = £
n=-N
-f-l *-l N-l
£ *.<* + £ + £ xnutfr
n=-JV n=-f
f-1
0 + X"UJ2N + 0 for iV < k < N
f
If we examine the case for k even, say k = 2p, we find that Xk = X2p =
X. However, when k is odd (k = 2p + 1) we have
A*. = = £ *.<4$*"
9
f-1
= X] (u2Nxn)u21V
n= T
£L-l
= 12 {wNxn)utr for < p < f 1,
V
n=-T
which is just the DFT of a rotated sequence. Hence, by the shift theorem
X2P+1 DFTff{ujtfXn}
= Xk.
2


30
However, since k is by definition odd here, Xk is actually located at a half-grid
point of lN. This may also be considered an interpolated value from the original
transform sequence {Xjt}. If the continuous function in the time domain is time-
limited, then equation (1.8) is applicable and the value of these odd coefficients
may also be determined (or verified) using the sampling theorem. Thus, the
relationship between grids AN and A2N for extension by zeroes on both ends is
just
Xk = Xk for -N < k < N- 1.
Function 1. Starting with the dual mode sine wave, pictured with its
transform in Figures 2.10a and 2.10b, we can see how extension by zeroes at
both ends of the function results in a very abruptly changing signal as seen in
Figure 2.10c. By extending the function to span the interval [27r, 27t] using
zero padding at both ends, we have essentially multiplied the function x(t) =
8$in(J) + szn(16t) by a boxcar function centered at zero with width 2ir. In the
frequency domain then we have convolved the original transform function F(f)
with a sine function. This results in a transform (Figure 2.lOd) that now has
many sidelobes instead of the clean two mode transform. The magnitude of the
transform alternates between zero (k even) and non-zero values (k odd). Since
the continuous version of the sampled function is infinite the sampling theorem
for odd values does not apply here.
Function 2. The shifted boxcar function also behaves unexpectedly.
When the original function is transferred from grid to grid Q,2N by zero
extension (Figures 2.11a and 2.11b), we have again in essence multiplied the
original function by a boxcar centered at zero with width 2. This is the same
as convolving with a sine function in the frequency domain. However, this new
function on Q,2N is no longer periodic. In order for this function to be periodic,


Figure 2.10
fl2N with Zero Extension for x(t) = 8sin(t) + sm(16t)
(a) x{t) on nN (b) F(f) on \N (c) x(t) on ft2N (d) F(f) on A2N
c*


2
(b)
(a)
Figure 2.11
ilN > fl2Ar with Zero Extension for x(t) = Boxcar function
(a) x{t) on HN (b) F(f) on \N (c) x(t) on 02" (d) F(f) on A2Ar
co
to


33
each of the boxcars would have to be centered at 1 or the function would have
to be sampled only over the interval [1.75,1.75]. Because of this non-periodic
nature and the convolution with the sine function, the transform of the new
function, pictured in Figure 2.lid, is very oscillatory. However, a plot of both
transforms plotted together will show that the functions do in fact agree at the
even points. Figure 2.12 shows how one sidelobe from the function on A2N en-
compasses two sidelobes of the function from AN. The values at the odd points
obviously do not agree with the original transform. The reasons for this are
currently not fully understood.
Function 3. Extending the original function (shown with its transform
in Figures 2.13a and 2.13b) with zeroes better approximates the infinite func-
tion x(t), but because of the improved resolution on A2N, it also provides a
much smoother transform function. The new transform, shown in Figure 2.13d,
demonstrates how the odd-numbered points on A2N are actually values interpo-
lated from the original transform. The closer spacing of grid points in the new
transform shows that a smoother, more accurate transform of the continuous
function is obtained.
Function 4. In the case of the triangle wave (Figures 2.14a and 2.14b),
extension by zero padding also improves the transform. The time-limited triangle
function possesses the Fourier transform sinc2(f), and extending the function
with zeroes (Figure 2.14c) will not change this. However, the improved resolution
in the frequency domain (Figure 2.14d) does help smooth the appearance of the
original transform function. This improvement is most noticeable at the central
peak (/ = 0).
2.4 Case 3: Extension and Injection QN flNe
Now we will combine injection and extension to a sequence of N numbers


Figure 2.12
F(f) on A" and F(f) on A2N
co


Figure 2.13
flN Sl2N with Zero Extension for x(t) = e-,rt2
(a) x(t) on ClN (b) F{f) on AN (c) x(i) on Q,2N (d) F(f) on A2N
co
Cn


QN fl2N with Zero Extension for x(t) = Triangle function
(a) x(t) on UN (b) F(f) on \N (c) x(t) on WN (d) F(f) on A27V
cc
Ol


37
to produce a new sequence of N numbers. As in the case where the points from
grid £lN were moved to grid we will again sample by selecting only the even-
numbered points. This new coarsely sampled grid will be called QNc. To extend
the grid so that it contains a full N points, extension methods similar to those
in the previous section will be employed, that is, periodic and zero extension.
2.4.1 Periodic Extension
The sequence {xn} injected to f2 2 yields the sequence {xn}, on grid QNc
given by
*2n+N for y < n < 1
xn = 2n for f < n < £ 1
. x2n-N for J < n < ^ 1
To examine the relationship between {Xfc} on grid and {Xfc} on grid
hNe, first split the transform into three parts:

E **# + E + E
n=-f

E x2n+NUfJ + E X2+ E ^2n-N^IV
nk
*
£-1
__ N
n 4
*-i

(n~%)k , nk , (n+y)fc
= 2^ X*nUN + 2^ X2nUN + 2^ X2n^N
71=0
__ N
n T
i£_l
nk i
__ .v
n T
Nk
-1
UN 2 E x2nUpf + E XlnW1N + V E X2
n=0
4F
n-T
, N N
for < k < .
2 ~ ~ 2
Nk
Since uN 2 = utf the first and third terms of this last equation combine to
yield
Nk *
£-1
f-1
Xk = WjV2 21 x2n^Jv + E X2nUnu
£
n~" 4


38
T-l
At = (1+W;v*) ^2 l2nW]vfe for Y < ^ < y.
Note also that urf = eAw* = etirk = (1)*, so that
X* = (l + (-l)*) £ XtoU,#
N
n- 4
When k is odd all terms are zero, but when k is even, say k = 2p, we have
S-1
i2p = 2 E x2nu#p
= 2 I2Uif
n_ w 2
n T
= 2 DFTz {x2ti}
= 2yp for-£ where Vj, is just the transform of the y-point series of even points only.
Therefore, the relationship between {A*} on AN and {A*} on using
periodic extension is
A*, = |
0 if k is odd
2y*c if k is even
for -y < A: < y 1.
A look at the previously seen functions for this grid extension is in order now.
Function 1. The dual mode sine function and its transform are shown
in Figures 2.15a and 2.15b. In moving the function from grid QN to (Fig-
ure 2.15c), no information is lost from the original signal because the original
sampling interval (tt/256) is well above the aliasing point. That is, even when
the sample spacing is doubled, both modes of the sine wave are still easily dis-
tinguishable in the transform (Figure 2.15d). The only difference between the
original transform and the transform on AjV is that the sampling interval in the
frequency domain is now half of what it previously was, which is reflected in the
width of the peaks for each mode.


Q,N SlNc with Periodic Extension for x(t) = 8sin(t) -j- sm(16t)
(a) x(t) on SlN (b) F(f) on A" (c) x{t) on (lN (d) F(f) on ANc
CO
CO


40
Function 2. The transform of the injected and extended boxcar function
behaves in a very predictable fashion. The new function (shown in Figure 2.16c)
is again a periodic function so its transform should behave in a manner very
similar to that of Figure 2.16b, the original transform on AN. The transform on
ANe (Figure 2.16d) has a shortened frequency interval (now [8,8]) and every
odd point is zero, as shown in the analytical results. The values of the transform
at the even points are non zero; however, a plot of both transforms together
(Figure 2.17) will show that they are very close indeed, especially near the center
of the spectrum.
Function 3. The transform of an injected and extended Gaussian func-
tion displays many of the same characteristics. The new function (Figure 2.18c)
is still very smooth and obviously periodic. Its transform (Figure 2.18d) shows
zeroes at the odd points and values very near the values of the original transform
at the even points.
Function 4. The triangle function and its transform also change very
little when injected and extended from grid to flNe. The transform of the
new function (Figures 2.19c and 2.19d) again has a shortened frequency domain
and a very oscillatory nature, due to the zeroes at odd points.
2.4.2 Zero Extension
Finally, we shall consider injecting the sequence {xn} from grid Q.N to
grid ClNc and extending by zeroes, forming the new sequence {xn} where
0 for _£<<_£_
2 4
*^2 n for £ < n < £ 1 4 4
. .0 for £ In order to examine the relationship between {A*} and {A*} we once again split


2
-10
0
-20
Figure 2.16
flN > ClNc with Periodic Extension for x(t) = Boxcar function
(a) x(0 on aN (b) F(f) on AN (c) (i) on (d) F(f) on A"
10
20


16


2
(a)
-4 -2 0 2 4
Figure 2.18
ttNc with Periodic Extension for x(t) = e_,rl*
(a) x(t) on nN (b) F(f) on AN (c) x(t) on SlN* (d) F(f) on ANc
CO


Figure 2.19
SlNc with Periodic Extension for x(t) = Triangle function
(a) x(t) on SlN (b) F(f) on AN (c) x(t) on (lNc (d) F(f) on AN


45
{xn} into three pieces:
_ N_1 ££_1 W_1
Xk = X *WAr* + + X ^"^AT*
-* n=-f n=*
= 0 + X a^nWjJr* + 0 for -y < fc < y 1.
When fc is even, say k = 2p, we have
T-l
^2p = X X2nLJAT2P
T"1
= X I2n^P
__ w 2
nT
= DFTtf,{x2n}
= rp for y < p < y 1.
However, when is odd, say fc = 2p + 1, we again have a rotated sequence:
^2p+l = X X2n^AT2P+1^
-*
y-1
= X (UiC2n)tJi'
n_ N 2 2
n=-T
= DFTz{R{x2n}}
= Xp+i for < p < % 1.
If we then substitute | for p + we find that
X2p+1=X fory This is again a case where Xk is actually a value from a half-grid point of QN
which is interpolated from its neighboring coefficients.
The transform of a sequence that has been injected and extended with
zeroes on both ends may be expressed in terms of the original transform in the


46
following way:
{Xk if k is odd
Yk if k is even
2
forf <* Perhaps a few pictures relating the transforms on grids AN and ANc will be
helpful.
Function 1. In Figures 2.20a and 2.20b, the original signal x(t) =
8sm(f)+sm(16i) and its transform appear. The results of injecting this sequence
to grid QNc are shown in Figure 2.20c and again, due to the high sampling rate
on the original grid, sampling only the even points of {xn} does not degrade the
signal. However, extending with zeroes at both ends introduces leakage around
both modes in the frequency domain (Figure 2.20d).
Function 2. When the shifted boxcar function is injected and extended
with zeroes (Figure 2.21c), it is no longer a periodic function, so its transform
behaves uncharacteristically. This new transform (Figure 2.21d) is very similar
to the transform of the sequence that has been extended with zeroes but not
injected to a coarser grid (Figure 2.7d).
Function 3. The Gaussian curve again shows an improvement from the
original transform (Figures 2.22a and 2.22b) because of the zero extension. The
new signal (Figure 2.22c) is a better approximation of the infinite function
x(t) = e-irfa, but because of the increased resolution in the frequency domain,
its transform is now much smoother (Figure 2.22d).
Function 4. Finally, when the triangle function (Figures 2.23a and 2.23b)
is extended by zeroes on both ends of the interval (Figure 2.23c), the transform
again is an improvement of the original transform due to the higher resolution
on ANc.


10
10
5
0
-5
-10
-10 -50 5 10

Figure 2.20
flN SlNi with Zero Extension for x(t) = 8sin(t) + sm(16Z)
(a) x(t) on nN (b) F(f) on AN (c) x(f) on 0,Nc (cl) F(f) on ANc
5
10


£lNc with Zero Extension for x(t) = Boxcar function
(a) ar(0 on ft* (b) F(f) on A* (c) x(t) on ft* (d) F(f) on A*c
tp-
GO


Figure 2.22
fiN - SlNc with Zero Extension for x(t) = e~ir{2
(a) x{t) on (b) F{f) on \N (c) *(*) on ClN (d) F(f) on ANc
CO


6
4
2
0
2
-1
er
4
2
0
2
-1
80
60
40
20
0
-5 0 5 10 -10 -5 0 5 10
80
60
40
20
0
-5 0 5 10 -10 -5 0 5 10
Figure 2.23
flN SlNc with Zero Extension for x(t) = Triangle function
(a) x(t) on ClN (b) F(f) on AN (c) x(t) on flNc (d) F(f) on ANc
(d)
(b)
Cn
O


51
2.5 Summary
Table 2.1 lists all of the preceding results for each grid.
Grid X, k
tlN Xk = Yk -4<*<£-l
nN n2N Periodic Extension ~ JO if A: is odd k ~ \ 2X| if k is even -N < k < N- 1
nN n2N Zero Extension Xk = Xk 2 -N < k < N-l
nN Periodic Extension - JO if Ar is odd k ~ \ 2F| if k is even
SlN nNc Zero Extension f Xk if k is odd ^k | Yk ii k is even > 2 -%<*<%-1
Table 2.1
Multilevel Transform Results


CHAPTER 3
FUTURE DIRECTIONS:
MULTILEVEL TRANSFORM SYSTEMS
The development of Fourier transforms on multiple grids suggests the
possibility of multilevel systems of DFTs involving transform on grids as shown
in the previous chapter. Multilevel transform systems also suggest several ques-
tions about intergrid transfers: How well do the frequency spectra on these new
grids actually represent the original frequency spectra? Can a DFT on a grid
that is more sparse than the original grid result in a transform that preserves in-
formation from the original DFT while reducing the overall computational cost?
Can the information in the new transform be obtained directly from the DFT
of the full sequence? While all of these questions cannot be fully answered at
this point, it opens many possibilities for future work. A look at some possible
multilevel transform systems is in order.
3.1 Transform System I
In Case 1 from Chapter 2, a sequence of points {xn} on grid was
injected to grid fiT by sampling only the even points of the sequence. This new
grid still had length T, but the new sequence {xn} consisted of N /2 points, with
N.
sample interval 2At. Define Ifi to be the injection operator that acts on the
E
sequence {xn} and produces {xn}, that is, Ifi {x} = {xn}.
In the frequency domain, the original transform sequence {A*} on AN
had length F and sample spacing A/, but the new sequence {A*} on had
length F/2 and sample spacing A/. Now we must ask: Is there some clearly


53
definable operator, say Tfa, that produces the sequence {-X*} from {Xjt}, i.e.
does Tft {A^} = {Xk}? Figure 3.1 demonstrates this possible relationship.
If the operator Tft is a clearly defined one, then we have two ways
~ f£ iL
through which to obtain the sequence {A^} on A 2: DFTs{Ift {xn}} or
N .
Tft{DFTrf{xn}}. Obviously, the first method involves fewer computations in
the DFT and seems to be the obvious choice. Its preference over the second
method must be evaluated by determining the existence of the T ft operator.
Recall that the FFT algorithm performs a splitting of the original series
of points by even and odd restriction. The injection operation I ft {xn} is exactly
this first split, keeping only the even points in the new sequence.
It was shown earlier that the values on the grid A 2" are
xk= £ x2nn%k for
____K
A look at the difference between Xk and Xk is one way to determine the
correction that must be applied to Xk in order to recover Xk.

*-1
Xk-Xk = £ *2nu#
2nk
71 T
/t-i
n T
T-l
f-1
7! x2n+lW^n+1^ | x2nUtf'k.
V=-T n=T

This last step just splits the series for Xk into even and odd terms. The first
and third terms now cancel, leaving
t-1
Xk-Xk = £ x2n+1u$n+1)*
n=T
= Ujft DFTn{x2n+l}
= ukNZk .
This last Zk term is just the other half of the FFT butterfly relation, i.e. the DFT


N I -i I t -1 II II I l-M-l I I
-N 0
2 At
N
2
N
''
1---1---h
0
2At
MlZ
iI\
At
j,n( =>|Xi.)
dftn
f-
-N
2
I I I I I I I 1 I I
0
,N
Y
N
2
N
'1
|7} 4=Mx(
DFTn
2
<111 -11
-N 0 N ,
4 At A'1
N
A2
Figure 3.1
Transform System I
MlZ


55
of the odd points in the sequence. This result is not unexpected since Xk also
equals Y* and by definition Xk = Yk+u^Zk so XkXk = Yk+uj^ZkYk =
Therefore, the operator Yfc is one which must perform the first split of
the inverse DFT, throwing out the points from the DFT of the even points of
{xn}. The grid A"? then introduces no new information about the frequency
spectrum that is otherwise unobtainable from the original frequency spectrum.
It might also be mentioned here that several alternatives to injection of
the even points exist for transferring data from flN to Some possibilities
include injection of the odd points, averaging the odd and even points, and mul-
tiple point weighted averages. Further work may be sought in those directions.
3.2 Transform System II
Case 3 from Chapter 2 introduced the grid ClNc which had twice the
sample spacing of the original grid but was extended on both ends to form a
sequence of N points. This new grid then produced a frequency domain grid
with twice the resolution of the original frequency grid but half the length. In
both cases the transform of the original sequence and the transform of the new
extended sequence required performing an N-point DFT.
Define the extension operator that extends and injects the data from grid
Qn to ClNc as EjF. Similarly, we would like to define an operator in the frequency
F
domain that compresses the data from grid A.N to A.Nc. Call this operator Cp.
The sequence {A*} on S.Nc could thus be obtained from the original sequence of
points in two ways: DFT^{Ep {xn}} or Cp {DFTm{xn}}. These operators and
their grids are shown in Figure 3.2. We would again like to study this operator
EL
Cp in order to see whether the data on is in fact recoverable from A.N.


n
N
1 I I I I Ml
-N ^ 0
2 At
Nc
N
o
Nc
H
-N
2
1--------1-------i
2At
0
ZIN
{ Xn | {Xk}
dftn
M H H M I
-N *0
2 AI

C
Nc
N

( Xn| 4=^ {**(
dftn
-N V 0 N
2 A! 2"
2
Figure 3.2
Transform System II
CJl
o>


57
3.2.1 Periodic Extension
Recall that, for the case where {in} was extended periodically, we
showed that
T-1
X = (l+(-l)) £ for-£<*<£-l
{0 if A: is odd
2 £ x2n^k if k is even
n- 4
The fact that the odd points are all zeroes means that no new information has
been added, even though the resolution of the grid in the frequency domain is
A//2. But how closely do the even coefficients compare with those from the
original transform? Obviously, when k is odd, the difference between Xk and Xk
is just Xk. For k even, first note that X2k on ANc corresponds to Xk on hN for
A. < k < ^ l. That is, only points in the center of the interval on AN may
be compared to points on ANc. Then we have
Xk-X2k =
T-1
51 XnN -2 J2 x2u#fc
s *
T

= J2 X* *UNk+ 51 Zin+lWtf1* -2 2
(2n+l)A:

4F )

V' ^ ,2nk i .k ~ ,2nfc
*

51 X2nUnl n_N 1 a- 4 + 5Z X2n+1 a/5 __ W 2 nT
__ N
n T
= -Yk+ukNZk for -j- < A: < ^ 1,
which is just the Cooley-Tukey butterfly relation equation with the transform of
the even subsequence negated. Thus calculating {Afc} from {A*} would mean
splitting the original series into even and odd subsequences and adding and


58
subtracting their DFTs to the full N-point DFT. Thus the sequence {X*.} is
certainly recoverable from {Xfc} (or vice-versa) but at a cost that may not be
justifiable.
3.2.2 Zero Extension
For the case where the sequence {xn} on is extended by zeroes on
both ends to fit the grid ClNc, recall that
Xk if k is odd
Xk={
E ji if is even
V 4
for y < & < y 1.
We will again look at the difference between Xk and Xk for each point.
For odd k, we know that the midpoints between each of the Xk correspond
directly to odd-numbered points of {X*}. That is, we want to look at the
difference
XkH-X2k+i for^ <* where the Xk+i are values between grid points and the X2k+i are the odd points
on \Nc that correspond to those midpoints of A.N. In secion 2.4.2 we saw that
X2p+i = Xp+i for ^ < p < ^ 1 so if we change variables and use k over the
range ^ < k < j- 1 we have X2k+i = Xk+k. Thus
*t+, X2M = Xi+i -Xk+i = 0 for -a <(: This says that the values of the odd points of {X/.} are exactly the value of
interpolated coefficients from {Xjt}. The value of these interpolated coefficients
may be determined using the sampling theorem if the original function in the
time domain is time-limited.
When k is even, we again want to compare values of X2k and Xk:
f"1 T"1
x-x2k = £ *<- £
r. £ ---SL


59
/4F-i f- \
= £ Z2nV%lk + 2 I2r,+lW$n+1)A!
W-T n=~T I
T"1
v (2n+l)fc
= 2^ x2n+iuyN
*
= ukNZk for-f __ H
71 T
X2
nW
2nJfc
JV
which is just the transform of the odd subsequence rotated by i.e. the second
half of the Cooley-Tukey butterfly relation.
In this case where zero extension is used, neither the odd nor even coef-
ficients are easily determined from the original transform. But it is worth noting
that information appears to be gained with the new transform. The resolution
of the new transform grid ANe is better than the original grid AN, and we now
have values that have been interpolated at no extra cost, i.e. an N-point DFT
was performed in both cases. The odd-numbered points of {A*} introduce in-
formation that may be used to, in effect, double the resolution of {At} without
actually interpolating values from the original signal {xn}.


CHAPTER 4
SUMMARY AND CONCLUSIONS
Chapter 2 showed several cases of multilevel DFTs and the analytical
results expected from those grid transfers. These results were also demonstrated
graphically through the display of several functions and their DFTs. It was
shown that injecting a sequence of N points to an y-point grid saved compu-

tational work but did not, however, produce any new information or knowledge
about the original transform.
Extending an iV-point sequence to 2N points only appeared profitable
if the extension was performed by padding with zeroes at both ends of the
interval. Periodic extension of the signal only managed to produce zeroes at
every other point in the transform, thereby giving no new information about
the original DFT. Zero extension, however, served to interpolate the values in
the original transform and thus produced a frequency spectrum as broad as the
original, but with twice the resolution. The cost of this added information is 2N-
point DFT. However, some consolation may be noted in that the alternative to
producing a 2iV-point transform by zero extension is to interpolate the original
sequence of data values, {xn}, to 2N points and then perform a 2,/V-point DFT.
Zero extension produces no extra work and does not introduce interpolated data
values in the time domain. So if computational cost is not an issue but improved
resolution in the frequency domain is, extending a sequence to 2N points by zero
extension is a very reasonable option.
We obtained similar results for sequences injected to an y-point grid
and then extended to fill an IV-point grid. Extending the sequence periodically


61
only added zeroes at all the odd points in the frequency domain, whereas ex-
tending with zeroes at both ends introduced interpolated values in the frequency
spectrum. However, due to the relationship between the time and frequency do-
mains, the length of the frequency spectrum on this new grid is only half the
length of the original frequency spectrum. So if increased resolution is desired
in the frequency domain but computational cost is a concern, this type of grid
transfer is preferable. This method can at least give a frequency spectrum with
better resolution over the center half of the frequency interval without increasing
the computational cost of performing the DFT.
Finally, two possibilities for multilevel transform systems were presented
to suggest further multigrid transform methods. Methods of recovering the orig-
inal transform from a new transform were discussed as well as the possiblility of
gaining information about a transform by moving it to another grid.


62
BIBLIOGRAPHY
[1] Bergland, G.D., A Guided Tour of the Fast Fourier Transform. IEEE
Spectrum, Vol. 6, No. 7, July 1969.
[2] Bracewell, R.N., The Fourier Transform and its Applications. McGraw-Hill,
Inc., New York, 1978.
[3] Briggs, W.L., A Multigrid Tutorial. SIAM, 1987.
[4] Briggs, W.L., Henson, V.E., The FFT as A Multigrid Algorithm. Draft,
Jan. 1989.
[5] Brigham, E.O., The Fast Fourier Transform. Prentice-Hall, Inc., Englewood
Cliffs, New Jersey, 1974.
[6] Cizek, V., Discrete Fourier Transforms and Their Applications. Adam Hilger
Ltd., Bristol, England, 1986.
[7] Dahlquist, G., and Bjorck, A., Numerical Methods. Prentice-Hall, Inc., En-
glewood Cliffs, New Jersey, 1974.
[8] Mersereau, R.M., Oppenheim, A.V., "Digital Reconstruction of Multidimen-
sional Signals from Their Projections. Proceedings of the IEEE, Vol. 62,
No. 10, October 1974.
[9] Press, Flanner, Teukolski, Vetterling, Numerical Recipes: The Art of Scien-
tific Computing. Cambridge University Press, 1986.
[10] Stark, H., Woods, J.W., Paul, I., Hingorani, R., An Investigation of Com-
puterized Tomography by Direct Fourier Inversion and Optimum Interpo-
lation. IEEE Transactions on Biomedical Engineering, Vol. BME-28, No.
7, July 1981.
[11] Stark, H., Woods, J.W., Paul, I., Hingorani, R., Direct Fourier Recon-
struction in Computer Tomography. IEEE Transactions on Acoustics,
Speech, and Signal Processing, Vol. ASSP-29, No. 2, April 1981.
[12] Yossef, T., Bi-Level Properties of Fourier Transform. Graduate Thesis,
Weizmann Institute of Science, Rehovat, November 1988.


Full Text

PAGE 1

MULTILEVEL DISCRETE FOURIER TRANSFORMS by Michael Anne Hare B.S., University of Texas, 1982 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master of Science Department of Mathematics 1989

PAGE 2

This thesis for the Master of Science degree by Michael Anne Hare has been approved for the Department of Mathematics by William L. Steven F. McCormick Roland A. Sweet /} A p JCJ Y't Date __

PAGE 3

Hare, Michael Anne (M.S., Applied Mathematics) Multilevel Discrete Fourier Transforms Thesis directed by Professor William L. Briggs lll In many applications of the Fast Fourier Transform (FFT) computations are necessary in both the physical space and the transform space. By manipu lating the grid in one space, the grid in the other space is altered in a manner consistent with the properties relating the two spaces. This change of grids in the time domain (or physical space) which produces a new sequence of values to be transformed may be accomplished in several ways, five of which are pre sented in this thesis. In each case, the resulting grid in the frequency domain (transform space) is known and the values expected from the new transform may be shown analytically. In some cases a change of grids in the time domain results in a higher resolution grid in the frequency domain. Whether this higher resolution grid actually provides new or insightful information about the frequency spectrum of a function will be investigated. In other cases, resolution in the frequency domain is not lost so we will investigate whether we have lost or gained information contained in the frequency spectrum by transferring the input sequence of data to another grid. Knowledge about multiple transform grids and their related output may then be used to advantage to develop systems of multilevel Fourier transforms. The form and content of this abstract are approved. I recommend its publication. Signed -Faculty member illafieOf thesis

PAGE 4

lV CONTENTS CHAPTER I. INTRODUCTION 1 1.1 The Fourier Transform . . . . . . . .. . . . . . . 1 1.2 D FT Properties ........................ . . . . . . 3 1.2.1 Linearity Property. . . . . . . . . . . 3 1.2.2 Shift Properties . . . . . 3 1.2.3 vs. Frequency Domain . . . . . . . . 4 1.2.4 Convolution . . . . . . . . . . . . . . . . 5 1.2.5 Properties of WN 5 1.2.6 Sampling Theorem . . . . . . . . . . 6 1.3 The Fast Fourier Transform . . . . . 9 II. DFTs ON MULTIPLE GRIDS .. . . .. . . . . .. .. . .. .. .. 12 2.1 Grid Definitions ................................... 13 2 2 C 1 In . r.N r.!!. ase : JeCtion ._l' 2 15 2.3 Case 2: Extension nN -+ n2 N 22 .3.1 Periodic Extension . . . . . . . . 22 2.3.2 Zero Extension . . . . . . . . . . . . . . 25 2.4 Case 3: Extension and Injection nN -+ nNe 33 2.4.1 Periodic Extension . . . . . . . . . . . . 37

PAGE 5

v 2.4.2 Zero Extension . . . . . . . . . . . . . . 40 2.5 Sununary . . . . . . . . . . . . . . . . . . . . 51 III. FUTURE DIRECTIONS: MULTILEVEL TRANSFORM SYSTEMS . . .. .. .. .. . .. .. . . . .. 52 3.1 Transform System I . . . . . . . . . . . . . . . 52 3.2 Transform System II . . . . . . . . . . . . . . . 55 3.2.1 Periodic Extension . . . . . . . . . . . . . 57 3.2.2 Zero Extension . . . . . . . . . . . . . . 58 IV. SUMMARY AND CONCLUSIONS .. .. .. .. .. .. .. .. .. .. .. 60 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . 62

PAGE 6

vi TABLES Table 2.1 Multilevel Transform Results . . . . . . . . . . . . 51

PAGE 7

Vll FIGURES Figure 1.1 The Sampling Theorem . . . . . . . . . . . . . . . . 7 2.1 Time and Frequency Domain Grids . . . 14 2.2 nN"----+ for x(t) = Ssin(t) + sin(16t) . 17 2.3 nN ----+ for x(t) = Boxcar function . . . . . . 18 2.4 ON ----+ for x(t) = e-1rt2 20 2.5 nN ----+ for x(t) = Triangle function.................... 21 2.6 nN ----+ n 2 N with Periodic Extension for x(t) = 8sin(t) + sin(16t) 24 2.7 nN ----+ n 2 N with Periodic Extension for x(t) = Boxcar function . . . . . . . . . . . . . 26 2.8 nN n 2 N with Periodic Extension for x(t) = e-"ll"t2 27 2.9 nN ----+ n 2 N with Periodic Extension for x( t) = Triangle function . . . . . . . . . . . . . . . 28 2.10 nN ----+ !12 N with Zero Extension for x(t) = Ssin(t) + sin(16t). 31 2.11 nN ----+ n 2 N with Zero Extension for x(t) = Boxcar function . 32 2.12 F(J) on AN and F(J) on A2N 34 2.13 nN ----+ n 2 N with Zero Extension for x(t) = e-7!"t2 35 2.14 nN ----+ n 2 N with Zero Extension for x(t) = Triangle function 36 2.15 nN ----+ nNe with Periodic Extension for x(t) = Ssin(t) + sin(16t) . . . . . 39

PAGE 8

Vlll 2.16 nN --+ nNe with Periodic Extension for x ( t) = Boxcar function . . . . . . . . . . . . . 41 2.17 F(f) on AN and F(J) on ANe .. .. .. .. .. .. .. .. .. .. .. 42 2.18 nN --+ nNe with Periodic Extension for x(t) = e-1!'t2 43 2.19 nN --+nNe with Periodic Extension for x(t) = Triangle function . . . . . . . . . . . . . . . 44 2.20 nN --+ nNe with Zero Extension for x(t) = 8sin(t) + sin(16t) . . . . . . . 47 2.21 f!N --+nNe with Zero Extension for x(t) = Boxcar function 48 2.22 nN --+ nNe with Zero Extension for x(t) = e-1!'t? 49 2.23 nN --+ !}Ne with Zero Extension for x(t) = Triangle function 50 3.1 Transform System I . . . . . . . . . . . . . . . . .. . 54 3.2 Transform System II ................... ;. . . . . . . . 56

PAGE 9

CHAPTER 1 INTRODUCTION The fast Fourier transform (FFT) is a powerful and very efficient al gorithm for computing the discrete Fourier transform of a series of complex numbers. The FFT has been widely applied in areas such as signal processing, antenna and radio wave theory, data analysis, solutions of PDE's, and image reconstruction. The work in this thesis was motivated by questions that arise in multilevel image reconstruction algorithms. However, the results should be applicable to a variety of other problems in which computation takes place in both a physical space and a transform space. In problems of this nature, it is generally possible to construct multiple grids in both spaces and use this system of multiple transform grids to advantage. The purpose of this thesis is to investigate such systems of grids. 1.1 The Fourier Transform The Fourier transform identifies or distinguishes the different frequency sinusoids and their respective amplitudes which combine to form an arbitrary waveform. The Fourier transform of a continuous function x(t) is defined as X(!) = j_: x(t)e2n-ift dt (1.1) where x(t) is the waveform to be decomposed into its frequency components. If the integral exists for every value of the parameter f then equation ( 1.1) defines X(!), the Fourier transform of x(t).

PAGE 10

2 The inverse transform allows the reconstruction of a function of time from its Fourier transform. The inverse is defined as x(t) =I: X(f)e-2rrift df (1.2) If the functions x(t) and X(!) are related by equations (1.1) and (1.2), the two functions are termed a Fourier transform pair and their relationship is indicated by x(t) <==?X(!). For computational reasons, it is necessary to discretize the Fourier transform. The discrete Fourier transform (D FT) of a periodic sequence of N complex N N for --< k < --1 2 --2 where { Xk} is another sequence of N complex numbers. Its similarity to the continuous form of the transform is readily visible. For notational ease, the transform sequence may also be denoted N N for --< k < --1 2 --2 (1.3) 2tri where WN = err. This relationship between the sequences {xn} and {Xk} is denoted The elements of the sequence {xn} are considered to reside in the time domain, while the sequence {Xk} is associated with the frequency domain. Note that the sequence {Xk} also has a period of length N. The inverse DFT is defined as N N for --< n < --1. 2 --2 (1.4)

PAGE 11

3 The fact that equations (1.3) and (1.4) are inverses of each other may be verified by substituting (1.3) into (1.4): 1 N I: Xm m=-lf n=-lf 27l"inm 21fink e--n-e--rr(1.5) This last summation in equation (1.5) equals proving that the right-hand side of (1.5) equals { N if m = k thus 0 otherwise 1.2 DFT Properties The definition given above in equation (1.3) may be used to demonstrate several properties of the DFT. This list of properties is by no means complete, but rather includes only those properties that will be useful in the following chapters. 1.2.1 Linearity Property The linearity property states that the transform of the sum of two sequences is the sum of the transforms. If { Xn} and {Yn} are two periodic sequences with period N whose transforms are and respectively, then 1.2.2 Shift Properties Shifting a sequence of values left or right in the time domain is equivalent to a rotation in the frequency domain. Define Sm { Xn} = { Xn-m} to be the sequence obtained by shifting {xn} to the right m units. Then the shift property

PAGE 12

says that N N for --< k < --1. 2 --2 4 The proof of this property follows immediately by applying equation (1.3) to the shifted sequence. Similarly, a shift in the frequency domain corresponds to a rotation in the time domain. If we define Rm { Xn} = { wr;,r Xn} as the sequence obtained by rotating { xn} in the complex plane in a counter-clockwise direction, then the shift property in the frequency domain says that 1.2.3 Time vs. Frequency Domain N N for --< k < --1. 2 --2 Define t:l.t to be the sampling interval of the N points that make up the sequence { Xn} in the time domain and t:l.f to be the corresponding sampling interval in the frequency domain. If we discretize the continuous form of the Fourier we have 00 X(kt:l.f) L x(nt:l.t) e2trint:.tk!:t.f for __: oo < k < oo. n=.-oo However, over the finite interval k -1, the DFT Xk was defined as l!-t 2 271"inlc Xk = Xn e----n-, n=-lf leading to the conclusion that t:l.tt:l.f = 1 This equation defines the relationship between the sampling intervals of the time and frequency. domains. If we also. define the length of the time domain as T, where T = N t:l.t and the length of the frequency domain as F, where F = N t:l.f, then it follows that T F = N.

PAGE 13

5 1.2.4 Convolution Given two continuous functions of time, x(t) and z(t), the convolution of x(t) and z(t) is defined as y(t) = /_: x(T)z(t-T) dT. In the discrete case, the convolution of two sequences {xn} and {zn}, both of which are periodic in N, is defined by the summation Yk = L Xn Zk-n n=-lf. For convenience of notation, discrete convolution is normally written as The discrete convolution theorem (Brigham [5]) states that the DFT of the convolved sequence is the product of the transforms of the original sequences; that is, 1.2.5 Properties of WN By the definition of WN = ea;i, two properties may be quickly identified which will be very helpful in later chapters: nk 2winlc 2.ri2nlc 2nk nlc w N = e ---yv= e ---ur= w 2 N = w ]}_ 2 f!!!. 2wiNic ; k ; 2.riNic _l!!!_ wrJ = e-rr:r = e1r' = ( -1) = e-1ra = e--rr:r wN 2 (1.6) (1. 7)

PAGE 14

6 1.2.6 Sampling Theorem The sampling theorem states that if the Fourier transform of a function x( t) is zero for all frequencies greater than a certain cutoff frequency fc, i.e. the frequency function is band-limited, then the continuous function x(t) can be uniquely determined from a knowledge of its sampled values (Brigham [5]). A graphical demonstration of this fact is worth presenting. First assume we have a continuous function x(t) (Figure l.la) which has been sampled in the time domain with sample spacing that does not exceed D.t == 2}c. This spacing will assure that the signal is sampled at a rate that is twice the highest frequency (the cutoff frequency) and thus avoids aliasing of any part of the signal. Sampling of the function x(t) amounts to multiplying the original signal by the shah Junction: 00 I II(t) = L o(t-nD.t) n=-oo which is just a train of delta (or impulse) functions with sample spacing D.t. III(t) and its transform, III(!), are shown in Figure l.lb. According to the convolution theorem, this multiplication in the time domain, 00 .x(t)III(t) = L x(t)o(t-nD.t) n=-oo is just the convolution of X (f) and I I I (f) in the frequency domain: x(t)III(t) ::::> X(J) *III(!). Since X(J) is band-limited and III(!) is also a repeated delta function sample spacing 1/ D.t == 2fc, their convolutionproduces a signal which is just X(J) repeated every 2fc units, as shown in Figure l.lc. Now we want to extract only one of the repeated functions from X(J), so we multiply X (f)* I I I(J) by

PAGE 15

x(t) 1.5 1 0.5 -4 -2 0 2 4 lll(r) 2 1 -4 -2 0 2 4 x(t)III(t) 2 1 -4 -2 0 2 4 q(t) -1 -4 -2 0 2 4 2 [ x(t)III( t) ]q( t) 1.5 1 0.5 0 -4 -2 0 4 (a) (b) (c) (d) (e) X(f) 2 -----, 1.5 0.5 -4 -2 0 2 4 II I( f) 2 -4 -2 0 2 4 X( f) III( f) -2 2 4 0 Q(f) 0 I I -1 -4 -2 0 2 4 2 [X( f) III( f) ]Q( f) 1.5 1 0.5 0 -4 -2 0 2 4 Figurel.l The Sampling Theorem 7

PAGE 16

8 a boxcar function, Q(f), where { 0 for l/1 > fe Q(f) = for 1/1 :=; fe Q(f) possesses the Fourier transform q(t), where () sin(21l'fet) q t = 211' Jet The function q(t) is also called the sine function, where ( 2 f, ) sin(211' Jet) sznc 1!' ct = 2 f, 1!' ct This transform pair (q(t) {:::::::} Q(f)) can be seen in Figure l.ld. The multipli cation of X (f)* I I I(!) by Q(f) in the frequency domain is just the convolution of x(t)III(t) with q(t) in the time domain. Thus, we now have the transform pa1r [x(t)II I(t)] q(t) {:::::::} [X (f)* I I I(f)]Q(f) which is shown in Figure l.le. This is then just an identity transformation that produces the original transform pair that we started with in Figure l.la; that is, [x(t)III(t)] q(t) = x(t). It follows then that x(t) [x(t)III(t)] q(t) 00 L q(t) n.=-oo n.=-oo 00 L Xn.sinc(211'fc(t-n.=-oo Therefore, if a function possesses a band-limited transform, the value of the function at any point in the time domain may be uniquely determined from the sampled values using the above equation.

PAGE 17

9 Analogous to time domain sampling, there exists a sampling theorem in the frequency domain. If a function x(t) is time-limited, that is x(t) = 0 for itl > Tc, then its Fourier transform X(!) can be uniquely reconstructed from equidistant samples of X(!). As a result of these operations, values of X(!) are given by X(f) -[X(f)III(f)] Q(f) 00 I: k=-oo 00 I: Xksinc(27rTc(f-k=-oo According to Bracewell [2], this infinite sum may be reduced to a finite sum if the coefficients are modified as follows: (1.8) 1.3 The Fast Fourier Transform A brief description of the FFT algorithm is in order here, for it will later become an important aspect of understanding the DFTs of functions that are shifted to multiple grids. A sequence of N elements may be divided into two shorter sequences of N /2 elements each by placing the even-numbered elements into the first subsequence and the odd-numbered ones into the second. These two subsequences can then be stretched and shifted so that their resulting DFTs may be added together to form the DFT of the original sequence. Bracewell[21 shows how, for example, we can write the eight point series {8 7 6 5 4 3 21} as the sum of the two subsequences {8 6 4 2} and {7 53 1 }. If {8 6 4 2} => {ABC D}

PAGE 18

10 then {8 0 6 0 4 0 2 0} {::::::> {ABC DAB CD}, and if {7 5 31} {::::::> {P Q R S} then {7 0 50 3 0 1 0} {::::::> {P Q R S P Q R S}. If we then shift the odd series, giving then the DFT of the entire sequence is just the sum of the transforms of the even and odd subsequences {8 0 6 0 4 0 2 0} and {0 7 0 50 3 0 1}. If we define {xn} to be the full sequence {8 7 6 54 3 2 1} and let {Yn} and {zn} be the even and odd subsequences, respectively, then we have for 0 < k N -1, which is just the butterfly relation associated with the CooleyTukey version of the FFT. In general, we will adopt the notation that where Yn = X2n < n and where Zn = X2n+1 n Similarly, this breaking down of each sequence may continue by splitting the sequence into four shorter sequences of length N j 4, and then eight sequences

PAGE 19

11 of length N /8, etc., until N sequences of length 1 are obtained. Since the trans form of a one-point sequence is itself, all that remains is to reconstruct the entire transform from all its pieces. This specific. algorithm assumes the original sequence is of length N where N is a power of 2, say N = 2m. If N =/: 2m a fast algorithm may still be constructed.

PAGE 20

CHAPTER 2 DFTs ON MULTIPLE GRIDS The input sequence {xn} is defined on a grid in the time domain and its transform is defined on a grid in the frequency domain whose length and sample spacing are determined by the equation = 1 In some Fourier transform applications, it is necessary to interpolate the grid points in the frequency domain in order to better resolve a function's frequency spectrum. But what if the transform is very oscillatory? Interpolation in this case can only provide a very crude estimate of the true transform. It is for this reason that we look at ways of improving resolution in the frequency domain using only modifications of the grid in the time domain. The relationship = 1 tells us that in order to double the reso lution in the frequency domain (i.e. to reduce the frequency sample spacing to ) we must either double the sample interval in the time domain or double the number of sample points to 2N: In either case we must construct a new grid in the time domain; this requires that a new input sequence, {xn}, be constructed in terms of {xn} The resulting grid in the frequency domain is then known and the transform of the new sequence may be determined analytically in terms of the original transform. These analytical results will then tell us whether the_ new transform has in fact provided valuable information at a higher resolution. There are many ways to. define how the original sequence of input data { xn} is to be defined on a new grid with different length or sample spacing. This chapter will explore some of those possiblities and their expected results.

PAGE 21

13 2.1 Grid Definitions We shall denote the physical grid on which the sequence {xn} is defined by nN, where N is an even natural number. It is useful to regard the indices of {xn} as actual coordinates on the grid nN. We shall also assume that the grid nN has spacing IJ.t between adjacent grid points, SO the total length of grid is T = N !:it. The corresponding grid in the frequency domain will be defined as AN which has spacing _!:if and length F = N !:if. The relationship between nN and AN is shown in Figure 2.1a. Case 1. The first type of grid transfer we consider consists of injecting the even-numbered points from the original sequence on grid nN to grid n If, where n!f has grid spacing 2/J.t and length T. The frequency domain corre sponding to n!f will be defined as A !f I where grid spacing on A !f is still D.f but its length is (N/2)!:l.f = F/2. Grids n!f and A If are shown in Figure 2.1b. Case 2. The next type ofgrid transfer involves extending the the original sequence to 2N points without changing the sample interval. Hence, all of the original data points will be retained and new ones added to make up the full 2N points. Two methods of extending the sequence will be explored: periodic and zero extension. This new grid, n2N, thus will have sample spacing !:it and total length 2N !:it = 2T. In the frequency domain, grid A2 N will then have sample spacing !:if /2, but the total grid length is once again (2N)(!:l.f /2) = F. This relationship between n2 N and A2 N is in Figure 2.1c. Case 3. The final type of grid transfer involves extension and injection of the original sequence resulting in a sequence of N points with sample spacing 26t. This new coarser grid, nNe, .will thus haye length 2T. This doubling of the sampling interval without halving the number of sample points, N, means that the spacing on the frequency domain grid ANc will now be D.f /2 and total grid

PAGE 22

oN N 02 02N ONe TIME DOMAIN T -. I I I I I I I 1-------. ---. .. 0 . 2 2 2 2 2At -----.. I I I I I (b) -N -N . 0 N N 1 -+1 --2 --4 4 4 4 At I I I I I I I I I -N -N-1 0 N-2 N-1 2At ,...--. I I I I I I I . 0 . 2 2 2 2 '-. ./ 2T At 4f -1 N -N TF Figure 2.1 (c) (d) FREQENCY DOMAIN F ---,--r Pi r 1 r----. 0 . 2 2 2 2 Af 2 1\ Af jj I I I ... 0 ... 4 4 1111 I 1111 -N 0 N-1 Af 2 1\ Ill I Ill -N 0 N 2 2-1 '---v---/ F 2 Time and Frequency Domain Grids AN N A2 A2N ANc ,;:...

PAGE 23

15 length will be F /2. These grids are shown in Figure 2.1d. As in Case 2, periodic and zero extension methods will be studied. 2.2 Case 1: Injection nN ---+ As shown in the grids pictured in Figures 2.la and 2.1b, sampling N/2 points produces a grid in the frequency domain that is half the length of the original frequency grid, but with the same spacing between points, t:l.f. We would like to determine if this new grid, is in any way representative of the original grid, ON. First it should be noted that on the frequency grid AN, coefficients with indices in the interval 0 lkl correspond to low frequency components, while the coefficients associated with < lkl < correspond to high frequency components. With this in mind, it seems clear that the transfer of grid points from ON to 0 !f will extract the low frequency modes from the original series. This is true simply because a lower sampling rate implies that higher frequency components cannot be resolved. The transform on grid n!f may be written in terms of the original series {xn} in the following way. Let {xn} = {x_tt:, x_tt:+I, ... xo, ... xtt:_2 Xtt:_1 } t t 4 4 be obtained by sampling only the even points of { Xn}. In that case, Xn = x2 n for n 1 so the DFT of {xn} can be written f-1 xk = L X2nw;.,nk n=-lf lf-1 2: n=-lf for -N < k < N -1 4 --4 which is just the DFT of the sequence of even points only.

PAGE 24

16 We now consider a few functions and their transforms on grids nN and Function 1. We first consider the simple dual mode sine wave x(t) = 8sin(t) + sin(16t) on the interval [-11',11'] with N = 256 on grid nN. This input signal has the two frequencies 1/211' = .159 and 16/211' = 2.55. Figures 2.2a and 2.2b show the function x(t) and its transform F(J), respectively. In this and all subsequent frequency domain plots, the transform is plotted on a frequency vs. amplitude graph. Notice the spikes located at .159 and 2.55 on the frequency axis which correspond to the frequencies of each of the modes composing the function. (The fact that these are not true spikes, but more like very steep triangles, is due to the plotting algorithm.) Figure 2.2c shows the same function which has been injected from nN to and now consists of N/2 = 128 sample points over the same interval [-11',;]. Notice in Figure 2.2d, the plot of F(J) on that the two modes are retained and only their amplitudes have changed. Function 2. The second function we will consider is a shifted boxcar function. We shift the typical boxcar function (which is zero everywhere except on a small region in the center of the entire interval) one unit to the right and examine the function on the interval [ -1, 1] with N = 64. We will also assume periodicity with this function so that one-half width of the original boxcar will be present at both ends of the interval [-1, 1]. Define x(t) to be { 1 for .75 ltl 1.0 x(t) = 0 for 0 itl < .75 as shown in Figure 2.3a. The transform of x(t) is the sine function and is shown in Figure 2.3b. (Remember that only amplitudes are plotted.) The frequency spectrum on AN has length P = 32 (given by the equation X F = N) and, hence, extends over

PAGE 25

10 (c) 1500 (d) 5 1000 0 500 -5 -1 0 0 L-.__ ...J.._____jj__J..lL__.l]L__---l.._ __ ...;,_; -1 0 -5 0 5 1 0 -1 0 -5 0 5 1 0 Figure 2.2 !lN -t for x(t) = 8sin(t) + sin(16t) (a) x(t) on !lN (b) F(f) on AN (c) x(t) on (d) F(f) on A J ....... -.)

PAGE 26

21 (a) 20 (b) I I I I 15 1 I l I I 10 Of5 -1 01 1 -2 -1 0 1 2 -20 -10 0 10 20 2 (c) 20 (d) 15 5 1 l r 0 10 0' 'ryvy.yyv, 1 -2 1 0 1 2 -20 -10 0 10 20 Figure 2.3 nN---+ for x(t) =Boxcar function (a) x(t) on nN (b) F(f) on AN (c) x(t) on (d) F(f) on Alf 1-' al

PAGE 27

21 (a) 200 (b) I I I I 150 1 1-A I 100 Ol50 I J \ \ -1 0 -4 -2 0 2 4 -4 0 ') 4 .... 21 (c) 200 (d) I I I I 150 I-1 1. A I 100 I-Ol50 t---1 01 I -4 -2 0 2 4 -4 -2 0 2 4 Fjpure 2.4 2 nN --+ n2 for x(t) = e-1rt (a) x(t) on nN (b) F(f) on AN (c) x(t) on N t-.:> (d) F(f) on A 2 0

PAGE 28

19 the interval [-16, 16]. Figure 2.3c displays the boxcar function which has been injected to grid where N = 32. Its transform, shown in Figure 2.3d, is also a sine function, but the length of the interval has been cut in half. Only the low frequency components from AN are retained, that is, frequencies lfl 8. Function 3. The next function to be considered is the Gaussian curve x(t) = e-1rt2 This function was sampled at N = 256 points over the interval The Gaussian curve also has a known transformitself! The transform pair x(t) -::::::> F(f) is shown in Figures 2.4a and 2.4b. Notice that the plot of the transform is not as smooth as the original function though, in theory, it should be. This is due to the sample spacing in the frequency domain (Dt.J = .318) and the use of piecewise linear plotting. Although it is impossible to tell from Figure 2.4b, the frequency interval on AN has length NJT = 81.49 and thus extends from -40.75 to +40.75; however, the majority of the signal is in the interval [-1.5, 1.5]. When the function is injected to the grid (Figures 2.4c and 2.4d), only the low frequency com-ponents of the original transform are kept; but in this case, the entire spectrum is in the low frequency range, so nothing is lost. Function 4. The last function to be investigated is a triangle function defined by { 4x + 4 for -1 < t < 0 x(t) = -4x + 4 for 0 t 1 0 for 1 ltl 4 It will be sampled with N = 128 points. This function also has a known transform: the. sinc2 function. The function x(t) and its transform F(J) can be seen in Figures 2.5a and 2.5b. The length of the frequency spectrum on AN is 16 and thus extends over the interval

PAGE 29

6 (a) 80[ (b) I I 4 A 60 2 40 I-I I 0 2:[ _JL --2 I -10 -5 0 5 10 -10 -5 0 5 10 6 (c) 80 (d) 4 60 2 40 0 20 -10 -5 0 5 10 -10 -5 0 5 10 Figure 2.5 nN --+ for x(t) = Triangle function (a) x(t) on ON (b) F(f) on AN (c) on (d) F(f) on .....

PAGE 30

22 [-8, 8]. Figures 2.5c and 2.5d show the function after it has been injected to grid which consists of N = 64 sample points. Its transform again contains only the low frequency components (1/1 4) from the original grid. 2.3 Case 2: Extension nN f!2 N We will now focus on keeping the saine sample spacing, but extending the original sequence of N input points to 2N points. This will produce values in the frequency domain on a grid that is the same length as AN. However, this new grid, A 2N, has a finer sampling interval of A/ /2, so it remains to be seen whether we have gained information about the original frequency spectrum on 2.3.1 Periodic Extension We will perform the extension to grid f!2 N in two ways. The first extends the original sequence on f!N to { xn} periodically in the intervals N n 1 and n N-1. Thusthe new sequence of points, {xn}, is { x.,.+N for .N n 1 { Xn} = Xn for n -1 Xn-N for n N -1 Now we can show the relationship between {Xk} and {Xk}: N-1 xk = I: n=-N

PAGE 31

By equation (1.7), wfJ = w;;;k = (-1)k so 'f-1 'f-1 L + ( -1)k L n=-!Y. n=-!Y. 2 2 'f-1 -(1+(-1)k) L: n=-lf Note that when k is odd, Xk = 0. When k is even, say, k = 2p, for _N < p < N -1. 2 --2 n=-lf By equation (1.6), w;'jf = w';J', so 'f-1 X2p 2 E np -XnWN n=-lf -2Xp for -N k N -1. Therefore, on grid A 2 N we have X { 0 if k is odd k -2X if k is even 23 This says that the values of the even coefficients are twice their value on the original grid (which is due to the fact that the DFT is not scaled by N), and the odd coefficients are all zeroes. Therefore, we have picked up no new information at the interpolated values on grid A 2N. Now we shall examine these results graphically as applied to the same functions shown in the previous section. Function 1. Figures 2.6a and 2.6b show the original function x(t) 8si_n(t) + sin(16t) and its transform F(f). Figures 2.6c and 2.6d show the

PAGE 32

10 (a) 3000 (b) 51 J I 2000 I-0 I I rJ I 1000 1-II .. -5 -101 I 01 m I I I I II {\ -10 -5 0 5 10 -10 -5 0 5 10 10 3000 (d) 5 20001---0 10001-5 0 I I l j I I -10 -5 0 5 10 -10 -5 0 5 Figure 2.6 nN --+ 02 N with Periodic Extension for x(t) = Ssin(t) + sin(16t) (a) x(t) on nN (b) F(f) on AN (c) x(t) on n2 N (d) P(J) on A2 N 10 t..,:)

PAGE 33

25 new function extended to 2N points over the interval [-21r, 21r] as well as its transform. Because the modes of this sine wave occur at even values of k, the zeroes at the odd points are not evident. However, notice the amplitude of each of the modal peaks has been doubled, as predicted. Function 2. The shifted boxcar again appears with its transform in Figures 2.7a and 2.7b. The function has been extended periodically to grid !12N, shown in Figure 2.7c, and now has each of the boxcars within the interval instead of at the ends of the interval. Its transform, pictured in Figure 2. 7 d, displays exactly what is expected from the above analytical results. Odd coefficients are now zero, while even coefficients are twice what they were in Figure 2.7b, making this transform much more oscillatory than the original transform. Function 3. The Gaussian curve (Figures 2.8a and 2.8b) displays many of the same characteristics. The original function on grid nN has been extended to grid !12N, as shown in Figure 2.8c, and now displays two Gaussian curves shifted by 31r. The transform of the extended function (Figure 2.8d) again shows a curve .where every other point is zero, but this function can be enveloped by a curve that is exactly twice the amplitude of the functionon AN. Function 4. Finally, tJ:le triangie function and its transform (Figures 2.9a and 2.9b) display the same characteristics when the points from grid i1N are extended to grid !12 N (Figure 2.9c). The new transform on grid A2 N (the sinc2 function) is highly oscillatory due to the alternating zeroes, but is still enveloped by the function with twice the amplitude of that on grid A 2N. 2.3.2 Zero Extension We now consider extending the original sequence to 2N points by padding

PAGE 34

2 (c) 40 (d) 30 1 1-.---.--20 01---' 10 0 I I -2 -1 0 1 2 -20 -10 0 10 20 Figure 2.7 nN fl2N with Periodic Extension for x(t) = Boxcar function (a) x(t) on nN (b) F(J) on AN (c) x(t) on S12 N (d) F(f) on A2 N l...:> 0)

PAGE 35

2 (a) 200 (b) 150 1 1-A I 100 Of50 I I \ \ \ -1 0 \..... -4 -2 0 2 4 -4 -2 0 ? 4 ._ 2 (c) 200 (d) 150 -1 100 10 5:[ Jmt J --4 -2 0 2 4 -4 -2 0 2 4 Figure 2.8" O,N ---+ D.2 N with Periodic for x(t) = e-'"'2 {a) x(t) on D,N (b) F(J) on AN (c) x(t) on D.2 N (d) F(f) on A2 N t-.:) -.J

PAGE 36

(a) 150 (b) 6 4 1\ I 100 2 01-____; L--I 5:t _A -2 I -10 -5 0 5 10 -10 -5 0 5 6 (c) -r---.---150 (d) 4 100 2 50 0 0 I I AI -10 -5 0 5 10 -10 -5 0 5 Figure 2.9 f!N --+ 02 N with Periodic Extension for x(t) = Triangle function (a) x(t) on f!N (b) F(f) on AN (c) x(t) on f!2 N (d) F(J) on A2 N 10 10 t-=> 00

PAGE 37

with zeroes at both ends. The sequence { Xn} is then defined as for -N < n < -N -1 --2 for !Y. < n < N -1 2 --2 n N -1 29 The reason for expanding in this way is that it will take a signal that has high amplitudes on both ends of the interval and make it a signal where the high amplitude signal is now nearer to the center of the interval. To again explore the relationship between {X.d and {Xk}, note as before that the transform can be broken into the three intervals corresponding to the original grid, giving for -N k N -1. If we examine the case fork even, say k = 2p, we find that xk = .x2p = XI!. However, when k is odd (k = 2p + 1) we have 2 for -N < p < N -1 2 --2 which is just the DFT of a rotated sequence. Hence, by the shift theorem X!!. 2

PAGE 38

30 However, since k is by definition odd here, X! is actually located at a half-grid 2 point of !}N. This may also be considered an interpolated value from the original transform sequence {Xk} If the continuous function in the time domain is time limited, then equation (1.8) is applicable and the value of these odd coefficients may also be determined (or verified) using the sampling theorem. Thus, the relationship between grids AN and A 2 N for extension by zeroes on both ends is just Xk=Xl!. 2 for -N :5 k :5 N -1. Function 1. Starting with the dual mode sine wave, pictured with its transform in Figures 2.10a and 2.10b, we can see how extension by zeroes at both ends of the function results in a very abruptly changing signal as seen in Figure 2.10c. By extending the function to span the interval [-211'", 211'"] using zero padding at both ends, we have essentially multiplied the function x(t) = 8sin(t) + sin(16t) by a boxcar function centered at zero with width 211'". In the frequency domain then we have convolved the original transform function F(f) with a sine function. This results in a transform (Figure 2.10d) that now has many sidelobes instead of the clean two mode transform. The magnitude of the transform alternates between zero (k even) and non-zero values (k odd). Since the continuous version of the sampled function is infinite the sampling theorem for odd values does not apply here. Function 2. The shifted boxcar function also behaves unexpectedly. When the original function is transferred from grid nN to grid fl2 N by zero extension (Figures 2.11a and 2.1lb), we have again in essence multiplied the original function by a boxcar centered at zero with width 2. This is the same as convolving with a sine fun.ction in the frequency domain. However, this new function on fl2 N is no longer periodic. In order for this function to be periodic,

PAGE 39

10 (a) 1500 (b) l I I I I 5 10001-II I l I 0 I .r I 5001--1111 --5 -101 I 01 A lll A _____ ... --I I I I -10 -5 0 5 10 -10 -5 0 f> JO 10 (c) ,.-----.------1500 (d) 5 1000 0 500 --5 0 I I A ..J!l A I I -10 -5 0 5 10 -10 -5 0 5 10 Figure 2.10 nN --f!2 N with Zero Extension for x(t) = 8sin(t) + sin(16t) (a) x(t) on nN (b) F(f) on AN (c) x(t) on f!2 N (d) F(J) on A2 N 1-'

PAGE 40

21 (a) 20 (b) I I I I 15 1 fl r I JO 5 -1 01 ,, -2 -1 0 1 2 -20 -10 0 JO 20 2 (c) 20 (d) 15 1 .--,-10 0 f-------' 5 0 I CT)C I 1/ I II I 1 I II I \( !)CT') I -2 -1 0 1 2 -20 -10 0 10 20 Figure 2.11 nN ____. n2 N with Zero Extension for x(l) = Doxcar function (a) x(t) on f!N (b) F(f) on AN (c) x(t) on f!2 N (d) F(J) on A2 N
PAGE 41

33 each of the boxcars would have to be centered at or the function would have to be sampled only over the [-1.75, 1.75]. Because of this non-periodic nature and the convolution with the sine function, the transform of the new function, pictured in Figure 2.1ld, is very oscillatory. However, a plot of both transforms plotted together will show that the functions do in fact agree at the even points. Figure 2.12 shows how one sidelobe from the function on A 2 N encompasses two sidelobes of the function from AN. The values at the odd points obviously do not agree with the original transform. The reasons for this are currently not fully understood. Function 3. Extending the original furiction (shown with its transform in Figures 2.13a and 2.13b) with zeroes better approximates the infinite func tion x(t), but because of the improved resolution on A2N, it also provides a much smoother transform function. The new transform, shown in Figure 2.13d, demonstrates how the odd-numbered points on A 2.rv are actually values interpo lated from the original transform. The closer spacing of grid points in the new transform shows that a smoother, more accurate transform of the continuous function is obtained. Function 4. In the case of the triangle wave (Figures 2.14a and 2.14b), extension by zero padding also improves the transform. The time-limited triangle function possesses the Fourier transform sinc2(!), and extending the function with zeroes (Figure 2.14c) will not change this. However, the improved resolution in the frequency domain (Figure 2.14d) does help smooth the appearance of the original transform function. This improvement is most noticeable at the peak(!= 0). 2.4 Case 3: Extension and Injection f2N f2Nc Now we will combine injection and extension to a sequence of N numbers

PAGE 42

-............................... ............. _______ ......... ................................... -................ --....... ---------------'"'----------................................................ ... ......... ----. co C\l --0 N 0 0 N 01 34 :;>: C'l < ::::: 0 ....-... .__., -Ct.t .... ::: = ell ::: 0 ....-... ..._., Ct.t

PAGE 43

21 (a) 200 (b) I I I I 150 1 I-A I 100 01:I I \ \ I I / -1 0 -4 -2 0 2 4 -4 -2 0 2 4 2 (c) 200 (d) 1 I/ 150 Of-\__ -1 100 50 -2 0 2 4 -4 -2 0 2 4 Figure 2.13 nN ---+ f12 N with Zero Extension for x(t) = e_.,.,l (a) x(t) on nN (b) F(J) on AN (c) x(t) on fl2 N (d) F(J) on A2 N en

PAGE 44

6 (a) 80 [ (b) I I 4 fl 60 2 40 f-I I -0 20 I I I -2 01 I Q 61. L_. -10 -5 0 5 10 -10 -5 0 f) JO 6 (c) 80 4 60 (\ -2 40 0 20 0 I I <> A/, \(\ Q I I -10 -5 0 5 10 -10 -5 0 5 10 Figure 2.14 f!N --+ f!2 N with Zero Extension for x(t) = Triangle function (a) x(t) on f!N (b) F(J) on AN (c) x(t) on f22 N (d) F(J) on A2 N w 0)

PAGE 45

37 to produce a new sequence of N numbers. As in the case where the points from grid nN were moved to grid we will again sample by selecting only the even numbered points. This new coarsely sampled grid will be called f!Nc. To extend the grid so that it contains a full N points, extension methods similar to those in the previous section will be employed, that is, periodic and zero extension. 2.4.1 Periodic Extension N The sequence {xn} injected to nT yields the sequence {xn}, on grid nNe given by { X2 +N for -N < n < -N -1 n 2 --4 x = x2 for -N < n < N -1 n n 4--4 X2n-N for :5 n ::; -1 To examine the relationship between {Xk} on grid AN and {Xk} on grid ANc, first split the transform into three parts: 2::: XnWNk + 2::: Xnw'lf + 2::: XnWNk n=-f n=f f-1 2::: X2n+NWNk + 2::: X2nwrt + 2::: X2n-NWrt n=-f Nlc Nk n=-lf X2nWN N N for --< k < -. 2 --2 Since w-;,2 = wtJ the first and third terms of this last equation combine to yield Nk !f-1 f-1 wT 2::: nk + 2::: nk -N X2nWN X2nWN n=-f

PAGE 46

Nlc 't-1 -(1 +w;:T) L for_!:!.< k < !:!.. 2 --2 n=-'t Nlc k k Note also that wrJ = e-u:r = e11" = ( so that When k is odd all terms are zero, but when k is even, say k = 2p, we have :t-1 2 E n=-'t f-1 -2 2: X2nw';l N 2 n=-T -2 DFT!!.. {x2n} 2 2Jt;, for -N < p < N -1 4 --4 where Yp is just the transform of the series of even points only. 38 Therefore, the relationship between {Xk} on AN and {Xk} on ANc using periodic extension is { 0 if k is odd = if k is even for -N < k < N -1. 2 --2 A look at the previously seen functions for this grid extension is in order now. Function 1. The dual mode sine function and its transform are shown in Figures 2.15a and 2.15b. In moving the function from grid nN to nNe (Fig ure 2.15c), no information is lost from the original signal because the original sampling interval ( rr /256) is well above the aliasing point. That is, even when the sample spacing is doubled, both modes of the sine wave are still easily dis tinguishable in the transform (Figure 2.15d). The only difference between the original transform and the transform on AN is that the sampling interval in the frequency domain is now half of what it previously was, which is reflected in the width of the peaks for each mode.

PAGE 47

10 (a) 1500 (b) :f / \ 1 1000 1-II \ 500 I-1111 --5 I '1. I ol -10 I A Ill' ,, .a.... _______ -10 -5 0 5 10 -10 -5 0 10 10 (c) 1500 (d) 5 1000 0 500 -10 -5 0 5 10 0 I I i i I I -10 -5 0 5 10 Figure 2.15 nN --+ nNe with Periodic Extension for x(t) = 8sin(t) + sin(16t) (a) x(t) on nN (b) F(f) on AN (c) x(t) on nNe (d) F(f) on ANc w

PAGE 48

40 Function 2. The transform of the injected and extended boxcar function behaves in a very predictable fashion. The new function (shown in Figure 2.16c) is again a periodic function so its transform should behave in a manner very similar to that ofFigure 2.16b, the original transform on AN. The transform on ANe (Figure 2.16d) has a shortened frequency interval (now [-8,8]) and every odd point is zero, as shown in the analytical results. The values of the transform at the even points are non zero; however, a plot of both transforms together (Figure 2.17) will show that they are very close indeed, especially near the center of the spectrum. Function 3. The transform of an injected and extended Gaussian func tion displays many of the same characteristics. The new function (Figure 2.18c) is still very smooth and obviously periodic. Its transform (Figure 2.18d) shows zeroes at the odd points and values very near the values of the original transform at the even points. Function 4. The triangle function and its transform also change very little when injected and extended from grid nN to nNe. The transform of the new function (Figures 2.19c and 2.19d) again has a shortened frequency domain and a very oscillatory nature, due to the zeroes at odd points. 2.4.2 Zero Extension Finally, we shall consider injecting the sequence { Xn} from grid nN to grid nNe and extending by zeroes, forming the new sequence {in} where for -N < n < -N -1 2 -4 for -N < n < t!.. -1 4 -4 for N < n < N -1. 4 --2 In order to examine the relationship between {Xk} and we once again split

PAGE 49

21 1 1-01-1 -2 2 1 0 -1 -2 (a) 20 (b) I I I I 15 l r I 10 5 01 /VVV\f\/\/\J 1 -1 0 1 2 -20 -10 0 10 20 (c) 20 (d) r---,---15 \ n 10 5 L___ 0 I I llllfllllllllllltllllllll 1111 Ill! 1 I -1 0 1 2 -20 -10 0 10 20 Figure 2.16 n,N f!Nc with Periodic Extension for x(t) = Boxcar function (a) x(t) on D,N (h) F(J) on AN (c) x(t) on n,Nc (d) F(J) on ANc ..

PAGE 50

I r I ---.. ------........ ---------................ .................. ---.... .................. -------------........... _____ I I I co C\l 0 --r -.. .......... ': 0 C\l ----__ ::--_.._ .. ----____ ::::::_.._.._.;;;;. 0 ------:::::=== ---.. C\l -------lO -.......... 0 C\l Of 42 <: .::: 0 -----t-.......... ----...... v '"0 "" .::: :I I'd c 0 -.......... ..__, C::.,

PAGE 51

2 (c) 200 (d) 150 11 100 I-0 501-J .JIAL.] -4 -2 0 2 4 -4 -2 0 2 4 Figure 2.18 nN --nNe with Periodic Extension for x(t) = e-Trt2 (a) x(t) on nN (b) F(J) on AN (c) x(t) on nNe (d) F(J) on ANe ,p..

PAGE 52

6 (a) 80 (b) 4 60 I2 40 I-0 2:r _Jl. -2 I -!..---:10 -5 0 5 10 -10 -5 0 5 10 6 (c) 80 (d) 4 60 2 40 0 20 -2 0 -10 -5 0 5 10 -10 -5 0 5 10 Figure 2.19 nN --nNe with Periodic Extension for x(t) = Triangle function (a) x(t) on nN (b) F(J) on AN (c) x(t) on nNe (d) F(J) on ANc .... "'"

PAGE 53

{ Xn} into three pieces: -f-1 f-1 l'f-1 L: Xnw'J/ + L: XnWNk + L: Xnwr;} n=-f n=-f n=f f-1 0 + L: X2nw'N" + 0 for -N < k < N -1. 2 --2 n=-f When k is even, say k = 2p, we have f-1 L: Yp n2p X2nWN for -N < p < N -1. 4 --4 However, when k is odd, say k = 2p + 1, we again have a rotated sequence: f-1 X2p+l L: X2nw';}2p+1) n=-f for -N < p < t:!.. -1. 4 -4 If we then substitute for p + t, we find that for -N < k < t:!.. -I. 2 --2 45 This is again a case where xk is actually a value from a half-grid point of nN which is interpolated from its-neighboring coefficients. The transform of a sequence that has been injected and extended with zeroes on both ends may be expressed in terms of the original transform in the

PAGE 54

46 following way: { X 1c if k is odd = Yt2 if k is even for -N < k < N -1. 2 --2 Perhaps a few pictures relating the transforms on grids AN anc;l f\Nc will be helpful. Function 1. In Figures 2.20a and 2.20b, the original signal x(t) = 8sin( t)+sin(16t) and its transform appear. The results of injecting this sequence to grid flNc are shown in Figure 2.20c and again, due to the high sampling rate on the original grid, sampling only the even points of {xn} does not degrade the signal. However, extending with zeroes at both ends introduces leakage around both modes in the frequency domain (Figure 2.20d). Function 2. When the shifted boxcar function is injected and extended with zeroes (Figure 2.2lc), it is no longer a periodic function, so its transform behaves uncharacteristically. This new transform (Figure 2.21d) is very similar to the transform of the sequence that has been extended with zeroes but not injected to a coarser grid (Figure 2.7d). Function 3. The Gaussian curve again shows an improvement from the original transform (Figures 2.22a and 2.22b) because of the zero extension. The new signal (Figure is a better approximation of the infinite. function x( t) = e-1rt2 but because of the increased resolution in the frequency domain, its transform is now much smoother (Figure 2.22d). Function 4. Finally, when the triangle function (Figures 2.23a and 2.23b) is extended by zeroes on both ends of the interval (Figure 2.23c), the transform again is an improvement of the original transform due to the higher resolution on f\Nc.

PAGE 55

10 (a) 1500 (b) 51 I 1000 1-II -0 I I ,) I 500 I-fill -I I .I I -5 I "\d) I ol lll -10 I A A -10 -5 0 5 10 -10 -5 0 5 10 10 (c) 1500 5 1000 I-0 500 I--5 -10 -5 0 5 10 0 1 1 A .Jn, .A 1 1 -10 -5 0 5 10 Figure 2.20 f!N --+ nNe with Zero Extension fe>r x(t) = 8sin(t) + sin(16t) (a) x(t) on nN (b) F(J) on AN (c) x(t) on nNe (d) F(f) on ANc -.J

PAGE 56

21 u-1 -2 2 1 0 -1 -2 (a) I I I _j l I l -1 0 1 2 (c) r\ n I I -1 0 1 2 20 (b) 15 10 5 0 -20 -10 0 10. 20 20 (d) 15 10 5 01 1 n 11 1 1 1r '" 1 1 -20 Figure 2.21 -10 0 10 20 nN ____. f!Nc with Zero Extension for x(t) = Boxcar function (a) x(t) on oN (b) F(f) on AN (c) x(t) on nNe (d) F(f) on ANc >l'-00

PAGE 57

2 (a) 200 (b) 150 1 _/\_ I 100 Of-50 I I \ \ \ -1 0 -4 -2 0 2 4 -4 -2 0 2 4 21 (c) 200 (d) I I I I 150 1 I I \ I 100 I J \ I 0 50 -1 0 -4 -2 0 2 4 ---4 -2 0 2 4 Figure 2.22 nN -nNe with Zero Extension for x(t) = e-11't2 (a) x(t) on f2N (b) F(f) on AN (c) x(t) on f2Ne (d) F(J) on ANc co

PAGE 58

6 (a) 60[ (b) I I 4 60 2 40 0 20 -2 01 I L -10 -5 0 5 10 -10 -5 0 5 10 6 (c) 80 (d) 4 60 2 40 0 20 -2 0 -10 -5 0 5 10 -10 -5 0 5 10 Figure 2.23 nN ---+ nNe with Zero Extension for x(t) =Triangle function (a) x(t) on f2N (b) F(J) on AN (c) x(t) on f2Nc (d) F(J) on f\Nc C,Jt 0

PAGE 59

2.5 Summary Table 2.1 lists all of the preceding results for each grid. II Grid f!N---+ f!T f!N---+ f!2N Periodic Extension flN---+ f!2N Zero Extension f!N---+ f!Ne Periodic Extension f!N---+ f!Nc Zero Extension xk = Yk xk = 0 if k is odd if k is even 2 xk 2 0 if k is odd 2Y .. if k is even 2 { x .. if k is odd xk = if k is even Table 2.1 Multilevel Transform Results k -'1 k -1 -N k N -1 -N k N 1 _N
PAGE 60

CHAPTER 3 FUTURE DffiECTIONS: MULTILEVEL TRANSFORM SYSTEMS The development of Fourier transforms on multiple grids suggests the possibility of multilevel systems of OFTs involving transform on grids as shown in the previous chapter. Multilevel transform systems also suggest several ques tions about intergrid transfers: How well do the frequency spectra on these new grids actually represent the original frequency spectra? Can a OFT on a grid that is more sparse than the original grid result in a transform that preserves information from the original OFT while reducing the overall computational cost? Can the information in the new transform be obtained directly from the OFT of the full sequence? While all of these questions cannot be fully answered at this point, it opens many possibilities for future work. A look at some possible multilevel transform systems is in order. 3.1 Transform System I In Case 1 from Chapter 2, a sequence of points {xn} on grid nN was injected to grid nf by sampling only the even points of the sequence. This new grid still had length T, but the new sequence {in} consisted of N/2 points, with !!. sample interval 2.6-t. Define to be the injection operator that acts on the N sequence {xn} and produces {in}, that is, !J {xn} ={in} In the frequency domain; the original transform sequence { Xk} on 1\.N had length F and sample spacing !:l.j, but the new sequence { .... Y'k} on A f had length F/2 and sample spacing !:l.f. Now we must ask: Is there some clearly

PAGE 61

53 N definable operator, say!"!;, that produces the sequence {Xk} from {Xk}, i.e. !:I. does T { Xk} = { Xk}? Figure 3.1 demonstrates this possible relationship. N H the operator T"J is a clearly defined one,. then we have two ways N through which to obtain the sequence {Xk} on DFTJ:I. {IJ {xn}} or 2 N. {DFTN{xn}}. Obviously, the first method involves fewer computations in the DFT and seems to be the obvious choice. Its preference over the second N method must be evaluated by determining the existence of the T "!; operator. Recall that the FFT algorithm performs a splitting of the original series N of points by even and odd restriction. The injection operation !J { Xn} is exactly this first split, keeping only the even points in the new sequence. It was shown earlier that the values on the grid A lf are f-1 Xk = 2: n=-f for -N < k < N -1. 4-4 A look at the difference between Xk and Xk is one way to determine the correction that must be applied to xk in order to recover xk. n=-lf n=-f X W2nk 2n N f.:.l L X2nwJ:k n=-lf This last step just splits the series for Xk into even and odd terms. The first and third terms now cancel, leaving f-1 X X (2n+1)k kk = L..J X2n+1WN n=-!f .w7., DFTlf {x2n+d wtzk This last Zk term is just the other half of the FFT butterfly relation, i.e. the DFT

PAGE 62

a" N 02 I I I I I I I I I I I I I I I I -N 0 !L1 i At 2 N I i N I I I I I I I I -N -0 N 4 241 4-1 Xn} 4=".> { Xk \ DFTN l ;n} 4=9 {Xk} DFTN i Figure 3.1 Transform System I I I I I I I I I I I I I I I I I -N 0 N z Af i-1 N yz N I I I I I I I I -N 0 N -Af --1 4 4 A" N Ai CTI

PAGE 63

55 of the odd points in the sequence. This result is not unexpected since Xk also equals 1-k and by definition Xk = Yk+w;_,.zk so Xk-Xk = 1-k+w;_,.zk-Yk = w;_,.zk. !!.. Therefore, the operator l' & is one which must perform the first split of the inverse DFT, throwing out the points from the DFT of the even points of {xn} The grid A If then introduces no new information about the frequency spectrum that is otherwise unobtainable from the original frequency spectrum. It might also be mentioned here that several alternatives to injection of the even points exist for transferring data from nN to nlf. Some possibilities include injection of the odd points; averaging the odd and even points, and mul tiple point weighted averages. Further work may be sought in those directions. 3.2 Transform System II Case 3 from Chapter 2 introduced the grid nNe which had twice the sample spacing of the original grid but was extended on both ends to form a sequence of N points. This new grid then produced a frequency domain grid with twice the resolution of the original frequency grid but half the length. In both cases the transform of the original sequence and the transform of the new extended sequence required an N-point DFT. Define the extension operator that extends and injects the data from grid nN .to nNe as E}T. Similarly, we would like to define an operator in the frequency F domain that compresses the data from grid AN to A Nc. Call this operator CJ. The sequence {Xk} on ANc could thus be obtained from the original sequence of F points in two ways: DFTN{E}T {xn}} or CJ {DFTN{xn}}. These operators and their grids are shown in Figure 3.2. We would again like to study this operator F CJ in order to see whether the data on ANc is in fact recoverable from AN.

PAGE 64

o" ONe I I I I I I I I -N 0 N i 4t i-1 INc N I I I I I I I I -N -0 N i 24t i-1 f xn l <-7 { Xk l DFTN {in} ( ) {Xkl DFTN Figure 3.2 Transform System ll I I I I I I I I -N 0 N i 41 i-1 CNC N IIIII II I -N V 0 N 4t --1 2-2 2 A" 1\.Nc "" 0)

PAGE 65

57 3.2.1 Periodic Extension Recall that, for the case where { Xn} was extended periodically, we showed that lf-1 -(1+(-1)k) 2: n=-lf if k is odd for -N < k < N -1 2 --2 if k is even The fact that the odd points are all z.eroes means that no new information has been added, even though the resolution of the grid in the frequency domain is /2. But how closely do the even coefficients compare with those from the original transform? Obviously, when k is odd, the difference between and is just For k even, first note that on ANc corresponds to on AN for :5 k :5 -1. That is, only points in the center of the interval on AN may be compared to points on ANc. Then we have --1 lf-1 """ X w"'k -2 """ x w 2 "'k ...J n N ...J 2n N n=-lf lf-1 lf-1 L X2nwJ.;k + L: !f-1 -2 L X2nw'f.{k n=-lf for -N < k < N -1 4 -4 I which is just the CooleyTukey butterfly relation equation with the transform of the even subsequence negated. Thus calculating {Xk} from {X,te} would mean splitting the original series into even and odd subsequences and adding and

PAGE 66

58 subtracting their DFTs to the full N-point DFT. Thus the sequence {Xk} is certainly recoverable from {Xk} (or vice-versa) but at a cost that may not be justifiable. 3.2.2 Zero Extension For the case where the sequence {xn} on nN is extended by zeroes on both ends to fit the grid {lNc, recall that { if k is odd xk = N ""--1 k 'f k LJ:=-lf x2nwi\r 1 1s even for -N < k < N -1. 2 --2 We will again look at the difference between Xk and Xk for each point. For odd k, we know that the midpoints between each of the Xk correspond directly to odd-numbered points of {Xk} That is, we want to look at the difference for -N < k < N -1 4 --4 where the xk+l are values between grid points and the x2k+l are the odd points 2 on ANc that correspond to those midpoints of AN. In secion 2.4.2 we saw that X2p+l = for p -1 so if we change variables and use k over the N N range -4 k 4 1 we have X2k+I = Xk+t Thus for -N < k < N -1. 4 --4 This says that the values of the odd points of {.Xk} are exactly the value of interpolated coefficients from {Xk} The value of these interpolated coefficients may be determined using the sampling theorem if the original function in the time domain is time-limited. When k is even, we again want to compare values of X2k and Xk: !f-1 f-1 xk x2k = I: XnWNk I: X2nwiJ'k n=-Jf n=-f

PAGE 67

!f-1 L: (2n+l)lc X2n+1WN for -N < k < q N -1 4 -4 59 ""' X w2nlc 2n N n=-!f which is just the transform of the odd subsequence rotated by wt, i.e. the second half of the CooleyTukey butterfly relation. In this case where zero extension is used, neither the odd nor even coef-ficients are easily determined from the original transform. But it is worth noting that information appears to be gained with the new transform. The resolution of the new transform grid ANc is better than the original grid AN, and we now have values that have been interpolated at no extra cost, i.e. an N-point DFT was performed in both cases. The odd-numbered points of introduce information that may be used to, in effect, double the resolution of without actually interpolating values from the original signal {xn}

PAGE 68

CHAPTER 4 SUMMARY AND CONCLUSIONS Chapter 2 showed several cases of multilevel OFTs and the analytical results expected from those grid transfers. These results were also demonstrated graphically through the display of several functions and their OFTs. It was shown that injecting a sequence of N points to an grid saved compu tational work but did not, however, produce any new information or about the original transform. Extending an N-point sequence to 2N points only appeared profitable if the extension was performed by padding with zeroes at both ends of the interval. Periodic extension of the signal only managed to produce zeroes at every other point in the transform, thereby giving no new information about the original OFT. Zero extension, however, served to interpolate the values in the original transform and thus produced a frequency spectrum as broad as the original, but with twice the resolution. The cost of this added information is 2N point OFT. However, some consolation may be noted in that the alternative to producing a 2N-point transform by zero extension is to interpolate the original sequence of data values, {xn}, to 2N points and then perform a 2N-point DFT. Zero extension produces no extra work and does not introduce interpolated data values in the time domain. So if computational cost is not an issue but improved resolution in the frequency domain is, extending a sequence to 2N points by zero extension is a very reasonable option. We obtained similar results for sequences injected to an grid and then extended to fill an N-point grid. Extending the sequence periodically

PAGE 69

61 only added zeroes at all the odd points in the frequency domain, whereas ex tending with zeroes at both ends introduced interpolated values in the frequency spectrum. However, due to the relationship between the time and frequency do mains, the length of the frequency spectrum on this new grid is only half the length of the original frequency spectrum. So if increased resolution is desired in the frequency domain but computational cost is a concern, this type of grid transfer is preferable. This method can at least give a frequency spectrum with better resolution over the center half of the frequency interval without increasing the computational cost of performing the DFT. Finally, two possibilities for multilevel transform systems were presented to suggest further multigrid transform methods. Methods of recovering the orig inal transform from a new transform were discussed as well as the possiblility of gaining information about a transform by moving it to another grid.

PAGE 70

62 BIBLIOGRAPHY [1] Bergland, G.D., "A Guided Tour of the Fast Fourier Transform". IEEE Spectrum, Vol. 6, No. 7, July 1969. [2] Bracewell, R.N., The Fourier Transform and its Applications. McGraw-Hill, Inc., New York, 1978. [3] Briggs, W.L., A Multigrid Tutorial. SIAM, 1987. [4] Briggs, W.L., Henson, V.E., "The FFT as A Multigrid Algorithm". Draft, Jan. 1989. [5] Brigham, E.O., .The Fast Fourier Transform. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1974. [6] Cizek, V., Discrete Fourier Transforms and Their Applications. Adam Hilger Ltd., Bristol, England, 1986. [7] Dahlquist, G., and Bjorck, A., Numerical Methods. Prentice-Hall, Inc., En glewood Cliffs, New Jersey, 1974. [8] Mersereau, R.M., Oppenheim, A.V., "Digital Reconstruction of Multidimen sional Signals from Their Projections". Proceedings of the IEEE, Vol. 62, No. 10, October 1974. [9] Press, Flanner, Teukolski, Vetterling, Numerical Recipes:. The Art of Scientific Computing. Cambridge University Press, 1986. [10] Stark, H., Woods, J.W., Paul, 1., Hingorani, R., "An Investigation of Com puterized Tomography by Direct Fourier Inversion and Optimum Interpo lation". IEEE Transactions on Biomedical Engineering, Vol. BME-28, No. 7, July 1981. [11] Stark, H., Woods, J.W., Paul, 1., Hingorani, R., "Direct Fourier Recon struction in Computer Tomography". IEEE Transactio_ns ori Acoustics, Speech, and Signal Processing, Vol. ASSP-29, No. 2, April1981. [12] Yossef, T., "Bi-Level Properties of Fourier Transform". Graduate Thesis, Weizmann Institute of Science, Rehovat, November 1988.