FPGA: Highest value in a running window?

[A.E.M]

Hi All.

I’m using LabVIEW FPGA to acquire data, and based on that data I’m taking a decision whether or not to trig the rest of the system.

Before talking that decision, I want to do some initial simple filtering.

I want to take the last 100 samples and see if at least one of them is bigger than a threshold. If so, return true.

In Windows, this could easily be achieved by using an array and update the oldest sample in the array with the newest one from the data acquisition and finally use the min / max LabVIEW build-in VI.

However, I don’t believe this method is the most beneficial one on a FPGA.

So I guess I should use a Memory block instead, but this rises 2 questions.

1) I have limited space available, but I need the decision to be taken fast. My device utilization is as follows:

Total Slices: 96,1% 
Slice Registers: 57,8% 
Slice LUTs: 72,5% 
DSP48s: 15,6% 
Block RAMs: 53,1%

Which memory implementation would be best in my case?

2) IF Memory is the way to go, then how do I read it all out to determine if any of the value are above my threshold?

Maybe there’s an even more clever way of finding the highest value in a running window??

[Jonas.H]

Hello A.E.P,

Using a memory block FIFO should be fine. You can have a look at the built in LabVIEW help and examples regarding using the FIFO read function, which you would be using to read it all out.

Rather limited information, so I am not sure if this was the answear you were looking for. Please do not hesitate to reply here if there is anything I am missing or anything else.

Best regards,

Jonas.H

[pnouvel]

Hi AEP

If you want to perform threshold detection, I would suggest you to not store these data in the FPGA but rather performing lively the threshold comparison. Thus, you'll save some memory ressources.

In other words :

1/ When a new data/sample is received, perform directly the threshold comparison.

2/ store the single data threshold comparison result at the MSB or LSB in a shift register

3/ shift the register each time a new sample is processed.

4/ perform a big AND operation on this register.

AND operation a resgister shifting are easy operation for FPGA. That should not take a lot of ressources

Cheers, 

Patrice NOUVEL

[A.E.M]

Thanks for your reply.

Let me try to explain in greater detail.

I acquire two datasets: one of them is the actual data I want to use; the other is used as my threshold.

However, I need to take 100 samples from the threshold data, and if 1 or more of these samples are above a giving threshold, a flag is set to true. If this flag is true, it is save to use the data.

See my drawing, this should make a lot more sense 🙂

My issue is how to calculate the flag on the FPGA. On Windows, I could just use an array and the Quotient & Remainder, but that's not really preferable on the FPGA.

So I’m looking for a design idea, while having in mind, that I don’t have much space left on the FPGA.

[pnouvel]

HI, 

OK, If I understand, you'll get the 100 "threshold" samples at one time and you need to process it . Ihmo, you have 2 options : 

1/ if you need to get the result one one clock cycle, you'll need to perform the threshold comparison on the full 100 samples at a time. The typical implementation to duplicate the code is to use a for loop, store the result in array and perform a massive AND operation. This will go fast (if you get timing violation, juts add a shift register before the AND comparion), but will take some ressources

2/ If you can afford performing this operation in 100 clock cycles, the idea is to read the the array of samples one by one and to perform each time the threshold comparison.

Just a comment of the ressouce utilization. I don't know which FPGA you're using but is seems you have some room left. You should not take the "total slice" in account to check if you can add additional function in your FPGA. Indeed, the ISE tools just take as much space as availble to relax constraint timing. So even if you've a small design, this number may be quite high. On the other side, the other number are quite important and can help you to identify optimisation to do if you reach the FPGA size limit. 

[Sam_Sharp]

Looking at your picture, why can't you do the following?

When you read a sample, compare it to the threshold and if it's true, reset a counter to 0 and set your flag to true. Each time you read a sample and it is outside the threshold, add one to the counter. If the counter is greater than 100, reset your flag to false.

[A.E.M]

@ pnouvel:
I only get 1 sample at a time. So the question really is, how to store the data on the FPGA, so I have 100 samples at all times (except for the first 100 samples). After this, I need to look at all samples and see if thet are above a giving threshold.

I'm asking for advise for best FPGA programming style to implement this. If using an array, I need a index, but how to get an index from 0-99 without using the Quotient & Remainder (expensive on a FPGA).

@ Sam:
That's not a running Window.

Then you'll start all over every time the counter hits 100.

See my new drawing 🙂

[pnouvel]

Does your threhold is changing value during runtime ? 

[A.E.M]

No, as a start we can assume the threshold does not change.

[Sam_Sharp]

I don't see the difference?

My solution only works if you don't need to change the threshold applied to the old data - if you want to change the threshold you either need to accept that the old data will be using the old threshold or you can 'reset' the counter when the threshold changes to refill. Only requires a U8 and a shift register (don't increment if over >100 to avoid rollover) so will be very efficient on FPGA resources.