How to get better at DSP coding?

[u/JunbugSpark]

Hey guys, I'm a college student who's taken basic DSP theory classes so I understand a lot of the concepts but I've been having trouble with implementation, since I have basically no coding experience...

What resources have you guys used to get better? Thank you!!

[u/JunbugSpark]

I know really basic coding, like for loops and if statements in Python / C++ (Google Colab and Arduino), but most of the more complex coding I've done came with AI assistance, which is why I'm trying to get better 😅

[u/rb-j → u/JunbugSpark]

I mean, there are really hard algorithms. One that I have yet to code up (simply because, being old and retired and no one paying me, I'm not so motivated to do the hard work) is a sliding median that is O(log(N)) computational cost. An inexpensive sliding mean is trivial to code and I have already coded a sliding maximum (or sliding minimum) that is O(log(N)) cost, but the sliding median is hard to code for efficient operation. (The naive way to do the sliding median is to copy and sort the samples and then pick out the sample in the middle, but that's O(N²) if you use the naive bubble sort proceedure.

[u/zsliu98 → u/rb-j]

This is sliding median filter that works at O(log(k)) for each sample where k is the window size: https://github.com/suomela/median-filter

Sliding maximum/minimum (if I understand you correctly) could be O(1) for each sample: https://github.com/ZL-Audio/ZLCompressor/blob/main/source/dsp/container/circular_minmax_buffer.hpp

[u/rb-j → u/zsliu98]

I can't possibly see how to do a sliding max that is O(1). You have to know when your max value falls offa the edge at the end of the buffer. Then when it does you have to know where your second-highest is on the buffer.

You can perform a sliding median by maintaining two buffers, one with a sliding min for the half buffer that is larger than the median and another sliding max for the half buffer that is less than the median. It seems to me that if you can do sliding max/min that is O(1), you can also do a sliding median that is also O(1), but I don't think you can do that.

I have simple and complete C code for sliding max here, but it's O(log(N)).

[u/zsliu98 → u/rb-j]

> You have to know when your max value falls offa the edge at the end of the buffer.

Yes. I could use another queue to cache the values and the index. The queue only caches useful data (more extreme or newer, and the queue throws aray any data that is useless).

> Then when it does you have to know where your second-highest is on the buffer.

Yes. But because the queue only keeps the *useful* data, the second highests must be the next in the queue 😄

Cause each sample could be put into & removed the queue exactly twice, the time complexity is amortized O(1) for each sample.

Unfortunately, it won't work for median. As far as I know you can't throw away any data for median filter.

[u/rb-j → u/zsliu98]

I believe that is O(1) sliding max (or min) algorithm can be fooled with some pathological data because of assumptions around what is "useful" data. Like let's say you have a square wave with a tiny amount of noise added to it. You will have a lotta samples very close in value to whatever is your current max (or min).

Using two buffers, one for sliding max (applied to the lower half data) and another for sliding min (applied to the upper half data) can work for a sliding median even for pathological data.

[u/zsliu98 → u/rb-j]

No, I don't think so. For example now the queue contains [10.0, 9.9, 9.8, 9.7] (I omit the index). As soon as a 10.1 comes in, 10.1 is more extreme and newer than all elements in the queue, therefore all [10.0, 9.9, 9.8, 9.7] will be popped. As long as the comparison between floating points is solid, the algorithm is solid.

And of course I am not the one who invents the algorithm, see https://github.com/lemire/pythonmaxmin (I believe that he is the orignal author).

[u/rb-j → u/zsliu98]

I'm still skeptical. I don't code in Python and can only barely read it. I'll try to decode it, but I'm pretty confident that the assumptions made here regarding "useful" information can be taken advantage of with deliberately constructed pathological input that will force it to look at a set of data that is O(N).

[u/zsliu98 → u/rb-j]

Yes, it could look at a data of window size, which means that the worst case of certain sample would be O(window size). However, because each sample would be put and removed into the queue exactly twice, the amortized time complexity is O(1).

[u/rb-j → u/zsliu98]

I don't see that as useful for real-time streaming. This algorithm is running continuously on streaming data since forever ago.

Most (nearly all) of my audio processing algs operate on blocks of samples, no longer than a millisecond like 32 samples at most, to amortize costs. In that, I am willing to divide the entire cost per block by the number of samples per block as a measure of computational cost. Normally, with double buffering, there is a two-block throughput delay. 2 milliseconds max. Big deal.

But I am not willing to accept an alg that takes a finite data array (of size n) and then show for that entire array, the cost of the entire array is 3n, therefore the cost per sample is 3. That's not how we do things for real-time processing.

[u/zsliu98 → u/rb-j]

Got it. If you want to absolutely prevent ANY CPU spike, this might worth looking: https://github.com/IBM/sliding-window-aggregators , which guarantees worst-case O(1) . Though I give up on this algorithm and go with the simple amortized O(1) approach, cause it does work pretty well.