### 04_Chapter 4 - Modular Comb logic

Chapter 4
Modular Combinational Logic
Decoders
Decoders

n to 2n decoder




n inputs
2n outputs
For each input, one and only one output
will be active.
Uses:




“Minterm generator”
Wordline (memory) circuit
Code conversion
Routing data
2 to 4 Decoder Example
2 to 4 Decoder – Truth Table

2 to 4 decoder
X1
0
X0
0
Y3
0
Y2
0
Y1
0
Y0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
2 to 4 Decoder Equations
Y0  X 1 X 0
Y1  X 1 X 0
Y2  X 1 X 0
Y3  X 1 X 0
2 to 4 Decoder: Circuit
2 to 4 Decoder: Block Symbol
Symbol
Circuit
3 to 8 Decoder Example
3 to 8 Decoder – Truth Table
x2 x1 x0 y7 y6 y5 y4 y3 y2 y1 y0
0 0 0 0 0 0 0 0 0 0 1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
3 to 8 Decoder Equations
Y0  X 2 X 1 X 0
Y4  X 2 X 1 X 0
Y1  X 2 X 1 X 0
Y5  X 2 X 1 X 0
Y2  X 2 X 1 X 0
Y6  X 2 X 1 X 0
Y3  X 2 X 1 X 0
Y7  X 2 X 1 X 0
3 to 8 Decoder: Circuit
3 to 8 Decoder: Block Symbol
Symbol
Circuit
Design Example
Example

Using only a 3x8 decoder and twoinput OR gates, design a logic
circuit which implements the
following Boolean equation
F  a, b, c    m  2, 4,5
Solution
m2
m4
m5
2 to 4 Decoder with Enable
2x4 Decoder with Enable



Enable is abbreviated as EN
EN is called a Control Signal
Control Signals can be

Active High Signal


EN = 1 – Turns “ON” Decoder
Active Low Signal

EN=0 – Turns “ON” Decoder
2 x 4 Decoder with Active High Enable
– Truth Table
En x1 x0 y3 y2 y1 y0
0 0 0 0 0 0 0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
1
0
1
1
0
0
1
0
0
1
1
1
1
0
0
0
2 to 4 Decoder with Enable Equations
Y0  E n X 1 X 0
Y1  E n X 1 X 0
Y2  E n X 1 X 0
Y3  E n X 1 X 0
2 to 4 Decoder with Enable Circuit
2 to 4 Decoder with Enable Symbol
2 x 4 Decoder with Active High Enable
– Truth Table (Short hand notation)
En x1 x0 y3 y2 y1 y0
0 d d 0 0 0 0
1
0
0
0
0
0
1
1
0
1
0
0
1
0
1
1
0
0
1
0
0
1
1
1
1
0
0
0
d = don’t care
En has “highest” priority.
If En=0, we “don’t care” about x1 or x0 because Y=0
2 x 4 Decoder with Active Low Enable
– Truth Table (Short hand notation)
EnL x1 x0 y3 y2 y1 y0
1
d d
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
d = don’t care
En has “highest” priority.
If En=1, we “don’t care” about x1 or x0 because Y=0
2 to 4 Decoder with Active Low Enable
Circuit
Design Example
Example

Design a 3x8 decoder using only
2x4 decoders and NOT gates.
Solution
“On” when A=0
“On” when A=1
TPS Quiz
Encoders
Encoders


Opposite of a decoder
2n to n encoder



2n inputs
n outputs
For each input, the circuit will
produce an “encoded” output
Example: 4 to 2 Binary Encoder
Truth Table
X3
0
X2
0
X1
0
X0
1
Y1
0
Y0
0
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
0
1
1
Assume only one input high at a time!!
4 to 2 Encoder Equations
Y0  X 1  X 3
Y1  X 2  X 3
Problems with initial design


