DSP Robotics Support

This is my simple approach to lookahead limiter. Feel free to optimize it. The biggest CPU hog is max from array...

Hi, I've done some research and it turns out it is possible to implement the "max from array" in O(1) steps (meaning the overall CPU usage will be independent of array-size). Here's a module I've made. Unfortunately it had to be done in assembler, but pseudocode is included. I have no idea how the algorithm works (some stack-based trickery).
One disadvantage of the module is, that the window-size must be set at stage(0), meaning you can't change it on the fly without glitches...

It can also be modified to calculate min from buffer...

KG_is_back wrote:Hi, I've done some research and it turns out it is possible to implement the "max from array" in O(1) steps (meaning the overall CPU usage will be independent of array-size). Here's a module I've made. Unfortunately it had to be done in assembler, but pseudocode is included. I have no idea how the algorithm works (some stack-based trickery).
One disadvantage of the module is, that the window-size must be set at stage(0), meaning you can't change it on the fly without glitches...

It can also be modified to calculate min from buffer...

Looks like a divide&conquer algorithm. They are known to be pretty independent from array sizes. A simple one with two halves will get the desired results from a 1-million-entries-array in 9 steps (100 entries -> 6 steps). Where did you find it?

tulamide wrote: Where did you find it?

on stackoverflow... http://stackoverflow.com/questions/32436689/find-maxand-min-on-the-moving-interval-using-python
I always knew this O(1) algorithm should exist, but I could not figure out how it should work... until I've found this one...

Note that my implementation uses one buffer, where first part is the push stack and second part is the pop stack and the division between them is just a pointer ("i" variable). I've found that this way I don't have to copy the input buffered values and I only have to recalculate the maxima in pop stack.

KG_is_back wrote:

tulamide wrote: Where did you find it?

on stackoverflow... http://stackoverflow.com/questions/32436689/find-maxand-min-on-the-moving-interval-using-python
I always knew this O(1) algorithm should exist, but I could not figure out how it should work... until I've found this one...

Note that my implementation uses one buffer, where first part is the push stack and second part is the pop stack and the division between them is just a pointer ("i" variable). I've found that this way I don't have to copy the input buffered values and I only have to recalculate the maxima in pop stack.

That's actually a very clever method! Thank you for the find. It's not divide&conquer, but makes use of the fact that the data changes over time, which also means you can compare each incoming data step by step, which is always the same amount of work, no matter how much data will come in. Clever!

KG, it seams that your max from buffer doesn't work properly...

Anyways, here is the updated version with different type of filtering. Filters do make a lot of difference. I wonder if there is some better filter for this job...

I think I've found what the issue was. It was some sort of weird input update for the streams vs. green when it comes to stage(0).
This one should work fine...

KG_is_back wrote:I think I've found what the issue was. It was some sort of weird input update for the streams vs. green when it comes to stage(0).
This one should work fine...

Thanks, this seams to work properly...

KG_is_back wrote:Hi, I've done some research and it turns out it is possible to implement the "max from array" in O(1) steps (meaning the overall CPU usage will be independent of array-size). Here's a module I've made.

Wow, this truly is powerful. Thank you for the find indeed!

Youlean wrote:Filters do make a lot of difference. I wonder if there is some better filter for this job...

This got me thinking.. could the algorithm above be modified to calculate the average of the buffer as well? Because that would make a nice filter for the lookahead (imo needs to be applied twice in a row with half the window size to make it smooth enough). I really have no clue about how it would be done in practice, but I suppose this couldn't be implemented in the exact same buffer (?). But "max from buffer" -> "average of buffer" chain should do the trick, and still be very light on CPU. If this is possible in the first place of course.

KG_is_back wrote:I think I've found what the issue was. It was some sort of weird input update for the streams vs. green when it comes to stage(0).
This one should work fine...

There still seems to be a minor issue. Sometimes when you change the window size on the fly when audio is put through, it loses all the information below a certain level (which seems to be random every time). Hard to explain, so I've attached an image about the problem.

nmakinen wrote:could the algorithm above be modified to calculate the average of the buffer as well?

Yes, it can be modified to calculate min, max and sum (average=sum/bufferSize).

nmakinen wrote:There still seems to be a minor issue. Sometimes when you change the window size on the fly when audio is put through, it loses all the information below a certain level (which seems to be random every time). Hard to explain, so I've attached an image about the problem.

At the moment, the algorithm is implemented in a way, that buffer-size is fixed (determined at the first sample). To change toe buffer-size you need to reset the stream (with clear-audio prim) which clears all the buffers and data is lost in the process. I can modify the algorithm to have adjustable buffer-size on the fly, but it will be slightly less efficient. Originally I thought this fixed-size would not be an issue.