YOUR TITLE

BY

YOUR NAME HERE

A Thesis Submitted to the Graduate Faculty of

WAKE FOREST UNIVERSITY GRADUATE SCHOOL OF ARTS AND SCIENCES

in Partial Fulfillment of the Requirements

for the Degree of MASTER OF ARTS

Department Date goes here

Winston-Salem, North Carolina

Approved By: Your Advisor, Ph.D., Advisor Committee Chair, Ph.D., Chair

Committee member, Ph.D. Committee member, Ph.D.

Acknowledgments

There are many people who helped to make this thesis possible. ......

Table of Contents

Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chapter 2 Name of chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chapter 3 Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Chapter 4 Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Appendix A A Title Goes Here . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Appendix B Title for 2nd Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Vita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Abstract

Your Name Your abstract text goes here 2nd Paragraph can go here if needed and a 3rd

Chapter 1: Introduction

This is sample text from an actual Thesis:

As images pass through the earth’s atmosphere they become distorted. In some cases so much so that the image has no similarities to it’s ”actual” form. The wave front relinquishes it’s form for a variety of reasons. Some of which include humidity, air temperature and general atmospheric turbulence [7]. By definition adaptive optics is the scientific and engineering discipline which deals with the control of light in some form of an adaptive looping process [7]. Even though no single person may be accredited as the founder of adaptive optics there have been vast advancements made in the past 50 years. The basic process behind adaptive optics is to obtain a sample of the gradient of the incoming wavefront which may be accomplished through the use of a Shack-Hartmann wave front sensor when a point source is available. Perhaps the most common method for correcting atmospheric aberrations is by phase conjugation. This method is the focal point in adaptive optics. Next, the obtained data is used to correct the wave front.

When any wave front passes through some aberrator it is modified. Once the distorted wave front bounces off of a conventional uncorrected mirror it again passes through the aberrator and the distortion in the wave front is now doubled as seen in Figure 1 located in the Appendix. The magnititudes of the bumps in the final distorted wave front directly determine the mirror correction necessary in order to retrieve the original wavefront. Multiplication of every distortion by - 1/2 determines the amount of correction needed over each particular mirror segment at the position in which the wavefront reflects off of the mirror segment. This is a very tricky process since most aberrations are constantly changing and therefore the correction for them must be a continuous process and must repeatedly occur in order to achieve accurate results. Correction is accomplished by quickly positioning the deformable mirror to correct the wavefront. The detection, estimation and correction process should not take longer than one one-hunderdth of a second [7]. Since the goal is to obtain real time data. The final images may be further enhanced by post-processing methods, but that topic will not be discussed in this paper.

[remainder of chapter deleted]

Chapter 2: Name of chapter 2

In the mid 1960’s, the Fast Fourier Transform, or FFT, was born. By 1977, various methods of FFT’s were implemented in a wide variety of applications. It is still considered to be one of greatest advancements in Numerical Analysis. FFT algorithms were developed as a ”quick” method for computing the Discrete Fourier Transform. The Discrete Fourier Transform, or DFT, is the result obtained by discretizing the Fourier Series. It is important to remember that the function in consideration must have periodicity, a finite number of maxima and minima during any period, a finite number of discontinuities if there are any at all, and it must be absolutely integrable in any period in order to have a fourier series representation [5]. Any algorithm whose computational efficiency is on the order of N log_{2}N is generally considered an FFT method. This implies that solutions to the inverse Discrete Fourier Transforms are also considered FFTs.

There are many types of FFT algorithms, but they fall into one of two general categories. The decimation in time approach and the decimation in frequency approach. The decimation in time approach breaks apart the time dependent input vector x in order to approximate the solution. The decimation in frequency approach breaks apart the frequency dependent vector y in its computation.

In order to use the so-called Radix-2 FFT, the matrix in question must be n × n where n = 2^{i} ∃ i ≥ 1. The general Radix algorithm requires the n × n matrix to be highly composite (i.e. having many small factors). There are also algorithms for computing FFTs of non-square matrices. However, the Radix-2 algorithms allow for faster execution than the more general ones. It is possible to modify a matrix whose dimension is not a power of two by padding it with zeros to obtain a square n × n matrix where n is some power of two.