Q: How do we tell the difference
between an input of all 0’s (i.e.
X=0) and X=1?
A: Add another output (IA) that
indicates that the input is valid.
Let’s make IA active low.
IA  X 0  X 1  X 2  X 3
Problems with initial design
If IA = 1 => all lines are 0
If IA = 0 => at least one line is 1



Q: What happens if more than one input
is high at the same time?
A: Design a “priority” encoder that will
encode the input with the highest priority.
Let’s set X3 with the highest priority,
followed by X2, X1, and X0
Example: 4 to 2 Priority Binary Encoder
Truth Table
X3
0
X2
0
X1
0
X0
1
Y1
0
Y0
0
0
0
1
d
0
1
0
1
d
d
1
0
1
d
d
d
1
1
Solution
x3x2
x1x0 00
01
11
10
00
1
1
1
01
1
1
11
1
10
1
x3x2
x1x0 00
11
10
00
1
1
1
01
1
1
1
1
11
1
1
1
1
1
10
1
1
1
Y1
Y1  X 2  X 3
01
Y0
Y0  X 1 X 2  X 3
4 to 2 Priority Encoder Equations
Y0  X 1 X 2  X 3
Y1  X 2  X 3
IA  X 0  X 1  X 2  X 3
Multiplexer/Data Selectors
MUX
Very Important Module!!!
Multiplexer(MUX)/Data Selector

N to 1 multiplexer




n data input lines
Log2(n) control inputs
One output
This circuit will “connect” the
selected input to the output. The
selected input is specified by a
decoding of the control inputs.
Example: 4 to 1 MUX Truth Table
Control
Inputs
Data Inputs
Output
D3
d
D2
d
D1
d
D0
D0
A
0
B
0
F
D0
d
d
D1
d
0
1
D1
d
D2
d
d
1
0
D2
D3
d
d
d
1
1
D3
d = don’t care /
Di = data on input i
4 to 1 MUX Equation
F  D 0 A B  D1 AB  D 2 A B  D 3 A B
3
F 
Dm
i
i
i0
D’s are the DATA inputs, AB are control inputs and called
the “select” lines.
4 to 1 MUX Circuit
Control Inputs
Data Inputs
Output
2x4 Decoder
Only a single AND gate will
be “ON” at a time.
4 to 1 MUX Symbol
Data
Inputs
Control
Inputs
Output
Data and Control Paths
Control Path
Outputs
Logic
Data Path
Inputs
Data Path
Outputs
Control Path
Inputs
MUX Applications
Example

Using a 4x1 MUX, design a logic
circuit which implements:
Y  a b
We have,
Y
Y  D 0 A B  D 1 AB  D 2 A B  D 3 A B
Example

Using a 4x1 MUX, design a logic
circuit which implements:
a
0
b
0
Y
0
Dn
D0
0
1
1
D1
1
0
1
D2
1
1
0
D3
Y  a b
Y  0 A B  1 AB  1 A B  0 A B  AB  A B
Solution
Multibit Multiplexers
Multi-bit Multiplexers

J-bit nx1 mux
d0
d1
J bits
deep
d2
…
F
J bits
deep
dn-1
sel
j
F
 j    Di  j  mi
i0
j=0 to 3
log2n
This is just J separate nx1 multiplexers
Example 4-bit 4x1 MUX
D0[3..0]
D1[3..0]
D2[3..0]
D3[3..0]
D0[3..0]
D1[3..0]
D2[3..0]
F[3..0]
F[3..0]
4 bits
deep
D3[3..0]
A
B
A
B
3
F
 j    Di  j  mi
i0
j=0 to 3
This is just 4 separate 4x1 muxes
Example

4-bit 4x1 MUX
F  0   D 0  0  A B  D1  0  AB  D 2  0  A B  D 3  0  AB
Bit 0
F 1  D 0 1 A B  D1 1 AB  D 2 1 A B  D 3 1 AB
Bit 1
F  2   D 0  2  A B  D1  2  AB  D 2  2  A B  D 3  2  AB
Bit 2
F  3   D 0  3  A B  D1  3  AB  D 2  3  A B  D 3  3  AB
Bit 3
Example 4 bit 4x1 MUX

