and/or for the performance hit of an
interpreted language like some Basics. If this
color organ was going to work, I would need
to code in assembly language and do so as
efficiently as possible.
The first hurdle I had to face was that
digital filters of the IIR (infinite impulse
response) variety are typically implemented
using difference equations of the form:
y[n] = A * y[n-1] + B * y[n-2]
where y is a three element array of output
history and A and B are floating point filter
coefficients that are determined from the type
and response of the filter being implemented.
To use such filters, I needed to be able to
multiply floating point numbers on a
microcontroller that doesn’t even know how
to multiply integers. Floating point arithmetic
is something one takes for granted when
using a HLL, but as I mentioned this was not
an option here.
Horner’s Method to the Rescue
In my investigation of how floating point
arithmetic might be done, I stumbled across a TI
application note (see Resources) that described
Horner’s method for floating point multiplication and division. Horner’s method provides
reasonably accurate results while only requiring
shift/rotate and add instructions; something the
MSP430 controller family has and does very
well in a single clock cycle.
The remainder of this article describes this
method along with a technique called
Canonical Sign Digit or CSD that can be used to
optimize the Horner results. Finally, I will present a program I wrote called Horner.java, that
generates Horner equations and can even generate the MSP430 code for performing floating
point multiplications and divisions. Note: Even
though the focus here is on the MSP430 family
of microcontrollers, the techniques presented
are applicable to any processor.
I won’t delve into the theory behind
Horner’s method; instead, I will show you how
“... a color organ is a device that splits
music up into numerous frequency bands
and modulates colored lights according to
the musical content ... With a color organ,
you can see the music, as well as hear it.”
the theory is applied. (The Resources sidebar
has some pointers to arithmetic theory for those
interested in reading further.) Suffice it to say,
Horner’s method allows multiplication and
division of signed and/or unsigned floating
point numbers using a rather elegant approach
which I will illustrate. Horner’s method is not
without its drawbacks, however, which include:
• When multiplying and dividing, the multiplier
or divisor must be known in advance and
cannot be changed dynamically. This is not an
issue with most DSP applications because most
coefficients are known at design time and don’t
change at runtime. (This is true in general, but
probably not true of everyone’s applications.)
• A division remainder is not available using
Horner’s method like it is in most other division
techniques. (Why this is so will be shown later.)
• The results of multiplication and division are
rarely 100% accurate and the errors vary
depending upon the types of numbers being
processed. (I will illustrate this with examples
For my color organ application, none of
these drawbacks turned out to be significant.
The process of using Horner’s method can
be broken down into the following series of
steps. Given a known multiplier or divisor:
1) If dividing, invert the divisor so that it
becomes a multiplier.
2) Convert the multiplier to its binary representation of the required bit length; usually 10, 12,
or 16 bits.
3) Optionally apply CSD to the binary
representation to optimize it. (CSD will be
4) Generate the Horner equations for the
multiplication from the binary representation.
5) Generate the computer code which
implements the Horner equations.
The example that follows will show how
this is done. It is actually kind of fun to generate
the equations and the code by hand the first
couple of times to aid in really understanding
the process. Horner.java came about because I
had to generate a lot of multipliers and the fun
quickly turned to tedium.
Let’s generate the equations for the multi-