Today we will move on to a newer topic that is Fourier computing, Fourier transforms using
numerical methods. So we are all familiar with familiar with Fourier series that is
when you have a function which is periodic in time, say this such a function which is
periodic in time or any variable t and it is periodic in the sense that.
Okay now it has a repeat period of given by t here and let us say this continues and then
we know that such a function can be written as a sum of sine functions and sine and cos
functions that is a n sine some, we will say some n omega t plus sigma n b n cos n omega
So we can write, we know this this is the Fourier series when the function is periodic
and where omega here would be 2 phi by t. So we have we can write this in this form
and then we know that to obtain the coefficients an and bn, we would integrate this function
f of t. So we would say that to get a n we would say that we will integrate this function
between the limits minus t by 2 to plus t by 2 f of t we say sine n omega t dt.
So that is that is what we would do to obtain this coefficients because we use the property
of the sine functions that integral minus phi to plus phi sine n omega t, sine m omega
t dt is equal to phi times delta n m that is what we are familiar with, so this means
that this is non-zero only when n equal to m and when it is n equal to m, the values
So we can use this property and obtain these coefficients as an as f of t sine n omega
t dt and bn as f of t cos n omega t dt, this is something which we are familiar with in
the Fourier series and we always that the function has to be periodic for you to obtain,
for that you can write it in this form. So Fourier transforms is the extension of this
into even non-periodic functions.
So that is what we are going to look at here. So remember that what we did here was to write
the function as a sum of sine and cosine functions with some coefficients an and bn and then
we obtain the coefficients an and bn by integrating multiplying this function with sine and cos
respectively and integrating from minus t by 2 to plus t by 2.
So it is a 1 over t of minus t by 2 to plus t by 2 is what we will get like this. Okay
so that is something which we are all familiar with, so now let us say we have instead of
a periodic function like this let us say we have a function of this form. Let us say,
we have a function which is something like this. So we have a function t and f of t.
So here, we have a finite set of coefficients we will get in your periodic function, we
have a finite set of coefficients, you will find this an's and bn which would make up
this periodic function which repeats itself. On the other hand, if you have a blip like
this and then you will have, if you want to writer this in terms of sine and cosine function
there will be all, there will be infinite number of harmonics in this kind of a function.
So the extension of the Fourier series to functions of this form, the extension of the
Fourier series to functions of this form would be to write this as f of omega as integral
minus infinity to plus infinity, e to the power of i omega t, f of t dt. So that would
be the form.
So actually you should write i omega here f of i omega as so normally written with a
capital F. So f of i omega as minus infinity to plus infinity of e to the power of i omega
t f of t d t and so this is this function are called the Fourier transform of f of t
for some variable t. So for some variable t, I can write an integral of this form e
to the power of i omega t, f of t dt and then I would get f of omega. So that is the extension
of the Fourier series which we know of for non-periodic functions.
So for non-periodic function instead of writing a Fourier series, we would write a Fourier
transform and the Fourier transform is given by this and the inverse Fourier transform
would be then, we can also write f of t in terms of f of omega and then I would write
1 over phi, 1 over 2 phi integral minus infinity to plus infinity, now e to the power of minus
i omega t, f of i omega.
So now you write f of i omega d omega that would the inverse Fourier transform. So now
we have a definition of a Fourier transform and an inverse Fourier transform. So what
we would be concerned about is how to compute such quantities, when we have a discrete set
of data points, when we have the function itself sampled at a discrete set of points
in t and then how do we compute the transform of such functions and that is what we would
be concerned about here, that is to say that we have values of the function given at let
us say some discrete interval t by n, let t is the total interval we have.
So we have a finite set of discrete values collected, let us say in an interval from
0 to capital T, that is the total interval which we have and then let us say it is in
n equally spaced sub intervals, we have this data collected that is equal space delta t
is t by n and then how do we compute the Fourier transform of this. So that is we will such
computation will be called a discrete Fourier transform as opposed to the integral transform,
we will use a discrete Fourier transform.
So as opposed to an integral to obtain the Fourier transform, we will here do a discrete
sum and that is what we will be looking at, so to fix a notation the data collected let
us say f of t is our sample the data collected in this interval we will write as f subscript
n. So that is the data f at time t, f as a function of t collected at the interval n
th interval will be written as fn and that is what we would be using it. So remember
these things, so what we have to do is to do a Fourier analysis of a non-periodic function
of this form. So that is what we want to do.
So and then we would write that Fourier transform and the inverse transform in this fashion
this 1 by 2 phi could be in either of them not in both you could put either here or here.
So this is part of the differential, so this 2 phi which is normalizing factor here. So
that is what we are trying to compute. So now let us say we do not have the data in
a continuous form like this but we have it collected at equal intervals in this variable
t, let us say in the interval from 0 to t and then we want to do the transform of that
and compute the transform of that, that is what we will be now looking at.
So in the discrete Fourier transform when we compute we said that we would divide the
interval into n equally spaced sub intervals and denote the function by fn. So graphically
it does that you have a function which goes from 0 to t and then you sample this at equal
intervals here and then each of these values in each of these values we denote by fn.
So that is the idea and then this transform which is our continuous transform which is
our continuous transform that is minus infinity to plus infinity f of t e to the power of
i omega t dt which is now sampled at n equal intervals. So we define this notation omega
k here which I wrote as 2 phi by n times some integer k. So this transform is then written
as in this form. So we would write the discrete transform from the continuous 1 that is f
of k. So what we have written before as f of i omega
k equal to integral minus infinity to plus infinity f of t, e to the power of i omega
k t dt will now be written as a sum of all the function values fn remember n is the function
value n sampled at the n th interval multiplied by e to the power of minus i omega naught
k times n. So where knn here are integers and the sum goes from n equal to 0 to n minus
1 there are n points here.
So n goes from 0 to n minus 1, so this 1 by n is again is a normalizing factor. So which
can be put either in this or in the inverse Fourier transform? So this continuous transform
is then now turned into a discrete sum and the inverse transform which is f of i omega
k, e to the power of i omega k td omega k for every t is now written as fn is k going
from 0 to n minus 1, fk e to the power of i omega 0kn.
So remember k and n are integers here. So now this is equivalent of saying f of t is
equal to integral minus infinity to plus infinity f of i omega k, e to the power of i omega
k t d omega k. So remember omega k here is 2 phi by n times k, k is an integer. So now
this is a 2 sum expressions which we are going to use to compute the discrete Fourier transform.
So that is the Fourier transform this is the function evaluated at a discrete set of points
and then we would get a f of k's and using the f of k's, we can compute the function
at that discrete set of points using the inverse Fourier transform.
So this is the 2 transforms and now you can see that if I want to actually compute this
transform using this n functions, n intervals and then to compute this quantity for every
k we have to do n into n operations. So let us look at that, so this has to be computed.
So we have n values of f capital n values of f from 0 to f n minus 1. So this sum now
that we know what the discrete transform is now this sum used for every k going from 0
to n minus 1.
So there are n such cases for each of this case we have to do n sums. So n products and
n sums, so the number of operations goes as n square. So as you increase the k number
of k values or the number of n values the computation involves also blows up as n square
and similarly, for the inverse Fourier transform so that is the problem with computing the
discrete Fourier transform. So you can compute this, so 1 way of computing this is the following
that we use the property that this can be written as cos that is I can write fk as 1
over n so times sigma n going from 0 to k minus 1 and we say that it is fn times cos
of i cos of omega 0 kn plus i times sine of omega 0 kn.
So that is how we compute this, so we have to evaluate these functions at all the for
each k, for each k we have to evaluate these functions n times and then do this product
separately. You write it in this fashion so that even in languages like c which cannot
handle complex numbers, this is a complex number. So languages like c which cannot handle
complex numbers can do this transform can compute this transform by using the doing
2, it in 2 different parts.
So we will have a f of k is the real part. So we will have, we will compute fk real,
so real part of f of k let us call it as f k real. So that will be 1 over n sigma n equal
to 0 to k minus 1 fn cos of omega 0 kn and then we compute f k imaginary part as 1 over
n sigma n equal to 0 to k minus 1, fn sine of omega 0kn. So we can compute these 2 separately
and thus I do not have to handle a complex number but the problem is really that the
numbers of operations are extremely high.
So that is the problem with this discrete Fourier transform computation of discrete
Fourier transform. Okay. so there are better methods of doing this and 1 of them is called
the fast Fourier transform and that is what we would be actually interested in. So let
me just summarize this, so we would divide the interval t into n equal intervals and
then denote the functions by fn and then you would compute the Fourier transform as using
this form, that is e to the power of ik omega 0n, fn as the Fourier transform and the inverse
Fourier transform as 1 over n, sigma n equal to 0 to here, it should be k equal to 0 to
n minus 1 e to the power of this sum is over k and this sum is over n.
So our omega 0 here is 2 phi by n. So as I said the problem is the number of operations
here and the number of operations can be reduced while going to what is called a fast Fourier
So this dft which is discrete Fourier transform requires n square complex operations the complex
operations can be reduced to the real operations by writing this as e to the power cos ik omega
0 n plus i sine k omega 0 n and then computing the real and imaginary part separately that
means we actually have 2 times n square real operations in this computation. So 1 way to
go around this is to use what is called the fast Fourier transform, this is a very clever
technique which allows us to compute this discrete Fourier transform in n log n operations.
So we use the symmetry of the trigonometric functions to get to compute this discrete
Fourier transform in n log n operations.
So that is what we would be now looking at, so the basic idea is here that you have this
n number, n functions, we have n functions now this n is now we have n such intervals.
So let us write that here. So we will, let us say we have functions like f0, f1, f2,
f3, f4, f5, f6 and f7, okay, let us say we have eight such function values and then the
idea is that we would divide this into 0 to 31 and 4 to 71 and compute the discrete Fourier
transform each of them and then we can show the whole idea behind fast Fourier transform
is that we can actually divide this into smaller and smaller sub sets and then compute the
Fourier transform as a cascade that is what we would see.
So that is the whole idea because what is called the Sand-Tukey algorithm. So we will
see that now in the, so the algorithm is the following that we would write the Fourier
transform f k of the function fn as a function of this form that is sigma n going to 0 to
n minus 1 fn wnk. Okay so now that is same as what we have written here.
So this 1 now the wn's now nk is nothing but that. So we are going to write this function
as write this discrete Fourier transform we are going to write as let us forget 1 over
n for the time being, let us say this is our discrete Fourier transform, we will put the
1 over n in the inverse Fourier transform and then we write this as sigma n going from
0 to capital n minus 1 we will say that it is fn we say some function called w to the
power kn, k and n are integers.
So now this w is nothing but e to the power of minus i omega naught and remember omega
naught is 2 phi by n that is what we have here. So now this is the form which we are
going to write remember we will always we using this w, so this w is e to the power
of minus i omega naught and I would write this as this transform as fn e w times kn.
So now as I said, we will divide this interval into 2 so this interval n minus 1, this n
functions will now divide it to n by 2 and n by 2 and write the sum now sigma n going
from 0 to n by 2 minus 1 fnwkn plus sigma n going from n by 2 to n minus 1 fnwkn. So
that is what we want to we would write so let us use slightly different it does not
So we have sigma n going to 0 to n by 2 minus 1. So this n is now split into, so the n functions
are now n function values which we have is split into now 2 intervals 1 goes from 0 to
n by 2 minus 1 and other goes from n by 2 to n minus 1. So these 2 intervals we will
write, so now we will make a small change of variable. So that the sum is actually going
from 0 to n by 2 minus 1.
So we want to write that so this the way we can write is to say that this is sigma n equal
to 0 to n by 2 minus 1 fn w kn, w to the power kn and then we say that here in the sigma
we say this is fn, we call some variable n plus n by 2 and w power k m now the m now
goes from 0 to n by 2 minus 1. So m goes from 0 to n by 2 minus 1.
So you see when m is 0 this is n by 2 and that is what, when n is n by 2 that is what
we have so these 2 are the same I just made a small change of variable went from n to
m and then by adding, so n is m plus n by 2. So I made n is m plus n by 2, I made this
small change of variable to write this as both the sum as 0 to n by 2 minus1. So I can,
here also I had to write that n by 2.
Okay so I have this thing here. So now you see these are dummy variables m and n are
dummy variables, so I can just write them as n itself so I will write the Fourier transform
my discrete Fourier transform as n going to 0 to n by 2 minus 1, we will say fnwkn plus
fn w power k times n plus capital N by 2. So now you see my sum is now only over n by
2 function values and 1 this fn w, so what I have done is this is a dummy variable. So
I just took the, this line is exactly the same as this line only thing is I have put
the sum as 1 here because m and n are dummy variables.
So I can actually pull out fn from here, we can see so you can write I can pull out wkn
from here and then write this sum as fn plus fn plus n by 2 w to the power n by 2 multiplied
by wk. So let us write it that fashion. So going back from here, we would write so what
we have written here is this that the Fourier transform we wrote as fk as sigma n equal
to 0 to capital n minus 1 and we said I can write it as fnwkn plus sigma m going from
n by 2 to capital n minus 1 this is n by 2 minus 1 this is n minus 1.
We said I can write it as fnwkn I just split that into 2 this Fourier sum and then we made
a change of variable and then we got this now as sigma n going from 0 to n by 2 minus
1 I can write it as fn plus w to the power kn by 2 into fn plus capital n by 2 into wkn.
So what we have done is to make a change of variable here and then I wrote it as m going
from 0 to n by 2 minus 1. So by making a change of variable, so this will become fn plus m
by 2 and w to the power kn plus m by 2 and then we split that. So let us go through over
this again once again.
So we have this written here and then I made a change of variable here and then make this
going from, instead of going from n by 2 to n minus 1, I have it going from I am going
from 0 to n by 2 minus 1 and then I change this to m plus n by 2 and here also m plus
n by 2 basically I made this change of variable here and then I said that this n and m are
So I can pull that out and write it as fn both as sum over n there is nothing which
prevents me from doing that because these are dummy variables and then I can pull out
this omega kn from this omega kn I can pull out, it is common in both the terms and write
it as fn plus wkn by 2 fn plus n by 2 wkn. So now remember what is w, so w is nothing
but e to the power of minus i times 2 phi by n that was our w, that is i omega naught
was omega naught was 2 phi by n.
So it is i times minus i times 2 phi by n, so what is w to the power kn, so w to the
power k n by 2 so w to the power kn by 2 is nothing but e to the power of minus i, 2 phi
by n into k times n by 2. So that is we know is nothing but e to the power of minus i phi
to the power k.
So realizing this is the key to fast Fourier transform. So from up to this it is a discrete
Fourier transform all we have done was to split this into 2 halves and we are still
doing the same number of sums. So here again we are doing the same number of sums but now
we realize this w to the power of kn by 2 is actually e to the power of minus i phi
to the power k and we know that e to the power of i phi is just minus 1. So this is just
minus 1, so what we have here is actually minus 1 to the power k, now that is the trick.
So we have minus 1 to the power k, so all we have to do is to write this as now fn plus
minus 1 to the power k fn plus n by 2 now this is obvious that this would mean that
for all odd integers this becomes minus and for all even case it becomes plus. So if you
are computing fk for even case then this is fn plus fn by 2 and if it is for odd case
then we are computing it as fn minus fn plus n by 2.
So that is the sum, so we will write this sum now remember this. So we can write this
as minus 1 to the power, so that is nothing but minus 1 to the power k. So we have now
this fk as so we say fk as sigma n going from 0 to n by 2 minus 1 so we say fn plus fn plus
n by 2 wkn for k odd, for odd k and equal to sigma n going from 0 to n by 2 minus 1, fn minus fn plus n by 2 wkn for
even k minus for even k and plus for, minus for odd k and plus for even k. So we have this sum,
okay now we have 2 different sums, we have sum of the functions here for all the even
k values and difference between the functions in the 2 halves for the odd k values.
So remember if you have the function tabulated in this form. Okay so now that is taking the
difference for, difference between 2 functions for all the odd k values and taking the sum
between the functions, so this and that. So we divide this into 2 halves here, so what
we are going to do is we are taking the difference between these 2 and the sum between these
2. So this is 0 and n by 2 minus 1, so that is what we are going to do.
So we are going to take the sum and the difference between these half functions and this half
functions and write them that is the key to this Sand-Tukey algorithm so we, so let me
summarize this again here. So we write this function fk as fnwnk and then we would write
that as 2 different sums that goes from 0 to n by 2 minus 1 and n by 2 to n minus 1
2 functions fn e to the power of minus i this is omega naught which I had written as kn
and e to the power of minus i 2 phi by n kn.
So now these can be written by a small change of variable going from this again, the second
part as we said the second part here we make a small change of variable here and make this
sum go from same 0 to n by 2 minus 1 that I can do by defining a variable m which is
n minus n by 2. So that is what I have done here. So we have that here.
So we have m going from 0 to n by 2 minus 1 fm plus n by 2 e to the power of i now there
is this m has to be replaced by m plus n by 2. So this part, so second part of the sum
we modified a little bit and to this form. So the sum is going from 0 to n by minus 1
and going from 0 to n by 2 minus 1 here also so I could pull out this sum here and also
pull out this e to the power of 2 phi, minus i 2 phi by nkn which is common for both of
this because m is just a dummy variable.
So I can pull out these 2 and then write it as f n e to the power of minus i phi k, now
phi k because now when I multiply it here you this 2 phi by n and this n by 2 cancel,
so we have i phi k, so fn plus e to the power of minus i phi k fn plus n by 2 e to the power
of minus 2 pi kn by n. So that is our Fourier transform and then we said that now this is
nothing but minus 1 to the power k, so that things become simple. So I can write now this
as 2 different parts.
So I can write this as 2 different parts 1 is for the even values that is f2k's, so now
I can write for the even functions I write it as sum because minus 1 to the power k is
1 for even k values. So that is f2k if I can write it as for k going from 0 to n by 2,
so I can write it as f 2 k and then for all the even functions I have it as sum of these
2 and for the odd functions that is 2k plus 1 so I split this sum k's into 2k and 2k plus
So then I can write that as the difference between these 2 functions. So I have 2 things
quantities here. So I have a f 2k and a plus and a minus function there are 2k plus 1.
So the idea here is that I am writing this as for odd k values this 1 and even k values
this. So to make sure that these odds I would write this as 2k, I can change that 2k and
say that this is for all k going from 0 to n by 2, n by 2 I can do this for n minus 1
by 2 I can do this for all k values for 2k.
So I can do this up to that n by 2 minus 1 n by 2 minus 2 here it will be, so I will
have that many values in the even thing and similarly, I can write this as f 2k plus 1
again 2k and 2k plus 1, this is for the odd function and this is for even values I can
write this as 2 different sums this is to make sure that this is 2k.
So I should write here also as 2k and I should write here as 2k plus n that is n, so I have
2 sums here 1 is 2k plus 1 and other is over 2k. So that is for odd and the even functions,
so that is what is here. So this is for the odd function, so w to the power 2k plus 1
is now here split into 2 parts 1 is 2 phi n by n and other is 2 phi kn by n by 2. So
2 parts I just, this is basically just w to the power 2k plus 1, so that is for the odd
values for the even values remember it is the sum here. So now that is the basic algorithm
this algorithm now can be implemented.
So in this 2 sums can be implemented very, in a easy fashion by replacing the function
values by its sum and its difference now that the whole trick here. So we have this f2k
that is for the, we have a series of fn function values we have going from 0 to n by, we have
0 to n, so we have 0 to n minus 1 we have n function values now this n function values
we take and we split that in to 2 halves n by 2 minus 1 and n by 2 to n and then what
we do is we take the sum and the difference of these function values and replace these
functions by its sum and difference.
So we will use a same array and then replace them by the same sum and difference. So that
is what you are going to do, so you see that we wanted to compute for the odd and the even
values of k, so 1 is replaced by the sum and the other is replaced by the difference and
then we do the discrete Fourier transform of that.
So if you look at this expression here these 2 expressions, so you see this very clearly
that this is the expression for the discrete Fourier transform of n by 2 functions n by
2 function values which is given by fn plus fn, n by 2 and this is our normal Fourier
transform. So remember how did we write the discrete Fourier transform, so when you wrote
the discrete Fourier transform we said that fk is sigma n going from 0 to n by 2 minus
1 fn plus fn e to the power of i omega k. So that is the same thing here i omega k that
is what we had written.
So now here the function to whose discrete Fourier transform we want to find is now fn
plus fn plus n by 2 that is the sum of the 2 functions here and here the second part
is the discrete Fourier transform of the difference of these 2 functions. So let me say that again,
so following that we have this functional values here. So now what we do is we take
the sum let us say now we are, I will write f0 plus f4 here and this and that I take the
sum and I write that and I take the difference and I write that here f0 minus f4 and also
multiply it by w to the power, in this case it will be w to the power n.
So that is what we would write here and then because you see the difference here is that
for the even functions it is w to the power 2nk and for the odd functions we have the
difference and there is also this extra wn here. So I would write that also if I have
to do the sum.
So I have to write this also here w to the power n and similarly I could take for all
of them now this will be replaced by f1 plus f5 and this will be by f2 plus f6 and this
will be f3 by f3 plus f 7 all the differences we would write here that is f1 minus f5 and
f2 minus f6 and f3 minus f7 all of them multiplied my wn. Okay and then we can do the discrete
Fourier transform of each of them now you do the discrete Fourier transform of each
of these values each of these function sets and then we would get the desired answer but
now you see we know that this scaling, let us look at the scaling we said that the discrete
Fourier transform as n squared operations.
So we have n is equal to 8 here. So we will have about 64 operations here and then while
this is 4 and this 4, so then we will have 16 plus 16 operations. So we have 30 operations.
So by splitting this into 2 halves and then doing the discrete Fourier transform of each
of them we are able to reduce the number of operations now we can split this into further.
We can split this again further and do the discrete Fourier transform for each of them
and that is the idea of the fast Fourier transform.
So graphically, we can show that here so before that let me summarize this. So what we are
saying is we are defining new functions which is fn plus n by 2 and fn minus, fn minus fn
by 2 this is I am calling these functions would be called as g0. So let me call this
in the notation we use this is g0, g1, g2, g3 and this we would call as h0, h1, h2 and
h3 and we do the discrete Fourier transform for each of these functions here separately
and that is what is written here. Okay, now these Fourier transforms would be called gk
and hk remember now it is 2nk here.
So it is 2nk when you are multiplying when you do the discrete Fourier transform remember
that this will be 2nk where omega where w here is e to the power of i times 2 phi by
capital n into 2nk, if you are doing the whole function Fourier transform, discrete Fourier
transform we would be writing it as fn. So remember if it is a full Fourier transform
using discrete Fourier transform then we would be saying that fk here, will be equal to sigma
n equal to 0 to n minus 1, now this n is actually n by 2 this sum is reduced to half.
So, otherwise it will be n minus 1 gnwnk this is gk function. So we have actually reduced
the numbers into 2 halves here. Okay now that can be I can show this in a simple, graphically
I can show this in this fashion. So I have this f0, f1, f2, f3, f4, f5, f6, f7 listed
here then you take 2 functions f0 and f4 and make the sum and the difference and you write
the sum here and the difference here and then you could do this for all the function values.
So you do this for f0, f4, f1, f5, f2, f6 etcetera and then you get these 2 sets now
this is what we call g0, g1, g2, g3 and this we call h0, h1, h2, h3 and then you do a n
by 2 point discrete Fourier transform here and then n by 2 point discrete Fourier transform
would give us the Fourier transform of all the k values which are even here and all the
odd values here.
So let me repeat this again that is I take these function values I tabulate them here
and then I take the sum for f0 and f4. So this is the line which marks that f0 and f4
and I take the sum here and write that and then I take the difference between that f0
and f4 which is here that is the difference multiplied by w0, w to the power 0. So because
I have written here remember I have to multiply it by this n.
So n here is 0, so w0 and then in this case it will be w1 and in this case it will be
w2 and in this case it will be w square and w cube etcetera. So that is what you have
to write and that is what I have written here. So here let us replay this once again we have
these functions here and you take these 2 and then you find the difference you have
written here and the sum there and similarly, you find all the sums and differences for
all for each of the pairs and then you take these functions here, the differences multiply
them by the weight that is w to the power 0, w to the power 1, w2 and w3 and then tabulate
them as g0, g1, g2, g3 and h0, h1, h2 and h3 and then you have a set of n by 2 points
here and you have another set of n by 2 points and you do the discrete Fourier transform
Let us say we stop it here we can actually do this again. So let us continue this operation
but let us first look at this I can do a n by 2 point discrete Fourier transform here,
now what do you get is here the f or the Fourier transform of this if this whole thing was
a black box, you do not know what is going on we put in these functions here and we got
the Fourier transforms out here, but when you put in f0, you get the corresponding Fourier
transform capital F0 and you put in f7and you get the corresponding value transform
of f seven f this for k equal to seven and this for k equal to 0 but the f1 will now
be replaced by f2 and f2 will be replaced by f4 and f3 by f6.
So now, so when you put in here the function values into this black box, you put in the
function values in this order the Fourier transform, we get in a slightly jumbled up
order. So we are going to get it as f0 and then we
are going to get f2 for k equal 2k equal to 4k equal to 6 and then k equal to 1 3 5 and
seven because we have segregated the even and the odd Fourier transforms. So now we
can do this continue this again we can take this box here, which has now n by 2 points
in this case there are 4 points and these 4 points can be split further up. So we see
that to start with we had this 8 points and then we made them into groups of 4 and then
we did a 4 point dft here.
So as I said we will further divide these 4 points and then continues this process.
So let us look at that in the next slide. So we have here this 8 points, that is 0 to
7 and then you had this now we had grouped them into 4 and 4 and then we said, that we
could do a 4 point Fourier transform here. So let us do a 4 point fast Fourier transform
again here. So that is, we could do a 4 point discrete Fourier transform or we could do
a 4 point fast Fourier transform.
So let us do this fast Fourier transform, so that means we will again do what we did
on these points here again that is, we took this 4 and 4 and we added f0 to f4 and replace
f0 with that sum and we took the difference between f0 and f4 and replace f4 with that
difference multiply it by w to the power 0 and we took f1 the difference between the
sum of f1 and f5 and replace f1 with that sum and we took the difference between f1
and f5 and multiply it by w to the power 1 and replace f5 with that and so on.
So we will do exactly the same here now the input to this was remember g0, g1 let us just
go back and see that again so we have the input as g0, g1, g2, g3 and here the input
we call as h0, h1, h2 and h3. So when we do an by 2 point fast Fourier transform instead
of dft, we will take g0 and g2 find the sum replace g0 with that and then g1 and g3 and
take the sum and replace g1 with that and take the difference between g0 and g2 and
multiply it by w to the power 0 and replace g2 with that and take the difference between
g1 and g3 multiplied by w to the power 2 and replace g3 with that.
So notice that difference that is when we take the difference here, we go away w0, w1,
w2 w square w3 etcetera but when you do that here, then we take g0 minus g2 multiplied
by w to the power 0 while g0 minus g3 multiplied by w to the power 2 similarly, here we replace
h2 by h0 minus h2 into w to the power 0 and h1 minus h3 into w to the power 2, that is
what we do.
So when we do that what we get is starting from these values so we will get, we have
these n by 2 points and we this g0, g1, g2, g3 here and h0, h1, h2 here and we do a again
a Fourier transform here, fast Fourier transform by doing this split. So let us look at that
here. So that is the 4 points g0, g1, g2 and g3 and then we can take the sum and the difference
of g0 and g2 and replace g0 and g2 by the sum and the difference, okay. So again note
that when I multiply g2 and g3 with w's it is w0 and w2, w square w2, I mean w square.
So then now we have this set of 2 points here and the set of 2 points here, now I can again
do the continue this transform again by taking these 2 points and then these points as these
2 difference set. So we had 8, we just split into 4 and then that is further split into
2 each and then that too we will use and take the sum and difference and write now the whatever
we got here.
Okay so we take that the sum of these 2 and replace this point with the sum and take the
difference between these 2 multiply it by w to the power 0 and replace that is just
the difference and we replace this point with that similarly we take the sum between these
2 points and replace this point with the sum and take the difference and replace this point
with the difference. So now that gives us the Fourier transforms, so final answer when
you do this cascading similarly we can do for h also.
So we could do the same thing for h, so we have the h0, h1, h2, h3 here we take the sum
between h0 and h2 and replace h0 with that take the difference between h0 and h2 and
then replace h2 with that and take the sum between h1 and h3 replace h1 with that sum
and take the difference between h1 and h 3 multiply it by w to the power 2 and replace
h3 with that and now we take these 2 points take the sum, replace the first point with
that and take the difference replace the second point with that and similarly here.
So that leads to the full Fourier transform when you do that here. So the end result is
that we have the Fourier transforms and in this order, so when you are do this thing
it is as we are taking the sum and the difference in replacing those numbers with those sum
and the difference multiplied by the appropriate weights what we find is that we actually jumble
up the order of the Fourier transform.
So we start with an array which contains the function values at 0 in an array, let us say
in this case dimension from 0 to 7 and in this case and finally what we get is the Fourier
transforms which are again goes from 0 to 7 but not in the same order as we have got
here. So it is not in the same order that we get here. So that is the highest value
and the lowest value will be the same for the k values.
So f0 and f7 are but the in between values get jumbled up you can see that after f0 the
next array point that is what we had the function in the f1 is now replaced by the Fourier transform
for k equal to 4 and f2 is say the same as 2 but f3 is now replaced by the Fourier transform
of k equal to 6. So what we see is that we start with an array which contain function
values from 0 to 7, we started with that and then we are ending with Fourier transforms
in the same array, the same array the functions are now replaced by its Fourier transform
but not in the same order.
So now what order it comes in and how we can decipher which k value, which function which
functional values replaced by the Fourier transform is what k values are they replaced
for we will see that in the next class.