Chapter 2（Digital Design and Computer Architecture）

Chapter 2

Logic circuit

Composition

• Inputs
• Outputs
• Functional specification
• Timing specification

Types

• Combinational Logic

  Memoryless

  Output determined by current values of inputs

  Rules of combinational composition

  1. Every element is combinational
  2. Every node is either an input / connect to 1 output
  3. no cyclic paths
  4. 

• Sequential Logic

  Has memory

  Output determined by previous and current values

Boolean Equations

Definitions

Complement :

Literal:

Implicant:

Minterm: product that includes all input variables

Sum: the OR of one or more literals

Maxterm: sum that includes all input variables

Sum-of-Products (SOP) Form

All equations can be written in SOP form

Product-of-Sums (POS) Form

All Boolean equations can be written in POS form

Boolean Algebra

Bubble pushing

From Logic To Gates

Two-level logic

ANDs followed by ORs

Multiple output circuits

A3>A2>A1>A0

Don’t cares

X’s and Z’s, Oh My

Unknown or Illegal : X

– Actual value somewhere in between

– Could be 0, 1, or in forbidden zone

• Warnings: – Contention usually indicates a bug.

​ – X is used for “don’t care” and contention

Floating : Z

Floating output might be 0, 1, or somewhere in between.

Tristate Buses

Many different drivers

Exactly one is active at once

Karnaugh Maps

K-Map Rules

• Every 1 must be circled at least once
• Each circle must be as large as possible
• Each circle must span a power of 2 squares in each direction
• A circle may wrap around the edges
• A X is circled only if it helps minimize the equation

Combinational Building Blocks

Multiplexers

Implementations

• Logic gates

  

• Tristates

  

4：1 Multiplexers

Reducing the size of multiplexers

Decoders

One-hot outputs : Only one output HIGH at once

Decoder Implementation

OR minterms

Timing

Propagation & Contamination Delay

• Propagation delay（传输延迟）:
• Contamination delay（最小延迟）: output

Cause of delay

Capacitance and resistance in a circuit

Speed of light limitation

• Reasons why tpd and tcd may be different:

– Different rising and falling delays

– Multiple inputs and outputs, some of which are faster than others

– Circuits slow down when hot and speed up when cold

Critical (Long) & Short Paths

Glitch

Fixing the glitch