For the jth output, we have
D0[j]
D1[j]
D2[j]
D3[j]
A
B
F[j]
Example 4 bit 4x1 MUX

For the bit 0 output, we have
D0[0]
D1[0]
D2[0]
D3[0]
A
B
F[0]
Example 4 bit 4x1 MUX

For the bit 1 output, we have
D0[1]
D1[1]
D2[1]
D3[1]
A
B
F[1]
Example 4 bit 4x1 MUX

For the bit 2 output, we have
D0[2]
D1[2]
D2[2]
D3[2]
A
B
F[2]
Example 4 bit 4x1 MUX

For the bit 3 output, we have
D0[3]
D1[3]
D2[3]
D3[3]
A
B
F[3]
Example 4 bit 4x1 Mux
Complete Circuit
Bit 0
Bit 1
Bit 2
Bit 3
F[0]
F[1]
F[2]
F[3]
Example 4 bit 4x1 MUX

Symbol
Design Example
Using a 4bit 4x1 MUX, design a 8bit
4x1 MUX

Solution
DeMultiplexers/
Data Distributors
Demultiplexer/Data Distributor


Opposite of a multiplexer
1 to N demultiplexer




1 data input
N data outputs
Log2(n) control inputs
This circuit will “connect” a data
input to one and only one output.
The selected output is specified by a
decoding of the control inputs.
Example: 1 to 4 DeMUX Truth Table
D
D
A
0
B
0
F3
0
F2
0
F1
0
F0
D
D
0
1
0
0
D
0
D
1
0
0
D
0
0
D
1
1
D
0
0
0
d = don’t care /
Di = data on input i
1 to 4 DeMUX Equations
F3  DAB  Dm 3
F2  D A B  D m 2
F1  D AB  D m 1
F0  D A B  D m 0
Fj  Dm j
D is the DATA inputs, AB are control inputs and called
the “select” lines.
1 to 4 DEMUX Circuit
Only one
F will be
active
2x4 Decoder
Only 1 AND gate will
be “ON”
1 to 4 DEMUX Symbol
Selected
Lines
Data
Input
Outputs
Example

Design a 3x8 decoder using only
2x4 decoders and NOT gates.
Solution
“On” when A=0
“On” when A=1
TPS Quiz
Basic Arithmetic Elements

S=A+B (arithmetic sum)
A
0
B
0
S1
0
S0
0
0
1
0
1
1
0
0
1
1
1
1
0
S0  a  b
S1  ab

S=A+B+C (arithmetic sum)
A
0
B
0
C
0
S1
0
S0
0
A
1
B
0
C
0
S1
0
S0
1
0
0
1
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
S0  a  b  c
S1  ab  ac  bc
S0  a  b  c
S1  ab  ac  bc
You can show!!!
S1  ab  c  a  b 
Synthesis
Logic Equation
S (0)  A  B  C
Logic Circuit
Synthesis
Logic Equation
S (1)  AB  C  A  B 
Logic Circuit
Synthesis
12
13
14
A A
B B
C Cin
XOR
INPUT
VCC
INPUT
VCC
XOR
10
OUTPUT
15
11
sum
S(0)
INPUT
VCC
AND2
16
OR2
OUTPUT
19
AND2
17
S(0)
S(1)
Simulation
18
S(1)
cout
Verification
We verify the circuit via a simulation
Logic Simulation
Inputs
S(0)
S(1)
S 00 01 01 10 01 01 01 11
Outputs
Verification Summary
12
13
14
A A
B B
C Cin
XOR
INPUT
VCC
INPUT
VCC
XOR
10
OUTPUT
15
11
sum
S(0)
INPUT
VCC
AND2
16
OR2
OUTPUT
19
AND2
17
Circuit
S(0)
S(1)
Simulation
18
S(1)
cout
Documentation
12
13
14
A A
B B
C Cin
XOR
INPUT
VCC
INPUT
VCC
XOR
10
OUTPUT
15
11
sum
S(0)
INPUT
VCC
AND2
16
OR2
OUTPUT
19
AND2
18
17
A
S(1)
S(0)
C
Block Diagram
S(1)
cout
Conceptualization

