Digital Logic

Design
Chapter 4

Circuit Analysis Procedure

Important concept analyze digital circuits
Given a circuit
- Create a truth table
-

Create a minimized circuit

Approaches
Boolean expression approach
Truth table approach

Leads to minimized hardware

Provides insights on how to design hardware
Tie in with K-maps (next time)

The Problem
How can we convert from a circuit drawing to an
equation or truth table?
Two approaches
Create intermediate equations
Create intermediate truth tables
A
B
C
A
B
C

Out

Label Gate Outputs

1. Label all gate outputs that are a function of input
variables.
2. Label gates that are a function of input variables
and previously labeled gates.
3. Repeat process until all outputs are labelled.
A
B
C
A
B
C

Out

Approach 1: Create Intermediate Equations

Step 1: Create an equation for each gate output based
on its input.

R = ABC

S=A+B

T = CS

Out = R + T
A
B
C
A
B
C

Out

Approach 1: Substitute in subexpressions

Step 2: Form a relationship based on input variables
(A, B, C)

R = ABC

S=A+B

T = CS = C(A + B)

Out = R+T = ABC + C(A+B)

A
B
C
A
B
C

Out

Approach 1: Substitute in subexpressions

Step 3: Expand equation to SOP final result

Out = ABC + C(A+B) = ABC + AC + BC

A
B
C
Out
A
C

B
C

Approach 2: Truth Table

Step 1: Determine outputs for functions of input
variables.
A B C R S
0 0 0 0 0
0 0 1 0 0
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
A
R
B
C

A
B
C

Out

Approach 2: Truth Table

Step 2: Determine outputs for functions of
intermediate variables.
A B C C R S
0 0 0 1 0 0
T = S * C
0 0 1 0 0 0
0 1 0 1 0 1
0 1 1 0 0 1
1 0 0 1 0 1
1 0 1 0 0 1
1 1 0 1 0 1
A
1 1 1 0 1 1
R
B
C

A
B
C

Out

T
0
0
1
0
1
0
1
0

Approach 2: Truth Table

Step 3: Determine outputs for function.

R + T = Out

A
B
C
A
B
C

A
0
0
0
0
1
1
1
1
T

B
0
0
1
1
0
0
1
1

C
0
1
0
1
0
1
0
1

R
0
0
0
0
0
0
0
1

S
0
0
1
1
1
1
1
1

T
0
0
1
0
1
0
1
0
Out

Out
0
0
1
0
1
0
1
1

Example 2
Step 3: Note labels on interior nodes

Example 2:

Truth Table

Remember to determine intermediate variables

starting from the inputs.
When all inputs determined for a gate, determine
output.
The truth table can be reduced using K-maps.
A
0
0
0
0
1
1
1
1

B
0
0
1
1
0
0
1
1

C
0
1
0
1
0
1
0
1

F2
0
0
0
1
0
1
1
1

F2
1
1
1
0
1
0
0
0

T1
0
1
1
1
1
1
1
1

T2
0
0
0
0
0
0
0
1

T3
0
1
1
0
1
0
0
0

F1
0
1
1
0
1
0
0
1

Combinational Design Procedure

Design digital circuit from specification
Digital inputs and outputs known
Need to determine logic that can transform data

Start in truth table form

Create K-map for each output based on function of
inputs
Determine minimized sum-of-product representation
Draw circuit diagram

Design Procedure
Design a circuit from a specification.
1. Determine number of required inputs and
outputs.
2. Derive truth table
3. Obtain simplified Boolean functions
4. Draw logic diagram and verify correctness
A B C RS
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
S = A+ B + C
R = ABC
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Design Procedure
Boolean algebra can be used to simplify
expressions, but not obvious:
how to proceed at each step, or
if solution reached is minimal.

Have seen five ways to represent a function:

Boolean expression
truth table
logic circuit
minterms/maxterms
Karnaugh map

Combinational logic design

Use multiple representations of logic functions
Use graphical representation to assist in
simplification of function.
Use concept of dont care conditions.
Example - encoding BCD to seven segment display.
Similar to approach used by designers in the field.

BCD to Seven Segment Display

Used to display binary coded decimal (BCD)
numbers using seven illuminated segments.
BCD uses 0s and 1s to represent decimal digits 0 9. Need four bits to represent required 10 digits.
Binary coded decimal (BCD) represents each
decimal digit with four bits
0

0 0 0 0

0 0 0 1

0 0 1 0

0 1 1 1

