Combinational Logic Design
Chapter 3
2
Digital Circuits
Overview
Part 1 - Implementation Technology and Logic Design
Design Concepts and Automation
Fundamental concepts of design and computer-aided design
techniques
The Design Space
Technology parameters for gates, positive and negative logic and
design tradeoffs
Design Procedure
The major design steps: specification, formulation, optimization,
technology mapping, and verification
Technology Mapping
From AND, OR, and NOT to other gate types
Verification
Does the designed circuit meet the specifications?
Part 2 - Programmable Implementation Technologies
Read-Only Memories, Programmable Logic Arrays, Programmable
Array Logic
Technology mapping to programmable logic devices
3
Digital Circuits
Combinational Circuits
A combinational logic circuit has:
A set of m Boolean inputs,
A set of n Boolean outputs, and
n switching functions, each mapping the 2
m
input combinations to
an output such that the current output depends only on the
current input values
A block diagram:
m Boolean Inputs
n Boolean Outputs
Combinatorial
Logic
Circuit
4
Digital Circuits
Hierarchical Design
To control the complexity of the function mapping inputs to
outputs:
Decompose the function into smaller pieces called blocks
Decompose each block’s function into smaller blocks, repeating as
necessary until all blocks are small enough
Any block not decomposed is called a primitive block
The collection of all blocks including the decomposed ones is a
hierarchy
Example: 9-input parity tree (see next slide)
Top Level: 9 inputs, one output
2nd Level: Four 3-bit odd parity trees in two levels
3rd Level: Two 2-bit exclusive-OR functions
Primitives: Four 2-input NAND gates
Design requires 4 X 2 X 4 = 32 2-input NAND gates
5
Digital Circuits
Hierarchy for Parity Tree Example
B
O
X
0
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
Z
O
9-Input
odd
function
(a) Symbol for circuit
3-Input
odd
function
A
0
A
1
A
2
B
O
3-Input
odd
function
A
0
A
1
A
2
B
O
3-Input
odd
function
A
0
A
1
A
2
B
O
3-Input
odd
function
A
0
A
1
A
2
X
0
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
Z
O
(b) Circuit as interconnected 3-input odd
function blocks
B
O
A
0
A
1
A
2
(c) 3-input odd function circuit as
interconnected exclusive-OR
blocks
(d) Exclusive-OR block as interconnected
NANDs
