Forums

Butterworth

Started by Vladimir Vassilevsky October 4, 2013
Butterworth-like 3rd order LPF.
Super slim.

// (c) VLV
//Fc ~ Fs/1400
//Dynamic range ~ 140 dB

s32 LPF(s32 *z, s32 x)
{
x = z[0] += (x - z[0]) >> 8;
x -= z[2] << 1;
z[1] += (x - z[1]) >> 8;
return z[2] += (z[1] - z[2]) >> 8;
}


Vladimir Vassilevsky
DSP and Mixed Signal Designs
www.abvolt.com
On 10/4/13 4:24 PM, Vladimir Vassilevsky wrote:
> > Butterworth-like 3rd order LPF. > Super slim. > > // (c) VLV > //Fc ~ Fs/1400 > //Dynamic range ~ 140 dB > > s32 LPF(s32 *z, s32 x) > { > x = z[0] += (x - z[0]) >> 8; > x -= z[2] << 1; > z[1] += (x - z[1]) >> 8; > return z[2] += (z[1] - z[2]) >> 8; > }
now my question is how does that number "1400" get related to that other number "8" in this algorithm above? or how does 1400 get related to 2^8? something like 1400 =approx 2^8 * pi * sqrt(3) ? it's only a numerological guess. also, is this supposed to be a block-everything-but-DC kinda filter? -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On Saturday, October 5, 2013 12:24:47 PM UTC+13, Vladimir Vassilevsky wrote:
> Butterworth-like 3rd order LPF. > > Super slim. > > > > // (c) VLV > > //Fc ~ Fs/1400 > > //Dynamic range ~ 140 dB > > > > s32 LPF(s32 *z, s32 x) > > { > > x = z[0] += (x - z[0]) >> 8; > > x -= z[2] << 1; > > z[1] += (x - z[1]) >> 8; > > return z[2] += (z[1] - z[2]) >> 8; > > } > > > > > > Vladimir Vassilevsky > > DSP and Mixed Signal Designs > > www.abvolt.com
A single op-amp is better
On Saturday, October 5, 2013 12:24:47 PM UTC+13, Vladimir Vassilevsky wrote:
> Butterworth-like 3rd order LPF. > > Super slim. > > > > // (c) VLV > > //Fc ~ Fs/1400 > > //Dynamic range ~ 140 dB > > > > s32 LPF(s32 *z, s32 x) > > { > > x = z[0] += (x - z[0]) >> 8; > > x -= z[2] << 1; > > z[1] += (x - z[1]) >> 8; > > return z[2] += (z[1] - z[2]) >> 8; > > } > > > > > > Vladimir Vassilevsky > > DSP and Mixed Signal Designs > > www.abvolt.com
When Being Clever Is Not Being Smart A certain kind of programmer likes to demonstrate how clever they are at every opportunity. I guess that we have all met similar people in many walks of life. Such programmers specialize in arcane code that might just be a tiny bit more efficient. A little thought about what &#2013266067;efficient&#2013266068; might mean can often give some useful insight. Here is an example of some &#2013266067;clever&#2013266068; code: void bin(int x) { if ((x/2) != 0) bin(x/2); printf("%d", x%2); } What does it do? To save you having to spend ages trying to analyze the code, I will tell you: it prints a number in binary format. What is wrong with the code? Two things. First, it is hard to understand, and since a large proportion of programming time is spent on maintenance, such lack of clarity is short-sighted. Second, the code is recursive, and while it is valid in C for an embedded application, recursion should be used with great caution and only when absolutely necessary. It is easy for the code to consume more resources (i.e., stack space) than may have been anticipated. Consider this alternative code (which does almost exactly the same thing): void bin(int x) { unsigned mask=0x80000000; int i; for (i=0; i<32; i++, mask >>= 1) if ((x & mask) != 0) printf("1"); else printf("0"); } This implementation may seem simplistic, but it is certainly much easier to understand. So, did the &#2013266067;clever&#2013266068; code have any virtues or advantages? It may have been faster, but, for a user I/O function like this, speed is not an issue. What about size? We compiled both pieces of code for a 68 K target using &#2013266067;optimize for size.&#2013266068; I expected the results to be similar and to argue that a few extra bytes are a small price to pay for extra clarity. I did not expect the result that I got: both produce exactly the same amount of code&#2013266071;60 bytes
On 06/10/2013 01:45, gyansorova@gmail.com wrote:

