Simplification with 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.

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.

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?

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.

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$".

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.

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 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.

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.

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.

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 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.