Chaotic Systems
The new science of chaos is fascinating in its own right, and
may have important implications for designers of embedded systems.
Published in Embedded Systems Programming, March, 1995

For novel ideas about building embedded systems (both hardware and firmware), join the 25,000+ engineers who subscribe to The Embedded Muse, a free biweekly newsletter. The Muse has no hype, no vendor PR. It takes just a few seconds (just enter your email, which is shared with absolutely no one) to subscribe. 
"Everything you know is wrong". This quote, from a 60sera
Firesign Theater album, sums up my feelings about sliding into
middle age, with life relentlessly hammering away in one direction
and the kids constantly reminding me of various inadequacies.
At least I can fall back on the determinism and certainty of digital
systems.
Or, can I? Science took a very unexpected twist in this century.
The reductionist approach advocated by Descartes and so many others
(i.e., "understand the parts and then you'll understand the
whole") was first assailed by Bohr and pals with their introduction
of quantum mechanics. Heisenburg pounded another nail in reductionism's
coffin by proving we'll never really be able to measure all of
the bits and pieces of atomic events.
James Lovelock's concept of Gaia, at the very least a tremendously
fascinating philosophical exercise, forced us to look at systems
from the top down. Part of his hypothesis implies that biological
environments are so tremendously complex that understanding comes
only from examining them on a macroscopic scale. That is, we'll
never derive the wonderfully intricate effects of life on the
environment by studying nothing more than cellular structures;
we have to look at the entire biosphere as a whole. In fact, as
NASA prepared to send a billion dollars of Viking hardware to
Mars to look for life by analyzing soil for animo acids, Lovelock
correctly (?) predicted life's absence by noting there is no oxygen
in the planet's atmosphere. An effect of life, Lovelock contends,
is a macroscopic change in the environment.
Now the emerging science of complexity  popularly called "chaos
theory"  undermines even our understanding of the behavior
of simple algebraic equations. Here's the bad news: iterative
solutions of many of the very simplest of polynomials can give
results that apparently make no sense.
A Quick Overview
Perhaps you've heard statements from the popular press claiming
that the weather is inherently unpredictable because the flapping
of a butterfly's wings in Brazil will ultimately have some effect
in your own home town. The essence of this statement is that
we can never, ever, know the initial conditions of a system with
enough precision to predict its outcome. Remember that Heisenberg
told us that the act of measurement effects the result, limiting
the resolution of any instrument we care to use to get this initial
data. If your system is wildly dependent on the starting point,
the limits imposed by quantum mechanics will give us wild results.
Our brains understand linear systems. Make a little change in
the input and you naturally anticipate a small change in the output
results. The effects of quantum uncertainties are so far down
in the noise as to be unimportant. Unfortunately, most of the
world is inherently nonlinear, and in many nonlinear systems
the output is sensitively dependent on initial conditions.
In 1961 Edward Lorenz, while studying weather simulations, found
that one of his equations behaved most oddly. He predicted that
the parameter X was a function of its state at some early time,
and related X' (the new value of X) to X by:
X'=AX(1X)
(This is the same equation used by population biologists to predict
the number of animals in an area in successive generations).
Lorenz had his primitive computer run numbers through his equation
repeatedly, at each stage substituting the last computed X' into
X. He found that as long as the constant A remained small X' converged
to a result that was proportional to the value of A. You'd expect
this. If the result monotonically diverged to infinity your sense
of proportion would be equally satisfied.
When A gets near the value 3 the equation gives results that simply
make no sense. For an identical A and X, iterating the equation
will converge to one of two results. Increase A to about 3.5 and
the same iterations yields four results. As A gets just a bit
larger the complexity of the result soars, with millions, then
billions, of answers... all for the same input data!
In Lorenz's case, he found that limited floating point precision
created tiny errors responsible for the apparently crazy concept
that one equation with one set of data could yield many answers.
However, it turns out that for any finite amount of floating point
precision the equation will still eventually degenerate into this
"chaotic" region, chaos meaning "pretty good data
in, crazy stuff out".
The figure shows a dramatic view of the descent of the equation
into chaos. The horizontal axis is "A"  the polynomial
coefficient. The vertical axis shows X'. I created the plot with
a simple (but huge!) Excel spreadsheet. For A less than 3 or so
the result is like that of a traditional function: a single value
in results in a single value out. Above 3 the curve forks into
two result for each value of A. At about 3.45 the curve forks
again, a process that repeats until an infinite number of answers
appear.
Mathematicians call this repeated forking "period doubling".
It's a common characteristic of chaotic systems.
Chaos and Us
It's easy to dismiss chaos as a result of Lorenz's odd equation.
Few of our systems use equations of this form... or do they?
Lorenz's equation is nothing more than a simple secondorder polynomial.
It's equivalent to:
X'=AXAX2
or,
X'=AX2 + BX + C
where A=B
where C is zero, though in fact any value of C will give a chaotic
result.
In other words, for the right (wrong?) values of A, if A=B any
iterated second degree polynomial is identical to Lorenz's illbehaved
equation!
Further research showed that chaos is a characteristic of nonlinear
equations of any degree. If your product iterates a polynomial,
beware!
Iterating is one of the things computers do best, and is a standard
part of any programmer's repertoire. Iteration is nothing more
than feedback, one of the most commonlyused techniques in analog
circuit design. Are we building systems grounded in mathematical
quicksand?
So, gentle reader, I pose a question: how sure are you that your
new product, that instrument using a micro to solve a series of
equations, operates in a nonchaotic region? As a mathematics
amateur I'll plead ignorance to the fine details of chaos. It's
clear, though, that simple equations are rife with scary behavior,
behavior we can ignore only at our own (and our customers') peril.
I think that our industry needs to examine the implications of
this theory for our products. Let's face it: while scores of mathematicians
develop beautiful theories to explain and manipulate chaos, we,
who write the code that makes the computers iterate, are basically
ignorant of its implications.
Iterations
I invite someone with mathematical authority to email in with
an explanation of what sort of conditions we should watch out
for. In the meantime I'd be wary of any nonlinear algorithm 
particularly one that iterates.
In a former life I worked on machines that computed the percentage
protein in wheat by measuring the amount of IR energy reflected
from a grain sample. Reflectances from numerous wavelengths all
contributed to the protein result in a complex manner, all combined
in a polynomial whose coefficients were determined by a tedious
iterative process much like that described above. Quite often
the coefficients gave an equation that predicted wildly erratic
protein values. At the time we called these "bad calibrations"
and blithely advised users to repeat the experiment, but now I
suspect the instruments operated on the edge of chaos.
In another situation, my former partner and I designed steel thickness
measuring equipment. The units were selfcalibrating: the software
tossed various known thicknesses of steel into the xray beam,
and then computed a least squares solution to a polynomial which
would predict the thickness of any piece of the same material.
Though the system worked pretty well, it was horribly sensitive
to changes in practically any parameter. Not supplying enough
knownthickness pieces resulted in crummy predictive powers of
the polynomial, as did any tiny error in the standards. We developed
empirical procedures that generally resulted in good results...
but never understood the why behind the what.
Now I wonder how much sense it makes to let a system automatically
compute coefficients of a polynomial of two or higher degree.
If you know the coefficients then you can probably model the system
to see if there is a tendency to degenerate into chaos. When the
computer picks the coefficients, anything goes.
Just how does one go about modeling potential chaos? I've been
building simulations using spreadsheets. For a polynomial like
Lorenz's this is easy: put slowly increasing hardcoded values
of A along the columns, and then iterations down the rows. Plot
the columns and look for values that do not converge to a single
answer.
It's a bit harder to do this for equations of higher degree with
so many more coefficients. Perhaps a better approach is a simple
C simulation of the equation that looks for chaos as the coefficients
are diddled around the values the system will use.
I'd be wary of running this experiment on a Pentium! Offload the
divisions to a coprocessor... or even a software floating point
emulation running on a good old reliable 8051. Those pesky Pentium
division problems will seed all sorts of errors into your results.
Questions
Any nonlinear system could be chaotic. Reference (3) includes
a chapter about predicting chaos, but it's far over my head. I
invite responses from anyone having experience or thoughts about
this.
A collerary of this could be: how close can we ride to the edge
of a known chaotic condition. In the case of the Lorenz equation
it's just a matter of knowing at what point A causes the system
to degenerate. When two, three or more variables are involved,
what do we do?
At the risk of admitting even more ignorance, some day I'd like
to understand the process of how a system falls into chaos. If
you maintain 80 bits of floating point precision, can the system
stand twice the iterations as with 40 bit precision? I'm looking
for an infiniteprecision BCD math package that will let me study
this. I'll report on the results... when there are some.
KnowitAlls
I advise every embedded software person to start studying chaos.
Given that it has such profound effects on even the simplest equation,
there's a chance you could spend a lot of time fighting what appears
to be a software bug but is in fact an artifact of the math.
It reminds me of trying to debug a system years ago that measured
absorption of oils in perclorethelene. Nothing worked; I spent
weeks looking fruitlessly for the problem. A chemist who fortuitously
dropped by explained that the effect I was looking for was swamped
by minute amounts of alcohol in the solvent.
The embedded world is truly interdisciplinary. You have to be
partly a hardware designer, partly a firmware guru, a chemist,
radiologist, and part Renaissance man (ah, person). If the system
computes mathematical solutions, you better study bone up on math
as well. What you don't know can, and will, bite you.
Read widely.
References:
1. Chaos, the Making of a New Science, by James Gleick,
1987, R. R. Donnelley & Sons Company, Harrisonburg, VA  This
is a mustread for any educated person. I couldn't put it down.
2. Exploring Chaos, by Nina Hall, 1991, W. W. Norton &
Company, NY, NY. You have to read this one. Chapter 12, Chaos,
Catastrophes and Engineering, covers chaotic failures in real
life. Chapter 13, Chaos on the circuit board, cuts uncomfortably
close to home for most of us.
3. Chaos, by Arun Holden, 1986, Princeton University Press,
Princeton, NJ. The math makes this a hard read for those of us
suffering from calculus withdrawal. Still, there's a lot of useful
information to be had here. Various chapters discuss chaos in
everyday life, from electronic feedback to cardiac rhythms.
4. Newton's Clock, by Ivars Peterson, 1993, W. H. Freeman
and Company, NY, NY. The universe seems held together by chaos,
as this book describes so well. There are important islands of
stability in chaotic systems, which explain the motion of many
of the solar system's moons.
5. The Turbulent Mirror, by John Briggs and F. David Peat,
1989, Harper & Row, NY, NY. A fascinating, very readable account
of chaos.
6. Ages of Gaia, by James Lovelock, 1988, W. W. Norton
& Company, NY, NY. This is the best of the Gaia books, from
the one who started it all.
