0
The main reason we use Gray code is because adjacent Gray codes only differ by 1 bit. This means that in a Gray encoded truth table, only one input changes between adjacent rows or adjacent columns. More importantly, the rows and columns "wrap around". They are cyclic; the first row immediately follows the last and the first column immediately follows the last, without affecting the 1 input difference between adjacent rows and columns. This cyclic nature means we can imagine a 2-dimensional truth table as a 3-dimensional toroid (like a ring doughnut).
K-maps are all about recognising patterns within complex logic in order to reduce boolean algebra to its simplest form. Gray codes help us achieve that by effectively increasing the number of truth tables whilst maintaining the simplicity of the relationship between adjacent rows and columns. For instance, a 4 input function has just 1 truth table, but it has 16 unique K-maps. The more maps, the easier it is to isolate the logic.
While it is possible to use just one truth table to determine the simplest boolean logic for any given function, the more inputs there are the harder this becomes. However, as the number of inputs increases, the number of K-maps also increases exponentially. But the more K-maps, the easier it is to find one that encapsulates the logic in its simplest form simply by looking for recognisable patterns.
What we want to achieve is a map that can be divided up into rectangular regions such that every region holds at least two truths. If we can adjust the map such that all truths are encapsulated by just one region, so much the better. However, frequently, we need to use several regions. The regions may overlap each other, so long as the truth holds in the overlap.
To understand how it works, let's start with a simple four-input function, f(A,B,C,D) and the following truth-table for that function:
# ABCD = f(ABCD)
0 0000 = 0
1 0001 = 0
2 0010 = 0
3 0011 = 0
4 0100 = 0
5 0101 = 0
6 0110 = 1
7 0111 = 0
8 1000 = 1
9 1001 = 1
A 1010 = 1
B 1011 = 1
C 1100 = 1
D 1101 = 1
E 1110 = 1
F 1111 = 0
The minterms (rows that evaluate 0) are {0, 1, 2, 3, 4, 5, 7, F}
The maxterms (rows that evaluate 1) are {6, 8, 9, A, B, C, D, E}
What we're attempting to do is to create the canonical form of the function such that:
f(A, B, C, D) {
if (is_maxterm (A,B,C,D))
return 1;
else
return 0;
}
In other words, we want the is_maxterm() function to be as simple as possible.
Let's start with the standard truth table laid out in a 4x4 grid with AB input pairs across the columns CD input pairs down the rows:
0000 0100 1000 1100
0001 0101 1001 1101
0010 0110 1010 1110
0011 0111 1011 1111
If we then map this grid to the corresponding outputs of the function, we get the following truth table:
0 0 1 1
0 0 1 1
0 1 1 1
0 0 1 0
We can clearly see that there's just two bits "out of sequence". However, there's no recognisable pattern to the logic. No matter how we divide the group of 1's, we always end up with at least one 1 on its own. That's no use to us because it means all four inputs influence that one truth. We want conditions that use just 1, 2 or 3 inputs only, never all 4 inputs.
Let's re-order those inputs using Gray code sequences instead. Gray codes are binary encodings where each code in the sequence differs by just one bit. Thus instead of the sequence 00, 01, 10, 11, we get 00, 01, 11, 10. We can also reorder the sequence by moving a Gray code from one end of the sequence to the other, thus we get four sequences in all: {00, 01, 11, 10}; {01, 11, 10, 00}; {11, 10, 00, 01} and; {10, 00, 01, 11}. However, let's start with the canonical form:
0000 0100 1100 1000
0001 0101 1101 1001
0011 0111 1111 1011
0010 0110 1110 1010
From that we get the following K-map:
0 0 1 1
0 0 1 1
0 0 0 1
0 1 1 1
That's much better. All the maxterms are grouped together and form three regular groups of two or more truths. That is, the maxterms occupy the 2x2 box in the top right, the 1x2 box in the lower right and the 2x1 box in the middle of row 4. So, as luck would have it, the canonical K-map suits us just fine.
Now that we have a recognisable pattern, we can now work out the maxterms using boolean logic.
In the top right 2x2 box, we can see that the output is 1 when A is 1 and C is 0.
In the lower right 1x2 box, we can see that the output is 1 when A is 1 and B is 0.
In the 2x1 box in the middle of the bottom row, the output is 1 when B and C are both 1 and D is 0.
Note that when A is 1 and B is 0 we also overlap the first condition. However, overlaps are fine. Remember we want to establish the simplest possible logic; excluding overlaps would just overcomplicate the logic unnecessarily.
From this, we can establish our function, f:
f (A, B, C, D) {
if ((A and not C) or (A and not B) or (B and C and not D))
return 1;
else
return 0;
}
Since the if statement is itself a boolean expression, we can simplify even further:
f (A, B, C, D) { return (A and not C) or (A and not B) or (B and C and not D); }
This is obviously a trivial example, but just think how much harder it would be to reduce the logic using just the normal truth table. It can be done, but it is far from trivial.