11 1
1111
1111
11110
For the “worst case” we need to add
three bits to generate a single output bit
with a possible carry out.
Can we use our single bit adder for this?


to create a ripple carry adder
The circuit gets its name because
the carry bit “ripples” from one bit
position to the next
Conceptualization
First, let’s look at two bits
A(1)
B(1)
A
S(1)
Sum(1)
S(0)
C
A(0)
B(0)
A
S(1)
Sum(0)
S(0)
C
Conceptualization
Let’s connect the two full adders
A(1)
B(1)
Cin
A(0)
B(0)
0
A
S(1)
S(1)
S(0)
C
Cout
A
S(1)
S(0)
S(0)
C
Set carry in for first bit to 0. Why?
Analysis
Let’s test this for a few cases:
0
0
0
0
0
0
A
S(1)
S(0)
C
A
S(1)
S(0)
C
0
0
0
0
00
00
000
Correct!!!
Rule of thumb: Always test simple cases first!!
Analysis
Let’s test this for the a few cases
1
1
1
1
1
0
A
S(1)
S(0)
C
A
S(1)
S(0)
C
1
1
1
0
11
11
110
Correct!!!
Analysis
Let’s test this for the a few cases
0
0
1
1
1
0
A
S(1)
S(0)
C
A
S(1)
S(0)
C
0
1
1
0
01
01
010
Correct!!!
Carry out
Carry in
Logic Simulation


Subtraction Circuit
Subtraction Circuit


Calculate 2’s complement of B
S  A  B  A   B   A  B  1
A
A
B
B
INV
B
Cin
1 1

S  A  B 1
A
A
S
Module
B
B
S
0
Functional
Result
S=A+B
1
S=A-B
Add is a control input. It is active low. This means
that the module will compute A+B when Add=0. It
Design using Modules
A
A
INV
B
B
2x1
MUX
B
A
Cin
S
A
A
INV
B
B
2x1
MUX
S  A B
B
A
Cin
S
0
0
Sub operation.
A
A
B
INV
B
B
2x1
MUX
S  A  B 1
B
A
Cin
S
1
1
TPS Quiz
17-18
Overflow/Underflow Detection
Numerical Overflow/Underflow

2’s complement number


We have S=A+B
Range of sum
2

n 1
S2
Overflow occurs if
S 2

n 1
n 1
1
Underflow occurs if
S  2
n 1
1
Example: Overflow

Let n=4, Range is
2  S  2  1
8  S  7
3

3
Let A=\$7, B=\$7, then
S=\$7+\$7=\$E, but \$E=%1110 = -2,
so Overflow has occurred.
Example: Overflow

Let’s examine this more closely
-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7
+7
8,9,A,B,C,D,E,F,0,1,2,3,4,5,6,7
So, overflow is the same as “wrap around.”
Example: Underflow



Let n=4, let A=-7 and B=-7,
in 2’s complement, A=B=\$9,
S=\$9+\$9=\$12=\$02
so underflow has occurred.
Example: Underflow

Let’s examine this more closely
-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7
+1
+6
So, underflow is the same as “wrap around.”
Overflow/Underflow Detection

How do we detect overflow and
underflow?

First adding a positive to a negative
number is always OK.


4 bit example: 7 + (-8) = -1
Let’s examine the sum of the MSB’s to
determine overflow and underflow.

