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.
By Jack Ganssle
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
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 the editor 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.