Ch9-1 FFT

NYCU OCW
75粉絲
2023年12月3日
DSP YouTube 播放清單:https://www.youtube.com/playlist?list=PLj6E8qlqmkFuUfwSfmEXgjeJI33ZxxmSd
The course aims to provide the fundamentals of discrete time signal processing.
授課教師:電機工程學系 林源倍老師(Yuan-Pei Lin)
課程資訊:http://ocw.nctu.edu.tw/course_detail.php?bgid=8&gid=0&nid=550
授權條款:Creative Commons BY-NC-SA 3.0
更多課程歡迎瀏覽交大開放式課程網站:http://ocw.nctu.edu.tw/
那我們今天看的這個第九章大概應該算是整個DFT的歷史上非常重要的一個發明
大家上次在做那個實驗的時候
是不是有寫那個
寫這個對不對
寫這個YK
寫那個DFT的那個式子對不對
用MainLab來做寫這個東西
我請大家用這個式子來implement那個DFT對不對
那當你的DFT的size比較大的時候有很慢嗎
有很慢齁
可以讓你感受一下這個慢了之後呢
就會覺得這是很偉大的發明
這個是Fast Fourier Transform
So that's what we gonna talk about Fast Fourier Transform
How to compute DFT in a fast manner
It's an algorithm that compute
Well actually there are many version of FFT
An algorithm that compute DFT efficiently
FFT efficiently
So let me first ask you a question
Suppose we have this Yn
And we want to compute this endpoint DFT
K from 0 to N-1
And it's an endpoint DFT right
Endpoint DFT
How much computation is involved
How much computation
When we talk about computation
We may think about the number of multiplications
And the number of addition
We need to do in order to compute the DFT
So what's the number of multiplication
And what's the number of addition
We need for computing the DFT
So how many multiplication and addition
Multiplication and addition are needed
Oh well
Remember DFT we can really
When we look at this DFT we can really
Remember in the video we talked about
The DFT can be arranged in a matrix right
In a matrix
And this is the DFT matrix
This is Y0 to Yn N-1
We did have this equation in the video do we
We do right
We have this video
We have this equation okay
So right sitting right here in the middle
Is the DFT matrix
And it's N by N matrix right
It's an N by N matrix okay
So to compute the DFT
It's essentially the same as multiplying
This matrix with this vector right
So what's the number of multiplication
And the addition doing
That we will need to do this
Well let me ask you a general question
Suppose I have this A matrix
This is N by N
And I want to multiply it with the vector Y
This is N by 1
How many multiplications do we need
It depends on N right
How is it related to N
N square yes thank you
It's N square right
It's N square
That's number of multiplications
Multiplication is N square
And how about additions
For each output element
How many additions do we need
We need to add up how many numbers
For compute for computing each element
We need to add up N numbers right
And when we add up N numbers
How many additions do we need
N minus 1 yes thank you
N minus 1
And we need to compute N output right
That's the number of multiplication
And addition in general
For A matrix and vector product
All right
So this is what we say in the order of N square
See this is N square
And this is N square minus N
And when N is large
This behaves in the order of N square
This is in the order of order
This O stands for order of N square
And for example
Suppose this N is equal to 1024
Around 1000
2 to the order 2 to the 10
This is a very common number for computing DFT
And this number goes up to around 1024 square
And then there will be around 10 to the 6
But that's the general case
That's the case when we just have some matrix A
And some vector that we don't know nothing about
That's the number of multiplication that we need
And the number of additions we need
But we are not talking about some arbitrary matrix here
We are talking about a matrix
That we already know
The elements
Each element we know very well
We know very well what it is
We know exactly what the MM element in this matrix is, right
So this is not some arbitrary matrix
We know a lot about this matrix
How is it possible that we can exploit
Some structure of the matrix
So that the computation of this output DFT
Can be made more efficient
And that's what FFT is
So for the next hour
What we are going to see is how we can exploit
The property of this DFT matrix
And then we can compute the DFT
Much more efficiently
Then just direct multiplying out
The element by element
All right
This FFT
It actually started very early
It was a long time ago
It was probably around 1805
Around 1805
Gauss
He wanted to compute the orbit of some little stars
So he used this concept of FFT
But his work
It was actually published after he died
And what kind of language
We don't know very well
At that time it was written in Latin
So not many people went to see this thing
So it seems that this thing has been forgotten
Then until the 1960s
Probably around 1960
At that time
The world was in a cold war
So there were the Soviet Union
And the United States
So in the 1960s
The Soviet Union was making nuclear weapons
They had some nuclear weapons
They made nuclear weapons
If they made nuclear weapons
Of course the United States wanted to know
How advanced their weapons were
So they wanted to collect this information
But when they made nuclear weapons
It must have been in their territory
It must have been in their country
Or in those places where the Soviet Union was
To make nuclear weapons
But the United States really wanted to know
Their information
So they thought about
Whether to use some earthquakes
Earthquake to detect
Because there was a wave when the nuclear weapons were made
So they wanted to put a lot of earthquakes
Of course the earthquakes
Could only be placed in these countries in the United States
Because the earthquake was very clear before
Maybe everyone's age
Let me think about it
Everyone's age
When everyone was born
The Cold War should have ended a long time ago
The Berlin Wall collapsed in 1989
Everyone was born after that
So the earthquake was very clear at that time
So if you want to put an earthquake
It must be placed in
These countries that are friendly to the United States
After they put some
When the wave passed
They would analyze this information
But this information
This is a wave, right?
Wave
So it sounds like it should be used
Time domain or frequency domain to analyze
They really wanted to use frequency domain to analyze
But when you use frequency domain to analyze
You need to do DFT
But at that time in the 1960s
Our
Computing power was not very strong
So I've been thinking about
How can I calculate faster
At that time in 1960
At that time
Gennady
The president at that time was Gennady
He held a meeting
He invited a lot of people to come and discuss
How can I do this
The analysis of that information
At that time
There was a man named Tutsi
This Mr. Tutsi
He is from IBM
At the time of the meeting
He came up with an idea
That is to say
What kind of method
Can make him calculate faster
Because at that time
There was another algorithm
It's called Good
Good
He came up with a
Algorithm called Prime Factor
That is to say
If the DFT I'm going to do now
It's when two values are multiplied
Then I can make him calculate faster
But this Tutsi
At that time he came up with
He wanted to say
Is it possible
That is, ordinary numbers can also
Then how can it be
To make him a little faster
When he came up with this idea
At that time there was another
The man from IBM
He just
The Tutsi he came up with
It's just an idea
He didn't have it yet
Very carefully
To calculate it
So how can I
To implement it
At that time IBM
There was another person
He helped Tutsi
Find a Princeton
At that time in Princeton's Cooley
Tutsi and Cooley
Cooley is from Princeton
He helped him find Cooley
Then he invited them together
To figure out how to do this
At that time he was in the Cold War
So everyone's love for this kind of thing
It's really confidential
So he didn't tell Cooley
Say we want
This is to do with
What kind of Soviet
What kind of nuclear test report
He didn't say
He just told Cooley
This is with the crystal
Tell him this is to
Analyze what crystal data
So Cooley was kept in the dark
But no matter what
The two of them worked together
Then the FFT algorithm
Was studied
And published in a
1965 paper
It also made a
Complete analysis
If we use
This FAST algorithm
Then compared to
In the past
If we didn't use FAST algorithm
At that time
How much saving
How much
How much budget can be saved
So this is
Almost 160 years later
Then it was rediscovered
Then we can look at
Cooley and Tukey
The two of them
This discovery
For our whole FFT
This budget
How much
How much benefit
So let's see
This is the endpoint DFT
So let's first
First look at the case
The simplest case
What is the simplest case of DFT
K, what is the simplest case
How many points of DFT
Will be the simplest
1
Well, for one point
You cannot do anything, right
2
2 is the simplest case, right
So let's start with 2
The case that n equal to 2
We would have 2 point DFT
If we have just have 2 point DFT
We would have yk
equal to y 0 plus y 1
And then e minus j pi k, right
n equal to 2, so it's just pi, right
And k equal to 0 and 1
So let me write it down
k equal to 0 and 1
Then we would have y 0 and y 1
We just have 2 point, right
And for y 0, for k equal to 0
What do we have here
When k is equal to 0
We have k equal to 0
And this term will go away
So we just have y 1 here
And then for y 1, we have y 0
And then k equal to 1
And what is this value
Minus 1, right
So y 0 minus y 1
So for 2 point DFT
How many multiplication and addition do we need
2, we need 2 addition, okay
So we need 2x
And how many multiplication
Usually in a computer
When we do this minus
When we multiply with minus 1
We don't really need to do any computation, right
But it depends on the representation, right
If you have a sign bit
Then let's just do the flip of the sign bit
So this part doesn't require multiplication
So we just have 2x, all right
So we have a y 0 here and y 1
And if we have a y 0 plus y 1
So this one goes up here
Then we get y 0
And this one moves down
y 0 minus y 1
We get y 1, is that okay
And this is what we call a butterfly
So for 2 point DFT, it's quite easy
We don't need any multiplication
Just addition is needed
And the implementation is quite simple as well
So this is what we call a butterfly
Now let's work on the case
When we have a big N
Now suppose, let's consider the more general case
And a bigger N
And this N is a power of 2
N is a power of 2
2 raised to the power r
And N is half N
So let me write down the equation y k again
y k is y 0 plus y 1
And w N k plus y 2 w N 2 k
All the way to, and let me write one more
y 3 w N 3 k w N N minus
This w k w N is e minus j 2 pi over N
Okay, in our lecture
Do we use the subscript N in the lecture
Okay, that doesn't matter
I just put a subscript here
So that we will know that this N is this N
Okay, all right
So that's DFT
Okay, now let's make one very, very important observation
y k, we have N terms here, right
And N is a power of 2, okay
Now let's split these N terms into two groups, okay
One that consists of even, even samples
y 0, y 2, y 4, okay, and so on
And the other group will be the odd samples
y 1, y 3, and y 5, and so on
Okay, so let's do that
So first we have a y 0
And then this one, y 2, w N 2 k
And then y 4, w N 4 k, continue on
All the way to y N minus 2, y N, N minus 2, and then k
These are the even samples
The terms corresponding to the even samples
And now the odd samples
y 1, and then y 3, and then y 5, okay, and continue on to 1
And for y 1, we have this term, right
y N k, y N k
And y 3 has y N 3 k, okay
Let's pull out this y N k, y N k, okay
If we pull this out, what will happen?
Then this y 1 will just be by itself, right
There is no additional term
And this y 3, it was 3, right, 3 k
And now we pull out k, we are left with w N 2 k, okay
And similarly for y 5, we only have 4 k
And this one will be the same as
After we pull this out, the first term
Consisting of all the even samples, the y bracket and the blue bracket
They will look the same, right
Except the numbers are different, except the numbers are different
But the formula is exactly the same
And what's the thing in the bracket?
What's the thing? For example, the y bracket
What's the thing in the y bracket?
Does it look a little bit like the DFT formula?
It looks very much like it, right
Only this power is different, right, okay
So let's try to observe what this is
See, if we have a w N, these are all the even power, right
2 k, 4 k and so forth
So if we have w N power of 2
What is w N power of 2?
This is e minus j 2 pi over N multiplied by 2, right
And this one we can move it 2 pi, move it to the denominator
Then this is actually w N over 2, right, N over 2
This is actually w N over 2
So that's the same as w N, right, N is half N
All right, so let's use this expression and apply it on the y bracket
Then what do we have?
We get y 0 plus y 2
And then w N
And this one, what is the power here?
w 2 k N, we would have, it would become w N k, right
So we get w N k and then all the way N minus 2
w N, then N minus 1
That's the y bracket
So what is the thing here?
What is this y bracket doing?
These are some numbers, right, some numbers
And for this one, we have multiplied by 1
And this one is w N k and the next one will be w N 2 k
And all the way to w N N minus 1 k
So what are we doing here?
What is this y bracket computing?
So what are, what kind of DFT are we computing here?
How many points of DFT?
N point DFT, right, N point DFT
So this is actually N point DFT
And what are the numbers that we are computing DFT with?
y 0, y 2, all the way to y N minus 2
All the even numbers, all the even samples, okay
And similarly, we have w N k
And then this is y 1 plus y 3
And w N k all the way to y N minus 1
w N N minus 1 k
And we are computing the DFT of all the odd samples
So let's call this y 1 k
This is called y 1 k
And this one y 2 k
So y k is simply y 1 k plus w N k y 2 k, okay
And what are y 1 k?
y 1 k is simply the DFT,
the N point DFT of the N point DFT of all the even samples
And y 2 k of all the, so what do we do here?
What have we done?
We are computing N point DFT, right
We are computing N point DFT
And this is the equation for computing N point DFT
And what we are doing here, this is what this equation is doing here
Is to split it into two terms
And this one corresponding to the N over 2 point DFT of all the even samples
And this one corresponds to all the N over 2 point DFT of all the odd samples, okay
So how do we compute y k now?
How do we compute y k?
We can first compute half N point DFT
And another half N point DFT
And then we add them up
Well, we still need this factor, okay
We need to take this factor into consideration when we do the adding up
And that's it, okay
So is there any sense in doing this?
Would this bring us any advantage?
Instead of doing this directly
Well, we can look at it, okay
So now, what's the complexity?
What's the complexity of computing y k in this way?
What do we need?
We need first, we need a true DFT
And this DFT is this many points, okay
I will use N over 2 as a subscript
To indicate that this is DFT of N over 2 points, okay
We need 2 DFT
But each DFT is of a smaller size
And then we also need to add them up, right
How, what's the computation involved in adding up this?
We need to compute k that goes from 0 to N minus 1, right
And for each k, we need one multiplication
And also one addition, right
So we need N multiplication and also N addition
So that's the computation involved, right
And we can try to get a feeling of what this number is
Remember, if we are trying to compute it like this
Treating the DFT as one matrix and do the multiplication
Then doing the multiplication and addition
Then we will need in the order of N square, right
Remember, the number of multiplication that we will need is N square
Okay, now let's try to see this
This is N over 2 point DFT
So if we are trying to do it directly
We will need N over 2 square
Because now the DFT size is N over 2, right
So this is N over 2 square
And we need two of them, right
Let's just compute the multiplication, okay
That's the number of multiplication that we need
And then we also need this N multiplication
So what do we have?
This is 2 and this is N over 2 square
So we will end up with 2 over N square plus N, right
And this is N and 2 N over 2 plus 1
So now, remember just to use the example that we have
N equal to 1, 0, 2, 4
Then this number N over 2 will be 512, right
512 will be much bigger than this 1
If N is equal to 1024, then this is 512
512 plus 1 will be around 512, right
So this is roughly about N over 2
So if we compare it
Compare it with the direct approach
That we are trying to, that we saw
If this is N square
And now we have N square over 2
So if we split a DFT into two DFT of smaller size
We get a factor of 2 saving in multiplication
Then if this is okay
Then everything will be based on this
And everything else will be easy
So we have a DFT N, right
N point DFT
And then instead of computing N point DFT directly
We can break it into two DFT plus N multiplication
And N addition
Okay, this means complexity
Okay, the complexity
We can compute N point DFT using two
N over 2 point DFT and N multiplication and N addition
Is it okay?
That's the complexity of N point DFT now
Can we continue this further on?
Can we continue in this fashion?
Now we have this N over 2 point DFT, right
N over 2 point DFT
How can we break it up?
Can we break it into DFT of smaller size again?
If we do, then how many points?
Then we can break it into half the size, right
Half the size will be DFT N over 4, okay
And again, each DFT N over 2 can be
Break it into two DFT of N over 4 point
And plus how many multiplication and addition
How many multiplications here?
N or N over 2?
N over 2, yes
Now we just continue on and on and on
DFT N over 4
It will be two DFT
It can be implemented using two DFT of N over 8
And plus N over 4 multiplication
And plus N over 4 addition
Until we come to DFT, the simplest DFT
And that will be DFT 4
We can break it into two DFT 2
This number is the same as this number, right
Okay, so that will be 4
Multiplication plus 4 addition
And DFT 2, there's nothing to break anymore
It's simply 2 addition
Now let's complete this whole picture
DFT N
It can be implemented using two DFT N over 2
Plus N multiplication and N addition
All right
And each DFT N over 2 is this much
Okay, this is one DFT N over 2
But now we have two, right
We have two DFT N over 2
So it's two of this
Okay, so it becomes 4 DFT N over 4
And then N multiplication and N addition
Okay, it can be implemented using 4 DFT N over 4
Plus N multiplication combined with this N
It's a 2N multiplication and 2N addition
Okay
And then each N DFT N over 4
Or 4, 4 DFT over 4
Then we get 8 DFT N over 8
Now this is 8 DFT N over 8
Plus how many multiplication and addition
We have 4, so that will be N, right
N multiplication and N addition
Plus this one, right
2N multiplication plus N
So we get 3N multiplication and 3N addition
Okay, and we just continue on all the way
Until we come to the DFT N N over
N over 4, N over 8, N over 2, right
If it's N over 2, then this becomes just DFT 2, right
So this 8 is the same as this 8
So we get N over 2 here
And then N log N over 2
See this is a 1 and this is 2
2 is a log 2, right
And then this we break it in
N over 8, this becomes a 3
And if we break it another 1 N over 16
Then this will be 4, right
Right, so it's the log of this one
Log of this number here, log of this number here
So we get log N over 2
We get log N minus 1
That's the link, log 2 N over 2
That's the multiplication
And also log N minus 1 addition
And we already know this is 2 point DFT, right
And 2 point DFT, the complexity for 2 point DFT
Is simply 2 addition
So let's put this in
Each 2 point DFT cost us 2 addition
So 2, if we take care of this
N over 2 then we will have N addition
So this is the same as N log 2 N minus 1 multiplication
Plus, plus N we get log 2 N addition
Oh, N is missing here, N log 2
So now the complexity is in the order
Remember, if we do the direct computation
The order is, the computation is in the order of N square, right
Now it's in the order of N log 2 N
Okay, and let's get a feeling of what this number is
For example, N is equal to 1024
And this N log 2 N, N log 2 N
Okay, this is the reduced complexity
The complexity we do FFT
And let's compare it with direct computation, N square
Then we get log 2 N over N
And when N is equal to 1024
This number is around, how much
1 over log 2 N, that's 10, right
And this is 10 to the power of 3, so we get 100
So now imagine that if you have some computation
That takes 1 second, okay
Usually it takes 1 second
Now if you use this fast algorithm
You only need 0.01 second, okay
That doesn't sound like much, right
But now say you have something that you
If you have a DFT that you compute
It takes 100 hours, 100 hours
Now it only needs 1 hour
100 hours is like 4 days, right, more than 4 days
But now it's reduced to only 1 hour
So that's quite a saving
All right, let's use the example N equal to 8
This is going to be a big example, a long example
N equal to 8, N equal to 8, all right
And then WA to be E minus J 2 pi over 8, okay
And YK will be like the equation that we have here
This is Y1 plus Y2, Y1K plus, Y1K plus WNKY2, right
W8KY2, right
Y2 where Y1, the 4 point DFT of all the even samples
1, 0, Y0, Y2, Y4, okay
And Y2K will be the 4 point Y7, okay
So this is just a special case that N equal to 8
And now we're going to continue on, right
We're going to break each 4 point DFT into 2 point DFT, okay
And Y1K, Y1K can be breaked into 2 DFT of smaller point
It will be Y3K plus Y4K, W4K, 1 has 3, has 4 points
And this Y3 and Y4, they are simply DFT, 2 point DFT, okay
Y1K are 4 point DFT of these 4 samples
And we're going to break it into 2, right
And we break this 4 point DFT into 2
We will have the even sample in one group
Because now these are the 4 new 4 points, right
So the even sample will be Y0 and Y4
And the odd sample will be Y2 and Y6, okay
So Y3, Y1 will be 2 point DFT
2 point DFT
And Y3 will be 2 point DFT
DFT of Y0 and Y4
And Y4, 2 and Y6, okay
And then similarly this Y2, it's a 4 point DFT
It can be implemented as 2 DFT of 2 points, okay
So let's see, 3, 4, so let's call this 5
And then 6, and this is W4K, okay
K again goes from 0 to 3
And this Y5K are the 2 point DFT of the even point
Y1, Y5 and Y6, okay
Are the 2 point DFT of Y3 and Y7
So for example, Y1, 0
Y1, 1
Y1, 2, 3, okay
It has 3 points, right
And we are going to compute it using Y3 and Y4, okay
Y3, 0
And Y4, 0
And this one will be raised to the power W4, 0, okay
And now Y1K, Y1, 1
K equal to 1, 1
So let me write down Y3, 1
And Y4, 1
And W4, 1, okay
So there's no problem, right
How about Y1, 2
When K equal to 2
K equal to 2, this is 2, this is 2, okay
But Y3, what is Y3?
Y3 is the 2 point DFT of Y0 and Y4, right
So K for this case, it only goes from 0 and 1, right
Because Y3 is a 2 point DFT
So K goes from 0 to 1, right, okay
So what is Y3, 2?
If we plug in Y3, 2
Then it will come back to what?
Because 2 point DFT, right
And we plug in K equal to 2
We will come back to K equal to 0 again, right
So this one will be Y3, 0
And similarly we have Y4, 0
And then W4, 2, okay
And this is Y3
Similarly this will be Y3, 1
And W4, 3
And then W4, 1
Let's plot the whole picture here
So first we have Y0 and Y4
And we compute the 2 point DFT, we get Y3
And we have Y2, Y6
We compute the 2 point DFT, we get Y4
And from Y3 and Y4, we can get Y1
And from Y1 and Y2, we will get Y, okay
So we have Y0 and Y4, right
And then we have Y2 and Y6
And we have Y1 and Y5
We have Y3 and Y7
And let me draw two very long lines here
So first Y0 and Y4, we will use 2 point DFT
We will apply 2 point DFT and that's 2 point DFT
So Y0 and Y4, we have a 2 point DFT
And at the output of the 2 point DFT we get, we get Y3
So that's Y3, 0
And Y3, 1
And then again, 2 point DFT of Y2 and Y6
Then we get Y4
Y4, 0
And now Y1 and Y5 together, 2 point DFT
We get Y5, 0
Y5, 1
And these two, 2 point DFT
We get Y6, 0
And Y6, 1
Alright
And from Y3, 4, 5, 6
We will be able to get Y1 and Y2
Now let's work on Y1 and Y2
Y1, 0 takes Y3 and Y4, 0
Y3 and Y4, 0
And Y1, 2 takes Y3, 0 and Y4, 0 again
0, 0, 0, 0
So Y3, 0 is here
Y4, 0 is here
So Y3, 0 plus Y4, 0
And there is a factor of W4, 0
Then we get Y1, 0
And then again, Y3, 0, Y4, 0
W4 raised to the power 2
We get Y1, 2
So this one coming down here
And this factor is
Oh, I'm sorry
This factor is W4 and 2
Then we get Y1
So that's Y1, 0, Y1, 2
And now let's look at Y1, 1
It takes Y3, 1, Y4, 1
And Y1, 3 again takes the value of Y3, 1 and Y4, 1
So from this value and this value
We are going to compute Y1, 1 and Y1, 3
Okay?
So let's do that
Let me use a different color
So this one coming down here
And this one going up there
Y3, 1 and Y4, 1
Here there is going to be a factor of W4, 1
Then at the output we get Y1, 1
Okay?
And now this one down here
The factor here will be YW4 raised to the power 3
And we get Y1, 3
It's okay?
This value coming down and this value
This multiply with this factor and we get Y1, 3
Okay
And now we can do exactly the same thing for this
For this 4-point DFT
For Y2
That will be exactly the same
So these two like so
That's exactly the same
So I'm going to draw a little bit faster
Okay?
This is W2, 4, 2
And then this is the same
They are exactly the same
This one is W4, 1
And then this one is W4, 3
Okay?
And at the output we will get Y2, 0
Y2, 1
Y2, 2
Y2, 3
Okay?
Move on to this now
Using Y1 and Y2
We will compute Yk
Okay
So now at the output we get
For Y1
It takes Y1, 1 and Y2, 1
Y1 for Y0
It takes Y1, 0 and Y2, 0
Okay?
Right?
So to compute this one here
We will take in this value here
And this value here
Y1, 0 and Y2, 0
To compute Y0
Okay
So this value will go up
This one will go up like so
Right?
And this vector will be W8, 0
And this one will come down
And this value will be W8
Oh, that's 0, right?
And this one, Y4
Y4 will be using the same true value again
So that's 4
Okay
And there's another butterfly
Like so
Right here
And then another butterfly
Right here
And right here
And one last butterfly
Coming down here
And then down here
Okay
And this one is W8, 1
This is W8, 2
W8, 3
This is 4
And this is 5
This is 6
And this is 7
And this algorithm is called decimation in time
Decimation in time
Because each time we split a DFT into two DFTs
Smaller size in time
Because see you have
We have a Y0, Y2, Y4, Y6
This is like decimation, right?
Decimated by two
Decimation in time
And in this whole computation
What we can see is
That it all involves
What it involves is actually
Two point DFT butterfly
Butterfly like this
And butterfly like this
And because of all the computation
Involve two point
Those butterfly
And two input and two output
Two input and two output
Two input and two output butterfly
This is called radix-2
Radix-2
Radix-2 FFT
And more general
We can have other number of radix
For example
Just now we are breaking
We are taking in all the even samples
Even sample and odd samples
We can also break the DFT in different way
For example instead of
We have a 0, 1, 2, 3, 4, 5, 6, 7, right?
And we are taking all the even sample
But we can also like taking in
4
We can also break it into
DFT of even smaller sizes
And then rearrange the equation
So that each butterfly
Has a 4 input and 4 output
Then that will give us a radix-4 FFT
Radix
For example in this example
We would have this two point DFT here
And then these two
Together
So we would have these two together
These two together
And then we would have 4 DFT output
This is a 1 DFT
0 and 4 1 DFT
This is 1 DFT
And we get 4 DFT
And each DFT is of size DFT
N over 4
OK
And now we would have the
Output from these 4 DFT
And then we would do this butterfly
This 4 input 4 output butterfly together
To get the output
And that's called radix-4
OK
So there are many many different kinds of
Gauss algorithm
For fast Fourier transform computation
