Pages: [1]   Go Down
Author Topic: Simple FFT Algorithm?  (Read 1544 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hi guys!
If you dont want to read the long story u can skip to the end, where it starts about algorithm.
Some random noob is here(me), but dont stop reading just yet.
I am doing some project that involves music visualisation on arduino, so i thought i'd put some LED matrix dancing to the music. Ordinary FFT stuff, there are lots of such videos on youtube and elsewhere on the internet. I downloaded some random library and script for it, modified it to my needs and it did some nasty stuff, well the thing was working, but some problems existed. Library was Fix_FTT. Actually i  searched a lot and found many different ones(PlainFTT etc.). Well i did not want to dig in someones library and change it, so i went to wikipedia and read about FFT.
So it says there that FFT is used to compute DFT and that DFT is basically transforming one function, that has X as Time into function that has X as frequency. So i saw a lot of algorithms there and even FFTW but all seemed too complicated and i have kinda little time for this stuff(can't use process language since i need code to be on arduino). So i came up with another method and it is what i want to ask u about. Is this what FFT does?
What i did was putting audio output from pc straight into Arduino, then  i collect 128 impulses, then i do following:samples-samples[i-1]. And then based on the result i add +1 to one of the columns.... What i get in the end is columns array with some numbers for each column and MAP() it for my LED matrix. Thats a rough sketch of the algorithm. Why do i do samples-samples[i-1]? I thought that sound is the vibrations so it has to be something like previous voltage - current voltage. Basically now i have information on how frequently do those voltages appear in the ranges(columns) in th time when i gathered samples.Basically it is frequency...
I tried it already and it does visualize the thing. Is it FFT or similar to it? If it is, is it slower/faster than those libraries which are on arduino cc?
Sorry for messy language and for not writing enough.... but well i am in kind of hurry:D
« Last Edit: April 10, 2012, 05:35:01 pm by FFTMaster » Logged

Offline Offline
Edison Member
*
Karma: 35
Posts: 1429
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
Is it FFT or similar to it?
Not even close. If it was that simple there would be no need for PlainFFT, Fix_FFT, FFTW etc.
When you subtract the previous measurement from the current one you are computing the slope of the curve which is essentially the derivative (i.e. the rate at which the voltage is changing). So, if you use that to drive the amplitude of a LED it will be brightest where the voltage changes the fastest (usually the loudest part) and dimmest where there's little or no change.

Pete
Logged

Where are the Nick Gammons of yesteryear?

Offline Offline
Newbie
*
Karma: 0
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
Is it FFT or similar to it?
Not even close. If it was that simple there would be no need for PlainFFT, Fix_FFT, FFTW etc.
When you subtract the previous measurement from the current one you are computing the slope of the curve which is essentially the derivative (i.e. the rate at which the voltage is changing). So, if you use that to drive the amplitude of a LED it will be brightest where the voltage changes the fastest (usually the loudest part) and dimmest where there's little or no change.

Pete
Okay, but still i think that the visual is pretty okay, i dont really see the difference between FFT and this(Visually).
The key point was not substraction but actually that im measuring voltages and then putting them into categories.
Basically i get the X with frequencies and Y with Voltage... I thought that was the point?
I do understand that im thinking quite naively... but id like to know what is wrong with my logic:D
« Last Edit: April 10, 2012, 06:45:51 pm by FFTMaster » Logged

Offline Offline
Edison Member
*
Karma: 35
Posts: 1429
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
but still i think that the visual is pretty okay
If it looks good, that's all that matters.

Pete
Logged

Where are the Nick Gammons of yesteryear?

Offline Offline
Newbie
*
Karma: 0
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

that much is true, but my interest has already been ignited:D
I am searching for the answer in the internet, wiki etc. but still do not understand fully, why my algorithm is not FFT:D
If u know, could u please tell me? I dont care how complicated it is:D
Logged

0
Offline Offline
Sr. Member
****
Karma: 5
Posts: 476
what?
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

The last FFT i did was with Borland Visual C++, it involved listening to two morse code stations close together but only decoding the loudest (this was on a shortwave receiver), it invloved breaking the band into 8 frequency ranges 1kzh, 2khz, 3khz.....so you take 16 samples then you calculated the difference between samples 1&9, 2&10 and so on and basically end up with an 8 band spectrum analiser, don't ask me to do it now though, it was 10 years ago and i still haven't recovered lol.
el_supremo is quite correct
Logged

Offline Offline
Edison Member
*
Karma: 35
Posts: 1429
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

This is very simplified, but the result of computing the FFT of a signal is an array of numbers . Each element of the array (often referred to as a "bin") corresponds to a small range of frequencies in the input signal. The value in each element allows you to determine the amplitude of the signal corresponding to that frequency.
Subtracting successive voltages only tells you the rate at which the voltage is changing. That doesn't tell you what the frequency is. If it did there would be no need for an FFT.

Quote
i am in kind of hurry
You're really going to have to slow down if you want to understand what the FFT does. To start with, to understand the FFT you have to understand the mathematical concept of complex numbers. If you don't know that, you've got a long way to go.

But if you're in a hurry, the executive summary is that what you're doing isn't an FFT.


Pete
Logged

Where are the Nick Gammons of yesteryear?

Offline Offline
Newbie
*
Karma: 0
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

This is very simplified, but the result of computing the FFT of a signal is an array of numbers . Each element of the array (often referred to as a "bin") corresponds to a small range of frequencies in the input signal. The value in each element allows you to determine the amplitude of the signal corresponding to that frequency.
Subtracting successive voltages only tells you the rate at which the voltage is changing. That doesn't tell you what the frequency is. If it did there would be no need for an FFT.

Quote
i am in kind of hurry
You're really going to have to slow down if you want to understand what the FFT does. To start with, to understand the FFT you have to understand the mathematical concept of complex numbers. If you don't know that, you've got a long way to go.

But if you're in a hurry, the executive summary is that what you're doing isn't an FFT.


Pete
Yeah, since i am in a hurry i am not going to use FFT right now i guess... unless my "algorithm" has some kind of fatal weakness....
About complex numbers and math... It is not like i dont know what are complex numbers and stuff... i have been studying in university for 3 ears already(actually this project is my bachelor's work and we are not given much time).
Sorry if i am being persistent by saying same thing all over again, i just think that u did not really understand what i wrote, since my language and explanations are pretty messy.
As i said before substracting is not the keypoint of this algorithm.
I get voltage signal from audio output(example values 252, 50, 100). And now what i do is look in which range of values it goes. For example if i have 5 columns i make ranges like: 0-49, 50-100, 100-150, 150-200, 200-infinity. I have columns array with 5 elements. So if i get 135 i add to columns[2]++. So basically it seems that i do the same thing as it was written in wikipedia? I do the sampling. Then i create an array which tells me how frequently(in the time of sampling) i get the values into those ranges.
Sorry if u did understand it before.
If i am wrong then i do not really understand what it means to have X as frequency. I understand that frequency is basically how many times in a time something happens? As i understand then those Hz are basically saying how often did i get value Y(voltage). If it was not frequent then  its somewhere near 0 and if it was frequent it goes somewhere to the right. If that is correct then i do get that, i get how frequently i get values in ranges predefined.
Logged

Gosport, UK
Offline Offline
Faraday Member
**
Karma: 19
Posts: 3114
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

If I understand it correctly, your algorithm analyses amplitude over time, and assign different amplitudes to your column array. An FFT algorithm, (again, as I understand it), effectively breaks down the incoming signal into different frequency bands (for example, bass frequencies, mid-range frequencies and high-range frequencies) and then analyses the amplitude of each band, which would then be assigned to the columns.
Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

If I understand it correctly, your algorithm analyses amplitude over time, and assign different amplitudes to your column array. An FFT algorithm, (again, as I understand it), effectively breaks down the incoming signal into different frequency bands (for example, bass frequencies, mid-range frequencies and high-range frequencies) and then analyses the amplitude of each band, which would then be assigned to the columns.
Okay, do you mean to say that for example from audio output comes 225 and it somehow breaks it into components? Is that really possible? Well if it is like that then it is really my bad:D Thank you for sharing with me. And yes if u want to visualize your audio, my method seems to be pretty nice.
It is laggy(phone camera), but at the end of it you can see the visualization. I have only 5 columns working, since it is what is needed for my project.

UPDATE: If i understand correctly breking into frequencies means breaking the complex sound wave into simple sin and cos waves?
« Last Edit: April 11, 2012, 05:11:09 am by FFTMaster » Logged

Pages: [1]   Go Up
Jump to: