Creating Linked-list type structure in LabVIEW FPGA for fast moving average?

[qumhh]

I Need a trailing average that I can specify the trailing amount. I can't want to use arrays, as removing the first element at index 0 and shifting everything in the array would be extremely expensive. Furthermore, lab-view FPGA requires fixed size arrays on compile. So I don't think I would be able to specify my moving average after initial compile. What kind of memory option would be best suitable for creating a custom linked list? Has anyone done this before?

[Bob_Schor]

Are you familiar with a "ring buffer"?  This is a fixed-length Array with two pointers, the "Start of Array" (used for reading) and the "Start of Free Space" (used for writing).  The two pointers are incremented modulo the length of the Array. 

In the old days of Fortran, you could simulate a Queue by creating an Array of, say, 1000 integers and set the Read and Write pointers to 1 (Fortran starts Arrays with 1, not 0).  If "Read = Write", the Queue is empty.  To Enqueue, you put the value in Array[Write] and increment Write (mod 1000).  To Dequeue, you ensure that Read <> Write (so the Queue isn't empty), read Array[Read] as the value, and increment Read (mod 1000). 

The size of the Array you use for your Ring Buffer should be larger than the maximum length of the Queue you will need.  When you go to Enqueue, you need to make sure that (Write - Read) mod Queue Size is < Queue Size, else the Queue is full.  Forgot to mention that.

Note that once in the Queue, the data don't move, only the pointers, and only once per item read or written (move the pointers instead of the Queue elements).  Also, the data structure to hold the Queue remains fixed.  Clearing the Queue is done by setting Write = Read.

Someone more experienced than I with FPGA programming may have a much better solution ...  [Another idea that comes to mind is to pass the data back to the PC Host, if there is one, and do the Queue operations on the PC's separate CPU -- probably depends on length of Queue and data rate ...

Bob Schor

[Terry_ALE]

---

@qumhh wrote:

I Need a trailing average that I can specify the trailing amount. I can't want to use arrays, as removing the first element at index 0 and shifting everything in the array would be extremely expensive. Furthermore, lab-view FPGA requires fixed size arrays on compile. So I don't think I would be able to specify my moving average after initial compile. What kind of memory option would be best suitable for creating a custom linked list? Has anyone done this before?

---

What is the maximum size of the number of elements in the running average?

[GerdW]

Hi qumhh,

---

@qumhh wrote:

Has anyone done this before?

---

I used a MemoryBlock on FPGA to handle my MovingAverage: you need a memory size of "num of channels" * "average size". In my case I just needed 16 channels with 16 samples per channel, so 256 entries in the MemoryBlock…

[Bob_Schor]

If having a "variable-sized" Ring Buffer is important, you'll (of course) need to allocate enough memory for the maximum size you'll need, and have one additional parameter, "Buffer Size", that handles the variable "wrap-around" (which, of course, you advance by incrementing the pointer and resetting it to 0 if it reaches "Buffer Size").

Bob Schor

[altenbach]

In addition, averaging might be a bit tricky, depending on the datatype, especially on FPGA.

Of course it is sufficient to keep track of the last N points in the original representation AND the sum separately, this way you only need to add the new point and subtract the oldest while replacing the oldest with the newest in the buffer.

Have a look at slides 12-14 in our presentation (part II) for some algorithm comparisons.

As bob already mentioned, all you need is a max size buffer, even if you use smaller averages. Of course you also need to decide what should happen if the size changes on the fly.