Introduction

• Combinational logic
  • Memoryless
  • Current values of inputs -> outputs

• Sequential logic

  • Has memory
  • Previous & current values of inputs -> outputs

• Nodes

  • Input (A, B, C)
  • Output (Y, Z)
  • Internal (n1)

• Circuit elements

  • E1, E2, E3

Rules of Combinational Logic

• Every element combinational
• Every node either an input, or connected to a single output
• No cyclic path

Boolean Equations

$$output = F(inputs)$$

Some Definitions

• Complement $$\overline{A}$$
• Literal $$A, \overline{A}$$
• Implicant: product of literals
• Minterm: product including all literals
• Maxterm: sum including all literals
• Precedence of operations: NOT > AND > OR

SOP (Sum of Products)POS (Product of Sums)

Choosing between SOP & POS depends on how many 0/1s in Y.

Boolean Algebra

Duality

Interchange 0 & 1, AND & OR, same expression.

Boolean Axioms

Boolean Theories

DeMorgan's Theorem

$$Y = \overline{AB} = \overline{A} + \overline{B}$$

$$Y = \overline{A + B} = \overline{A} \cdot \overline{B}$$

Bubble Pushing

Begin at final output, push towards input; draw gates in a form that bubbles cancel.

• Backward

• Forward

From Logic to GatesMultiple-Output Circuits

Priority Circuit

Contention: X

• Might change with temperature, voltage, time, noise
• Causes excessive power dissipation
• Usually indicates a bug
• X used for don't care & contention

Floating: Z

e.g. tristate buffer

Karnaugh Map

• Prime implicant: largest circle in map

Rules

• Each 1 circled
• Each circle spans a power of 2 squares
• Each circle as large as possible
• A circle can wrap around edges
• Don't cares can be circled if help with minimizing the equation

Combinational Building Blocks

Multiplexer

$$log_2 N$$ bits to select $$N$$ inputs.

e.g. 2:1 muxImplementation

• Logic gates

• Tristates

  • N inputs, N muxes

  

Logic using Muxes

• Lookup table
• Reducing size of mux

Decoder

$$N$$ inputs, $$2^N$$ one-hot outputs.Implementation

Logic using Decoders

• OR minterms

Timing

Delay

• Delay types
  • Propagation delay $$t_{pd}$$: max delay from input to output
  • Contamination delay $$t_{cd}$$: min delay from input to output
• Cause
  • Capacitance & resistance in circuits
  • Speed of light limitation
• Why $$t{pd}$$ might be different from $$t{cd}$$
  • Different rising & falling delays
  • Multiple inputs & outputs with different speed
  • Temperature affects speed

Critical Path & Short Path

• Critical path: $$2 t{pd_AND} + t{pd_OR}$$
• Short path: $$t_{cd_AND}$$

Glitches

A single input change -> multiple output changes; or simultaneous transitions on multiple inputs.

Possible when going across circles in a K-map.

Fixture

Glitches are not an error and impossible to eliminate. Need time to settle down. Don't cause problem because of synchronous design conventions.