Digital Design · Karnaugh Maps and Wrapped Groups

#06 Map a four-variable truth table in Gray order and reduce an eight-cell wrapped group to the complement of B

Use Gray-code adjacency, valid rectangular groups and edge wrapping to simplify a four-variable function to one literal.

Question

Whole existing English final frame showing the four-variable Karnaugh map, Gray-code labels, edge adjacency or the worked eight-cell group and its B-prime result. — Rows use AB and columns use CD, both in Gray order 00,01,11,10. In the worked example, the top and bottom rows contain all eight ones and form one wrapped group. Only B remains zero, so the result is its complement.

Use a fully specified four-variable Boolean function with independent binary inputs A,B,C,D. Rows use AB and columns use CD, both in the cyclic Gray order 00,01,11,10. The decimal minterm index is 8A+4B+2C+D using ordinary integer arithmetic for the address. Every cell corresponds to one input assignment/minterm; the value written in the cell is the function output at that assignment. A zero-valued cell is still associated with a minterm. The initial all-zero illustrations explain addresses and layout, not the later worked function. In Boolean expressions, plus means inclusive OR, a dot means AND and a prime means complement, not differentiation. Horizontal or vertical neighbors, including opposite edges, differ in exactly one bit. Diagonals are not adjacent. The ordinary binary labels 01 and 10 differ in two bits. For example A·X+A'·X=(A+A')·X=X: a variable may be removed when both of its values occur with the same remaining conditions. For SOP with no unspecified input cases, each group contains only one-cells and is a rectangle on the wrapped map with side lengths 1,2 or4. Its size is 2^k for integer k from0 through4, and its product term contains4-k constant literals. An isolated one is a group of one; an all-one map forms a group of sixteen and represents constant1. All required one-cells must be covered; groups may overlap. A set merely having power-of-two size is insufficient if it is not a valid rectangle/Boolean subcube. The two marked edge cells in the adjacency illustration are minterms0 and2; they differ in C alone and give A'·B'·D'. The curved marks indicate edge adjacency, not inclusion of intervening zero-cells. For the worked example F is one exactly at indices0,1,2,3,8,9,10,11 and zero elsewhere. Top row AB=00 contains indices0,1,3,2 in the displayed column order. Bottom row AB=10 contains8,9,11,10. These rows are adjacent across the top/bottom boundary and form a single2-by4 wrapped group of eight. Their separate row terms are A'·B' and A·B'; their OR is B'. A changes and C,D cover all four combinations; B alone remains0. Verify all sixteen assignments. Since the function is nonconstant, a zero-literal constant cannot represent it, while one complemented literal does: this particular result is minimal in literal count. In general, prefer maximal valid groups, then select a cover of all required ones. A largest-group-first heuristic alone does not prove a globally minimum number of terms or literals for every function; essential groups and alternative covers may need comparison. Do not treat a source suggestion to make large groups as a universal greedy optimality theorem. Do not include zero-cells or invent don't-care inputs to enlarge groups. Logical simplification preserves the steady Boolean function; it does not establish a particular physical propagation delay or freedom from transient hazards. NAND-only or NOR-only universality refers to networks of multiple gates with suitable wiring, not one isolated gate. Keep these qualifications within the lesson's mathematical scope.

Written solution and narration transcript(shows the full solution)

Below are all the lines written in the notebook together with the full narration transcript.

