Electronics Guide

Basic Definitions

A Boolean algebra is defined over a set B containing at least two distinct elements, conventionally labeled 0 and 1. Three basic operations are defined:

• AND (conjunction): Represented as A AND B, A * B, or simply AB. Returns 1 only when both operands are 1.
• OR (disjunction): Represented as A OR B or A + B. Returns 1 when at least one operand is 1.
• NOT (complement): Represented as NOT A, A', or A with an overbar. Returns the opposite value of the operand.

Huntington Postulates

The Huntington postulates provide a minimal set of axioms that formally define Boolean algebra:

• Closure: For any A and B in B, both A + B and A * B are also in B.
• Identity elements: There exist elements 0 and 1 such that A + 0 = A and A * 1 = A for all A.
• Commutativity: A + B = B + A and A * B = B * A.
• Distributivity: A * (B + C) = (A * B) + (A * C) and A + (B * C) = (A + B) * (A + C).
• Complement: For every element A, there exists an element A' such that A + A' = 1 and A * A' = 0.
• Distinct elements: There exist at least two elements A and B in B such that A is not equal to B.

Basic Theorems

The following theorems apply to single variables:

• Idempotent Law: A + A = A and A * A = A
• Null Elements: A + 1 = 1 and A * 0 = 0
• Involution: (A')' = A (double complementation returns the original value)
• Complement of Constants: 0' = 1 and 1' = 0

Absorption Theorems

Absorption theorems allow terms to be eliminated when they are "absorbed" by other terms:

• Absorption: A + (A * B) = A and A * (A + B) = A
• Absorption (variant): A + (A' * B) = A + B and A * (A' + B) = A * B

These theorems are particularly useful because they reduce the number of terms and literals in an expression without altering its logical function.

Consensus Theorem

The consensus theorem identifies redundant terms that can be eliminated:

• Consensus: (A * B) + (A' * C) + (B * C) = (A * B) + (A' * C)
• Dual form: (A + B) * (A' + C) * (B + C) = (A + B) * (A' + C)

The term (B * C) or (B + C) is called the consensus term, and its redundancy can be demonstrated by considering all possible values of A.

Associativity

Although not explicitly stated in Huntington's postulates, associativity can be proven:

• (A + B) + C = A + (B + C)
• (A * B) * C = A * (B * C)

This property allows terms to be grouped in any order, simplifying the analysis of expressions with multiple variables.

Statement of De Morgan's Laws

De Morgan's laws state that:

• First Law: (A + B)' = A' * B' (the complement of a sum equals the product of the complements)
• Second Law: (A * B)' = A' + B' (the complement of a product equals the sum of the complements)

Generalized Form

De Morgan's laws extend to any number of variables:

• (A + B + C + ... + N)' = A' * B' * C' * ... * N'
• (A * B * C * ... * N)' = A' + B' + C' + ... + N'

Practical Applications

De Morgan's laws are essential for:

• Gate conversion: Converting between NAND/NOR implementations and AND/OR implementations
• Expression simplification: Transforming expressions to use fewer types of gates
• Universal gate design: NAND and NOR gates are universal because any logic function can be implemented using only one type, facilitated by De Morgan's laws
• Bubble pushing: A visualization technique for tracing signal inversions through logic circuits

Minterms and Maxterms

Canonical forms are based on two fundamental building blocks:

• Minterm: A product term containing each variable exactly once, either complemented or uncomplemented. For n variables, there are 2^n possible minterms. Each minterm equals 1 for exactly one combination of input values.
• Maxterm: A sum term containing each variable exactly once, either complemented or uncomplemented. Each maxterm equals 0 for exactly one combination of input values.

Minterms are typically denoted as m followed by a decimal index (e.g., m3 for the minterm ABC' when n=3), while maxterms use M with the same indexing scheme.

Sum of Products (SOP) Form

The Sum of Products canonical form, also called the disjunctive normal form (DNF), expresses a function as an OR of minterms:

F(A, B, C) = sum of minterms for which F = 1

For example, a function that is true when the input binary value is 1, 3, 5, or 7 would be written as:

F = m1 + m3 + m5 + m7 = A'B'C + A'BC + AB'C + ABC

This is commonly abbreviated using sigma notation as F = sum(1, 3, 5, 7).

Product of Sums (POS) Form

The Product of Sums canonical form, also called the conjunctive normal form (CNF), expresses a function as an AND of maxterms:

F(A, B, C) = product of maxterms for which F = 0

Using the same function as above, the POS form would be:

F = M0 * M2 * M4 * M6 = (A + B + C)(A + B' + C)(A' + B + C)(A' + B' + C)

This is commonly abbreviated using pi notation as F = product(0, 2, 4, 6).

Conversion Between Forms

Converting between SOP and POS forms is straightforward: the minterms of a function are the complementary indices to its maxterms. If F = sum(1, 3, 5, 7), then F = product(0, 2, 4, 6).

Similarly, the complement of a function can be expressed by using the opposite set of terms: if F = sum(1, 3, 5, 7), then F' = sum(0, 2, 4, 6).

Prime Implicants

A prime implicant is a product term that:

• Implies the function (whenever the term is 1, the function is 1)
• Cannot be combined with another implicant to form a simpler term while still implying the function

Finding all prime implicants is the first step in systematic minimization methods.

Essential Prime Implicants

An essential prime implicant is a prime implicant that covers at least one minterm not covered by any other prime implicant. Essential prime implicants must appear in any minimal expression.

Cost Functions

Different cost metrics are used depending on the implementation technology:

• Literal count: Total number of variable appearances (complemented and uncomplemented)
• Gate count: Number of logic gates required
• Gate inputs: Total number of inputs across all gates
• Levels of logic: Maximum number of gates on any path from input to output

K-Map Structure

A Karnaugh map is organized so that physically adjacent cells (including wrap-around at edges) represent logically adjacent minterms:

• 2-variable K-map: 2x2 grid with 4 cells
• 3-variable K-map: 2x4 grid with 8 cells
• 4-variable K-map: 4x4 grid with 16 cells
• 5-variable K-map: Two 4x4 grids representing 32 cells
• 6-variable K-map: Four 4x4 grids representing 64 cells

The row and column labels follow Gray code ordering (00, 01, 11, 10) to ensure that adjacent cells differ by only one variable.

Grouping Rules

The minimization process involves grouping adjacent 1s (for SOP) or 0s (for POS):

• Groups must be rectangular and contain a power of 2 cells (1, 2, 4, 8, 16, etc.)
• Each 1 must be covered by at least one group
• Groups may overlap
• Groups may wrap around edges (the map is topologically a torus)
• Larger groups yield simpler terms (a group of 2^k cells eliminates k variables)

Don't Care Conditions

Don't care conditions, denoted by X or d, represent input combinations that either cannot occur or whose output does not matter. Don't cares can be included in groups if doing so produces larger groups, but they need not be covered. This flexibility often enables significant additional simplification.

Limitations

Karnaugh maps become impractical for functions with more than six variables due to the difficulty of visualizing adjacencies in higher dimensions. For larger problems, algorithmic methods such as the Quine-McCluskey algorithm are preferred.

Algorithm Overview

The Quine-McCluskey method proceeds in two main phases:

1. Find all prime implicants: Systematically combine minterms that differ by exactly one variable
2. Find minimum cover: Select the smallest set of prime implicants that covers all minterms

Phase 1: Finding Prime Implicants

The procedure for finding prime implicants:

1. List all minterms and group them by the number of 1s in their binary representation
2. Compare terms in adjacent groups; if two terms differ by exactly one bit, combine them into a new term with a dash (-) in that position
3. Mark combined terms as "checked"
4. Repeat the comparison process with the newly formed terms
5. Continue until no more combinations are possible
6. All unchecked terms are prime implicants

Phase 2: Prime Implicant Chart

The prime implicant chart (or covering table) is used to find a minimum cover:

1. Create a table with prime implicants as rows and minterms as columns
2. Place an X in each cell where a prime implicant covers a minterm
3. Identify essential prime implicants (those covering minterms with only one X in their column)
4. Include all essential prime implicants in the solution
5. Remove covered minterms from consideration
6. If minterms remain, use row dominance, column dominance, or branching to complete the selection

Handling Don't Cares

Don't care conditions are included in Phase 1 to potentially generate larger prime implicants. However, in Phase 2, columns for don't care minterms are omitted from the covering table since they do not need to be covered.

Shared Prime Implicants

In multiple-output minimization, a product term can be shared if it appears in multiple output functions. The goal is to find a set of product terms that:

• Covers all minterms for all outputs
• Minimizes the total cost including sharing benefits

Multi-Output Prime Implicants

The concept of prime implicants extends to multiple outputs. A multi-output prime implicant is associated with a specific subset of outputs and represents a product term that:

• Implies all outputs in its associated subset
• Cannot be expanded (combined with another term) while maintaining this property

Optimization Strategies

Approaches to multiple-output minimization include:

• Extended Quine-McCluskey: Modified algorithm that considers all combinations of output subsets
• Iterative improvement: Start with independent solutions and look for sharing opportunities
• Boolean division: Factor common subexpressions from multiple output functions

Definition

The Boolean difference of function F with respect to variable x is defined as:

dF/dx = F(x=0) XOR F(x=1)

where F(x=0) and F(x=1) are the cofactors of F with respect to x.

Interpretation

The Boolean difference equals 1 for input combinations where changing the value of x causes the output F to change. This makes it useful for:

• Fault detection: Identifying conditions that sensitize a path from an input to the output
• Test generation: Creating test vectors for stuck-at fault testing
• Hazard analysis: Finding input conditions that might cause timing hazards

Properties

Key properties of Boolean difference include:

• d(F')/dx = dF/dx (complementing F does not change the difference)
• d(F + G)/dx = (dF/dx * G') + (dG/dx * F') + (dF/dx * dG/dx)
• d(F * G)/dx = (dF/dx * G) + (dG/dx * F) + (dF/dx * dG/dx)

Positive Polarity Reed-Muller Form

The Positive Polarity Reed-Muller (PPRM) form, also called the algebraic normal form or ring-sum expansion, expresses a function using only AND and XOR operations with uncomplemented variables:

F = a0 XOR (a1 * x1) XOR (a2 * x2) XOR ... XOR (a12 * x1 * x2) XOR ...

where each coefficient ai is either 0 or 1.

Fixed Polarity Reed-Muller Form

Fixed Polarity Reed-Muller (FPRM) forms allow each variable to appear in either complemented or uncomplemented form, but the polarity is fixed for each variable throughout the expression. There are 2^n different FPRM forms for a function of n variables.

Conversion to Reed-Muller Form

Converting a standard Boolean expression to PPRM form can be done by:

1. Replace OR operations using the identity: A + B = A XOR B XOR (A * B)
2. Replace complements using: A' = 1 XOR A
3. Simplify using XOR properties (A XOR A = 0, A XOR 0 = A)

Alternatively, a tabular method can compute coefficients directly from the truth table using the positive Davio decomposition.

Applications

Reed-Muller expansions are particularly useful for:

• Error-correcting codes: RM codes are a well-known class of linear codes
• Reversible logic: XOR-based circuits are naturally reversible
• Quantum computing: Many quantum gates have direct RM circuit counterparts
• Testability: Functions with low polynomial degree in RM form have efficient test sets
• Area optimization: Some functions have more compact RM representations than SOP forms

ESPRESSO Algorithm

ESPRESSO is a heuristic logic minimization algorithm developed at UC Berkeley. Rather than finding all prime implicants, ESPRESSO uses iterative improvement operations:

• Expand: Enlarge each term as much as possible
• Reduce: Shrink terms to potentially enable further expansion of others
• Irredundant: Remove terms that have become redundant

ESPRESSO typically produces near-optimal results much faster than exact methods for large problems.

Binary Decision Diagrams

Binary Decision Diagrams (BDDs), particularly Reduced Ordered Binary Decision Diagrams (ROBDDs), provide a canonical representation for Boolean functions. BDDs enable efficient manipulation and comparison of Boolean functions and form the basis for many modern logic optimization and verification tools.

Technology Mapping

In practice, logic optimization must consider the available technology library. Technology mapping algorithms transform technology-independent logic representations into implementations using specific gates from a target library, considering factors such as:

• Available gate types and sizes
• Timing constraints
• Power consumption
• Physical design constraints

Timing Hazards

Minimum-cost implementations may introduce timing hazards, brief incorrect outputs caused by unequal propagation delays. Static hazards can be eliminated by including consensus terms that ensure no momentary glitches during single-variable transitions.

Fan-in and Fan-out Limitations

Physical gates have limited input (fan-in) and output (fan-out) capabilities. Highly minimized expressions may require gates with large fan-in, necessitating decomposition into multiple levels of logic.

Testability Considerations

Minimum-gate implementations are not always the most testable. Design for testability may require adding redundant logic to improve fault coverage or controllability and observability.

Power Optimization

In modern designs, power consumption is often as important as area. Minimization strategies may need to consider switching activity, glitch reduction, and power-aware technology mapping.