In the last article, we established how to use Boolean algebra to form Boolean functions that represent our circuits – then we tried to make them! If you watched last week’s video, you might think to yourself, “We have to do all of that EVERY time?!”. If that were the case, I think even the most enthusiastic electronics hobbyist would throw up their wires. Thankfully, the wonderful thing about human beings is that we are all, to some extent, cheap and lazy – which is the root of all innovation.
Gate-level minimization is the task of trying to represent a circuit in a form that is easier to build and cheaper to make. How do we do this? We use K-maps.
The Map Method
We’ll explain this concept using the truth table from the last article:
The first thing we’ll do is make a map out of it so we can see all the areas that are shared by the 1s:
What we did is we placed the possible values for “a” along the columns:
Then we placed the possible values for “b” and “c” along the rows:
Then we placed the values from the truth table into the actual map area. For instance, an input of a = 0, b = 1, and c = 1 has a result of f = 0 in our truth table and therefore would be mapped accordingly:
Three important things to know:
Never change the order of your input variables. If your truth table has the inputs “abc”, then you map them in the k-map as “a\bc” not “a\cb” or “b\ca” because it will mess up your mapping and further calculations.
Always map the side with two input variables as “00,01,11,10” which may seem confusing because in binary, that means we’re saying “0,1,3,2” instead of “0,1,2,3” which would be “00,01,10,11”. The reason for this is that this sequence isn’t your average binary sequence. This is a gray code sequence where only one bit in the code group changes in going from one number to the next. All that means is that in this system, 3 comes before 2, and 7 comes before 6.
Another interesting feature about K-maps is that they wrap around themselves. You’ll see what I mean in the next few steps.
So now we have our 3-variable k-map. FYI, we never go beyond 4 variables when using the k-map method because it gets too complicated. That’s why we have computers to deal with gate level minimization problems for us. But it is important to know how to do it yourself if you ever want to make a computer do it for you in the future.
The next step is to find the areas where the 1s in the kmap are next to each other in groupings of 2^n:
You will notice that the pink group and the yellow group share a 1 that is in position 110 (minterm 6). That is fine because you can overlap 1s as long as you’re introducing a new 1 in your grouping each time, otherwise, it becomes redundant.
Now we can prepare a sum of products form of the equation:
F1: A’B’C’ + AB’C’
Simplified F1: (A’+A)(B’C) = B’C’
F2: A’BC’ + ABC’
Simplified F1: (A+A’)(BC’) = BC’
F3: ABC + ABC’
Simplified F3: (C+C’)(AB) = AB
The solution: F = B’C’ + BC’ + AB
Now, while this gives a simpler form of the equation, we can go further. Consider the K-Map to be something that wraps around itself from left to right and up and down. This means that if there is a 1 in every corner, that can be its own grouping.
When we have a 3-variable k-map, the largest possible grouping is 8 minterms, which gives us a function equal to 1. Then, the second largest grouping is 4 minterms, simplifying to a grouping of one variable. Then two minterms produce a term with 2 variables and 1 minterm produces a term with 3 variables. The groupings must be of the form 2 to the power of something with the max of that something being the number of variables introduced in the k-map.
With that being said, it is necessary to always find the largest groupings in a K-map to find the simplest boolean function.
Therefore, we will try this again:
Now, let’s simplify using the K-map the correct way, which is to group as many 1s together as possible.
F1: A’B’C’ + AB’C’ + A’BC’ + ABC’
Simplified F1: C’ (Please reach out if you’d like steps on how we got here)
F2: ABC + ABC’
Simplified F2: (C+C’)(AB) = AB
The solution: F = AB + C’
As you can see, when we find the largest areas with connecting minterms (product of variables resulting in 1), we can find the simplest Boolean expression for a given truth table.
Now, let’s build the circuit for this function:
Now that we have the simplest function mapped out in a circuit diagram, we can get to building it in real life!
Comments