1 0 0 0

1 0 0 1

a
f

b
c

BCD to Seven Segment Display

List the segments that should be illuminated for
each digit.
0
1
2
3
4
5
6
7
8
9

a,b,c,d,e,f
b,c
a,b,d,e,g
a,b,c,d,g
b,c,f,g
a,c,d,f,g
a,c,d,e,f,g
a,b,c
a,b,c,d,e,f,g
a,b,c,d,f,g

a
f

b
c

BCD to seven segment display

Derive the truth table for the circuit.
Each output column in one circuit.
Inputs

Outputs

Dec

w x y z

a b c d e .

0 0 0 0

1 1 1 1 1 .

0 0 0 1

0 1 1 0 0 .

0 0 1 0

1 1 0 1 1 .
.

0 1 1 1

1 1 1 0 0 .

0 0 0

1 1 1 1 1 .

0 0 1

1 1 1 1 0 .

BCD to seven segment display

Find minimal sum-of-products representation for
each output
For segment a :
yz
00 01 11 10
wx
00 1 0 1 1
01 0

11
10 1

Note: Have only

filled in ten
squares,
corresponding to
the ten numerical
digits we wish to
represent.

Dont care conditions (BCD display) ...

Fill in dont cares for undefined outputs.
Note that these combinations of inputs should never happen.

Leads to a reduced implementation

For segment a :
yz
00 01 11 10
wx
00 1 0 1 1
01 0

11 X X X X
10 1

X X

Put in X (dont
care), and interpret as
either 1 or 0 as
desired .

Dont care conditions (BCD display) ...

Circle biggest group of 1s and Dont Cares.
Leads to a reduced implementation
For segment a :
yz
00 01 11 10
wx
00 1 0 1 1
01 0

11 X X X X
10 1

X X

Fa1 y

Dont care conditions (BCD display)

Circle biggest group of 1s and Dont Cares.
Leads to a reduced implementation
For segment a :
yz
wx

00 01 11 10
00 1

01 0

11 X X X X
10 1

X X

Fa2 w

Dont care conditions (BCD display) ...

Circle biggest group of 1s and Dont Cares.
All 1s should be covered by at least one implicant
For segment a :
yz
yz
00 01 11 10
wx
00 01 11 10
wx
00 1 0 1 1
00 1 0 1 1
01 0

01 0

11 X X X X

11 X X X X

10 1

10 1

X X

Fa3 x z

X X

Fa4 xz

Dont care conditions (BCD display) ...

Put all the terms together
Generate the circuit
For segment a :
yz
00 01 11 10
wx
00 1 0 1 1
01 0

11 X X X X
10 1

X X

F y w x z xz

BCD to seven segment display

Derive the truth table for the circuit.
Each output column in one circuit.
Inputs

Outputs

Dec

w x y z

a b c d e .

0 0 0 0

1 1 1 1 1 .

0 0 0 1

0 1 1 0 0 .

0 0 1 0

1 1 0 1 1 .
.

0 1 1 1

1 1 1 0 0 .

0 0 0

1 1 1 1 1 .

0 0 1

1 1 1 1 0 .

BCD to seven segment display

Find minimal sum-of-products representation for
each output
For segment b :
yz
00 01 11 10
wx
00 1 1 1 1
01 1

11
10 1

See if you
complete this
example.

Binary Adders and

Subtractors

Addition and subtraction of binary data is fundamental

Need to determine hardware implementation

Represent inputs and outputs

Inputs: single bit values, carry in
Outputs: Sum, Carry

Hardware features
Create a single-bit adder and chain together

Same hardware can be used for addition and

subtraction with minor changes
Dealing with overflow
What happens if numbers are too big?

Half Adder
Add two binary numbers
A0 , B0 -> single bit inputs
S0 -> single bit sum
C1 -> carry out

A0
B0

A0 B0 S0 C 1

0
0
1
1

0
1
0
1

0
1
1
0

0
0
0
1

S0

C1

Dec Binary

1
+1
2

1
+1
10

Multiple-bit Addition
Consider single-bit adder for each bit position.
A3 A2 A1 A0

A 0 1 0 1

A
B

1
0
0
1

1
1
1
1

1
0 1
1 1
0 0

B3 B 2 B 1 B 0

B 0 1 1 1

Ci+1

Ci
Ai
+Bi
Si

Each bit position creates a sum and carry

Full Adder
Full adder includes carry in Ci
Notice interesting pattern in Karnaugh map.
Ci Ai Bi Si Ci+1
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

0
1
1
0
1
0
0
1

0
0
0
1
0
1
1
1

AiBi
00
Ci

11

0
1

01

10
1

Si

Full
Add
Full adder includes carry in Ci
er
Alternative to XOR implementation
Ci Ai Bi Si Ci+1
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

0
1
1
0
1
0
0
1

0
0
0
1
0
1
1
1

S = CAB + CAB + CAB + CAB

S = C(AB + AB) + C(AB + AB)
S = C (A XOR B) + C (A XOR B)
S = C XOR (A XOR B)

Full
Add
er
Now consider implementation of carry out
Two outputs per full adder bit (Ci+1, Si)
Ci Ai Bi Si Ci+1
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

0
1
1
0
1
0
0
1

0
0
0
1
0
1
1
1

AiBi
00
Ci

01

10

0
1

11

Ci+1

Full
Add
Now
er consider implementation of carry out
Minimize circuit for carry out - Ci+1
Ci Ai Bi Si Ci+1
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

0
1
1
0
1
0
0
1

0
0
0
1
0
1
1
1

AiBi
00
Ci

01

10

0
1

11

Ci+1
Ci+1 = AiBi + CiBi + CiAi

Full Adder
Ci+1 = AiBi + CiBi + CiAi
Ci+1 = AiBi +Ci (Ai+Bi)
Ci+1 = AiBi +Ci (AiBi+Ai Bi)
Ci+1 = AiBi +Ci (Ai XOR Bi)
As we have:
Si = Ci XOR (Ai XOR Bi)
Ci+1 = AiBi +Ci (Ai XOR Bi)

Full Adder
Full adder made of several half adders
Si = Ci XOR (Ai XOR Bi)
Ci+1 = AiBi +Ci (Ai XOR Bi)
Ci
Ai

Si

Bi

Half-adder

Half-adder

C i+1

Full
Add
Hardware
repetition simplifies hardware design
er

Ci
Ai
Bi

S
half-adder
C

half-adder

Si
C
C i+1

A full adder can be made from

two half adders (plus an OR gate).

Full
Add
Putting
it all together
er
Single-bit full adder
Common piece of computer hardware

Ai

C i+1

Bi

Full Adder

Si

Block Diagram

Ci

4Bit
Chain
Add single-bit adders together.
er
A3

B3

A2

Full Adder

Full Adder
C3

C4

S3

A1

B2

Full Adder

C2

S1

S2

C
A
B
S

B1

1
0
0
1

1
1
1
1

1
0
1
0

0
1
1
0

A0

C1

B0

Full Adder

S0

Negative Numbers 2s Complement.

Subtracting a number is the same as:

1. Perform 2s complement
2. Perform addition

If we can augment adder with 2s complement

hardware?

4-bit Subtractor: E = 1

A3

B3

A2

B2

A1

B1

A0

B0
E

Full Adder
C

C4

SD 3

Full Adder
3

SD2

Full Adder
C2

Full Adder
C1

SD1

SD 0

Add A to B (ones complement) plus 1

That is, add A to twos complement of B
D=A-B

+1

Adder- Subtractor Circuit

Overflow in twos complement

addition
Definition: When two values of the same signs are
added:
Result wont fit in the number of bits provided
Result has the opposite sign.

AN-1
BN-1

Overflow?

CN-1

Assumes an N-bit adder, with bit N-1 the M

Addition and
subtraction
Addition and subtraction are fundamental to computer
systems
Key create a single bit adder/subtractor
Chain the single-bit hardware together to create bigger designs

The approach is call ripple-carry addition

Can be slow for large designs

Overflow is an important issue for computers

Processors often have hardware to detect overflow

Magnitude Comparators
Digital building block
Magnitude comparators
Compare two multi-bit binary numbers
Create a single bit comparator
Use repetitive pattern

Multiplexers
Select one out of several bits
Some inputs used for selection
Also can be used to implement logic

Magnitude
Comparator

The comparison of two numbers

outputs: A>B, A=B, A<B

Design Approaches
the truth table
- 22n entries - too cumbersome for large n
use inherent regularity of the problem
- reduce design efforts
- reduce human errors

A[3..0]
B[3..0]

Magnitude
Compare

A<B
A=B
A>B

Mag
nitu
de
Co
mp
arat
or

A0
A1
A2
A3

B0
B1
B2
B3

C0

D01

C1

A_EQ_B

C2
C3

D23

