Boolean Algebra
Do you get the boolean blues? Those hardware weenies keep chatting
about DeMorgan, truth and evil... and you're feeling left out?
Read on.
For hints, tricks and ideas about better ways to build embedded systems, subscribe to The Embedded Muse, a free biweekly e-newsletter. No hype, just down to earth embedded talk. Click here to subscribe.
My June column about Software PALs sparked quite a bit of feedback.
I was struck by the number of folks with little understanding
of Boolean algebra, the basis for the design of logic circuits.
Every design engineer learns Boolean, but it seems few software
folks master this important tool.
One of my brothers is completing a Ph.D. in philosophy. I was
fascinated to learn that Boolean algebra is an important trick
used in the defense of philosophical ideas. True - mostly they
use a somewhat less formalized version than we do, but the "Rules
of Logic" are nothing more than a statement of the truths
we bury into algebraic formulation. Isn't it nice that philosophers
consider our basic premises, as expressed by Boolean logic, to
be the basis of testing truth? Maybe what we do is quite profound
and fundamental, after all.
How often have you seen ten nested IF statements in C that lead
to an incomprehensible conclusion if all are fulfilled? Too often
the programmer gets lost in the process, creating an incorrect
routine that is practically undebuggable. Boolean algebra, and
the tools we use to deal with it, can help simplify, or at least
document, such convoluted code.
The Basics
If we define the character "*" to represent a logical
AND (the same as the "&" operator in C), and "+"
to mean logical OR (C's "|" operator), then the following
relations are defined to be true:
- A*B is true (i.e., a "1") if both A and
B are true. In other words, and AND function generates a one if,
and only if, A and B both are ones.
- A+B is true -- a one -- if either A or B is true.
- /A (i.e., "not A") is a one only if A is a zero.
/A is the inverse of A.
Boolean algebra is nothing more than the process of combining
these simple relations into a mathematics that lets us express
any logical idea via ANDs, ORs, and NOTs.
The algebra satisfies the communitive law we learned so painfully
in high school: ordering is not important. A*B is the same as
B*A.
The distributive law works as well. (A+B)*C is the same as A*C+B*C.
Think about it: the (A+B) portion of the equation is irrelevant
if C is a zero; clearly A*C+B*C has the same effect.
The algebra is nothing more than a compact way of expressing everyday
occurrences. For example, "the car can run only if the brake
system self-test works (call this variable BREAKS), and if the
engine's ignition is on (IGNITION), and if the seatbelts are connected
(SEATBELTS), and if the airbag system has detected no faults (FAULTS).
This is the same as:
RUN = BREAKS * IGNITION * SEATBELTS * /FAULTS
Since every embedded system controls some sort of real-world thingamajig,
much of the code we write boils down to a representation of these
sort of events.
There's one other relation commonly used, though it is not an
identity since it is derivable from the earlier assumptions. The
"exclusive OR" is a function whose output is true only
if the two inputs are different - if both are zero or both are
one, then the result is zero. This is:
AB = A*/B + /A*B
where the symbol means "exclusive OR".
The exclusive OR might seem a little abstract, but it's often
used in embedded systems. A0xFFFF results in the complement of
A - for computers with no NOT instruction it's a quick way to
invert a register. AA is zero, a fact often exploited in assembly
language to quickly clear a register. I used to set register A
to zero on a Z80 via
XOR A
which is only a single byte opcode. Painful experience taught
that most of what I do is wrong, so now I explicitly load a zero
into the register, as follows:
LD A,0
Then, I can instantly patch the 0 to any value when debugging
the code.
The Search for Truth
Great minds can take a complex logic problem and instantly come
up with its Boolean formulation. The rest of us must resort to
some sort of trick.
The Truth Table is a semi-graphical way of viewing the components
of any logical expression. Used properly, it will show you instantly
how to combine the various elements into a single equation.
Suppose we're dealing with the following problem:
An operator perched high above a railway yard controls a small
train that runs back and forth on a dedicated track. The MOVE
button on his console makes the train move - unless it is all
the way at the right or left end of the track, as indicated by
the LEFT or RIGHT limit switches. Being a control freak, the operator
can make the train go past either limit by also pressing the OVERRIDE
button. If you were writing the code to handle these conditions,
what would it look like?
We can boil the English-language description down to the following
truth table, where ON means the train can move:
ON MOVE LEFT RIGHT OVERRIDE
0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 0 1 1
0 0 1 0 0
0 0 1 0 1
0 0 1 1 0
0 0 1 1 1
1 1 0 0 0
1 1 0 0 1
0 1 0 1 0
1 1 0 1 1
0 1 1 0 0
1 1 1 0 1
0 1 1 1 0
1 1 1 1 1
The truth table is nothing more than a list of all possible states
of the input variables, with the result (ON) computed for each
state.
Since the goal of the program is to turn the motor on if the right
conditions are met, we can ignore any entry in the table where
the result is zero. The sixteen cases thus reduce to only 5. Further
examination, though, reveals an important simplifying fact: if
the MOVE and OVERRIDE buttons are both pressed, the limit switches
are not significant. Further, if no limit switch is hit, the OVERRIDE
condition is not important. If we replace irrelevant entries with
X ("don't cares" in logic parlance), the table looks
like:
ON MOVE LEFT RIGHT OVERRIDE
1 1 0 0 X
1 1 X X 1
1 1 X X 1
1 1 X X 1
1 1 X X 1
Clearly, the last four conditions are the same, so the equations
of motion for the train are now just:
ON = (MOVE * OVERRIDE) + (MOVE * /LEFT * /RIGHT)
or,
ON = MOVE * (OVERRIDE+/LEFT*/RIGHT)
It doesn't take much thought to realize that you can add global
disable terms just by ANDing more variables with the final equation.
For instance, to stop motion if a FIRE alarm is detected:
ON = FIRE * MOVE * (OVERRIDE + /LEFT*/RIGHT)
Truth tables are particularly valuable for identifying non-obvious
relationships. Suppose this example resulted in 13 conditions
where the train moved, instead of just 5. If you skipped the truth
table exercise you'd probably come up with a hideously complex
program that dealt with all 13 conditions. The truth table will
clearly show the 13 ones.... as well as 3 cases where the equations
result in a zero (don't move) condition. Why not decode these
don't move conditions, and then just invert the result?
The great simplification brought to bear by a truth table often
obscures the truths being worked on. If you did decode just the
three "zero" results and then inverted the output, no
one will ever figure out your logic. Great job security, but a
terrible disservice to your successors. Use the table as a documentation
device. Include it in the program's (or PAL's) comments, so it's
clear where the code came from.
DeMorgan's Theorem
Logic designers resort to another trick to reduce the amount of
electronics needed in a circuit. DeMorgan's Theorem lets you change
ANDs to ORs and vice versa.
The Theorem states:
A*B = /(/A + /B)
or, conversely,
A+B=/(/A * /B)
You'll see this used extensively in circuit design where there
may be spare OR gates but no spare ANDs - DeMorganizing a term
might save adding extra ICs. When writing PAL equations you reduce
the number of product terms (the ANDs of variables) by DeMorganizing
OR terms. This saves output pins, again ultimately reducing chip
count.
ESC Follow-up
If you read PC Magazine you'll see John Dvorak's reviews of big
conferences like Comdex. Like so many other authors he effects
an air of boredom, and complains each year about the industry's
lack of innovation.
Well, John and friends, if you go to a show expecting little,
with eyes blinded by your own self-importance, you'll probably
find just what you expect. Me, I go to a show looking for technically
cool stuff and a good time.
I'm sure Tyler will have much to say about this year's Embedded
Systems Conference held in September in Santa Clara. Suffice to
say, the show as bigger than ever: more booths and greatly increased
foot traffic.
Motorola and IBM pushed the PowerPC aggressively. If sheer marketing
can make a part successful then the PowerPC will surely become
an important high-end processor. At the low end of the spectrum
Intel introduced new members of the venerable 8051 family. Microchip
broadened its line of PIC microcontrollers, and added a new controller
to reduce the power consumption of fractional horsepower motors
(I hope to cover this in detail in a later column). The tool market
continues to expand, with more and more vendors offering Windows-hosted
versions of their products.
Suffice to say, you could have spent at least two days wandering
the halls, soaking up neat technology and fascinating discussions.
It seems like all of the industry's movers and shakers
attend this show. To me, next to the parties, the best part of
this annual event is the chance to meet with these very smart,
very opinionated folks whose mission in life seems to be to create
the change and chaos that non-techies are so afraid of.
As an exhibitor I do a certain amount of booth duty, which is
a fascinating experience to one who loves to watch people. Some
folks creep by with scowls painted on their faces, trying hard
to avoid their mostly wrong perception of glad-handing sales folks
that leap from booths in an attempt to push their wares. Others
are anxious to discuss their latest project or problem, drawing
on the show's attendees and vendors as a resource.
The purpose of the conference is to talk. Let's face it: you can
see the highlights of the exhibits in the advertising pages of
this magazine. It's nice to see the vendors' goodies in person,
but much more important is a chance to tap their, and your colleagues,
minds.
This show does offer an extensive series of classes, which are
a formal forum for a one-way exchange of ideas. It's best, though,
at a show like this, to proactively search out people whose opinions
you'd like to solicit. What processor should you use next year?
What's going on in real time OSes? How will one deal with protected
mode on the new embedded 386's? Its foolish to think that you,
or any one person knows all the answers. Come to this and other
shows to listen, challenge, and engage in a dialog that will help
focus your thoughts.
Most engineers work in a sort of isolation, relying only on the
written or electronic word to shape their decisions for future
products. It's so important to get out of your usual environment
and engage others. Even if your opinions are simply confirmed,
the experience is a mental vacation that helps you see the industry
in a new light.
And, as for the rumors of late night parties on the hotel's roof,
well, I plead the fifth. All I can say is that a happy face was
worn by all.
I'm going to Electronica in Munich in November, which is reportedly
the largest electronics show in the world. Although I'll only
have a day and a half at the show, I expect to get more of a European
slant on the embedded world. Expect a report in these pages in
the months to come. Don't expect a Dvorak-like cynicism: I, for
one, am quite sure Electronica will have surprises and novel ideas.
Parties, too, with a bit of luck.
|
