Combinational Logic Circuits

Chapter 2: Combinational Logic Circuits

Overview

• Author: Tim Berner, Rutgers University

• Date: 2/14/2026

• Content Structure: The chapter includes various topics essential for understanding combinational logic in computer architecture.

Chapter 2 Topics

• Binary logic and Gates

• Boolean Algebra

• Standard Forms

• Cost Criteria

• Maps Structure and Optimization

• Gate Propagation delay

• HDL Overview

Binary Logic and Gates

Digital Circuits

• Definition: Digital circuits are hardware components that manage binary information.

• Integrated Circuits: Implemented using transistors and semiconductors, these circuits are a fundamental aspect of digital technology.

• Logic Gates: Basic circuits used to perform operations on binary variables.

• Boolean Algebra: A mathematical system used to describe and analyze the operations of logic gates.

Binary Logic

• Deals with binary variables that take 2 discrete values, with mathematical logic applied.

• Values: Either 1 or 0.

• Basic Operations:

  • AND (*): Both values must be 1 for the result to be true.

  • OR (+): At least one of the values must be true.

  • NOT (-): Negates the value (flips 1 to 0 and 0 to 1).

Truth Table

• A truth table provides a set of combinations of binary values that show the relationship between variables and the result of operations.

Logic Gates

• Definition: Electronic circuits that operate on one or more input signals to produce an output signal.

• Transition: A change from 0 to 1.

• Transition Region: The space between changes from 0 to 1.

• Timing Diagram: Illustrates the transitions of input and output signals over time.

  • Horizontal Axis: Time.

  • Vertical Axis: Shows change from 0 to 1.

• Gate Delay: The time taken for an input change to result in a corresponding output change.

• Small Circle: Represents a negation indicator or bubble.

• NAND Gate: Considered a universal gate as it can create any other gate.

Commonly Used Logic Gates

Gate Table

HDL Representation of Gates

• Definition: HDL (Hardware Description Language) is a programming language specifically designed to describe the structure and behavior of electronic circuits.

• Structural Description: Describes the interconnections between components.

• Netlist: Consists of several components: blocks, ports, pins, and nets.

• Advantages: HDL is better suited for larger circuits compared to schematics and truth tables.

Boolean Algebra

• Boolean Expression: An algebraic expression formed by binary variables, the constants (1 and 0), logic symbols, and parentheses.

• Binary Function: A variable followed by a binary expression.

  • Two Types:

  1. Single output

  2. Multiple output

• Truth Table: Lists all possible outcomes for an equation.

• Algebraic Functions: Can be translated into circuit diagrams.

• Combination Logic Gates: Circuit gates interconnected by wires that carry logic signals.

• Expression Simplification: A simpler expression reduces the number of inputs to gates.

Basic Identities of Boolean Algebra

Algebraic Manipulation

• Simplification: Boolean functions can be simplified using algebraic manipulation through a trial and error approach.

• Duality Principle: A Boolean equation remains valid when we take the dual of the expression on both sides of the equal sign.

• Consensus Theorem: Used for eliminating redundant terms in functions.

• Complement of Function: Involves interchanging 1s and 0s.

Standard Forms

• Purpose: Simplifying Boolean expressions.

• Forms:

  • Product Terms: Terms where all variables appear exactly once.

  • Sum Terms: Results in a logical sum that assists in establishing true conditions.

Miniterm

• A miniterm is a product term in which all variables appear exactly once, taking a value of 1 for one combination and 0 for others.

• There are 2^n distinct miniterms for n variables, with values ranging from 000 to 2^n - 1.

Maxterm

• A maxterm is a sum term containing all variables either in complemented or uncomplemented form.

• A sum of miniterms is an expression that can be formulated from a truth table logically summing all miniterms that produce a 1.

• Conversely, the product of maxterms is formulated where the values equal 0.

Properties of Miniterms

• Any Boolean function can be expressed as a logical sum of miniterms.

• The complement of a function contains those miniterms not included in the original function.

• A function incorporating all 2^n miniterms equates to logic 1.

Simplified Sum of Miniterms

• Defined as a reduced format of the sum of miniterms used to cut down on the number of variables involved.

• Represents a logical product of sum terms.

• This can be achieved through summation followed by product operations, which informs the standard form of logic gates.

Two-Level Circuit Optimization

• Challenges: Simplification via algebraic expressions often lacks clear rules.

• Karnaugh Map (K-map): A visual method to simplify expressions up to 4 terms.

• Definition: A K-map is a diagram made of squares representing rows of a truth table, or empty spaces corresponding to miniterms of a single output function.

• Provides a visual structure for possible arrangements that can be written in standard form while optimizing terms represented in sum of products or product of sum forms.

Cost Criteria

• Two key cost criteria to consider:

  • Literal Cost: Determined by counting literals in an equation, which serves as a measure of complexity of logic gates.

  • Gate-Input Cost: Involves counting the number of inputs, analyzed through

  • All literal appearances

  • Number of terms excluding terms consisting of only single literals, optionally counting distinct complemented literals.

• This is a good indicator for contemporary logic implementations, as it correlates with the number of transistors and wires required for construing a logic circuit.

Map Structures

• Number of squares in a map equals the number of miniterms in the function.

• Maps are labeled in two ways:

  • With variables arranged at the top left per column and row, labeled by binary combinations of those variables.

  • Single variable labels at the map edges, applying brackets to either single or double rows and columns to signify their relationships.

• Each location in the map corresponds to a value of 1 based on input/output conditions.

Basic Steps in Using K-maps

1. Entering the Function: Derive from truth table or shorthand notation (Σm) for sum of minterms.

2. Identify Squares: Locate squares on the map that represent desired product terms aiming for a simplified expression.

3. Goal: Achieve the fewest rectangles covering all squares marked as 1, resulting in minimum product terms with the lowest input costs.

4. Default Selection: Choose the largest rectangle over smaller ones when necessary.

Map Manipulation

Goals

• Ensure all miniterms of function are included.

• Minimize redundant terms within optimized functions.

Main Strategies

1. Essential Prime Implicant: A product term that represents a function if that function has a value of 1 for all miniterms of that term.

2. Non-Essential Prime Implicants: Optimize by reducing overlaps among prime implicants.

3. Product of Sum Optimization: Similar to achieving a sum of products but focuses on zeros instead of ones.

4. Don’t Care Conditions: These situations hold that all unspecified miniterms can equal either 1 or 0 under certain combinations.

EXCLUSIVE OR Operator

• Symbol: ⊕

• Mathematical Expression: X igoplus Y = XY' + X'Y

ODD FUNCTIONS

• In a three-variable configuration, XOR yields 1 if either one or three of the variables are equal to 1.

• Odd functions appear when XOR functions involve more than two variables and their corresponding miniterms displayed are distant from each other in the K-map.

Gate Propagation Delay

• Propagation Delays: The time taken for a signal value to propagate from input to output.

• The operational speed of a circuit is inversely related to the longest propagation delay throughout the circuit.

• Key Parameters:

  • High to Low Propagation Time: The delay observed when measuring from the reference voltage on input to output transitioning from high to low at a reference point of 50%.

  • Low to High Propagation Time: Distance measured from input low to output transitioning to high.

  • Defined Propagation Delays: Taken as the maximum of the above two values.

• Two Models:

  • Transport Delays: Occur when changes in output follow input changes after a specified delay.

  • Inertial Delays: Outputs may ignore changes if they occur in rapid succession (within a rejection time).

• Rejection Time: A given value no larger than the propagation delay, often equating with it.

HDL Overview

• Schematic Capture: Tools for drawing blocks and interconnections across multiple levels and establishing design hierarchy.

• Logic Verification: Tools for validating inputs against the diagram.

• Logic Synthesizers: Tools that optimize designs considering area and delay parameters.

  • HDL System Description: Expressed in an intermediate level known as Register Transfer Language (RTL).

• Logic Synthesis Flow: Translates HDL into a netlist that describes interconnections of primitive components.

Logic Synthesis Process

1. Translation: Converts HDL description into a workable form.

2. Optimization: Enhances designs per required constraints.

3. Technology Mapping: Sets the mapped technology for implementing the netlist into physical hardware.

Conclusions

• The critical understanding of combinatorial logic circuitry incorporates various mathematical and structural concepts that form the basis of digital circuit design.

• Emphasis on Boolean algebra, K-maps, cost optimization, and HDL usage enhances the capability in designing efficient, practical logic circuits.

• The integration of theoretical and practical knowledge results in proficient implementation within computing systems.