How can we find A > B?

How many rows would a truth table have?

28 = 256

Mag
nitu
de
A0
CoB0
mp
A1
B1
arat
A2
orB2
A3

B3

C0

D01

C1

A_EQ_B

C2
C3

Find A > B

D23

Because A3 > B3
i.e. A3 . B3 = 1

If A = 1001 and
B = 0111
Therefore, one term in the
is A > B?
logic equation for A > B is
Why?
A3 . B3

Magnitude Comparator

If A = 1010 and
B = 1001
is A > B?
Why?

A > B = A3 . B3
+ C3 . A2 . B2
+ ..
Because A3 = B3 and
A2 = B2 and
A1 > B1
i.e. C3 = 1 and C2 = 1 and
A1 . B1 = 1
Therefore, the next term in the
logic equation for A > B is
C3 . C2 . A1 . B1

Magnitude
Comparison
Algorithm -> logic
A = A3A2A1A0 ; B = B3B2B1B0
A=B if A3=B3, A2=B2, A1=B1and A1=B1

Test each bit:

- equality: xi= AiBi+Ai'Bi'
- (A=B) = x3x2x1x0

More difficult to test less than/greater than

(A>B) = A3B3'+x3A2B2'+x3x2A1B1'+x3x2x1 A0B0'
(A<B) = A3'B3+x3A2'B2+x3x2A1'B1+x3x2x1 A0'B0
Start comparisons from high-order bits

Implementation
xi = (AiBi'+Ai'Bi)

Multiplexer
s
Digital building block

Select an input value with one or more select bits

Use for transmitting data
Allows for conditional transfer of data
Sometimes called a mux

4 to 1- Line Multiplexer

Quadruple 2to1-Line Multiplexer

Notice enable bit

Notice select bit
4 bit inputs

Multiplexer as combinational
modules
Connect input variables to select inputs of
multiplexer (n-1 for n variables)

Set data inputs to multiplexer equal to values of

function for corresponding assignment of select
variables
Using a variable at data inputs reduces size of the
multiplexer

Implementing a Four- Input Function with a Multiplexer

Typical multiplexer uses

Thr
ee-
A multiplexer can be constructed with three-state gates
stat
e Output state: 0, 1, and high-impedance (open ckts)
gat If the select input (E) is 0, the three-state gate has no
es output

Opposite true here

Thr
eestat
e
gat
es

A multiplexer can be constructed with three-state gates

Output state: 0, 1, and high-impedance (open ckts)
If the select input is low, the three-state gate has no output

Encoders and
Decoders

Binary decoders

Converts an n-bit code to a single active output

Can be developed using AND/OR gates
Can be used to implement logic circuits.

Binary encoders
Converts one of 2n inputs to an n-bit output
Useful for compressing data
Can be developed using AND/OR gates

Both encoders and decoders are extensively used in

digital systems

Binary Decoder
Black box with n input lines and 2n output lines
Only one output is a 1 for any given input

n
inputs

Binary
Decoder

2n outputs

2-to-4 Binary Decoder

Truth Table:
X
0
0
1
1

Y F0
0 1
1 0
0 0
1 0

F1 F2 F3
0 0 0
1 0 0
0 1 0
0 0 1

F0 = X'Y'
F1 = X'Y
F2 = XY'

From truth table, circuit for

2x4 decoder is:
Note: Each output is a 2variable minterm
(X'Y', X'Y, XY' or XY)

X
Y

2-to-4
Decoder

F3 = XY

F0
F1
F2
F3

3to-8
Truth
Bina Table:
ry
x y z F0 F1 F2
Dec
0 0 0 1 0 0
oder
0 0 1 0 1 0
0
0
1
1
1
1

1
1
0
0
1
1

0
1
0
1
0
1

0
0
0
0
0
0

0
0
0
0
0
0

1
0
0
0
0
0

F0 = x'y'z'
F3
0
0
0
1
0
0
0
0

F4
0
0
0
0
1
0
0
0

F5
0
0
0
0
0
1
0
0

F6
0
0
0
0
0
0
1
0

F7
0
0
0
0
0
0
0
1

F1 = x'y'z
F2 = x'yz'
F3 = x'yz
F4 = xy'z'
F5 = xy'z
F6 = xyz'

F0
X
Y
Z

F7 = xyz

F1

3-to-8
Decoder

F2
F3
F4
F5
F6
F7

Implementing Functions Using

Decoders

Any n-variable logic function can be implemented using

