Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00001987/00001
## Material Information- Title:
- Multilevel discrete Fourier transforms
- Creator:
- Hare, Michael Anne
- Place of Publication:
- Denver, CO
- Publisher:
- University of Colorado Denver
- Publication Date:
- 1989
- 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 )
## Auraria Membership |

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<* 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-^ 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 {xn+N for -N 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 |

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. |