# MIT 18 310C - The Finite Fourier Transform (8 pages)

Previewing pages*1, 2, 3*of 8 page document

**View the full content.**## The Finite Fourier Transform

Previewing pages
*1, 2, 3*
of
actual document.

**View the full content.**View Full Document

## The Finite Fourier Transform

0 0 81 views

- Pages:
- 8
- School:
- Massachusetts Institute of Technology
- Course:
- 18 310c - Principles of Applied Mathematics

**Unformatted text preview:**

23 The Finite Fourier Transform and the Fast Fourier Transform Algorithm 1 Introduction Fourier Series Early in the Nineteenth Century Fourier in studying sound and oscillatory motion conceived of the idea of representing periodic functions by their coefficients in an expansion as a sum of sines and cosines rather than their values He noticed that if for example you represented the shape of a vibrating string of length L fixed at its ends as y x ak sin 2 kx L the coefficients ak contained important and useful information about the quality of the sound that the string produces that was not easily accessible from the ordinary y f x representation of the shape of the string This kind of representation of a function is called a Fourier Series and there is a tremendous amount of mathematical lore about properties of such series and for what classes of functions they can be shown to exist One particularly useful fact about them is how we can obtain the coefficients ak from the function This follows from the orthogonality property of sines sin 2 kx L sin 2 jx L dx if the integral has limits 0 and L is 0 if k is different from j and is L 2 when k is j To see this notice that the product of these sines can be written as a constant multiple of the difference between cosines of 2 k j x L and 2 k j x L and each of these cosines has 0 integral over this range By multiplying the expression for y x above by 2 jx L and integrating the result from 0 to L we get then the expression aj 1 f x sin 2 jx L dx Fourier series represent only one of many alternate ways we can represent a function Whenever we can by introducing an appropriate weight function in the integral obtain a similar orthogonality relation among functions we can derive similar formulae for coefficients in a series 2 The Fourier Transform Given a function f defined for all real arguments we can give an alternative representation to it as an integral rather than as an infinite series as follows f x exp ikx g k dk where the integral is over all real values of k The representation of f by the function g is called a Fourier transform of f and it is very important tool in physics One reason for this is that exponential functions e ikx which f is written as an integral which is a sort of a sum of are eigenfunctions of the derivative That is the derivative acting on an exponential merely multiplies the exponential by ik This makes the Fourier transform a useful tool in investigating differential equations Another example of it s application In quantum mechanics we represent the state of a particle in a physical system has wave function x and x 2 dx represents the probability that the particle in this state has position that lies between x and x dx The same state can also be represented by its wave function in momentum space and that wave function of the variable p is a constant multiple of the Fourier transform of x p c exp ipx x dx We can invert the Fourier Transform in much the same way that we can invert Fourier Series The resulting formula is g k 1 2 exp ikx f x dx again the integration is over all real values of x 3 The Finite Fourier Transform Given a finite sequence consisting of n numbers for example the ccoefficients of a polynomial of degree n 1 we can define a Finite Fourier Transform that produces a different set of n numbers in a way that has a close relationship to the Fourier Transform just mentioned I like to look at it backwards Suppose we have a polynomial p of degree n 1 It can be described by its coefficients aj with p x j 0 to n 1 aj xj We can also represent p by giving its values at any n arguments p xk This can be done as follows Observe first that the polynomial of degree n 1 f xj x x1 xj x1 exclude x xj xj xj x xn xj xn takes the value f xj at x xj and is 0 at all other of our arguments x k We can recover p from its values by summing similar terms over all j To evaluate a polynomial of degree n 1 at n values appears to require n2 actions n evaluations each of n terms Similarly the procedure just described for recovering p from its values requires at least n 2 operations to obtain all the coefficients of p When you evaluate a polynomial at an argument x whose magnitude is not close to 1 the powers of x that are big dominate those that are small by so much that you have to worry about losing the smaller terms entirely from round off errors The finite Fourier transform can be defined as the act of evaluating a polynomial of degree n 1 at n roots of unity that is at n solutions to the equation x n 1 This transform can be performed upon polynomials with coefficients in any field in which this equation has n solutions which will happen when there is a primitive n th root of unity in the field This means a number such that xn 1 but xk is not 1 for any k between 1 and n 1 The n roots of unity are then the various powers of the primitive root When does this happen It does for complex numbers in which case we have exp 2 i n which is cos 2 n isin 2 n as primitive n th root of unity But it also happens for remainders on dividing by a prime number of the form kn 1 In such fields there is a primitive kn th root of unity and hence a primitive n th root of unity such as the k th power of the former The analogy between this finite transform and the Fourier transform is mnost apparent when we use complex numbers Then if the coefficients of the polynomial are aj the evaluations become p exp 2 ik n j aj cos 2 jk n i j aj sin 2 jk n This is why we say that we are doing things backwards It is the aj which are analogous to the Fourier coefficients for the function p In general if we let z be our primitive n th root of unity the same expression becomes Transforms of this kind can be defined for any value of n And there is a symmetric form for the inverse transformation which takes the values p zk which we shall abbreviate as p k and produces the a j so there is no significant difference between defining this transform forward or backward We can obtain the inverse transformation by multiplying each p k by z sk and summing over the n values of k We get j k …

View Full Document