Exercises: Simplification using Karnaugh maps

Explain how a two-variable Karnaugh map is constructed: how many cells it has, what each cell represents, and why the columns and rows are labelled following Gray code ($00$, $01$, $11$, $10$) instead of the usual binary order.

State the rules for forming groups in a Karnaugh map: which group sizes are valid, what it means for cells to be adjacent (including the edges), and how the simplified term for each group is obtained.

The Karnaugh map in the figure corresponds to a function of three variables $f(a, b, c)$. Indicate the groupings you would make (draw them or describe them by their cells) and obtain the resulting minimal function.

Build the two-variable Karnaugh map for $A$ and $B$ for the function $F = A \cdot B$ (AND function) and answer:

1. a) How many cells does the map have?

1. b) In which cell does the only $1$ go? State the values of $A$ and $B$ for that cell.

1. c) Try to group the ones on the map into groups of 1, 2 or 4 adjacent cells: what do you notice? Can the canonical expression of $F$ be simplified?

In a two-variable map there are ones in cells $ab = 10$ and $ab = 11$. Describe the grouping and reason which variable is eliminated (the one that changes within the group) and which remains fixed, writing down the simplified term.

Explain why a group of two cells eliminates one variable, one of four cells eliminates two, and one of eight eliminates three. What group size would eliminate all variables in a three-variable function, and what function results then?

A rectangular group in a map covers the cells where $a = 1$, with $b$ and $c$ taking all values. Write the term that represents this group and justify the rule: "the term contains only the variables that do not change within the group, negated if equal to $0$ and unnegated if equal to $1$".

Transfer to a three-variable Karnaugh map (columns $ab$: $00$, $01$, $11$, $10$; rows $c$: $0$, $1$) the minterms $0$, $2$, $5$, and $7$ of a function. Draw the complete map with its ones and zeros in each cell.

You can do it on paper and send a photo with your answer.

The function $f(a,b,c)$ equals $1$ for the combinations $1$, $3$, $5$, and $7$ (in decimal, with $a$ as the most significant bit). Transfer the truth table to a three-variable Karnaugh map, form the largest possible grouping, and obtain the minimal function. Check the result by substituting two combinations.

Simplify the function $f = \overline{a} \cdot \overline{b} \cdot c + \overline{a} \cdot b \cdot c + a \cdot \overline{b} \cdot c + a \cdot b \cdot c$ using a three-variable Karnaugh map, indicating which variable is eliminated in the group formed. Comment on which Boolean property confirms the result ($x \cdot c + \overline{x} \cdot c = c$).

In a four-variable map, explain why the top-left corner cell is adjacent to the top-right corner cell, and form with an example the four-corner grouping: what simplified term does a group with the four corners of a four-variable map produce?

Simplify with a three-variable map the function that equals $1$ at the minterms $1$, $2$, $3$, and $6$ (with $a$ as the most significant bit): draw the map, mark the two required groupings, and write the minimal function as a sum of two products.

You can do it on paper and send a photo with your answer.

In a three-variable map, the ones occupy cells $0$, $1$, $4$, and $5$. Show that there is a unique grouping of four cells, explain why it is valid even though cells $0$ and $4$ do not physically touch on the map (edge adjacency), and obtain the minimal function.

The figure shows a four-variable Karnaugh map $f(a,b,c,d)$ with seven ones. Identify the largest possible grouping, write the minimal function, and verify the result with the combinations $0000$ and $0101$.

The three-variable function $f$ equals $1$ at the minterms $1$, $3$, $4$, $5$, and $7$. Draw the map, find the groupings (one of four and another of two, with overlap), and obtain the minimal function. Explain why a one can belong to two groups at the same time.

You can do it on paper and send a photo with your answer.

Two classmates obtain the functions $f = \overline{a} \cdot c + a \cdot b$ and $f = \overline{a} \cdot c + a \cdot b + b \cdot c$ for the same truth table. Check using a Karnaugh map whether they are equivalent and explain what a redundant (or consensus) term is in this context.

