# Butterworth

Started by 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;
}

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;
>
> }
>
>
>
>
>
>
> 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;
>
> }
>
>
>
>
>
>
> 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)
{
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
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

```