You are previewing Digital Logic Design: A Rigorous Approach.
O'Reilly logo
Digital Logic Design: A Rigorous Approach

Book Description

This textbook, based on the author's fifteen years of teaching, is a complete teaching tool for turning students into logic designers in one semester. Each chapter describes new concepts, giving extensive applications and examples. Assuming no prior knowledge of discrete mathematics, the authors introduce all background in propositional logic, asymptotics, graphs, hardware and electronics. Important features of the presentation are:

  • All material is presented in full detail. Every designed circuit is formally specified and implemented, the correctness of the implementation is proved, and the cost and delay are analyzed
  • Algorithmic solutions are offered for logical simulation, computation of propagation delay and minimum clock period
  • Connections are drawn from the physical analog world to the digital abstraction
  • The language of graphs is used to describe formulas and circuits
  • Hundreds of figures, examples and exercises enhance understanding. The extensive website (http://www.eng.tau.ac.il/~guy/Even-Medina/) includes teaching slides, links to Logisim and a DLX assembly simulator.

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Contents
  5. List of Algorithms
  6. Preface
  7. Part I: Preliminaries
    1. 1 - Sets and Functions
      1. 1.1 - Sets
      2. 1.2 - Relations and Functions
      3. 1.3 - Boolean Functions
      4. 1.4 - Commutative and Associative Binary Operations
    2. 2 - Induction and Recursion
      1. 2.1 - Induction
      2. 2.2 - Recursion
      3. 2.3 - Application: One-to-One and Onto Functions
    3. 3 - Sequences and Series
      1. 3.1 - Sequences
      2. 3.2 - Series
    4. 4 - Directed Graphs
      1. 4.1 - Definitions
      2. 4.2 - Topological Ordering
      3. 4.3 - Longest Path in a DAG
      4. 4.4 - Rooted Trees
    5. 5 - Binary Representation
      1. 5.1 - Division and Modulo
      2. 5.2 - Bits and Strings
      3. 5.3 - Bit Ordering
      4. 5.4 - Binary Representation
      5. 5.5 - Computing a Binary Representation
      6. 5.6* - More on Unique Binary Representation
    6. 6 - Propositional Logic
      1. 6.1 - Boolean Formulas
      2. 6.2 - Truth Assignments
      3. 6.3 - Satisfiability and Logical Equivalence
      4. 6.4 - Interpreting a Boolean Formula as a Function
      5. 6.5 - Substitution
      6. 6.6 - Complete Sets of Connectives
      7. 6.7 - Important Tautologies
      8. 6.8 - De Morgan’s Laws
    7. 7 - Asymptotics
      1. 7.1 - Order of Growth Rates
      2. 7.2 - Recurrence Equations
    8. 8* Computer Stories: Big Endian versus Little Endian
  8. Part II: Combinational Circuits
    1. 9 - Representations of Boolean Functions by Formulas
      1. 9.1 - Sum of Products
      2. 9.2 - Product of Sums
      3. 9.3 - The Finite Field GF(2)
      4. 9.4 - Satisfiability
      5. 9.5 - Relation to P versus NP
      6. 9.6* - Minimization Heuristics
    2. 10* The Digital Abstraction
      1. 10.1 - Transistors
      2. 10.2 - A CMOS Inverter
      3. 10.3 - From Analog Signals to Digital Signals
      4. 10.4 - Transfer Functions of Gates
      5. 10.5 - The Bounded-Noise Model
      6. 10.6 - The Digital Abstraction in the Presence of Noise
      7. 10.7 - Stable Signals
      8. 10.8 - Summary
    3. 11 - Foundations of Combinational Circuits
      1. 11.1 - Combinational Gates: An Analog Approach
      2. 11.2 - Back to the Digital World
      3. 11.3 - Combinational Gates
      4. 11.4 - Wires and Nets
      5. 11.5 - Combinational Circuits
      6. 11.6 - Properties of Combinational Circuits
      7. 11.7 - Simulation and Delay Analysis
      8. 11.8 - Completeness
      9. 11.9 - Cost and Propagation Delay
      10. 11.10 - Example: Relative Gate Costs and Delay
      11. 11.11 - Semantics and Syntax
      12. 11.12 - Summary
    4. 12 - Trees
      1. 12.1 - Associative Boolean Functions
      2. 12.2 - Trees of Associative Boolean Gates
      3. 12.3 - Optimality of Trees
      4. 12.4 - Summary
    5. 13 - Decoders and Encoders
      1. 13.1 - Buses
      2. 13.2 - Decoders
      3. 13.3 - Encoders
      4. 13.4 - Summary
    6. 14 - Selectors and Shifters
      1. 14.1 - Multiplexers
      2. 14.2 - Cyclic Shifters
      3. 14.3 - Logical Shifters
      4. 14.4 - Arithmetic Shifters
      5. 14.5 - Summary
    7. 15 - Addition
      1. 15.1 - Definition of a Binary Adder
      2. 15.2 - Ripple Carry Adder
      3. 15.3 - Lower Bounds
      4. 15.4 - Conditional Sum Adder
      5. 15.5 - Compound Adder
      6. 15.6 - Reductions between Sum and Carry Bits
      7. 15.7 - Redundant and Nonredundant Representation
      8. 15.8 - Summary
    8. 16 - Signed Addition
      1. 16.1 - Representation of Negative Integers
      2. 16.2 - Computing a Two’s Complement Representation
      3. 16.3 - Negation in Two’s Complement Representation
      4. 16.4 - Properties of Two’s Complement Representation
      5. 16.5 - Reduction: Two’s Complement Addition to Binary Addition
      6. 16.6 - A Two’s-Complement Adder
      7. 16.7 - A Two’s Complement Adder/Subtractor
      8. 16.8 - Summary
  9. Part III: Synchronous Circuits
    1. 17 - Flip-Flops
      1. 17.1 - The Clock
      2. 17.2 - Edge-Triggered Flip-Flop
      3. 17.3* - Arbitration
      4. 17.4* - Arbiters: An Impossibility Result
      5. 17.5* - Necessity of Critical Segments
      6. 17.6 - A Timing Example
      7. 17.7 - Bounding Instability
      8. 17.8 - Other Types of Memory Devices
      9. 17.9 - Summary
    2. 18 - Memory Modules
      1. 18.1 - The Zero Delay Model
      2. 18.2 - Registers
      3. 18.3 - Random Access Memory (RAM)
      4. 18.4 - Read-Only Memory (ROM)
      5. 18.5 - Summary
    3. 19 - Foundations of Synchronous Circuits
      1. 19.1 - Definition
      2. 19.2 - The Canonic Form of a Synchronous Circuit
      3. 19.3 - Timing Analysis: The Canonic Form
      4. 19.4 - Functionality: The Canonic Form
      5. 19.5 - Finite State Machines
      6. 19.6 - Timing Analysis: The General Case
      7. 19.7 - Simulation of Synchronous Circuits
      8. 19.8 - Synthesis and Analysis
      9. 19.9 - Summary
    4. 20 - Synchronous Modules: Analysis and Synthesis
      1. 20.1 - Example: A Two-State FSM
      2. 20.2 - Sequential Adder
      3. 20.3 - Initialization and the Corresponding FSM
      4. 20.4 - Counter
      5. 20.5 - Revisiting Shift Registers
      6. 20.6 - Revisiting RAM
  10. Part IV: A Simplified Dlx
    1. 21 - The ISA of a Simplified DLX
      1. 21.1 - Why Use Abstractions?
      2. 21.2 - Instruction Set Architecture
      3. 21.3 - Examples of Program Segments
      4. 21.4 - Summary
    2. 22 - A Simplified DLX: Implementation
      1. 22.1 - Datapath
      2. 22.2 - Control
      3. 22.3 - RTL Instructions
      4. 22.4 - Examples of Instruction Execution
      5. 22.5 - Summary
  11. Bibliography
  12. Index