Combinational Optimization, K-Maps & Arithmetic Circuits

1. Canonical Boolean Representations

Every Boolean switching function of $n$ variables $F(x_1, x_2, \dots, x_n)$ can be expressed uniquely in two complementary canonical forms:

1. Minterms ($m_i$) and Canonical Sum-of-Products (SOP): A minterm is a product (AND) of all $n$ variables, with each variable appearing exactly once in either its uncomplemented or complemented form. An $n$-variable function possesses $2^n$ distinct minterms ($m_0$ through $m_{2^n-1}$). Minterm $m_i$ evaluates to 1 for exactly one input combination whose binary representation equals index $i$. Any function is uniquely defined as the logical sum (OR) of its 1-generating minterms:
   $$F(A, B, C) = \sum m(1, 4, 6, 7) = \bar{A}\bar{B}C + A\bar{B}\bar{C} + AB\bar{C} + ABC$$
2. Maxterms ($M_i$) and Canonical Product-of-Sums (POS): A maxterm is a sum (OR) of all $n$ variables. Maxterm $M_i$ evaluates to 0 for exactly one input combination whose binary representation equals index $i$. By De Morgan's theorem, each maxterm is the exact complement of the corresponding minterm:
   $$M_i = \overline{m_i}$$
   Any function is uniquely defined as the logical product (AND) of its 0-generating maxterms:
   $$F(A, B, C) = \prod M(0, 2, 3, 5) = (A + B + C)(A + \bar{B} + C)(A + \bar{B} + \bar{C})(\bar{A} + B + \bar{C})$$

2. Conversion Between Canonical SOP and POS

Because the indices that do not belong to the minterm list $\sum m$ must generate 0s, they form the maxterm list $\prod M$:

Furthermore, the complement function $\bar{F}$ is simply the sum of all missing minterms:

1. Geometric Adjacency & Gray Code Ordering in K-Maps

Maurice Karnaugh (1953) organized truth tables into a planar graphical grid termed the Karnaugh Map (K-map). The rows and columns are arranged in reflected Gray code sequence ($00, 01, 11, 10$):

• Adjacent cells horizontally and vertically differ in exactly one literal.
• The edges wrap around cyclically (toroidal topology): the leftmost column is geometrically adjacent to the rightmost column, and the top row is adjacent to the bottom row.
• Four-corner cells ($m_0, m_2, m_8, m_{10}$ in a 4-variable map) are mutually adjacent and form a valid group of four.

2. Grouping Rules and Prime Implicant Extraction

By applying the Boolean absorption identity $x y + x \bar{y} = x (y + \bar{y}) = x$, grouping adjacent cells containing 1s eliminates the differing literals:

• A group of $2^1 = 2$ adjacent cells (pair) eliminates 1 literal.
• A group of $2^2 = 4$ adjacent cells (quad) eliminates 2 literals.
• A group of $2^3 = 8$ adjacent cells (octet) eliminates 3 literals.
• A group of $2^k$ adjacent cells eliminates $k$ literals.

Fundamental K-Map Optimization Axioms:

1. Groups must be rectangular and contain a power-of-two number of cells ($1, 2, 4, 8, 16$).
2. Every 1 must be covered by at least one group.
3. Groups should be made as large as possible to maximize literal elimination.
4. The total number of groups must be minimized to minimize gate count.
5. A Prime Implicant (PI) is a group that cannot be combined with any other cells to form a larger group.
6. An Essential Prime Implicant (EPI) is a prime implicant that covers at least one '1' that is not covered by any other prime implicant. All EPIs must be included in the minimal sum.

3. Incompletely Specified Functions: Don't Care States ($\times$)

In many digital circuits (e.g., BCD decoders), certain input combinations never occur physically (e.g., binary values $10 - 15$ in 4-bit BCD). The output for these combinations is immaterial and designated as a Don't Care ($\times$ or $d$).

In K-map reduction, a Don't Care condition $\times$ may be treated as 1 if doing so allows a group to expand to a larger power-of-two size (eliminating more literals), or as 0 if it does not help enlarge any group. Don't Care cells are never grouped alone.