Set V=1, if overflow/underflow occurs
Examination of MSB
a,b are the MSBs of A and B. cin is carry in; cout=carry out
b a cin S Co V Explanation
0 0 0
0 0 0 A+B < 2n-1 (OK)
0 0 1
1
0
1 A+B>2n-1 -1 (overflow)
0 1 0
1
0
0 -A+B (OK)
0 1 1
0
1
0 -A+B (OK)
1 0 0
1
0
0 A-B (OK)
1 0 1
0
1
0 A-B (OK)
1 1 0
0
1
1 -A-B< -2n-1 (underflow)
1 1 1
1
1
0 -A-B > -2n-1 (OK)
Overflow/Underflow Detection

We find
V  an1 bn1cin,n1  an1bn1 cin,n 1
Overflow/Underflow Detection

You can also use
V  cin ,n 1  cout , n 1

That is, if for the MSB carry_in is
not equal to carry_out, overflow or
underflow has occurred.
TPS Quiz
19-20
Comparators
Equal Comparator

Design a logic circuit which will
compute
F0 = (A = B)
2-bit Equal Comparator Truth Table
b1 b0 a1 a0 F0
0 0 0 0 1
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
0
2-bit Equal Comparator Truth Table
b1 b0 a1 a0 F0
1 0 0 0 0
1
0
0
1
0
1
0
1
0
1
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
Solution
You can show,

F0  a1  b1
 a
0
 b0

N-bit Equal Comparator

F0  an 1  bn 1
  a  b  a
1
1
0
 b0

Not Equal Comparator

Design a logic circuit which will
compute
F = (A <> B)
F = (A = B)
i.e. Just invert our Equal Comparator circuit
Magnitude Comparator

Design a logic circuit which will
compute
F2 = (A>B)
F1 = (A<B)
Let’s develop a truth table for 2-bits
2-bit Magnitude (unsigned) Comparator
Truth Table
b1 b0 a1 a0 F2 F1
0 0 0 0 0 0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
1
0
0
1
1
1
1
0
2-bit Magnitude (unsigned) Comparator
Truth Table
b1 b0 a1 a0 F2 F1
1 0 0 0 0 1
1
0
0
1
0
1
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
0
0
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
0
0
You can show
F2  a1 b1  a0 b1 b0  a1a0 b0
F1  a1b1  a1 a0b0  a0b1b0
TPS Quiz
21
Arithmetic Logic Units (ALUs)
Arithmetic Logic Unit (ALU)
A[n-1,,0]
ALU
B[n-1..0]
S[m-1..0]
F
A,B are data inputs of n bits each in depth
S is a control input. We have 2m operations
F is the output
Example




Let n=4,m=3
We have A[3..0] and B[3..0]
With m=3, we have 23 = 8 operations
Let’s look at a possible function table
Function Table
s2 s1 s0
0 0 0
Function
F=AB
0
0
1
F=A+B (logical OR)
0
1
0
F=NOT A
0
1
1
F=A XOR B
1
0
0
F=A+B (Arithmetic)
1
0
1
F=A-B
1
1
0
F=A + 1
1
1
1
F=A - 1
Design using a Truth Table

How large is the truth table?






2n from data inputs A and B
 Example: n=8, we have 16 data inputs
 A[7..0] and B[7..0]
3 control inputs
Total of 2n+3 inputs
 N=8, we have 19 inputs
Our truth table will have
192 (361) rows and 8 outputs
Too complex. Let’s explore another
alternative using a “system” or modular
approach
Design using Modules

Note:




For S2=0, we have logic operations
For S2=1, we have arithmetic
operations
So, let’s use S2 to control a 2x1 MUX
to select between logic and arithmetic
operations, so our top level design
would look like:
ALU Design
A
B
A
B
Logic
Module
F
A
S[1..0]
B
A
B
2x1
F
MUX
Arithmetic
Module
S[1..0]
F
S[2]
F
ALU Design S2=0
A
B
A
B
Logic
Module
F
A
S[1..0]
F
B
A
B
2x1
F
MUX
Arithmetic
Module
S[1..0]
F
S[2]
With S2=0, F is the output from
the logic module
ALU Design S2=1
A
B
A
B
Logic
Module
F
A
S[1..0]
F
B
A
B
2x1
F
MUX
Arithmetic
Module
S[1..0]
F
S[2]
With S2=1, F is the output from
the arithmetic module
Logic Module Design
Function Table for Logic Module

