From the original SynthMaker forum (2004–2014), with its members’ names and dates.
martinvicanek ·
Hi!
Following the work of Tzarls and Disco_Steve in this thread, I have implemented a 64 point FFT and iFFT. The attached demo is just an FFT/iFFT pair with nothing interesting happening in between. Anyway, CPU load is modest, so there is some headroom to get creative. 😉
While it is not hard to generate code for 128 or more points, I have not succeeded in making it work in SM. Perhaps there is some limit regarding code length, I don't know.
Even the 64 points schematic is not as efficient as it could be without SM's inherent limitations (and possibly my own limitations regarding ASM 😊 ). Also the present implementation is for complex valued input/output - for real input half of the processing is wasted. So the 64 points code can still be optimized, however I am more skeptical about a possible extension to 128 or more points.
Disco_Steve ·
Great work 🙂
Please tell me you wrote a script to generate this code and didn't write this all out by hand!!!!
It has been a few years since I was working on this, but I'm sure that you can FFT higher lengths using smaller lengths. So the 64 point limit may not be a problem. but like I said, it has been a while!
It is such a piety I'm so scarce for time - I would love to play with this stuff more again. 🙂
I'll try my best to find time to give more input to the SM forum in general, I don't think I have posted in ages!:)
Steve
martinvicanek ·
Disco_Steve wrote: Great work 🙂
Please tell me you wrote a script to generate this code and didn't write this all out by hand!!!!
Thanks, Steve, glad you are still around! No, I didn't do it by hand, I used a C-Code to generate this. That's why I said it's no big deal to generate code for 128 etc.
treacherousumbrella ·
Nice work as per usual 🙂 Managed to get a 16 point DFT/iDFT functioning before but the FFT always seemed out of reach with SM's code limitations. Do you have any more info on the script you used to generate the code? Never really fancied the arduous task of unwrapping the FFT's nested loops. Thanks for sharing, wish I had more time to check out it's possibilities right now.
martinvicanek ·
treacherousumbrella wrote: Nice work as per usual 🙂
Thanks! 😍
treacherousumbrella wrote: Do you have any more info on the script you used to generate the code?
It's no big thing really. Just grab an FFT code and replace some instructions that do the actual computing by suitable print instructions. Like this:
int nn=64;
int isign=1;
int n,mmax,m,j,istep,i;
double wtemp,wr,wpr,wpi,wi,theta; // Double precision for the trigonometric recurrences.
float tempr,tempi,tmp;
int b0,b1,b2,b3,b4,b5,b6,b7;
fprintf(ifFileNr,"// Pass the bucket to populate the input data\n");
for (i=1; i<nn; i++) fprintf(ifFileNr,"inR%d = inR%d; inI%d = inI%d;\n",i-1,i,i-1,i);
fprintf(ifFileNr,"inR%d = inReal; inI%d = inImag;\n",nn-1,nn-1);
fprintf(ifFileNr,"// pass the bucket to stream the output data\n");
fprintf(ifFileNr,"outReal = x0; outImag = y0;\n");
for (i=1; i<nn; i++) fprintf(ifFileNr,"x%d = x%d; y%d = y%d;\n",i-1,i,i-1,i);
fprintf(ifFileNr,"}\n");
treacherousumbrella ·
Ah OK thanks, makes sense. Will be diving into C a bit deeper when I have some spare time (one day), work mainly in code in SM anyway. Surprised this hasn't had more interest, I was under the impression people had been attempting a stream FFT for quite some time. Hopefully everyone is too busy trying to come up with some creative uses for it 🙂
stw ·
treacherousumbrella wrote: Ah OK thanks, makes sense. Will be diving into C a bit deeper when I have some spare time (one day), work mainly in code in SM anyway. Surprised this hasn't had more interest, I was under the impression people had been attempting a stream FFT for quite some time. Hopefully everyone is too busy trying to come up with some creative uses for it 🙂
Oh i'm very much intrested though i haven't any use for it right now.
I didn't reply here because not everybody is able to handle all the praises! And i don't want martin to suffer from that. 😈
But since i'm in now anyway i'll express my excitement about this excellent piece of (SM) coding. Very much appreciated martin!! 😍 (as usual)
martinvicanek ·
treacherousumbrella wrote: Surprised this hasn't had more interest [...]
stw wrote: [...] i haven't any use for it right now.
Not so surprising if you do the numbers: At 44.1 kHz the FFT64 analyses the audio stream in snipplets of 1.5 ms and throws the data into frequency bins at 0 Hz, 689 Hz, 1378 Hz etc. Interesting things may be happening between 0 Hz and 689 Hz, however these will leave FFT64 quite indifferent. 😉 A more relevant regime would be addressable with a 1024-point FFT, but as I stated earlier, I doubt this road will lead us there.
stw wrote: [...] not everybody is able to handle all the praises! And i don't want martin to suffer from that. 😈
Right, good point there! To be on the safe side, I'd suggest no more than one praise a week. 😀
treacherousumbrella ·
Quick & dirty attempt at converting from real/imaginary values to magnitude/phase
Magnitude is functioning fine although there is an error in the phase conversion at the moment. The arctan, sin & cos approximations are accurate between Pi & -Pi, but stupidly forgot that radians are 0 to 2Pi, this may be the cause of the problem. Also included an FFT low pass filter.
Here is the conversion formula if any one fancies having a crack at fixing it, I'm pretty low on time right now.
On a side note, if there is a limit to code length in SM, hacking out the imaginary section of the FFT may free up enough lines for 128 point or more. Been way too long since I've studied FFTs 😕
{Edit: See below for fixed version}
martinvicanek ·
Nice first application!
treacherousumbrella wrote: [...] there is an error in the phase conversion at the moment.
Note that arctan(x/y) will give you a value between -Pi/2 and Pi/2, whereas the phase may be anywhere in the interval [-Pi,Pi] or, if you prefer, [0,Pi]. Some languages provide a function arctan(x,y) which covers the full circle.
But actually you don't need to convert to modulus and phase and back for your example, just apply the LP to the real and imaginary parts directly! 🙂
P.s. Yes, you could probably rearrange the data to get a 128 point real FFT.
treacherousumbrella ·
The low pass filter was actually just a quick (badly implemented) addition, not the goal.
Have since improved the accuracy of the pade approximates of the atan, sin & cos but still have issues with the reconstruction after iFFT. Maybe will try some silly high polynomials to check whether this is still the problem. Will repost tomorrow when back at my computer. There's quite a few effects that can be implemented with phase and magnitude difference information between frames. Is the signal windowed in any way? Also is there an internal clock in the Fft that could be hijacked for overlapping frames? Sorry haven't had time to delve too deeply into the code. Thanks again for your contribution(s) 🙂
martinvicanek ·
treacherousumbrella wrote: Have since improved the accuracy of the pade approximates of the atan, sin & cos but still have issues with the reconstruction after iFFT. Maybe will try some silly high polynomials to check whether this is still the problem.
For trig approximations have a glance at http://www.ganssle.com/approx.htm. Takes a bit of work to implement in SM but could be worth it.
treacherousumbrella wrote: Is the signal windowed in any way? Also is there an internal clock in the Fft that could be hijacked for overlapping frames?
No windowing applied. Yes, at some point you would probably want overlapping frames. I haven't found an elegant way to do that yet (only a clumsy way).
treacherousumbrella ·
Fixed real/imaginary to magnitude/phase and back again
Think my brain was wired back to front yesterday, was expecting an input between 0 & 2Pi at the arctan. Arctan approximation was accurate within that range, but obviously the imaginary/real division before it will tend towards infinity at points 😊
Arctan implemented with a few modifications for accuracy from Martin's previous link, although some sections were missing in the link. Full text can be found here: http://www.ganssle.com/approx/approx.pdf
Wrote something here? To have a post removed or your name hidden, write to [email protected].
SynthMaker