Let the vector y = ( y_{0} ; y_{1} ; ⋮ ; y_{n−1} ) be the Discrete Fourier Transform of x = ( x_{0} ; x_{1} ; ⋮ ; x_{n−1} ) .

Each y_{k} = ∑_{j=0}^{n−1}[cos(2πkj/n)−isin(2πkj/n)]x_{j} = ∑_{j=0}^{n−1} e^{−2πkji/n}x_{j} for k = 0, 1, ...,n-1. There are several variations on computing the Radix-2 FFT. One is the omition of the \frac{1}{n} term for each y_{k}. Another is to omit the negative sign from the power of the exponential function. The DFT of y may also be seen as the product of a matrix and a vector where y = F_{n}x and F_{n} is an n × n matrix with rows indexed by k and columns indexed by j. Each entry in F_{n} is denoted by f(k,j) and is equal to e^{−2πkji/n}. In order to reduce the number of flops the convention of dropping the 1/n term will be applied in the formulation of the DFT.

Sample Matlab code to set up the Discrete Fourier Transform matrix given by [8]: for k = 0:n-1

m = e^{−2π/n}

F(k,0) = 1

for j = 1:n-1

F(k,j) = mF(k,j-1)

end end

The efficiency of an algorithms is commonly measured in flops which are floating point operations. There are two flops for complex addition and six flops for complex multiplication. The total number of flops for the above code is given by O(6n^{2}) flops.

Assuming the vector x still has length n. Define

ω_{m} = diag(1, e^{−2π/n}, (e^{−2π/n})^{2}, ..., (e^{−2π/n})^{(}m − 1))  (2.1)

where m is initially \frac{n}{2} and diag refers to an m × m matrix with the entries listed going down the diagonal. Define EOP erm_{n} to be an n × n matrix using sequential even and odd format respectively and beginning with 0 as the first element in the even list. One of the interesting properties of EOP erm_{n} is that the transpose of this matrix is its inverse such that EOP erm_{n}EOP erm_{n}^{T} = I_{n}. Applying EOP erm_{n} to F_{n} on the right will yield a matrix of the form

F_{n}EOP erm_{n} = ( \begin{matrix}F\frac{n}{2} & ω\frac{n}{2} F\frac{n}{2} \\ F\frac{n}{2} & −ω\frac{n}{2} F\frac{n}{2} \end{matrix} ) = ( \begin{matrix}I\frac{n}{2} & ω\frac{n}{2} \\ I\frac{n}{2} & −ω\frac{n}{2} \end{matrix} ) ( \begin{matrix}F\frac{n}{2} & 0 \\ F\frac{n}{2} & 0 \end{matrix} )

Since EOP erm_{n}^{−1} = EOP erm_{n}^{T} then multiplying both sides by EOP erm_{n})^{T} on the right yields:

F_{n}EOP erm_{n}EOP erm_{n}^{T} = ( \begin{matrix}I\frac{n}{2} & ω\frac{n}{2} \\ I\frac{n}{2} & −ω\frac{n}{2} \end{matrix} ) ( \begin{matrix}F\frac{n}{2} & 0 \\ F\frac{n}{2} & 0 \end{matrix} ) EOP erm_{n}^{T}

F_{n}I_{n} = F_{n} = ( \begin{matrix}I\frac{n}{2} & ω\frac{n}{2} \\ I\frac{n}{2} & −ω\frac{n}{2} \end{matrix} ) ( \begin{matrix}F\frac{n}{2} & 0 \\ F\frac{n}{2} & 0 \end{matrix} ) (EOP erm_{n})^{T}

Multiplying both sides by the vector x on the right gives:

F_{n}x = ( \begin{matrix}I\frac{n}{2} & ω\frac{n}{2} \\ I\frac{n}{2} & −ω\frac{n}{2} \end{matrix} ) ( \begin{matrix}F\frac{n}{2} & 0 \\ F\frac{n}{2} & 0 \end{matrix} ) x(EOP erm_{n})^{T}

F_{n}x = ( \begin{matrix}I\frac{n}{2} & ω\frac{n}{2} \\ I\frac{n}{2} & −ω\frac{n}{2} \end{matrix} ) ( \begin{matrix}F\frac{n}{2} & 0 \\ F^{n} \end{matrix}