a single n-to-2n decoder to generate the minterms
OR gate forms the sum.
The output lines of the decoder corresponding to the minterms
of the function are used as inputs to the or gate.

Any combinational circuit with n inputs and m outputs

can be implemented with an n-to-2n decoder with m OR
gates.
Suitable when a circuit has many outputs, and each
output function is expressed with few minterms.

Implementing Functions Using

Decoders
x y z
Example: Full adder
S(x, y, z) = (1,2,4,7)
C(x, y, z) = (3,5,6,7)

3-to-8 0
Decoder 1
x

S2

S1

S0

2
3
4
5
6
7

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

C S
0 0
0 1
0 1
1 0
0 1
1 0
1 0
1 1

Building a Binary Decoder with NAND Gates

Start with a 2-bit decoder
Add an enable signal (E)

Note: use of NANDs

only one 0 active!
if E = 0

Use two 3 to 8 decoders to make 4 to 16 decoder

Enable can also be active high
In this example, only one decoder can be active
at a time.
x, y, z effectively select output line for w

Encoders
If the decoder's output code has fewer bits than the
input code, the device is usually called an encoder.
e.g. 2n-to-n
The simplest encoder is a 2n-to-n binary encoder
One of 2n inputs = 1

Output is an n-bit binary number

2n
inputs

.
.
.

Binary
encoder

.
.
.

n
outputs

8-to-3 Binary Encoder

At any one time, only
one input line has a value of 1.

I0
I1

Inputs

I0
1
0
0
0
0
0
0
0

I1
0
1
0
0
0
0
0
0

I2
0
0
1
0
0
0
0
0

I3
0
0
0
1
0
0
0
0

I4
0
0
0
0
1
0
0
0

Outputs

I5
0
0
0
0
0
1
0
0

I6
0
0
0
0
0
0
1
0

y2 = I4 + I5 + I6 + I7

I2
I3

y1 = I2 + I3 + I6 + I7

I4
I5
I6
I7

y0 = I1 + I3 + I5 + I7

I7
0
0
0
0
0
0
0
1

y2
0
0
0
0
1
1
1
1

y1
0
0
1
1
0
0
1
1

y0
0
1
0
1
0
1
0
1

8-to-3 Priority Encoder

What if more than one input line has a value of 1?
Ignore lower priority inputs.
Idle indicates that no input is a 1.
Note that polarity of Idle is opposite from Table 4-8 in
Mano
Inputs

I0
0
1
X
X
X
X
X
X
X

I1
0
0
1
X
X
X
X
X
X

I2
0
0
0
1
X
X
X
X
X

I3
0
0
0
0
1
X
X
X
X

I4
0
0
0
0
0
1
X
X
X

Outputs

I5
0
0
0
0
0
0
1
X
X

I6
0
0
0
0
0
0
0
1
X

I7
0
0
0
0
0
0
0
0
1

y2
x
0
0
0
0
1
1
1
1

y1
x
0
0
1
1
0
0
1
1

y0 Idle
x 1
0 0
1 0
0 0
1 0
0 0
1 0
0 0
1 0

Priority Encoder (8 to 3 encoder)

Assign priorities to the inputs

When more than one input are asserted, the output generates the
code of the input with the highest priority

Priority Encoder :
H7=I7
(Highest Priority)
H6=I6.I7
H5=I5.I6.I7
H4=I4.I5.I6.I7
H3=I3.I4.I5.I6.I7
H2=I2.I3.I4.I5.I6.I7
I0
H1=I1. I2.I3.I4.I5.I6.I7
I1
H0=I0.I1. I2.I3.I4.I5.I6.I7
IDLE= I0.I1. I2.I3.I4.I5.I6.I7 I2

Encoder
Y0 = I1 + I3 + I5 + I7
Y1 = I2 + I3 + I6 + I7
Y2 = I4 + I5 + I6 + I7

Priority encoder
Priority Circuit

Binary encoder

I0

H0

I0

I1

H1

I1

I2

H2

I2

Y0

I3

I3

H3

I3

Y1

I4

I4

H4

I4

Y2

I5

I5

H5

I5

I6

I6

H6

I6

I7

I7

H7

I7

IDLE

Y0
Y1
Y2

IDLE

Encoder Application (Monitoring Unit)

Encoder identifies the requester and encodes the value

Controller accepts digital inputs.

Alarm
Signal

Contoller
Response

Machine 1
Machine 2
Encoder

Machine n

Action

Machine
Code

Controller