In a 4-bit communication bus ($A, B, C, D$, with $A$ as MSB), a combinational circuit is needed to discriminate certain data words.

1. a) Formally prove using a Karnaugh map that the function $f_1 = \sum m(0, 2, 4, 6, 8, 10, 12, 14)$ reduces to a single literal. Justify the result based on the adjacency property of Karnaugh maps and the weight of the least significant bit in natural binary.
2. b) A technician confuses "even integer" with "even parity" and proposes using that same function $f_1$ to check whether a 4-bit word has even parity (an even number of ones, considering zero as even: minterms $0, 3, 5, 6, 9, 10, 12, 15$). Critically evaluate their proposal: draw the Karnaugh map for even parity, explain why its checkerboard geometric pattern prevents any simplifying grouping, and calculate the percentage error that the technician's circuit would make over the total of 16 possible combinations.

It is desired to design a prime number detector combinational circuit for a 4-bit bus ($A, B, C, D$, with $A$ as MSB). In the range $[0, 15]$, the numbers $\{2, 3, 5, 7, 11, 13\}$ are considered prime ($0$ and $1$ are not prime).

1. a) Obtain the minimum simplified logic function in sum-of-products (SOP) form from its Karnaugh map, justifying the selected loops.
2. b) Obtain the minimum product-of-sums (POS) expression by grouping the zeros on the map. Rigorously compare both implementations (SOP and POS) in terms of the number of logic gates and the total number of inputs (literals). Which one would you choose to minimize silicon area?
3. c) Assume that the designed SOP circuit suffers a physical fault: input line $B$ is permanently shorted to logic high (stuck-at-1). Predict which prime numbers will cease to be detected and which non-prime numbers will erroneously activate the output.

In the control system of an industrial hopper, 3 digital level sensors are monitored ($A, B, C$, with $A$ as MSB). Due to the mechanical design of the installation, there are forbidden states or don't-care conditions ($X$). The discharge gate must be activated ($S = 1$) only for the combination $m_5$ ($101_2$), and remain closed ($S = 0$) for the combinations $\{0, 1, 2, 3\}$. Combinations $\{4, 6, 7\}$ correspond to mechanically impossible states.

1. a) Using a Karnaugh map, derive the minimal function $S_{\text{with } X}$ taking advantage of the don't-cares, and compare it with the function $S_{\text{without } X}$ that would result from preventively setting all don't-cares to '0'. Quantify the savings in literals and logic gates.
2. b) During a maintenance operation, a sensor fails and the system temporarily reaches the unexpected combination $m_6$ ($110_2$). Predict with reasoning the response of the gate in each of the two designs ($S_{\text{with } X}$ and $S_{\text{without } X}$). Justify which of the two options offers greater safety against uncontrolled spills of hazardous material (fail-safe criterion).

A decoder module converts a BCD code ($A, B, C, D$, with $A$ as MSB) to drive the top segment ($a$) of a 7-segment display. The segment must turn on ($a = 1$) for digits $0, 2, 3, 5, 6, 7, 8$, and $9$. The binary combinations from 10 to 15 do not belong to the BCD encoding and are considered don't-care conditions ($X$).

1. a) Using a Karnaugh map, obtain the minimized simplified function in sum of products (SOP). Explicitly state which logic value ($0$ or $1$) each of the six don't-care combinations ($m_{10}$ to $m_{15}$) has adopted in your final design.
2. b) If, due to a synchronization fault on the data line, the invalid binary code $1101_2$ ($13$ in decimal) enters the decoder, predict whether segment $a$ will light up or remain off according to the function you designed.
3. c) In a critical application, it is required that, for any invalid code ($10$ to $15$), all segments must obligatorily remain off to warn the user of a read error. Design the new function for segment $a$ under this strict requirement and calculate the extra cost in number of gates and literals compared to the design with don't-cares.

