Hi, I have made a rough outline to implement FFT-analysis on the DSO nano. I welcome everbody to join this thread and give feedback on my ideas. My plan is to implement FFT-analysis this way the coming month. Any comment and/or suggestions are welcome!
Memory size is an issue which gives limitations to the quality ans speed of the algorithm. The choice we can make is between N=256 or 512 bins. For bin size N, memory is needed for algorithm input of 2N shorts, that is 4N bytes. Also the same amount of memory is needed for algorithm output.
Therefore, for N=512, we need at least 4K RAM extra. For N=256, this is 2K.
Fortunately, we can re-use some existing buffers: F_Buff, the buffer for USB communication (see files.c) and Data_Buffer, for reading and writing Micro SD card (see memory.c) are both 512 bytes. By overlaying these buffers on the FFT-algorithm input-buffer, the amount of extra RAM for FFT is lowered by 1024 bytes.
I would like to choose N=512, as the quality of the FFT is higher with more bins.
As Jerry already described in thread viewtopic.php?f=12&t=971&start=10 , the company Embedded Signals has made made an open source 16 bit assember FFT routine that can be used for non-commercial purposes. One routine is available for N=64, 256 and 1024. ANother routine is available for N=128 and 512. Both are highly optimised assember functions that can be called from C.
FFT can be drawn instead of the reference wave. That way no extra memory is needed for storage of the fft wave.
Also the FFT wave can be drawn on the same screen as the normal wave, just like the reference is laid over the normal wave.
Only the first 300 bins of the 512 are shown on the display. Perhaps that some scrolling function could be implemented to view the other 212 bins. The frequency range that is calculated with the FFT algorithm is: 0 … sample_freq/2. Hence the
frequency range on the 300 pixels screen width is 0 … sample_freq/2 * 300/512.
The pseudo code for implementing FFT on the DSO Nano is:
(this code should be called every time the normal waveform is refreshed)
Step 1. Statically allocate memory
short FFT_in [ 1024 ]; //input data 16 bit
short FFT_out[ 1024 ]; //output data 16 bit
Step 2. Copy Scan_Buffer to input buffer, copy data around the triggerpoint
if ( Scan_buffer is empty )
break; // no fft calculation when no data
short scanindex = triggerpoint - 256;
for ( short i=0; i<1024; i=i+2 )
{
FFT_in[ i ] = Scan_Buffer[ scanindex++ ]; //real value
FFT_in[ i+1 ] = 0; //imaginair value
}
Step 3. Calculate Windowing function
// multiply each real input value with hanning windowing function which is multiplication by value between 0 and 1
for ( short i = 0; i < 1024; i=i+2 )
{
// windowfactor is array in flash memory
// multiplication is done with int values, therefore factors are between 0…65535
// and are precalculated as windowfactor[i] = 65535 * (0.5 - 0.5 * Cos(2 * PI * i / (1024 - 1)));
FFT_in[i] = ((int) FFT_in[i] * windowfactor[i]) / 65536;
}
4. compute FFT
fft512( FFT_out, FFT_in );
5. calculate magnitude of output (and store result back in FFT_in)
short j=0;
for ( short i = 0; i < 1024; i=i+2 )
{
FFT_in[ j++ ] = sqrt( FFT_in[i] * FFT_in[i] + FFT_in[i+1] * FFT_in[i+1] );
}
6. calculate logarithmic scale (dB)
for ( short i = 0; i < 512; i++ )
{
FFT_in[ i ] = 20 * Log10(FFT_in[ i ]);
}
7. display FFT values on screen
erase_fftwave();
draw_fftwave();
What do you think? Feel free to give suggestions/ideas/feedback.