Using Hardware Engineering Techniques in Software Development (part 1)
Armando Baratti
Senior Python Developer | 25+ years experience in software development
OK, I must confess: my academic formation is as Electronic Engineer. Worse, I’ve developed hardware form more than 8 years on the past.
What I have to say in my favor is that on the last 25+ years I’ve being developing software professionally (I hope I'm forgiven then).
To develop hardware is different from develop software, but they have much in common. During all this years I have had the opportunity to use some hardware engineering techniques and tools to help me in developing software.
It's about these techniques and tools that I'm coming here to talk.
Taming boolean logic complexity
Some times, when developing software we face some logic that is hard to grasp.
I’m not talking of simple conditions like this:
Even in simple situations I’ve seeing developers testing many combinations, almost by trial and error, until they find something that they think is working.
“ Must I use and or or to join these expressions?
Maybe I need to negate the first one.
No, if I do that it doesn’t works on that other situation...”
When things get more complex this mental reasoning can (and probably will) lead to unpleasant, subtle and sometimes hidden errors and side effects.
An example, please
Suppose you’re developing an application that offers paid access plans.
The user has access to determined functionalities according the plan purchased.
There are two plans available, Basic and Advanced.
You received a detailed description of the access logic that product people had been elaborating with business people.
They are thinking in introduce a “trial period”, that starts when the user purchases a plan and last five days, during which they have additional privileges to access features they would not have in their regular plan.
Also the marketing people have closed a deal with a partner to send coupons to their customers that give additional privileged access to your company application.
The rules run like this:
This is an example very close to what usually happens in specifications like this.
To summarize: you need to determine the degree of access the user have based on the plan they have purchased (or not), if they are within “trial period” and if they have a partner coupon.
Off course you can try to reason about the logic above and start to code something.
Probably you’ll be able to reach a tree of ifs, elifs and elses with many boolean expressions in the branches of it.
You’d have to check every possible condition, in your head, to assure some expression doesn’t spoil the result of the logic.
But wouldn’t it be great if we have a tool that could lead us to a correct result, consistently every time?
Well, this tool exists.
Veitch-Karnaugh Map
The Veitch-Karnaugh map (also known simply as Karnaugh Map) is a graphical tool to help us to minimize complex boolean expressions.
When I say “graphical tool” I’m not referring necessarily to a GUI program (I don’t even know if it exists in this form) but as a two-dimensional grid that you can create using pen and paper or a spreadsheet.
First we gather all input combinations in a table together with the resulting boolean output (one output per table).
Then we transfer the output result values from the table to the map.
This will help us in find (graphically) opportunities to aggregate input conditions and extract a minimized boolean expression using simple rules.
Get to work!
The first thing we need to do (as in any programming task) is to understand the problem and isolate it’s main elements (or entities if you prefer).
There are two kind of plans:
and also there are two more input conditions for our logic:
We want to determine access to three different sets of features (these are our output results):
Conventions
When we code we must use descriptive names for the variables and other code components, but here as we’ll be representing input conditions and output results in a grid, we don’t have much space so we’ll be using short abbreviations for it’s names.
Input conditions:
Output results:
Note that in this example the output results are independent, so a user that has access to advanced features (Adv = true) would not have necessarily access to basic features also (Bas = true), but we’ll guarantee this by our logic.
Also, due to space limitations (and to avoid name conflicts with input naming) I’ll represent boolean values, False and True as 0 and 1 respectively, the same way they are usually represented in hardware development.
Sometimes there are input combinations that cannot occur.
For example, the user cannot have purchased Basic and Advanced plan at same time.
For this situations we’ll represent the output result neither as 0 (false) nor 1 (true), but as X, meaning it can assume any of the former values, according what will be more convenient for us.
Once we have chosen a value for such combination of input conditions, we must stick with it for a given output result.
When dealing with boolean expressions is conventional to represent boolean operations like this:
This way, for example, an expression like this: A * /T + B, would means the user has an Advanced plan and is not within “trial period” or the user has a Basic plan.
The boolean operators precedence is (probably) the same as that of your programming language ( (A * /T) + B for the previous example).
Tell me the truth
Now let’s construct that table with all input combinations that I mentioned before and that’s called the truth table.
We’d need a table for each output result, but as every input combinations are the same I’ll simply represent each output result as a different column on the table using the same input columns:
You must be sure the truth table reflects exactly the logic rules.
This is the most important part of the process, and in fact has nothing to do with the Veitch-Karnaugh map by itself.
Treasure’s map
Now we’ll transpose the values from the truth table to the maps.
One map for each output result.
Here we grouped two of the input conditions (B and A) in columns and the other two (T and C) in rows. We can use the grouping scheme that we like.
Note that the order of combinations on the map are a bit different from those on the truth table.
On the table we followed the traditional order that corresponds to binary numbering:
But on the map we need that two adjacent columns or rows have just one bit modified. So we have to use the following order:
(note the two last rows seems swapped respective to the table).
Following the rules
Now it’s time to use the map rules to extract the boolean expression.
I’ll show you first some simpler cases and then proceed with our example.
Let’s imagine we have the following map:
That means that the output result is true (1) only in one situation, when:
W (be what it means in this case) is false
and X is true
and Y is true
and Z is false
This can be expressed as:
Res = /W * X * Y * /Z
or in code (Python) as:
res = not(w) and x and y and not(z)
Let’s see another example, with this other map:
领英推荐
In this case there are two input conditions where the output result is true, but note that in both inputs the value of W is irrelevant.
It doesn’t mater if W is 0 (false) or 1 (true), the output result is the same, as long as the other inputs remains the same.
So we’ll disregard W from our resulting expression:
Res = X * Y * /Z
We’ve done a boolean expression minimization graphically!
This is why adjacent rows or columns must have just one bit modified.
Another example will show better how helpful this can be:
In this case we have two groups of boolean expressions.
On one hand we have the same expression of the previous map:
X * Y * /Z
But we have also another expression represented by the larger grouping.
Here, no mater what values Y and Z assume (all combinations between them change), the output result is the same and the same occurs with X.
So this grouping would result in just:
W
But how could we join both expressions?
Well, for the output be true (1), there one or the other of these expressions must occur.
So the resulting expression is:
Res = X * Y * /Z + W
Veitch-Karnaugh map always generate sum of products expressions.
You can try to do this just by seeing the truth table or the logical requirements for it, but believe me, it would be much harder and error prone.
Grouping can occur around the edges of the map, like this:
Here there are only two groupings (grouping A and grouping B), both spanning through one edge to the other.
This also is possible because the adjacent cells change only one bit.
The resulting expression would be:
Res = X/ * Z + W/ * Z/
Returning to our journey
Well, now that you already knows how to use a Veitch-Karnaugh map, let’s return to our main example.
We have three tables from which we have to extract boolean expressions.
The first of them is this:
Remember I’ve told you we can exchange those Xs for the value that is more convenient for us?
Well, now is the moment for this:
Remember, we once we choose a set of values for the Xs we must stick with them for the same output result (Bas, in this case).
Now let’s minimize it.
As we cannot choose an odd number of columns or lines to group output values, our best bet is to have these three groupings.
That would result in:
Bas = B + A + C
what means:
“Every user that have purchased a Basic plan or have purchased an Advanced plan or has a partner coupon can access the basic functionality.”
Note that with this we’re saying that even if the user don’t have purchased a plan, but have a partner coupon they can access basic functionality (what’s in accord with the second rule stated by product people).
The other output results would be:
Adv = A + (B * T)
Prm = A * C + A * T
that we can minimize further with simple boolean algebra (distributivity):
Prm = A * (C + T)
Changes happens (all the time)
What if the PMs change their mind and resolve to change one of the rules?
For example the last rule could be changed from:
“If a user with Advanced plan has a partner coupon they can access premium content even if they aren’t within “trial period”.”
to:
“All paying users with a partner coupon they can access premium content even if they aren’t within “trial period”.”
As the rule affects only the output related to premium content, only the last table was to be modified.
This would lead to:
Prm = A * C + A * T + B * T
Prm = A * (C + T) + B * T
You wouldn’t need to reason about all the logic again (in this simple example it don’t seems much) and risk to commit a mistake.
You can do this with confidence in getting the correct result for the change and not spoiling the other results achieved before.
Putting it all together
Now, with the output expressions on hand, we can implement this in code:
While it might seem like an obvious implementation just by looking at the business rules, there are many small details here that could be overlooked.
Furthermore, by implementing it with pure boolean expressions and using the decorator property in Python, we make the code more declarative and thus less coupled.
Conclusion
By using Veitch-Karnaugh maps we can deal with very complex logic with low risk, repeatability and excellent maintainability.
The technique presented here has many advantages with respect to the traditional ways to deal with logic in software development leading to:
If you think this can have limited use or that you wouldn’t need it on practical applications, let me tell you that I used this technique on a web application, with six input conditions and four output results, to deliver very complex presentation information (buttons that must or not be visible, signaling the need to present a blocking modal, to change of content on the page, to change of behavior of buttons) for the front end.