 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
So, in my quest of understanding I have decided to look closer at these
magical functions. Everyone who's ever encountered an audio player
probably knows what an FFT. Or has a vague abstract idea as to what it
can be used for. because it's usually called something like FFT. or FFT
filter. FFT spectrum. Whatever. I've seen the term floated around in
such a cavalier manner.
OK, so it's the application of the FFT. Or rather the DFT, seeing as FFT
is just an optimization of the DFT.
I have a very good handle now on what DFT actually does, and it's a
pretty nifty transform. What I can't seem to wrap my head around is FFT.
But I think I'm getting there. I know it does a bizarre sort at the
beginning, essentially ordering the data as if the indexes had their
bits reversed, which allows the next step to happen. The values are then
recombined, reversing the previous sorting process in such a way as to
reveal the sine and cosine components of the source signal.
That part is really toasting my brain. I /almost/ understand the theory
behind it, but there's some part that's blocking me. The amazing part is
that it takes two nested loops of, say 256 values, and makes it
essentially a 2-deep nesting of around 8 values with a rather small
inner loop.
And its entirely reversible. (!)
The cool thing is you can take frequency domain set, multiply it by
another frequency domain set, invert the DFT, and boom, you just
filtered your data. No messy convolution.
As an example, you can achieve a blur effect on an image by using
multiply operations on the image's frequency domain data. rather than
create a convolution matrix to do the same thing.
I'm not 100 % on the theory of noise reduction, but my basic
understanding is it basically analyzes a constant signal area of the
image in the frequency domain, then subtracts that spectrum from the
noisy signal, thereby cleaning the image, and only minimally harming the
actual image. Thats my guess, at least. I know most of the popular NR
algorithms out there work in the frequency domain...
Anyway, I'm rambling :)
--
~Mike
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mike Raiford <"m[raiford]!at"@gmail.com> wrote:
> What I can't seem to wrap my head around is FFT.
> But I think I'm getting there. I know it does a bizarre sort at the
> beginning, essentially ordering the data as if the indexes had their
> bits reversed, which allows the next step to happen. The values are then
> recombined, reversing the previous sorting process in such a way as to
> reveal the sine and cosine components of the source signal.
Yikes. Never had to worry about those details. I'm usually content enough just
to know that FFTW works! That said, I'm remembering something about a recursive
factorization for the DFT matrix. Is that the basis for the FFT, or are the
practical algorithms much more complicated than that?
Anyway, here's someone describing some of the details:
http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/detail/lecture26.htm
And here's a book with some details:
http://books.google.com/books?id=coq49_LRURUC&pg=PA391&lpg=PA391
> And its entirely reversible. (!)
That's really just a property of the Fourier transform itself, isn't it? At
least to a constant.
> The cool thing is you can take frequency domain set, multiply it by
> another frequency domain set, invert the DFT, and boom, you just
> filtered your data. No messy convolution.
Yes, very convenient. O(n^2) to O(n log n). Much less messy, too.
> I'm not 100 % on the theory of noise reduction...
Don't wavelets come into play here? Fourier transforms aren't local, so doesn't
that amount to a low-pass filter? I guess you could just break it up like jpeg,
but then you may as well move on to wavelets. I never really had a reason to
dig into all the details, but I think it might be a worthwhile endeavor.
> Anyway, I'm rambling :)
An enjoyable ramble.
- Ricky
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mike Raiford wrote:
> I have a very good handle now on what DFT actually does, and it's a
> pretty nifty transform. What I can't seem to wrap my head around is FFT.
> But I think I'm getting there.
Every signal can be represented as a sequence of samples, or as the sum
of some sine (and cosine) components of different frequencies. Two
different ways to describe the same signal. The DFT (and its inverse)
convert one into another. This presumably you have already long figured out.
The FFT works by a divide-and-concor method, rather like quicksort and
mergesort. Take your signal, split it into two signals, transform them
both [by recursively applying the same algorithm], combine the results
back together into a single result.
The whole "swap the bits of the indicies around" trick is an
optimisation to avoid recursively shuffling the samples around. It lets
you do all the shuffling in a single step instead of log N steps, that's
all.
Much like quicksort, the DFT of 1 sample is... that 1 sample, unaltered.
Combining in the frequency domain must undo what was done by splitting
in the frequency domain... There are actually several slightly different
(but essentially equivilent) ways to arrange the FFT.
> The cool thing is you can take frequency domain set, multiply it by
> another frequency domain set, invert the DFT, and boom, you just
> filtered your data. No messy convolution.
>
> As an example, you can achieve a blur effect on an image by using
> multiply operations on the image's frequency domain data. rather than
> create a convolution matrix to do the same thing.
Multiplication in the frequency domain is convulotion in the time
domain, and vice versa. FFT convolution is mildly more tricky than it
looks at first. (You gotta chop the input into "blocks" to run it
through the FFT, and you need to overlap them after you're done or the
"blur" will stop at the block edges - which is wrong.)
Any further questions?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
...he says, as if he knows *exactly* what he's talking about! ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Every signal can be represented as a sequence of samples, or as the sum
> of some sine (and cosine) components of different frequencies. Two
> different ways to describe the same signal. The DFT (and its inverse)
> convert one into another. This presumably you have already long figured
> out.
Yep. I pretty much figured that out ... real is the cosine, imaginary is
the sine components. Add those components together, and you get the
original time-domain signal. (Well, really average)
>
> The FFT works by a divide-and-concor method, rather like quicksort and
> mergesort. Take your signal, split it into two signals, transform them
> both [by recursively applying the same algorithm], combine the results
> back together into a single result.
> The whole "swap the bits of the indicies around" trick is an
> optimisation to avoid recursively shuffling the samples around. It lets
> you do all the shuffling in a single step instead of log N steps, that's
> all.
>
That much I got, and the order of the data seemed to make sense to me,
what's racking my brain is the butterfly... That seems to be the "magic"
piece that makes the whole thing work.
> Much like quicksort, the DFT of 1 sample is... that 1 sample, unaltered.
> Combining in the frequency domain must undo what was done by splitting
> in the frequency domain... There are actually several slightly different
> (but essentially equivilent) ways to arrange the FFT.
Yep, figured that part out, too. Realizing that 1 sample is essentially
DC, and the real value at index 0 is the DC component made that clear.
>
>> The cool thing is you can take frequency domain set, multiply it by
>> another frequency domain set, invert the DFT, and boom, you just
>> filtered your data. No messy convolution.
>>
>> As an example, you can achieve a blur effect on an image by using
>> multiply operations on the image's frequency domain data. rather than
>> create a convolution matrix to do the same thing.
>
> Multiplication in the frequency domain is convulotion in the time
> domain, and vice versa. FFT convolution is mildly more tricky than it
> looks at first. (You gotta chop the input into "blocks" to run it
> through the FFT, and you need to overlap them after you're done or the
> "blur" will stop at the block edges - which is wrong.)
>
I'm supposing this is where Hamming and Blackmann windows come into play?
> Any further questions?
>
Heh, as more come to me. I'm tossing together a little C# app to play
around with the FFT and be able to examine it in both rectangular and
polar forms.
I knew you'd have something to add to this, since you seem to be quite
advanced in mathematics.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Michael Raiford <mra### [at] hotmail com> wrote:
> Heh, as more come to me. I'm tossing together a little C# app to play
> around with the FFT and be able to examine it in both rectangular and
> polar forms.
Aha, I knew I had that lying around somewhere. If you just want to play with
the behavior and not implement it yourself, there's always Matlab, or its free
equivalent, Octave. Here's the simplest low-pass filter:
n=101; tmin=0; tmax=10;
%calculate time & frequency
tbase = linspace(tmin,tmax,n);
dt = (tmax-tmin)/(n-1);
ni = floor((n-1)/2);
fbase = [0:floor(n/2),ni:-1:1] /ni/2.0/dt;
%calculate y and fft(y)
y = rand(size(tbase));
Y = fft(y);
%filter
Y_filt = Y;
Y_filt(find(fbase>2.0)) = 0;
y_filt = ifft(Y_filt);
%plot
figure(1); plot(tbase,y,tbase,y_filt);
figure(2); plot(fbase,abs(Y_filt));
- Ricky
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> That much I got, and the order of the data seemed to make sense to me,
> what's racking my brain is the butterfly... That seems to be the "magic"
> piece that makes the whole thing work.
Well, you *could* take the time-domain signal and cut it into two
halves. But that's not very easy to undo in the frequency domain. So
what they usually do is take all the odd samples and all the even samples.
Taking all the even samples is just halving the sampling rate. [Assuming
0-based indexing!] Halving the time domain means doubling the frequency
domain. (Think about it: You take a sound, cut out half the samples,
that's like doubling the playback speed. All the pitches are twice as high!)
Taking all the odd samples is like shifting one sample to the side and
then halving the sampling rate as per above. In the frequency domain,
such a time shift is a multiplication by a sinewave.
So, to undo all this, double both signals, multiply one by a sinewave,
then add them back together. Hence, the butterfly.
>> Combining in the frequency domain must undo what was done
>> by splitting in the frequency domain...
Grr... "Combining in the *frequency domain* must ondo what was done by
splitting in the *time domain*." Get it right, boy! >_<
>> Multiplication in the frequency domain is convulotion in the time
>> domain, and vice versa. FFT convolution is mildly more tricky than it
>> looks at first. (You gotta chop the input into "blocks" to run it
>> through the FFT, and you need to overlap them after you're done or the
>> "blur" will stop at the block edges - which is wrong.)
>
> I'm supposing this is where Hamming and Blackmann windows come into play?
No. Those come into play if you're trying to desing a digital filter.
(E.g., a "perfect" lowpass filter has an infinite frequency response,
but we can't do that. If you just chop the ends off it screws up the
frequency response. Using (say) a Hamming window reduces the effect -
but doesn't eliminate it.)
Recall that the convolution of a signal by some kernel is *longer* than
the original signal. This is the effect you have to repeat when doing
FFT convolution. (The details escape me at this exact moment... Suffice
it to say that your inverse-FFT results have to be overlapped to get a
smooth result.)
> I knew you'd have something to add to this, since you seem to be quite
> advanced in mathematics.
Meh. I wanted to build a digital filter, so I read a rather excellent
book on the subject. ;-)
Wanna see the Z-transform?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>
> Meh. I wanted to build a digital filter, so I read a rather excellent
> book on the subject. ;-)
But, you see ... you have an interest in such things.
> Wanna see the Z-transform?
Z transform?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Meh. I wanted to build a digital filter, so I read a rather excellent
>> book on the subject. ;-)
>
> But, you see ... you have an interest in such things.
I read Wikipedia - and discovered that it is *completely useless* for
learning this kind of thing! But then I found a book online, and read
that. ;-)
>> Wanna see the Z-transform?
>
> Z transform?
Weeell... The Fourier transform comes in several different "flavours",
but essentially you have
- The continuous Fourier transform takes a formula and turns it into a
different formula.
- The discrete Fourier transform takes some numbers and turns them into
some other numbers.
There is a generalisation of the [continuous] Fourier transform called
the Laplace transform. The correspondin discrete version is called the
Z-transform.
The Laplace transform is the trippy mumma you use for designing Infinite
Inpulse Response filters.
See, Finite Impulse Response (FIR) filters are very easy to design, and
very flexible, but they take quite a bit of compute power. If you want
precise filtering (e.g., for scientific purposes) then you're going to
use FIR.
On the other hand, Infinite Impulse Response filters use feedback to
generate an impulse response which is effectively "infinitely long". The
downside is that only certain impulse responses can be created by
feedback. Oh, and that controlling feedback is damned tricky.
Enter the Laplace transform. This makes it relatively easy to figure out
how much feedback to apply.
It just so happens that the impulse response of a perfect lowpass filter
"nearly" matches the kinds of impulse responses that an IIR can produce.
The net result of this is that with only a tiny amount of calculation,
you can get pretty good results.
In other words, IIR is massively, massively faster than FIR. (It's also
far less precise, nowhere near as flexible, and way harder to design.)
While we're on the subject, the Laplace transform turns differential
equations into algebraic equations, making them drastically easier to
solve. As I understand it, that's why mathematicians came up with it in
the first place.
Jesus Christ, SOMEBODY HIRE ME!! >_<
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> So, to undo all this, double both signals, multiply one by a sinewave,
> then add them back together. Hence, the butterfly.
I want you to know that's the first explanation of it I've ever been able to
follow. I'm not a very mathematical person.
You definitely should write some Haskell documentation. :-)
--
Darren New, San Diego CA, USA (PST)
Why is there a chainsaw in DOOM?
There aren't any trees on Mars.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