S2=0
s2 s1 s0
0 0 0
Function
F=AB
0
0
1
F=A+B (logical OR)
0
1
0
F=NOT A
0
1
1
F=A XOR B
We can use a 4x1 mux to
implement this module
Logic Module Design
A
B
A
AND F
B
A
A
OR F
B
B
C
4
X
1
D
A NOT F
S[1..0]
S1 S0
A
XOR F
B
F
Logic Module Design
A
B
A
AND F
B
A
A
OR F
B
B
4
X
1
C
F
F=AB
D
A NOT F
S[1..0]
S1 S0
A
XOR F
B
0
0
AND Operation
S[1..0]=00
Logic Module Design
A
B
A
AND F
B
A
A
OR F
B
B
4
X
1
C
F
F=A+B
D
A NOT F
S[1..0]
S1 S0
A
XOR F
B
0
1
OR Operation
S[1..0]=01
Logic Module Design
A
B
A
AND F
B
A
A
OR F
B
B
4
X
1
C
F
F=A
D
A NOT F
S[1..0]
S1 S0
A
XOR F
B
1
0
NOT Operation
S[1..0]=10
Logic Module Design
A
B
A
AND F
B
A
A
OR F
B
B
4
X
1
C
F
F=A XOR B
D
A NOT F
S[1..0]
S1 S0
A
XOR F
B
1
1
XOR Operation
S[1..0]=11
What do these logic modules
look like?
AND Module
A
AND F
B
OR Module
A
OR
B
F
NOT Module
A
NOT
F
XOR Module
A
XOR
B
Arithmetic Module
A
A
S
Module
B
B
S
Function Table for Arithmetic Ops
s2 s1 s0
1 0 0
Function
F=A+B (Arithmetic)
1
0
1
F=A-B
1
1
0
F=A + 1
1
1
1
F=A - 1
Note:
S0 can be use to indicate Addition or Subtraction.
S1 can be use to indicate the B data input
Arithmetic Module Design
A
A
Module
B
A
VDD
B
2
X
1
F
B
S
S1
S0
S
S
Arithmetic Module Design
A
A
Module
B
A
VDD
B
2
X
1
F
B
0
S
F=A+B
S[1..0]=00
S
S1
S
S0
0
Arithmetic Module Design
A
A
Module
B
A
VDD
B
2
X
1
F
B
0
S
F=A-B
S[1..0]=01
S
S1
S
S0
1
Arithmetic Module Design
A
A
Module
B
A
VDD
B
2
X
1
F
B
1
S
F=A+1
S[1..0]=10
S
S1
S
S0
0
Arithmetic Module Design
A
A
Module
B
A
VDD
B
2
X
1
F
B
1
S
F=A-1
S[1..0]=11
S
S1
S
S0
1
Overall Design
We have
ALU Design
A
B
A
B
Logic
Module
F
A
S[1..0]
B
A
B
2x1
F
MUX
Arithmetic
Module
S[1..0]
F
S[2]
F
Logic Module Design
A
B
A
AND F
B
A
A
OR F
B
B
C
4
X
1
D
A NOT F
S[1..0]
S1 S0
A
XOR F
B
F
Arithmetic Module Design
A
A
Module
B
A
VDD
B
2
X
1
F
B
S
S1
S0
S
S
Total Design
A
B
A
AND F
B
Logic Module
A
A
OR
F
B
B
4
X
1
C
F
D
A NOT F
S[1..0]
S1
S0
A
A
XOR F
B
B
2
X
1
F
S
S2
A
Module
A
VDD
B
2
X
1
F
B