> > When Being Clever Is Not Being Smart > A certain kind of programmer likes to demonstrate how clever they are at every opportunity. > I guess that we have all met similar people in many walks of life. Such programmers > specialize in arcane code that might just be a tiny bit more efficient. A little > thought about what &#2013266067;efficient&#2013266068; might mean can often give some useful insight. > Here is an example of some &#2013266067;clever&#2013266068; code:
.. ..
> This implementation may seem simplistic, but it is certainly much easier to understand. > So, did the &#2013266067;clever&#2013266068; code have any virtues or advantages? ...
Hmm. Vlad was posting something of interest to specialists in integer dsp (professionals, if you will). Those specialists are very likely indeed to understand it (at least at the code level!), and maybe post an interesting follow-up question. While in dsp speed may not be the ~only~ important issue, it is still a very important one. A process may need to run a large number of filters, under rigid deadlines, on relatively constrained hardware. Smart is as smart does, as they say. Are you saying the code is difficult to understand or that recursion is difficult to understand? That is taught in schools these days. For example, it is a specified topic in the UK "GCSE" Computing curriculum for 14 to 16-year-olds, and is likely to be introduced to 12-year-olds too. However, in relation to your examples, the teachers may need be a bit more rigorous, and, presented with that code, they will likely ask questions such as: * what hard-coded assumption does the non-recursive version make, compared to the recursive one? What effect does that have on the output of the two functions? * the argument is a signed int. Did you test both functions, as presented, with negative values? Richard Dobson
Richard Dobson <richarddobson@blueyonder.co.uk> wrote:

(snip)
> Hmm. Vlad was posting something of interest to specialists in integer > dsp (professionals, if you will). Those specialists are very likely > indeed to understand it (at least at the code level!), and maybe post an > interesting follow-up question. While in dsp speed may not be the ~only~ > important issue, it is still a very important one. A process may need to > run a large number of filters, under rigid deadlines, on relatively > constrained hardware. Smart is as smart does, as they say.
OK, regarding fixed vs. floating point, a problem like the following is assigned in some CS class: Given three points, x and y coordinates as integers, determine if they are colinear. The explanation goes on to explain that one should special case the case where some of the x values are the same, and do some rounding to allow for the inexact floating point arithmetic. But you can avoid the special case and floating point precision by doing the calculation in fixed point! Is this not something that CS students should learn? (They should also learn to work with floating point for problems that should be done in floating point.) -- glen
On 06/10/2013 20:27, glen herrmannsfeldt wrote:
> Richard Dobson <richarddobson@blueyonder.co.uk> wrote: >
..
> > OK, regarding fixed vs. floating point, a problem like the following > is assigned in some CS class: > > Given three points, x and y coordinates as integers, determine > if they are colinear. The explanation goes on to explain that one > should special case the case where some of the x values are the same, > and do some rounding to allow for the inexact floating point > arithmetic. > > > But you can avoid the special case and floating point precision > by doing the calculation in fixed point! Is this not something that > CS students should learn? (They should also learn to work with > floating point for problems that should be done in floating point.) >
Fixed point is probably a bit much to expect at school level CS. I can only answer for the UK; they learn the basics of integer and f/p arithmetic at GCSE (14 to 16), along with the basic issues of precision etc, in the context of general-purpose languages such a V. Basic and Python. They would not be working on dsp or other integer-based hardware, and the UK exams themselves do not require knowledge of fixed point as such. The computing curriculum is somewhat new to the UK (hitherto it has been predominantly "ICT" with programming mostly conspicuous by its absence). It is possible that the higher-level maths courses will deal with issues relating to computer calculation, but again it is not something specified in the exam curricula, so it would be something a particular teacher might choose to explore "for the fun of it" with the brighter students. It is to be hope there will be greater overlap between subjects in future years. Richard Dobson
Richard Dobson <richarddobson@blueyonder.co.uk> wrote:

