Combinational logic design

Introduction
Boolean Equations
Boolean Algebra
From Logic to Gates
Multilevel Combinational Logic
X’s and Z’s, Oh

A logic circuit is composed of:
Inputs
Outputs
Functional specification
Timing specification

Introduction

Nodes
Inputs: A, B, C
Outputs: Y, Z
Internal: n1
Circuit elements
E1, E2, E3
Each a

Combinational Logic
Memoryless
Outputs determined by current values of inputs
Sequential Logic
Has memory
Outputs determined

Every element is combinational
Every node is either an input or connects

Functional specification of outputs in terms of inputs
Example: S = F(A,

Complement: variable with a bar over it
A, B, C
Literal: variable

Y = F(A, B) =

All equations can be written in SOP

Y = F(A, B) =

Sum-of-Products (SOP) Form

All equations can be written

Y = F(A, B) = AB + AB = Σ(1, 3)

Sum-of-Products

Y = F(A, B) = (A + B)(A + B) =

You are going to the cafeteria for lunch
You won’t eat lunch

You are going to the cafeteria for lunch
You won’t eat lunch

SOP & POS Form

SOP – sum-of-products
POS – product-of-sums

SOP – sum-of-products
POS – product-of-sums

E = (O + C)(O + C)(O

Axioms and theorems to simplify Boolean equations
Like regular algebra, but simpler:

Boolean Axioms

B 1 = B
B + 0 = B

T1: Identity Theorem

B 1 = B
B + 0 = B

T1: Identity Theorem

B 0 = 0
B + 1 = 1

T2: Null Element Theorem

B 0 = 0
B + 1 = 1

T2: Null Element Theorem

B B = B
B + B = B

T3: Idempotency Theorem

B B = B
B + B = B

T3: Idempotency Theorem

B = B

T4: Identity Theorem

B = B

T4: Identity Theorem

B B = 0
B + B = 1

T5: Complement Theorem

B B = 0
B + B = 1

T5: Complement Theorem

Boolean Theorems Summary

Boolean Theorems of Several Vars

Note: T8’ differs from traditional algebra: OR

Y = AB + AB

Simplifying Boolean Equations

Example 1:

Y = AB + AB
= B(A + A) T8
= B(1) T5’

Y = A(AB + ABC)

Example 2:

Simplifying Boolean Equations

Y = A(AB + ABC)
= A(AB(1 + C)) T8
= A(AB(1)) T2’

Y = AB = A + B
Y = A + B

Backward:
Body changes
Adds bubbles to inputs
Forward:
Body changes
Adds bubble to output

Bubble Pushing

What is the Boolean expression for this circuit?

Bubble Pushing

What is the Boolean expression for this circuit?

Y = AB +

Begin at output, then work toward inputs
Push bubbles on final output

Bubble Pushing Example

Bubble Pushing Example

Bubble Pushing Example

Bubble Pushing Example

Two-level logic: ANDs followed by ORs
Example: Y = ABC + ABC

Inputs on the left (or top)
Outputs on right (or bottom)
Gates flow

Wires always connect at a T junction
A dot where wires cross

Example: Priority Circuit
Output asserted
corresponding to
most significant
TRUE input

Multiple-Output Circuits

Example: Priority Circuit
Output asserted
corresponding to
most significant
TRUE input

Multiple-Output Circuits

Priority Circuit Hardware

Don’t Cares

Contention: circuit tries to drive output to 1 and 0
Actual value

Floating, high impedance, open, high Z
Floating output might be 0, 1,

Floating nodes are used in tristate busses
Many different drivers
Exactly one is

Boolean expressions can be minimized by combining terms
K-maps minimize equations graphically
PA

Circle 1’s in adjacent squares
In Boolean expression, include only literals whose

3-Input K-Map

Y = AB + BC

3-Input K-Map

Complement: variable with a bar over it
A, B, C
Literal: variable

Every 1 must be circled at least once
Each circle must span

4-Input K-Map

4-Input K-Map

4-Input K-Map

K-Maps with Don’t Cares

K-Maps with Don’t Cares

K-Maps with Don’t Cares

Multiplexers
Decoders

Combinational Building Blocks

Selects between one of N inputs to connect to output
log2N-bit select

2-<>

Logic gates
Sum-of-products form

Tristates
For an N-input mux, use N tristates
Turn on exactly

Using the mux as a lookup table

Logic using Multiplexers

Reducing the size of the mux

Logic using Multiplexers

N inputs, 2N outputs
One-hot outputs: only one output HIGH at once

Decoders

Decoder Implementation

OR minterms

Logic Using Decoders

ENOUGH FOR TODAY!

Delay between input change and output changing
How to build fast circuits?

Timing

Propagation delay: tpd = max delay from input to output
Contamination delay:

Delay is caused by
Capacitance and resistance in a circuit
Speed of light

When a single input change causes an output to change multiple

What happens when A = 0, C = 1, B falls?

Glitch

Glitch Example (cont.)

Fixing the Glitch