Support

If you have a problem or need to report a bug please email : support@dsprobotics.com

There are 3 sections to this support area:

DOWNLOADS: access to product manuals, support files and drivers

HELP & INFORMATION: tutorials and example files for learning or finding pre-made modules for your projects

USER FORUMS: meet with other users and exchange ideas, you can also get help and assistance here

NEW REGISTRATIONS - please contact us if you wish to register on the forum

Lookahead limiter

DSP related issues, mathematics, processing and techniques

Lookahead limiter

Postby Youlean » Wed Jul 27, 2016 2:04 am

This is my simple approach to lookahead limiter. Feel free to optimize it. The biggest CPU hog is max from array...
Attachments
Youlean look ahead limiter.fsm
(40.61 KiB) Downloaded 1566 times
Youlean
 
Posts: 176
Joined: Mon Jun 09, 2014 2:49 pm

Re: Lookahead limiter

Postby KG_is_back » Wed Jul 27, 2016 7:17 am

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...
Attachments
max_from_buffer.fsm
(1.18 KiB) Downloaded 1510 times
KG_is_back
 
Posts: 1196
Joined: Tue Oct 22, 2013 5:43 pm
Location: Slovakia

Re: Lookahead limiter

Postby tulamide » Wed Jul 27, 2016 8:27 am

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?
"There lies the dog buried" (German saying translated literally)
tulamide
 
Posts: 2686
Joined: Sat Jun 21, 2014 2:48 pm
Location: Germany

Re: Lookahead limiter

Postby KG_is_back » Wed Jul 27, 2016 8:37 am

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
 
Posts: 1196
Joined: Tue Oct 22, 2013 5:43 pm
Location: Slovakia

Re: Lookahead limiter

Postby tulamide » Wed Jul 27, 2016 8:23 pm

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!
"There lies the dog buried" (German saying translated literally)
tulamide
 
Posts: 2686
Joined: Sat Jun 21, 2014 2:48 pm
Location: Germany

Re: Lookahead limiter

Postby Youlean » Wed Jul 27, 2016 10:58 pm

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...
Attachments
Youlean look ahead limiter 2.fsm
(135.01 KiB) Downloaded 1566 times
Max from buffer bug.fsm
(45 KiB) Downloaded 1441 times
Youlean
 
Posts: 176
Joined: Mon Jun 09, 2014 2:49 pm

Re: Lookahead limiter

Postby KG_is_back » Sat Jul 30, 2016 3:10 am

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...
Attachments
max_from_buffer.fsm
(6.32 KiB) Downloaded 1521 times
KG_is_back
 
Posts: 1196
Joined: Tue Oct 22, 2013 5:43 pm
Location: Slovakia

Re: Lookahead limiter

Postby Youlean » Mon Aug 01, 2016 8:41 pm

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...
Youlean
 
Posts: 176
Joined: Mon Jun 09, 2014 2:49 pm

Re: Lookahead limiter

Postby nmakinen » Tue Sep 06, 2016 3:21 pm

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.
Attachments
max_from_buffer_bug.jpg
max_from_buffer_bug.jpg (22.49 KiB) Viewed 37914 times
nmakinen
 
Posts: 5
Joined: Fri Oct 28, 2011 5:31 am

Re: Lookahead limiter

Postby KG_is_back » Tue Sep 06, 2016 4:28 pm

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.
KG_is_back
 
Posts: 1196
Joined: Tue Oct 22, 2013 5:43 pm
Location: Slovakia

Next

Return to DSP

Who is online

Users browsing this forum: No registered users and 21 guests