A telemetry receiver module processes 4-bit frames ($A, B, C, D$, with $A$ as MSB). The validation output $f$ must be asserted ($1$) for the canonical minterms $\{1, 3, 7, 11, 15\}$. The combinations $\{5, 9, 13\}$ have been classified in the protocol as 'theoretical don't-cares' ($X$), since they correspond to maintenance commands that should not appear during regular operating mode.

1. a) Using a Karnaugh map, obtain the minimized function $f_1$ by taking advantage of the don't-cares, and the minimized function $f_0$ by forcing $X = 0$. Compare both in terms of implementation cost (number of gates and literals).
2. b) The cybersecurity team warns that an attacker could inject packets deliberately using the maintenance frames $\{5, 9, 13\}$ to activate the system without authorization. Analyze what will happen with each of those three frames under the $f_1$ implementation and under $f_0$.
3. c) Propose a modification in the synthesis of the function that allows keeping a low gate cost while guaranteeing that none of the reserved frames $\{5, 9, 13\}$ activates output $f$, deriving the resulting function algebraically.

In integrated CMOS fabrication technology, Product of Sums (POS) synthesis using NOR gates may require fewer transistors or less propagation delay than traditional Sum of Products (SOP).

Consider a 3-variable combinational function $f(A, B, C)$ defined by its zero maxterms $M(0, 1, 4, 5)$ (that is, the output equals $0$ only for those combinations).

1. a) Formally prove the analytical derivation of the simplified POS form by grouping zeros in the Karnaugh map and applying Boolean algebra / De Morgan's laws.
2. b) Obtain the minimal SOP form by grouping ones. Compare both architectures (POS vs. SOP) by calculating the exact number of CMOS transistors required for each, knowing that a NOT inverter requires 2 transistors and a basic gate (NAND or NOR) with $n$ inputs requires $2n$ transistors.
3. c) Apply the same comparative analysis (POS vs. SOP) to a 4-variable function $g(A, B, C, D)$ whose zeros are located exclusively at the four corners of the Karnaugh map: $M(0, 2, 8, 10)$. Determine whether either of the two forms offers an advantage in the number of gates or transistors in this case, and justify the result by symmetry.

In the control unit of an industrial automaton, two logic outputs must be generated from 3 input variables ($A, B, C$, with $A$ as MSB).

The main output corresponds to the canonical function $F_1(A, B, C) = \sum m(0, 1, 2, 5, 6, 7)$.

1. a) Using the Karnaugh map, prove that there are no essential prime implicants and obtain the two alternative minimal covers possible for $F_1$, verifying that both have identical cost in terms and literals.
2. b) The second required signal is $F_2(A, B, C) = \sum m(6, 7)$. If both functions must be implemented together in the same circuit sharing intermediate logic gates to minimize total area, rigorously justify which of the two covers of $F_1$ obtained in part (a) should be selected.
3. c) Draw the schematic of the resulting optimal combinational circuit that generates both outputs ($F_1$ and $F_2$) sharing gates, and state how many gates and total inputs are saved compared to implementing both functions separately.

A development team is designing an integrity checker for a 4-bit bus ($A, B, C, D$, with $A$ as MSB) carrying natural BCD codes. Output $V$ must be $1$ if the input combination represents a valid BCD digit ($0$ to $9$) and $0$ if it represents an out-of-range code ($10$ to $15$).

1. a) A novice designer claims: “Since in a BCD system values from 10 to 15 will never occur, we can mark them as don't-cares ($X$) in the Karnaugh map so that the circuit is as simple as possible.” Technically refute this statement: find what function would result from applying their idea and explain the paradox that would completely defeat the purpose of the circuit.
2. b) Design the optimal simplified circuit without don't-cares using the Karnaugh map, both in Sum of Products (SOP) and in Product of Sums (POS). Justify which of the two minimal canonical forms is preferable in terms of gate cost.
3. c) Implement the chosen function using exclusively universal NAND gates with no more than 2 inputs. Describe the circuit connections and determine the total number of NAND gates required.