0
$\begingroup$

I have used Scilab functions to produce a low-pass filter for an audio signal and the coefficients for the associated constant coefficient difference equation (CCDE). I then produced filtered signals by running the Scilab filter() function and by running my implementation of the CCDE on the audio signal. The results are identical.

The Scilab filter() function runs considerably faster, by perhaps a factor of 30.

I am new to DSP and I am trying to better understand what the Scilab filter() function is doing that allows it to use the same coefficients so efficiently. In looking at the associated Scilab files, it looks like there is some compiled code behind the filter() function.

Any pointers as to technique or reference materials would be appreciated.

$\endgroup$
  • $\begingroup$ 30X faster than what? Obviously you implanted your own filter but how. It is impossible suggest improvements to speed up what is not specified $\endgroup$ – Stanley Pawlukiewicz Jul 30 '18 at 14:57
  • $\begingroup$ Stanley, I should have specified that the Scilab filter() function produced the same filtered signal 30 times faster than did my interpreted implementation of the CCDE. $\endgroup$ – user34299 Jul 30 '18 at 15:58
0
$\begingroup$

Scilab's filter, for short coefficient vectors, function implements a linear convolution in C code; that alone, since there's no python to actually be evaluated here, just multiplication and addition, is much much faster than writing something in a scripting language that can't 100% be just-in-time compiled.

For longer vectors, scilab implements fast convolution; ie. it exploits the fact that (circular) convolution in time domain corresponds to point-wise multiplication in (discrete) frequency domain, and uses zero-padding and saving of overlaps to emulate the linear convolution (which filtering represents) with that.

So, either way, use your libraries when doing signal processing! Aside from the convolution, there's other things that are generally faster if done via clever usage of library functionality: For example, whenever you have a loop that looks like

sum = 0 for a, b in zip(vectorA, vectorB): sum += a*b

you'd be far, far better of doing a dot product of the two vectors.

You have to consider this: Your CPU is very fast at doing basic math operations – often, it can do for example 8 multiply-and-accumulates (MAC) operations in a single step. Compared to that, parsing the structure of the (precompiled, even) for loop, building temporary python objects to hold the individual values for a and b, and overwriting the sum object, thus removing the old object and replacing it with a new one, leading to garbage collection and so on, is way way way way more work than just doing the maths. I like to put it like this:

Imagine you're tasked with multiplying a lot of numbers between 0 and 10, but the numbers you need to multiply are written in text form in a book.
Reading that book will take much, much longer than the multiplications

That's how it is to use dynamic languages to do basic math operations.

$\endgroup$
  • $\begingroup$ Marcus, Thank you for your informative answer. Besides trying to better understand how Scilab was implementing its internal functions, I also want to run this CCDE algorithm on an Arduino Uno. So the issues of floating point vs. integer calculations are of concern. The concept of circular convolution, of which I have heard but know little, may be applicable here. Any other thoughts you have on that next step, i.e., to the Arduino, would be appreciated. $\endgroup$ – user34299 Jul 30 '18 at 16:05
  • $\begingroup$ I don't understand the problem: An arduino is a microcontroller, right? So you write C for that, anyway. So, you're natively implementing the convolution in a compiled language. Unless you know very much about the microarchitecture of the microcontroller, you won't get better than that. Also, I'm pretty sure that if I was to do signal processing on a microcontroller, Arduino wouldn't be my choice of framework, primarily because it's pretty bad at handling interrupt-y code, which is really what you need when e.g. dealing with data from a timer-driven ADC. $\endgroup$ – Marcus Müller Jul 30 '18 at 16:10
  • $\begingroup$ your problem really is that the speed of "doing convolution in Python" is dominated by the "Python" aspect, not by how clever or stupid you implement it. So, since you're not doing Python on the microcontroller, that's not a problem. Doing convolution / filtering in any programming language is very straight forward: For each "length of tap vector" subsequence in your sample stream, you do a dot product with the (reverse) tap vector; thats one output sample. Done. Fast convolution is probably not an option on any microcontroller that you call Arduino, since too little RAM makes that impossible. $\endgroup$ – Marcus Müller Jul 30 '18 at 16:13
  • $\begingroup$ Oh, I just looked up the Arduino UNO: Don't use that. It's an 8-bit microcontroller running at a low speed with barely any interconnect on which you can get high rate data in and out. Most other microcontrollers will be far easier to work with!! Also, make sure a microcontroller is really what you need here. In fact, I think you should ask a question of the type "I want to achieve {GOAL} by {FILTERING SOMETHING WITH SOMETHING FOR REASON SOMETHING}. I'm not sure what kind of hardware platform to use here – is an Arduino UNO feasible? Are other Microcontrollers the right choice? DSP boards?" $\endgroup$ – Marcus Müller Jul 30 '18 at 16:21
  • $\begingroup$ Include as many constraints on your DSP system as you can, and give numbers instead of qualitative statements ("low power" means nothing, "less than 0.1 W" does mean something), and explain your background and time frame for implementation. Giving background info about why you're doing things always helps, too. This site might seem a bit theoretic, but unless you're directly asking for someone else to do your work (which you really don't seem to intend), the folks on here are extremely curious and like to think about how they'd implement something. $\endgroup$ – Marcus Müller Jul 30 '18 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.