1. Rearrange truth-table rows into a map
Rows use AB and columns use CD, both in Gray order 00,01,11,10. In the worked example, the top and bottom rows contain all eight ones and form one wrapped group. Only B remains zero, so the result is its complement.
A Karnaugh map represents the same function as its truth table.
Rearrange input assignments so one-bit neighbors become adjacent.
Four-variable cell count:
$\displaystyle N = 2^{4} = 16$
Binary row index:
$\displaystyle m = 8\cdot A+4\cdot B+2\cdot C+D$
The layout changes while the Boolean function stays the same.
Use adjacency to see which product terms can combine.
Narration transcript
A Karnaugh map is still a truth table. It simply rearranges the rows into a grid, so useful neighbors sit next to each other. Each cell stands for one exact minterm: one input combination, and one possible output value. For four variables, the row labels use A and B, and the column labels use C and D. The map is not a new Boolean rule. It is a better geometry for seeing which terms can merge.
2. Use Gray-code adjacency
Rows use AB and columns use CD, both in Gray order 00,01,11,10. In the worked example, the top and bottom rows contain all eight ones and form one wrapped group. Only B remains zero, so the result is its complement.
Gray-code ordering preserves the intended adjacency.
Use the cyclic label order zero-zero, zero-one, one-one, one-zero.
Consecutive labels, including the last and first, differ in one bit.
A horizontal or vertical move changes one input bit; a diagonal move does not qualify.
Ordinary binary neighbors zero-one and one-zero differ in two bits.
Keep Gray-code order on both axes of this four-variable map.
Boolean elimination:
$\displaystyle Y = A\cdot X+A'\cdot X = X$
Narration transcript
The order along each edge is the important trick. We write zero zero, zero one, one one, one zero. That is Gray-code order. Moving one cell left, right, up, or down changes exactly one input bit. Ordinary binary counting would put zero one next to one zero, even though both bits change. Gray order avoids that mistake. When two one-cells differ in only one variable, that changing variable can disappear from the simplified term.
3. Build valid rectangular groups
Rows use AB and columns use CD, both in Gray order 00,01,11,10. In the worked example, the top and bottom rows contain all eight ones and form one wrapped group. Only B remains zero, so the result is its complement.
For SOP, form groups of cells whose output is one.
Allowed group size:
$\displaystyle G = 2^{k}$
Retained literals in a four-variable group:
$\displaystyle L = 4-k$
Groups may overlap when this helps cover all required one-cells.
Treat the map as wrapping across opposite edges.
The first and last columns are neighbors, as are the first and last rows.
Narration transcript
For a sum-of-products map, circle the cells whose output is one. Each group must contain a power of two cells: one, two, four, eight, or sixteen. The group must be rectangular on the map, and it should be as large as the available ones allow. A cell may belong to more than one group when that creates a larger or cleaner answer. One rule often feels surprising: the map wraps around. The first and last columns are neighbors, and the first and last rows are neighbors too.
4. Wrap eight cells across an edge
Rows use AB and columns use CD, both in Gray order 00,01,11,10. In the worked example, the top and bottom rows contain all eight ones and form one wrapped group. Only B remains zero, so the result is its complement.
Simplify the complete four-variable example.
The one-minterms are zero, one, two, three, eight, nine, ten and eleven.
Place exactly those eight ones in the sixteen-cell map; every other cell is zero.
Two filled row terms:
$\displaystyle F = A'\cdot B'+A\cdot B'$
The top and bottom rows are adjacent across the map boundary.
Join both rows into one wrapped group of eight cells.
Narration transcript
Let us simplify a complete example. Suppose the function is one for minterms zero, one, two, three, eight, nine, ten, and eleven. Place those eight ones into the four-variable map. They fill the top row, where A B is zero zero, and the bottom row, where A B is one zero. Those rows look separate on paper, but the K-map joins them across the top and bottom edge. Together they form one wrapped group of eight cells.
5. Read the constant literal
Rows use AB and columns use CD, both in Gray order 00,01,11,10. In the worked example, the top and bottom rows contain all eight ones and form one wrapped group. Only B remains zero, so the result is its complement.
Read variables that remain constant across the entire group.
A takes both values within the group and therefore drops out.
C and D take all their combinations and also drop out.
Constant input:
$\displaystyle B = 0$
Simplified function:
$\displaystyle F = B'$
Eight canonical minterms reduce to one complemented literal.
Narration transcript
Now read the group, not the individual cells. Across all eight cells, A changes from zero to one, so A disappears. C and D also take every possible value, so they disappear as well. Only B stays fixed, and it stays zero. A zero variable is complemented, so the entire eight-cell group becomes B prime. That is the payoff: eight canonical minterms have collapsed into one literal.
6. Review the map simplification method
Rows use AB and columns use CD, both in Gray order 00,01,11,10. In the worked example, the top and bottom rows contain all eight ones and form one wrapped group. Only B remains zero, so the result is its complement.
Apply the map method to a fully specified Boolean function.
Place the truth-table ones at their Gray-code addresses.
Find large valid rectangular groups, including groups that wrap across edges.
For each group, retain only its constant variables and OR the resulting product terms.
Verify the resulting expression against the complete truth table.
Next, implement functions with networks drawn from the NAND or NOR gate family.
Narration transcript
Here is the K-map workflow. Put the truth-table ones into Gray-code order. Make the largest power-of-two groups you can, including across an edge when the map wraps. Then keep only the variables that remain constant in each group. Karnaugh maps turn Boolean simplification into a visual checkable process. Next, we will use NAND and NOR gates to build any Boolean function from universal building blocks.