1. Limitations of K-Maps and the Need for Algorithmic Reduction

While Karnaugh maps are intuitive for 2, 3, and 4 variables, 5-variable maps require dual overlay planes, and 6-variable maps require 4 sub-cubes, becoming visually error-prone. For functions of $n \ge 6$ variables, algorithmic computer-aided design (CAD) relies on the Quine-McCluskey (Q-M) Tabulation Method.

2. Step-by-Step Quine-McCluskey Algorithm

1. Group by Hamming Weight: Express all minterms and don't cares in binary and partition them into groups based on the count of 1s (Hamming weight).
2. Pairwise Comparison: Compare each term in group $k$ with every term in group $k+1$. If two terms differ in exactly one bit position, combine them by replacing that bit with a dash ($-$) and check off ($\checkmark$) both contributing terms:
   $$0101 \ (5) \text{ and } 0111 \ (7) \implies 01-1 \ (5, 7)$$
3. Iterative Expansion: Repeat the comparison process for 2-cell implicants, 4-cell implicants, etc., matching dashes in identical positions, until no further combinations are possible.
4. Prime Implicants: All terms that remain unchecked at the end of the process are the Prime Implicants (PIs).

3. Prime Implicant Selection Chart & Petrick's Method

Construct a matrix where rows correspond to the PIs and columns correspond to the original function minterms (Don't Cares are omitted from columns):

• Place an $\times$ in each column covered by a given PI.
• If a column contains only a single $\times$, the corresponding row is an Essential Prime Implicant (EPI). Check this row and cross off all columns covered by it.
• If uncovered minterms remain (cyclic prime implicant charts), apply Petrick's Method: formulate a product-of-sums Boolean expression $\prod (P_i + P_j + \dots)$ asserting that each column must be covered, and expand algebraically into SOP to identify the minimal literal solution.

1. Mathematical Definition of Radix Complements

To perform binary subtraction using standard adder hardware (eliminating the need for separate borrow-subtractor units), modern ALUs utilize complement arithmetic. In base $r$ with $n$ digits:

1. Diminished Radix Complement ($r-1$'s Complement):
   $$(r - 1)\text{'s Complement of } N = (r^n - 1) - N$$
   In binary ($r=2$), the $1$'s complement is $(2^n - 1) - N$, achieved simply by inverting every individual bit ($0 \to 1, 1 \to 0$). In decimal ($r=10$), the $9$'s complement is obtained by subtracting each digit from 9.
2. Radix Complement ($r$'s Complement):
   $$r\text{'s Complement of } N = r^n - N = [(r^n - 1) - N] + 1 = (r - 1)\text{'s Complement} + 1$$
   In binary, the 2's complement is obtained by inverting all bits and adding 1:
   $$N_{2's} = \bar{N} + 1$$
   Shortcut: Leave all least significant zeros and the first '1' unchanged; invert all remaining bits to the left.

2. Subtraction Using 2's Complement Arithmetic

To compute $M - N$ for $n$-bit unsigned numbers, the ALU evaluates $M + (2^n - N) = M - N + 2^n$:

• Case 1 ($M \ge N$): The sum produces an End Carry of $2^n$ ($C_{\text{out}} = 1$). Discarding the carry yields the correct positive difference $M - N$.
• Case 2 ($M < N$): No end carry occurs ($C_{\text{out}} = 0$). The result is negative and equals the 2's complement of the true magnitude: $-(2^n - \text{Sum})$.

3. Signed Binary Representation & Arithmetic Overflow

In signed $n$-bit 2's complement representation, the Most Significant Bit (MSB) acts as the sign bit ($0 \leftrightarrow +, 1 \leftrightarrow -$):

For an 8-bit byte: $-128 \le X \le +127$. Crucially, 2's complement features a unique zero ($00000000_2$), unlike 1's complement which suffers from $+0$ and $-0$ ambiguities.

Overflow Condition ($V$): When adding two numbers of identical sign, the magnitude may exceed the representable range. Hardware detects overflow via an XOR gate comparing the carry into the sign bit ($C_{n-1}$) with the carry out of the sign bit ($C_n$):

If $V = 1$, an arithmetic overflow exception is signaled.

1. Half-Adder and Full-Adder Logic

The elementary building blocks of binary addition:

1. Half-Adder (HA): Adds two 1-bit inputs $A$ and $B$, producing Sum $S$ and Carry $C$:
   $$S = A \oplus B, \quad C = A B$$
2. Full-Adder (FA): Adds three 1-bit inputs: operands $A, B$ and carry-in $C_{\text{in}}$:
   $$S = A \oplus B \oplus C_{\text{in}}$$
   $$C_{\text{out}} = A B + B C_{\text{in}} + A C_{\text{in}} = A B + C_{\text{in}}(A \oplus B)$$
   A Full-Adder can be synthesized using two Half-Adders and one OR gate.

2. Ripple-Carry Parallel Adder Limitations

An $n$-bit parallel adder cascades $n$ Full-Adders, with $C_{\text{out}, i}$ connected to $C_{\text{in}, i+1}$. While hardware cost is minimal, the critical path requires the carry bit to "ripple" sequentially through all $n$ stages:

For a 64-bit adder with $t_{\text{carry}} = 1\text{ ns}$, the total propagation delay is $64\text{ ns}$, severely throttling CPU clock frequencies.

3. Carry-Lookahead Adder (CLA) Acceleration

To eliminate serial carry propagation, the Carry-Lookahead Adder generates all carry bits simultaneously in parallel using two auxiliary functions:

• Carry Generate ($G_i$): $G_i = A_i B_i$ (a carry is generated inside stage $i$ regardless of carry-in).
• Carry Propagate ($P_i$): $P_i = A_i \oplus B_i$ (a carry-in to stage $i$ is propagated forward to stage $i+1$).

Expressing stage carries recursively:

Each carry depends strictly on the input operands and initial carry $C_0$, bypassing intermediate stages. All carries are computed simultaneously within a constant two-gate delay, irrespective of word length.

1. BCD Decimal Adder Architecture

In a Binary Coded Decimal (BCD) adder, two 4-bit BCD digits ($A, B \in [0, 9]$) and carry-in $C_{\text{in}}$ are summed using a standard 4-bit binary adder. If the binary sum $K \le 9$, the result is a valid BCD digit. However, if the sum exceeds 9 ($10 \le K \le 19$), the 4-bit binary adder produces an invalid BCD codeword ($1010_2$ to $1111_2$) or an unrecorded carry:

• Correction Condition: An invalid decimal state is flagged if:
  $$\text{Correction Carry } C_{\text{out}} = K_4 + S_3 S_2 + S_3 S_1$$
  where $K_4$ is the binary carry-out, $S_3 S_2$ flags 12 and 13, and $S_3 S_1$ flags 10 and 11.
• Correction Circuit: Whenever $C_{\text{out}} = 1$, the hardware adds $6_{10} = 0110_2$ to the sum via a second 4-bit binary adder. Adding 6 skips the 6 invalid 4-bit states, correctly producing the lower BCD digit and propagating the decimal carry $C_{\text{out}} = 1$ to the next decade.

2. Controlled Adder/Subtractor Circuit

A single hardware unit performs both binary addition and subtraction by routing operand $B$ through conditional XOR inverters controlled by mode bit $M$:

• When $M = 0$: $B_i^* = B_i$ and $C_{\text{in}} = 0 \implies$ Evaluates $A + B$ (Addition).
• When $M = 1$: $B_i^* = \bar{B}_i$ and $C_{\text{in}} = 1 \implies$ Evaluates $A + \bar{B} + 1 = A - B$ (2's complement Subtraction).

3. Binary Array Multipliers

Multiplication of two unsigned binary numbers ($A = a_{m-1}\dots a_0$ and $B = b_{n-1}\dots b_0$) is synthesized as the accumulation of $m \times n$ partial products $P_{i,j} = a_i \cdot b_j$ generated by 2-input AND gates. In an $m \times n$ array multiplier, partial product rows are shifted and summed using a 2D matrix of full adders, yielding product bits with delay scaling linearly with word length.