I made a more final version, and it goes blazing fast, I don't have the time to see the pure FFT transfrom happen on a PDA, definately way less than a second ! The time to first open my recorded, one second wave-file from disk, checking if it's the right format, putting the last 4096 (mono) bytes of it into an array, etc.. cost me another 3 seconds. But that's OK. 4 seconds total calculation time is great ! On the other hand (just some wishful thinking now), this makes me wonder: if I could capture the wave-bytes directly from memory while they are being received/recorded, then it would be possible to make a real-time tachometer of a continuous sound. Let's say with one indication of the RPM per second or so. But i guess the recorder.dll doesn't allow me to capture parts of this stream of bytes directly. Agraham, while we're discussing this, would you mind if I would mention you in the credit list of my app ? You sure deserved it ! In fact, you can see the start of it here, and even download a copy: http://users.telenet.be/heliport/ Don't expect too much, I'm just a hobbyist.
@agraham, really amazing and fast, the algorithm and your reaction time, as usual. @redbird As agraham was quicker than I, I stopped testing your FFT algorithm. But I played with agraham's library. As your samples are real, you dont even need to add the imaginary samples with 0 values. I entered 4096 real samples in the data() array without adding imaginary samples. You get 2048 real and 2048 imaginary samples in response from the Fft.Transform. As I didn't know the expected results with your raw data I added the calculation of 2 sine signals, one with one pure sine (first spectral line) and a second one with 3 pure sines (1st, 4th and 10th spectral lines). Added the test program. Best regards.
@Firebird Please do. Unfortunately I don't know of any way to get sound samples directly into memory. @Klaus I'm not too hot on maths. I understand interpreting the real and imaginary values obtained using the complex FFT with only real input values and the imaginary input values all 0. I don't understand what the real and imaginary values obtained represent when the imaginary input values are also sampled values. I've Googled but not found an answer (that I understand!). Is there an easy explanation? Also I modified CalcSin with "For i=0 To NM1 Step 2" to only produce real values assuming that the real values of data() are even indeces and imaginary are odd. The expected frequencies seem to appear in the imaginary data and phase in the real data. Would you expect it to be this way round? EDIT:- I've got the answer to my second question. From (years ago!) brief exposure to FFTs I was under the misapprehension that the output was freqency amplitudes and phase. In fact it is Sine (imaginary) and Cosine (real) frequency amplitudes. I still don't understand the first question!
Hi Andrew, I suppose that your algorithm is a real input DFT. Discrete Fourier transform - Wikipedia, the free encyclopedia look at the The real input DFT. In that case for N real samples the DFT returns N/2 real values and N/2 imaginary conjugated values. I tried also with 0's on the odd indexes for the imaginary part, but I didn't get consistent results. Could you post your test program with the imaginary input, so I will check if I made a somewhere a mistake or if the results are also not consistent. When you calculate the FFT in my test program with 3 Sines, you will see that the spectral lines 1,4 and 10 have a value near 1024 for both the real and imaginary value corresponding to the 'frequencies' of the 3 sines. All other values are near 0, as it must be because the sines are pure, only one spectral line per sine. A pure sine means in that case beginning with 0 and with a whole number of periods in the 'window'. Normally FFT's ampltudes are normalized, when you click onto the A button to calculate the Amplitude of the sine you will see values near 0.707 for the 3 spectral lines (that's the standard normalization in FFT analysers, power spectrum). I have used FFT in the past in one of my programs and normalized the amplitude to get the same amplitude as the original sines wich in the test program is 1. I had also looked at a Fourier series instead of FFT but it is awfully slow. The advantage, for redbird, would have been that the bandwidth could probably have been limited to the interesting area. Best regards.
I'm not sure what you mean by "your algorithm" but the library does a complex input FFT. I think the long words and funny symbols in the articles that I Google are the problem to my not understanding. If I set the imaginary part of the input to 0 and make a Cosine input by altering your Sub CalcSin as follows I get what I expect. A Real (Cosine) as a fourth harmonic and two Imaginary (Sine) harmonics as the fundamental and the tenth. I sort of understand this but don't know what the negative signs of the Imaginary values mean or why the Imaginary conjugates are of opposite sign whereas the Real conjugates aren't, something to do with "i" presumably. Code: Sub CalcSin(nb) Dim I As Number Dim j As Number, w0 As Number, w1 As Number, w2 As Number w0=cPI/ND2 w1=cPI/ND2*4 w2=cPI/ND2*10 lbxResult.Clear For i=0 To NM1[COLOR="red"] Step 2[/COLOR] data(i)=Sin(w0*i) [COLOR="Red"]data(i+1) = 0[/COLOR] If nb=3 Then data(i)=data(i)+[COLOR="Red"]Cos[/COLOR](w1*i) data(i)=data(i)+Sin(w2*i) End If lbxResult.Add(i&" "&data(i)) Next FillList(NM1,"Sinus")End Sub With your original Sub, which inputs samples in both Real and Imaginary input parts the FFT produces aproximate values of Real at 1 of 1024, 4 of 1 of 1018, 10 of 1024 and at 2047(1) of, 1025, 2044(4) of 1024, 2038(10) of 1040 Imag at 1 of -1022, 4 of 1024, 10 of -1008 and at 2047(1) of, 1025, 2044(4) of 1024, 2038(10) of 1040 What I don't understand is what these represent. Presumably they are amplitudes and obviously they are at the input frequencies but the signs of the values puzzle me. It looks like the initial values in the Imaginary output carry phase information but the relected values of the Imaginary don't, presumably its' something to with "i" again
Hi Andrew, I looked more deeply into the FFT and played more with your library. I must apologise I did some mistakes and misinterpreted some results. Your library works perfectly, sorry for having made you loosing your time. The imaginary samples set to 0 are necessary. Setting the data() array with a set of real samples as in my previous test program is almost similar to setting the imaginary samples equal to the real samples and the results looked almost OK. Attached a new test program allowing to 'play' with your library, with some graphics making hopefully the subject better understandable (desktop only). The program is written with version 6.9. Source code and an exe file for those who don't have version 6.9. Best regards.
Ahh, thanks Klaus - no wonder I didn't understand what was going on! I've added a few methods to the library that might speed things up slightly, especially on a device CopyArray(array As Double) As Double fast .NET method for cloning of an array ToAmplitude(real As Double(), imag As Double(), scale As Double) as Double() where scale determines the scaling of the output values which with a scale value of 1 are the input values ToPhase(real As Double(), imag As Double()) as Double() and ToReal(amplitude As Double(), phase As Double(), scale As Double) as Double() ToImaginary(amplitude As Double(), phase As Double(), scale As Double) as Double() where scale is the same value as used for ToAmplitude. Any comments?
Hi Andrew, It seems that you are reading in my mind ! I was about asking for a method to get at least the amplitude because in frequency analysis that's what the user is the most intersted in, the phase is not that impotant. In practice I'v never used Real and Imaginary. Best regards and thank's. EDIT: Have you already uploaded the new version ? I was thinking about getting Amplitude and Phase directly in return from Fft.Transform as this is the most useful, but there would be the scale variable needed. This would avoid needing to calculate it afterwords. I have seen that Fft, the name of the FFT object, is highlighted in green in the IDE, is this a new feature ? Could be intersting for other objects too.
I kept the conversion as individual ones for that reason so as to keep things quick. It needs to be calculated separately anyway as the algorithm produces Sine and Cosine. As the overhead of doing them in the Basic4ppc code rather than automatically in the library is very small, only that of a single call to the library and as only Amplitude is interesting a lot of the time I didn't incoporate it into the actual Transform. Also having Real and Imaginary available lets you see what is going on if you need to. I've no idea why the IDE thinks that FFT is a keyword, it doesn't highlight other library objects, although I have suggested to Erel that it should but he wasn't keen on the idea. Here's the next version of the library with the five methods above added.
My impression is that object names get highlighted if their names are the same as the library but not otherwise. Which seems strange to me; does a library name have any relevance in code? Mike.
I'd forgotten that the latest IDE highlights library Class (Object) names. I think it was added because the Control keyword is superseded by a new syntax that uses an objects or controls' Class name and this in turn lets Intellisense work as the IDE now knows the type of the object so a library name is now relevant within code. Control ("Form" & i, Form).Circle(...) 'old syntax Form ("Form"& i).Circle (...) 'new syntax
Hi Andrew, Thank's for uploading the last version of the FFT library. I tried the new functions and saw an error with the ToPhase function wich gives wrong results. The Tan function should be the ATan2 function with 0 < angle < PI when y is positive and 0 <angle < -PI when y is negative When, in the attached, new version of the test program you : - click on '1 Sine damped', pure damped sine - click on the 'Calc FFT' button - click on the 'A / P' button You get the result in the first image, but it should be like the 2nd image. The 2nd real sample is 1.364... and the imag sample is -0.00035... with x positive and y negative the angle should be negative. Shouldn't we open a new thread for the FFT library ? Best regards.
You missed attaching the attachment It does use the .NET Math.Atan2 function. It is the same Atan2 function as Basic4ppc uses so the problem must be elsewhere. ph = Math.Atan2(imag, real) * DegPerRad; In the docs Atan2 is specified as the return value is the angle in the Cartesian plane formed by the x-axis, and a vector starting from the origin, (0,0), and terminating at the point, (x,y). It is an angle, θ, measured in radians, such that -π≤θ≤π, and tan(θ) = y / x, where (x, y) is a point in the Cartesian plane. Observe the following: For (x, y) in quadrant 1, 0 < θ < π/2. For (x, y) in quadrant 2, π/2 < θ≤π. For (x, y) in quadrant 3, -π < θ < -π/2. For (x, y) in quadrant 4, -π/2 < θ < 0. I was waiting till we were happy with it and then I was going to do a help before starting a new library thread for it. EDIT:- Commenting out 'FFTPhase(i)=ATan2(FFTImag(i),FFTReal(i))*RadDeg in the For loop in CalcFFT in your previous example and inserting FFTPhase() = Fft.ToPhase(FFTReal(), FFTImag()) after the Next looks OK for me. Did you get the order of the parameters of ToPhase correct? I see your graph if I reverse them.
Sorry, my mistake ! I had inverted the order of Real and Imag in the ToAmplitude function. When doing it right it works OK ! Unfortunately, as often the most obvious mistakes are overseen. Attached the last test program version. Best regards.
You are a bit off form today Klaus . You have got FFTAmpl()=Fft.ToAmplitude(FFTReal(),FFTImag(),1) FFTPhase()=Fft.ToPhase(FFTReal(),FFTImag()) inside your For loop which is of course a "bad thing". Not like you to miss something like that I'll put together a help and library archive and post it in a day or so. Is it OK if I use your program as the demo app for the library?
Klaus and Agraham, I admire your work and knowledge a lot, but I'm afraid I don't understand all of it anymore. Could you please confirm this rather simple question for me, as I'm starting to doubt now: I take 4096 subsequent bytes of a recorded, uncompressed 8 bit sampled sound file, being timed amplitudes in fact, and i put these values (varying from 0 to 256) in the array data(), without adding any zeros for imag numbers. A plain and simple real value array. And after doing the fft.transform(rawdata()), do I get the correct (2 X 2048) numbers back in the array, being a real value, an imag value, a real value, an imag value, and so on ? Klaus his words about his results that seemed close without adding zero values confused me a bit, I probably didn't understand completely. Note: I rely on this array to calculate the magnitudes by looking to the absolute values (square root of (real^2) + (imag^2)). And the largest magnitude in the frequency range I'm looking for allows me to determine the unknown frequency at last, knowing the sample rate of 11025 samples/second in my case.
Yes, and I'm most impressed with that, as at first I thought it was only for the included and packaged libraries - but it does it for any library (tested with many of yours)
You need to take your 4096 samples and put them in a 8192 long array, say data(), at even numbered (Real) positions setting the odd (Imaginary) positions to 0. Do the FFT and data() will now contain the Cosine amplitudes at even (Real) positions and Sine amplitudes at odd (Imaginary) positions. Use FFT.Split to separate data() into two 4096 long arrays containing the Real and Imaginary values. Use FFT.ToAmplitude, the scale parameter doesn't matter for you - use 1. This returns a new array 4096 long which contains the amplitudes. Use the first 2048 values of this to look for your maximum. Is it always valid to assume that the maximum amplitude frequency is the one you are interested in? Perhaps a bit of visualisation for the user to confirm or select the chosen frequency might be a useful feature. As it is mainly the Real amplitudes that are of interest I will add a ToRealAmplitude method that will extract those, in your case 2048 values, directly from the data() array so avoiding the Split step. EDIT : - ToRealAmplitude is not a good name because of "Real." I thought I might call it ToAmplitudes, note the plural, but is that too close to the existing ToAmplitude method name? I will also add the complementary ToPhases method.
Hi Andrew and redbird, I did some 'brainstorming' last night, luckily not all night. Coming back to the FFT priciple: - from the mathematical point of view the, the imaginary samples are necessary in the FFT algorithm in agraham's library . - from the user's point of view, almost all calculations are done with physical signals without any imaginary component. In redbirds example: - today he has 4096 real samples from his physical signal - he needs to create an array with 4096 zeros for the imaginary part (with no use other than to satisfy the mathematic algorithm) - he gets back 4096 real and 4096 imaginary frequency samples - half of them are of no use because the second half of the samples are the conjugate values of the first half (first half real + imag second half real - imag ) the real values are the same the imaginary values are oppsite (sign changed) My suggestions: 1) - send, in the data() array to the FFT object, only the real values - the imaginary 0 samples are generated inernally in the FFT dll - get back only the first half of the real and imaginary samples, only the useful ones 2) or eventually use a 'FFT algorithm specialized for real and/or symmetric data' with the same inputs and outputs. Fast Fourier transform - Wikipedia, the free encyclopedia In redbirds example. sending 4096 samples instead of 8192 getting back two sets of 2048 samples instead of two sets of 4096 samples That's what I was used to, and that's what made my confusion at the beginning. And I am shure that it will avoid confusions for others in the future. I tested the library at the beginning with very low frequencies, this means that the succesive samples had relatively small differences. This was seen by the library as having the real and imaginary samples similar. So the results looked almosed coherent. But with higher frequencies the results are wrong. In frequency analisys the user is mostly interested in the highest peaks of the amplitude signal. Some analizers have a function returning a list of the frequencies higher than a certain threshold. @agraham Could you please take in consideration my suggestions, at least the 1st one. For shure you can use my test program as the demo program ! I will make some improvements: - add some more possibilities - make a better more userfriendly interface - add some help for the user Best regards.