(snip, I wrote)
>> OK, regarding fixed vs. floating point, a problem like the following >> is assigned in some CS class:
>> Given three points, x and y coordinates as integers, determine >> if they are colinear. The explanation goes on to explain that one >> should special case the case where some of the x values are the same, >> and do some rounding to allow for the inexact floating point >> arithmetic.
>> But you can avoid the special case and floating point precision >> by doing the calculation in fixed point! Is this not something that >> CS students should learn? (They should also learn to work with >> floating point for problems that should be done in floating point.)
> Fixed point is probably a bit much to expect at school level CS. I can > only answer for the UK; they learn the basics of integer and f/p > arithmetic at GCSE (14 to 16), along with the basic issues of precision > etc, in the context of general-purpose languages such a V. Basic and > Python. They would not be working on dsp or other integer-based > hardware, and the UK exams themselves do not require knowledge of fixed > point as such. The computing curriculum is somewhat new to the UK > (hitherto it has been predominantly "ICT" with programming mostly > conspicuous by its absence).
OK, I was thinking about first or second year college CS courses. Given a fairly simple problem, one should come up with a reasonable algorithm, code it up, and be able to run it. The solutions are in the 5 to 10 lines range. The solution to the given problem involves cross multiply which I think we learned in about 6th grade, but maybe a little later. That removes the divide and the problems associated with it. But too often, it seems to me, the floating point solution that takes a little less thought is used, and which generates less useful results. -- glen
On 10/6/13 5:24 PM, Richard Dobson wrote:
> On 06/10/2013 20:27, glen herrmannsfeldt wrote: >> Richard Dobson <richarddobson@blueyonder.co.uk> wrote: >> > ... >> >>> Vlad was posting something of interest to specialists in integer dsp (professionals, if you will).
BTW, i did *not* put in the effort to confirm Vlad's 3-order Butterworth LPF is correct. it could be, for all i know. i can tell you that it's linear, time-invariant, and 3rd-order. that's all i know.
>> But you can avoid the special case and floating point precision >> by doing the calculation in fixed point! Is this not something that >> CS students should learn? (They should also learn to work with >> floating point for problems that should be done in floating point.) >> > > Fixed point is probably a bit much to expect at school level CS. I can > only answer for the UK; they learn the basics of integer and f/p > arithmetic at GCSE (14 to 16), along with the basic issues of precision > etc, in the context of general-purpose languages such a V. Basic and > Python. They would not be working on dsp or other integer-based > hardware, and the UK exams themselves do not require knowledge of fixed > point as such.
so if a assignment was that these students do something requiring arithmetic on real numbers that involved intrinsically fractional quantities, would these kids have an idea how to do it without the use of float or double? what makes fixed-point a graduate or professional level problem is to do numerical stuff like inverting a 3x3 carefully or some transcendental functions or even sqrt. and to have a grip at every point of quantization (where the word width is decreased) what is the nature of the roundoff error (p.d.f., variance, spectrum). that's what makes fixed-point a specialty to master. having this grip of the intensity of quantization error at every point of quantization helps one decide what word width is needed along the signal chain to accomplish a spec'ed SNR or BER. floating-point DSP may worry about that too, but they might just do it in float and not worry about it (when, perhaps they should). besides the moving-average filter (that is better implemented in fixed point than in floating), another issue that some naive floating-point DSPers may miss is that of the cosine-of-a-small-value. the hidden one bit in floating point doesn't help you there. because all of the information really is represented in the *difference* cos(x) is from 1, as x gets small, the bits fall off the edge, even in floating-point. lotsa zeros in the mantissa when x is small. it's much better to replace every occurrence cos(x) in your math with: cos(x) <-- 1 - 2 (sin(x/2))^2 and represent (sin(x/2)^2 as a float. this is useful also in a fixed-point context. i think it's called the "cosine problem". -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On 07/10/2013 05:09, robert bristow-johnson wrote:
..
> so if a assignment was that these students do something requiring > arithmetic on real numbers that involved intrinsically fractional > quantities, would these kids have an idea how to do it without the use > of float or double? >
I will have to ask around a bit (not being a school teacher myself) but I suspect almost certainly not; nor most of the teachers either, unless they happen to have that sort of background already. For GCSE CS the curriculum requires them just to know the basic principles of exponent and mantissa, typically modelled simply, in perhaps 16 bits, with a few hand-written exercises. Beyond that, they just need to know that there are integer and f/p types in most languages. Fixed-point fractional is way beyond the curriculum. Subjects are somewhat siloed - very little maths in the CS course and very little computing in the maths course. And none of either in the music course! A situation I am with colleagues trying to change: http://people.bath.ac.uk/masrwd/smcs/smcshome.html So I am open to all suggestions for "simple" multi-disciplinary projects, which might for example demonstrate some of the issues you describe. An ideal project is one which can be written once, but used in (for example) any of a maths, music or CS class (maybe also physics), each with their particular focus. A good topic is one which offers "progression"; there is something for the weaker students to get marks for, but also something which can be used to stretch the brighter students. Richard Dobson