FPGA - moving windowed average, variance, standard deviation, kurtosis, skewness

[charlie87]

Hi !

I am processing data in  FPGA and I want to calculate MOVING WINDOWED average, variance, standard deviation, kurtosis, skewness online for last N (N  is windows size) items. The frequency is about 100kHz and N is about 10000 (100 ms of the signal).

I have found something like EMA (exponential moving average) ....

Have anyone solved anything like this ? Any ideas how to solve it ?

[JLewis]

The most common way of doing this requires storing the last N data points in BRAM, then updating the calculation for each new point by adding in the effect of the new point k and subtracting that of the k-N point exiting the window. Choose a constant power-of-2 window size if possible in order to get the divide for free via a Scale By Power of 2 operation.

This isn't too bad for the mean, but gets more complicated and expensive for higher-order statistics. You can look at the desktop implementations in the Signal Processing>>Point By Point>>Probability & Statistics PtByPt palette to get an idea of the computation needed on the newest and oldest points. There's a lot of extra code in those VIs to handle inifinite window sizes and such, so they are only useful for the algorithmic aspects--the FPGA architecture will be completely different, using Memory or FIFOs instead of arrays, FXP types, etc.

Jim

[charlie87]

I have considered this option too. I wanted to use FIFO queue to save the last N items and execute some algorithm as well as you described. The point is that we don't have enough memory to process all channels. We have 16 channels and the length of the window N is 10000 items. (100 ms when freq = 100kHz) (This is the worst case) The data type is FXP 27/5. The available memory is for cRIO 9076 "only" 2088 kb.

I am new in FPGA problematic. Maybe I havent understood my cRIO specification (RAM size or BRAM size, etc) but I think it is impossible to implement algorithm  as I described above. Maybe I am wrong. Please explain if really I am.

Moreover I was said that the cRIO ram is used as a buffer for FIFO DMA transfer. Not for computation. (??? !!!) Is it correct idea ? 

This is the reason why I am looking for same kind of recursive online algorithm...

[JLewis · Accepted solution]

That does look like a problem. What kind of window do you require? Is the exponential moving average an option? There are online algorithms described in Wikipedia, but they can suffer from numerical accuracy issues when implemented in fixed point (depending on the nature of the data). They would be worth looking into, though.

Other than that, here's a few options I can think of:

• Bigger FPGA
• Do part of the processing on the RT controller--have you looked into that?
• Revisit your requirements and push back on some of the numbers. Do you really need 100 ms in all cases, etc?
• Depending on the nature of the data, some simple compression techniques might be an option
• Do some precision analysis to determine the minimum data type you really need. Getting down to 25 bits, for example, would have a huge impact on your multiplier cost.
• Consider floating point math (using Xilinx IP cores) for the online methods. Your data rate is reasonably low, so you could share computational resources between all of the channels. Managing the different channel states gets complicated but is doable.

The BRAM will be used for the FIFO buffers, but is also available for general purpose use to implement FIFOs and Memories. Some IP uses BRAM under the hood, so you have to keep an eye on the compile summaries to monitor how much you have left.

[charlie87]

Well. I have been searching for some recursive algorithm and i found some equations for average, variance and RMS which are suffucient. However kurtosis and skewness are still unknown ...

I am thinking about your suggestions such as save some fpga resources and implement the algorithm with FIFO queue. I am not sure how long the buffer for DMA FIFO. What size should be efficient and safe for the device when no data losing is acceptable. Could you explain me a little bit this issue ? I found something in the web pages but it is usually said "Set buffer size to according the DMA read and write rate". This is not understoodable for me. As I said I am new one in FPGA and LabView....

[JLewis]

I'm not an expert on DMA transfers, but in my experience the FPGA-side buffer doesn't have to be too big as long as you have a sufficient host buffer. The host buffer needs to be big enough to account for worst-case jitter in the Windows or RT DMA Read loop. Normally, the default FPGA buffer size is fine--you could try reducing it a bit but there won't be enough savings to have much impact on your problem. The main concern for the FPGA buffer is at startup; if the FPGA VI starts writing before the host starts reading, you can quickly fill up the buffer.

Take a look at <LV>\examples\R Series\FPGA Fundamentals\Analysis and Control\FFT\FFT with Handshaking for an example that provides lossless DMA transfer of FFT frames.

[gprakash66]

Hi are you able to implement recursive algorithm online. I am also looking foe the same. If you have implemented can you please share VI.