Forums

Some ideas I had

Started by DHMarinov 6 years ago7 replieslatest reply 6 years ago194 views

Hi there,

I am a recent graduate from Aarhus University in Denmark. I have been doing DSP for a while now (~3 years), and as I encounter more and more problems I am starting to get some ideas, which are not described anywhere. Therefore I decided to write some of them down and present them in front the DSP community. 

I have included two ideas: a lo-fi filter which can be made only of statements, and an envelope/peak detector alternative, which is also based on if statements.

I have tried to express my ideas as easily as possible, therefore do not expect any fancy words :D. Also English is not my mother tongue, therefore I apologize for any mistakes.

Finally I would appreciate  your feedback. You can download the description from my GitHub : https://github.com/DHMarinov/MATLAB/blob/master/Description.docx .


Thank you.

[ - ]
Reply by Tim WescottNovember 15, 2016

You have the misfortune of being born too late.  Silicon has gotten cheap enough that such heroic measures are rarely needed, unless you actually need the characteristics you're driving at.

Low pass:

Been done.  You're basically seeking the median of the data rather than the mean -- these numbers are the same for some data sets, different for others.  Note that you have _not_ exactly designed a median filter -- that's a different critter.

And, you _are_ carrying a state: your 'cap' variable.

On most processors, overall, you're not gaining much -- silicon is getting ridiculously cheap these days, and "if then increment" doesn't take much less real estate on an ASIC than "arithmetic shift then add a couple of times".  You're also losing linearity, which means that -- from a linear systems point of view -- the filters apparent characteristics will change dramatically with the input amplitude.

"Arithmetic shift then add" refers to a low-pass filter that uses a multiply by a constant power of two.  Given \(x_k\) as an input, and \(y_k\) as the output, then specify your filter as $$y_k = y_{k-1} + 2^{-N} \left( x_k - y_{k-1} \right)$$.  You're saving yourself from an (expensive) multiply, and keeping the filter linear, but you have somewhere between twice and three times the same and maybe half again the real estate in the additions than in the increment of the "if and increment" filter.  (I edited this, because while I was taking the increment into account as almost the same amount of work as an add, I was forgetting that the magnitude compare operation is basically a subtract -- and a conditional increment/decrement circuit may end up being as big as, or bigger than, a simple add).

Envelope Detection:

Books could be written about envelope detection.  If written by people who need them to work in a wide range of conditions, they would be full of expletives.  Your way will work, but be sensitive to noise.  Another, easier, way for finding min and max, that works well with the right kind of data, is just to implement a conditional low-pass filter.  Implement a regular-old first-order low-pass, except that for the maximum, if the input data exceeds the filter state then nail the filter state to the input value.  For minimum, just change "exceeds" do "is lower than".

English Language Skills:

This is just my opinion, but your written English skills are just fine.  Your writing is perfectly understandable, with only a slight "accent" that is only detectable in light of your admission that you're not a native speaker -- had you said nothing, I wouldn't have been able to tell you from a native English speaker who's writing a bit casually.  In my opinion, it's far more important to make your statement clearly, completely, and succinctly than it is to make it read like a native speaker.

[ - ]
Reply by ombzNovember 16, 2016

Appreciate the comprehensive answer.

Now I'm curious: what are the topics that we're not born for too late? :p

[ - ]
Reply by Tim WescottNovember 18, 2016

Oh god, there's no limit.  I'm 54, and I can get a chip that's 3mm on a side that has more storage and processing power than the first desktop computer I worked with in 1976.  There's an endless list of analog circuits that are now better implemented in software, and entire solutions (like bug-robots as big as your thumb) that weren't even thinkable 20 years ago.

[ - ]
Reply by dudelsoundNovember 16, 2016

If you are into writing more efficient code for very special cases (which is something I really enjoy) - you will probably find this site very nice:

http://bits.stephan-brumme.com/

Regarding your code I agree with Tim that I don't believe it is much more efficient than a real filter with multiplies and adds. I do a lot of programming on small microcontrollers with few mips and all. But even on a 1$ microcontroller a multiply - and most of the time even a multiply-and-add, sometimes even a multiply-and-add-and-move is a single cycle instruction, whereas if-then-else tend to be very expensive if there is more than a single command in each branch. Oftentimes the CPU needs to branch (to jump over code) when using if-then-else - and on most modern architectures this means the pipeline needs to be flushed using up many valuable cycles.

In my code I usually even stopped doing conditional code execution if the code is small:

for example I replace this code:

if (doProcess)

out = alpha * in + (1-alpha) * dout;

else

out = in;

with this code:

out = alpha * in + (1-alpha) * dout;

if (!doProcess)

out = in;

This avoids pipeline flushes and the last 'if' statement is usally coded with two moves in assembler, one of them being conditional...

All I want to say is: Whether a code or algorithm is efficient or not is largely dependant on the platform you are implementing it on.

Regards

Markus


[ - ]
Reply by Tim WescottNovember 16, 2016

In theory, if you haven't marked anything as 'volatile' that shouldn't be, a good optimizing compiler would generate the same assembly code from either of those two examples.

I've found -- much to my chagrin -- that working really hard to make the code efficient often just confuses the hell out of the optimizer and gives me slower code.

The compiler-writer's mantra to write the code to express intent, and let the optimizer do what it's supposed to do is getting more true every day.  The only places I've found in the last decade or so where that's not true is when the underlying machine does stuff that don't fit well with the C virtual machine, and the optimizer hasn't been programmed to understand this.  For the last couple of decades, for me, this has been for things like DSP chips and vector dot products -- but I've been told that even some of the more common DSP chips come with compilers that can recognize a vector dot product and turn it into a hardware loop with MACs.

[ - ]
Reply by dudelsoundNovember 17, 2016

You may well be right - but the last little 'machine' I did this on came with a coprocessor which was extremely useful to me, but unfortunately only programmable in assembler :)

[ - ]
Reply by Tim WescottNovember 18, 2016

There you go.  In such cases you're stuck with hand-optimizing.  I often end up steering customers away from such design choices, because most of my customers to date have done low-volume production.  There's a whole engineering cost vs. product introduction time vs. bill of materials cost, and when someone is only ever going to build 1000 of something, a $5 part is cheaper than a couple of man-weeks of engineering time.