Grouping
The map is full. Now comes the fun part: grouping. The idea is to enclose the ones that sit together in groups, and each group becomes a term of the simplified function.
And why does grouping work?
Because of the Gray code. Two neighbouring cells differ in a single variable, so when you add them that
variable cancels out. For example, cells 5 (0101) and 7 (0111) differ only in
C:
That is exactly what a group does: the variables that change inside the group drop out, and the ones that stay the same remain, plain if they are 1 and complemented if they are 0. With that in mind the rules follow on their own. In the examples, the small number in each cell is its index in the truth table.
# The rules
# 1. Only ones are grouped
In a sum of products (SoP) each group marks cells where the function is 1. If a group swallows a 0, its term would also be 1 in that cell and it would no longer be the same function. (Further down we will see that it can also be done the other way round, grouping zeros.)
Cell 15 is 0: this group would say the function is 1 there.
Two pairs that only touch ones.
# 2. Groups of 1, 2, 4, 8 or 16 cells
The size of a group is always a power of 2, because each variable that cancels out doubles the cells it covers: a group of 2k cells removes exactly k variables. With 4 variables, a single cell keeps all 4, a pair keeps 3, a group of 4 keeps 2, one of 8 keeps 1, and if all 16 cells are ones, f = 1.
2 cells: one variable goes (C).
4 cells: two go (C and D).
8 cells: only B is left.
# 3. Rectangles only
A line or a block, nothing else. In an L, a diagonal or a staircase there is no set of variables that changes while all the others stay fixed, so no single term comes out.
And careful: being a rectangle is not enough, rule 2 must hold too. Each side is 1, 2 or 4 cells long, so the group has 2n elements: 1, 2, 4, 8 or 16. A rectangle of 3, 5, 6 or 7 cells is not valid, like the 2 × 3 one in the last example.
A 2 × 2 block.
A whole row.
Two rows: a 2 × 4 block.
A 2 × 3 rectangle: 6 cells is not a power of 2. The right way is two 2 × 2 blocks.
# 4. Edges and corners count
Remember the torus? The left column is a neighbour of the right one and the top row is a neighbour of the bottom one, so a group can leave through one side and come back in through the other. And the four corners make a group of 4.
From left to right.
From top to bottom.
The four corners.
# 5. As large as possible
Two pairs can be correct and still not be minimal. The larger the group, the more variables cancel out and the shorter the term.
Two pairs: two terms of 3 variables.
A group of 4: one term of 2 variables.
# 6. Groups may overlap
A cell can be in several groups. If reusing a 1 that is already grouped lets you make a larger group, use it: in a sum, repeating a term changes nothing (A + A = A).
Without overlapping, 13 and 15 end up in a pair.
Reusing 5 and 7 gives a group of 4.
# 7. Every one covered, no spare groups
Every 1 has to be in at least one group, even on its own. But if all the cells of a group are already covered by other groups, that group is spare: it adds a term without covering anything new.
The group of 5 and 13 is spare: both are already covered.
Two groups are enough.
# 8. Don't-care cells are wildcards
A - (don't care) is a combination of inputs that will never happen or whose output
does not matter to you. You can treat it as a 1 if it helps you make a larger group, or as a 0 if it does
not. What you never need to do is cover it.
Without using the -: two pairs.
Taking the - as a 1: a group of 4.
# 9. Mandatory groups first
An order that helps a lot: look for the ones that can only be grouped in one way and make those groups first, because they are mandatory (textbooks call them essential prime implicants). Then cover what is left with as few groups as possible. Careful, starting with the largest group is not always best: in this example the central block is large, but it is spare, because the four mandatory groups already cover all its cells.
And sometimes there is more than one minimal solution: different groupings with the same number of terms and variables. They are all correct; the solver shows them to you when there are several.
Starting with the large block: the four pairs are still needed afterwards, and the block is spare.
Cells 1, 6, 12 and 11 have only one possible pair each: those four groups are enough.
# Typical mistakes
Almost every mistake comes from forgetting one of the rules. These are the most common:
A group of 3: not a power of 2. The right way is two pairs sharing cell 5.
Diagonal: 0 (0000) and 5 (0101) differ in two variables, they are not neighbours.
An L: it is 4 cells, but three variables change among them, not two.
Forgetting the edge: 0 and 8 are neighbours and together make a pair.
A group of only -: it covers no 1, it just adds a term.
# What if I group the zeros?
That works too, and it is called a product of sums (PoS). The rules of shape and size are the same; only the way each group is read changes: the variables that stay the same go in the other way round (plain if they are 0, complemented if they are 1) and are added, and then the groups are multiplied. Sometimes one form is shorter than the other; the solver lets you choose between the two.
Zeros in the corners: the function is 0 only when B and D are 0.
# All together
In the end, the simplified function is the sum of the terms of all the groups. For example, for f = Σm(0, 2, 5, 7, 8, 10, 13, 15) two groups of 4 are enough: the corners and the central block. Eight minterms of 4 variables become two terms of 2.
f is 1 when B and D are equal.
If you want to check it, enter those minterms in the solver and see which groups it draws.