04_Chapter 4768 - Modular Comb logic.ppt

logicxvf

1. Chapter 4
Modular Combinational Logic

2. Decoders

3. Decoders
n to 2
n
decoder
n inputs
2
n
outputs
For each input, one and only one output
will be active.
Uses:
“Minterm generator”
Wordline (memory) circuit
Code conversion
Routing data

4. 2 to 4 Decoder Example

5. 2 to 4 Decoder – Truth Table
2 to 4 decoder
X1X0Y3Y2Y1Y0
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0

6. 2 to 4 Decoder Equations
0 1 0
1 1 0
2 1 0
3 1 0
Y XX
Y XX
Y XX
Y XX





7. 2 to 4 Decoder: Circuit

8. 2 to 4 Decoder: Block Symbol
Symbol
Circuit

9. 3 to 8 Decoder Example

10. 3 to 8 Decoder – Truth Table
x2x1x0y7y6y5y4y3y2y1y0
00000000001
00100000010
01000000100
01100001000
10000010000
10100100000
11001000000
11110000000

11. 3 to 8 Decoder Equations
0 2 1 0
1 2 1 0
2 2 1 0
3 2 1 0
Y X X X
Y X X X
Y X X X
Y X X X




4 2 1 0
5 2 1 0
6 2 1 0
7 2 1 0
Y X X X
Y X X X
Y X X X
Y X X X





12. 3 to 8 Decoder: Circuit

13. 3 to 8 Decoder: Block Symbol
Symbol
Circuit

14. Design Example

15. Example
Using only a 3x8 decoder and two-
input OR gates, design a logic
circuit which implements the
following Boolean equation
   , , 2,4,5F abc m

16. Solution
m2
m4
m5

17. 2 to 4 Decoder with Enable

18. 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

19. 2 x 4 Decoder with Active High Enable
– Truth Table
Enx1x0y3y2y1y0
0000000
0010000
0100000
0110000
1000001
1010010
1100100
1111000

20. 2 to 4 Decoder with Enable Equations
0 1 0
1 1 0
2 1 0
3 1 0
n
n
n
n
Y EXX
Y EXX
Y EXX
Y EXX





21. 2 to 4 Decoder with Enable Circuit

22. 2 to 4 Decoder with Enable Symbol

23. 2 x 4 Decoder with Active High Enable
– Truth Table (Short hand notation)
Enx1x0y3y2y1y0
0dd0000
1000001
1010010
1100100
1111000
d = don’t care
En has “highest” priority.
If En=0, we “don’t care” about x1 or x0 because Y=0

24. 2 x 4 Decoder with Active Low Enable
– Truth Table (Short hand notation)
EnLx1x0y3y2y1y0
1dd0000
0000001
0010010
0100100
0111000
d = don’t care
En has “highest” priority.
If En=1, we “don’t care” about x1 or x0 because Y=0

25. 2 to 4 Decoder with Active Low Enable
Circuit

26. Design Example

27. Example
Design a 3x8 decoder using only
2x4 decoders and NOT gates.

28. Solution
“On” when A=1
“On” when A=0

29. TPS Quiz

30. Encoders

31. Encoders
Opposite of a decoder
2
n
to n encoder
2
n
inputs
n outputs
For each input, the circuit will
produce an “encoded” output

32. Example: 4

to 2 Binary Encoder
Truth Table
X3X2X1X0Y1Y0
0 0 0 1 0 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!!

33. 4 to 2 Encoder Equations
0 1 3
1 2 3
Y X X
Y X X
 
 

34. 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.
0 1 2 3
IA X X X X   

35. 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

36. Example: 4

to 2 Priority Binary Encoder
Truth Table
X3X2X1X0Y1Y0
0 0 0 1 0 0
0 0 1 d 0 1
0 1 d d 1 0
1 d d d 1 1

37. Solution
x3x2
x1x0
00 0111 10
00
01
11
10
Y1
x3x2
x1x0
00 0111 10
00
01
11
10
Y0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1 2 3
Y X X 
0 1 2 3
Y X X X 

38. 4 to 2 Priority Encoder Equations
0 1 2 3
1 2 3
Y XX X
Y X X
 
 
0 1 2 3
IA X X X X   

39. Multiplexer/Data Selectors
MUX
Very Important Module!!!

40. Multiplexer(MUX)/Data Selector
N to 1 multiplexer
n data input lines
Log
2(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.

41. Example: 4

to 1 MUX Truth Table
D3D2D1D0A B F
d d d D00 0 D0
d d D1d 0 1 D1
d D2d d 1 0 D2
D3d d d 1 1 D3
d = don’t care / Di = data on input i
Data Inputs
Control
Inputs
Output

42. 4 to 1 MUX Equation
0 1 2 3
F DAB DAB DAB DAB   
3
0
i i
i
F Dm


D’s are the DATA inputs, AB are control inputs and called
the “select” lines.

43. 4 to 1 MUX Circuit
2x4 Decoder
Only a single AND gate will
be “ON” at a time.
Output
Control Inputs
Data Inputs

44. 4 to 1 MUX Symbol
Data
Inputs
Control
Inputs
Output

45. Data and Control Paths
Logic
Data Path
Inputs
Data Path
Outputs
Control Path
Inputs
Control Path
Outputs

46. MUX Applications

47. Example
Using a 4x1 MUX, design a logic
circuit which implements:
Y a b 
We have,
Y
0 1 2 3
Y D AB D AB D AB D AB   

48. Example
Using a 4x1 MUX, design a logic
circuit which implements:
Y a b 
a b Y Dn
0 0 0 D0
0 1 1 D1
1 0 1 D2
1 1 0 D3
0 1 1 0Y AB AB AB AB AB AB     

49. Solution

50. Multibit Multiplexers

51. Multi-bit Multiplexers
J-bit nx1 mux
sel
d0
d1
…
dn-1
d2
F
J bits
deep
log
2n
J bits
deep
 
0
j
i i
i
F j D j m


j=0 to 3
This is just J separate nx1 multiplexers

52. Example 4-bit 4x1 MUX
A B
D0[3..0]
D1[3..0]
D3[3..0]
D2[3..0]
F[3..0] 4 bits
deep
D0[3..0]
D1[3..0]
D2[3..0]
D3[3..0]
A B
F[3..0]
 
3
0
i i
i
F j D j m


j=0 to 3 This is just 4 separate 4x1 muxes

53. Example
4-bit 4x1 MUX
   
0 1 2 3
0 0 0 0 0F D AB D AB D AB D AB   
   
0 1 2 3
1 1 1 1 1F D AB D AB D AB D AB   
   
0 1 2 3
2 2 2 2 2F D AB D AB D AB D AB   
   
0 1 2 3
3 3 3 3 3F D AB D AB D AB D AB   
Bit 0
Bit 3
Bit 2
Bit 1

54. Example 4 bit 4x1 MUX
For the jth output, we have
D0[j]
D1[j]
D2[j]
D3[j]
A
B
F[j]

55. Example 4 bit 4x1 MUX
For the bit 0 output, we have
D0[0]
D1[0]
D2[0]
D3[0]
A
B
F[0]

56. Example 4 bit 4x1 MUX
For the bit 1 output, we have
D0[1]
D1[1]
D2[1]
D3[1]
A
B
F[1]

57. Example 4 bit 4x1 MUX
For the bit 2 output, we have
D0[2]
D1[2]
D2[2]
D3[2]
A
B
F[2]

58. Example 4 bit 4x1 MUX
For the bit 3 output, we have
D0[3]
D1[3]
D2[3]
D3[3]
A
B
F[3]

59. Example 4 bit 4x1 Mux
F[0]
F[1]
F[2]
F[3]
Complete Circuit
Bit 0
Bit 1
Bit 2
Bit 3

60. Example 4 bit 4x1 MUX
Symbol

61. Design Example
Using a 4bit 4x1 MUX, design a 8bit
4x1 MUX

62. Solution

63. DeMultiplexers/
Data Distributors

64. Demultiplexer/Data Distributor
Opposite of a multiplexer
1 to N demultiplexer
1 data input
N data outputs

Log
2
(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.

65. Example: 1

to 4 DeMUX Truth Table
D A B F3F2F1F0
D 0 0 0 0 0 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

66. 1 to 4 DeMUX Equations
3 3
F DAB Dm 
j j
F Dm
D is the DATA inputs, AB are control inputs and called
the “select” lines.
1 1
F DAB Dm 
2 2
F DAB Dm 
0 0
F DAB Dm 

67. 1 to 4 DEMUX Circuit
Only 1 AND gate will
be “ON”
2x4 Decoder
Only one
F will be
active

68. 1 to 4 DEMUX Symbol
Data
Input
Selected
Lines
Outputs

69. Example
Design a 3x8 decoder using only
2x4 decoders and NOT gates.

70. Solution
“On” when A=1
“On” when A=0

71. TPS Quiz

72. Basic Arithmetic Elements
Half Adder

73. Half Adder-Truth Table
S=A+B (arithmetic sum)
A B S1S0
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
0
S a b 
1
S ab

74. Half Adder Circuit

75. Full Adder-Truth Table
S=A+B+C (arithmetic sum)
ABCS1S0
00000
00101
01001
01110
0
S a b c  
1
S ab ac bc  
ABCS1S0
10001
10110
11010
11111

76. Full Adder
0
S a b c  
1
S ab ac bc  
You can show!!!

1
S ab c a b  

77. Synthesis
(0)S A B C  
Logic Equation
Logic Circuit

78. Synthesis
 (1)S AB CA B  
Logic Equation
Logic Circuit

79. 17
AND2 18
OR2
19 cout
OUTPUT
16
AND2
VCC14 Cin
INPUT
VCC13 B
INPUT
10
XOR
11
XOR
15 sum
OUTPUT
VCC12 A
INPUT
Synthesis
Full Adder Circuit
S(0)
S(1)
C
A
B
S(0)
S(1)
Simulation

80. Verification
S(0)
S(1)
We verify the circuit via a simulation
Logic Simulation
Inputs
Outputs
S 00 01 01 10 01 01 01 11

81. 17
AND2 18
OR2
19 cout
OUTPUT
16
AND2
VCC14 Cin
INPUT
VCC13 B
INPUT
10
XOR
11
XOR
15 sum
OUTPUT
VCC12 A
INPUT
Verification Summary
S(0)
S(1)
C
A
B
S(0)
S(1)
Simulation
Circuit

82. Documentation
17
AND2 18
OR2
19 cout
OUTPUT
16
AND2
VCC14 Cin
INPUT
VCC13 B
INPUT
10
XOR
11
XOR
15 sum
OUTPUT
VCC12 A
INPUT
S(0)
S(1)
C
A
B
FullAdder
C
A
B
S(0)
S(1)
Block Diagram

83. Ripple Carry Adder

84. Conceptualization
4-bit adder (worst case)
1111
1111
11110
111
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?

85. Ripple Carry Adder
We can cascade several full adders
to create a ripple carry adder
The circuit gets its name because
the carry bit “ripples” from one bit
position to the next

86. Conceptualization
FullAdder
C
A
B
S(0)
S(1)
FullAdder
C
A
B
S(0)
S(1)
First, let’s look at two bits
A(0)
B(0)
B(1)
A(1)
Sum(0)
Sum(1)
What about the carry?

87. Conceptualization
FullAdder
C
A
B
S(0)
S(1)
FullAdder
C
A
B
S(0)
S(1)
Let’s connect the two full adders
A(0)
B(0)
B(1)
A(1)
S(0)
S(1)
Set carry in for first bit to 0. Why?
Cout
Cin
0

88. Analysis
FullAdder
C
A
B
S(0)
S(1)
FullAdder
C
A
B
S(0)
S(1)
Let’s test this for a few cases:
0
0
0
0
0
0
0
0
0
0
00
00
000
Correct!!!
Rule of thumb: Always test simple cases first!!

89. Analysis
FullAdder
C
A
B
S(0)
S(1)
FullAdder
C
A
B
S(0)
S(1)
Let’s test this for the a few cases
0
1
1
1
1
1
1
0
1
1
11
11
110
Correct!!!

90. Analysis
FullAdder
C
A
B
S(0)
S(1)
FullAdder
C
A
B
S(0)
S(1)
Let’s test this for the a few cases
1
1
0
0
0
1
1
1
0
0
01
01
010
Correct!!!

91. Four Bit “Ripple” Adder
Carry in
Carry out

92. Logic Simulation

93. 8-bit Ripple Carry Adder
Use two 4-bit adders

94. 16-bit Ripple Carry Adder
Use two 8-bit adders

95. Subtraction Circuit

96. Subtraction Circuit
Calculate 2’s complement of B
Add –B to A
ADDER
INV
A
B
S
1
Cin
A
B
 1S A B A B A B       
B
1
1S A B  

97. Add/Sub Circuit

98. Add/Sub Circuit Module
Add/Sub
Module
A
B
S
Add
A
B
Add
S

99. Function Table for Add/Sub Module
Add Functional
Result
0 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
will compute A-B when Add=1.

100. Add/Sub Circuit
Design using Modules

101. Add/Sub Circuit
ADDER
INV
2x1
MUX
A
B
S
B
B
A
S Cin
A
Add

102. Add/Sub Circuit
ADDER
INV
2x1
MUX
A
B
S
B
B
A
S Cin
A
Add
Add operation. Add=0
0 0
S A B 

103. Add/Sub Circuit
ADDER
INV
2x1
MUX
A
B
S
B
B
A
S Cin
A
Add
Sub operation. Add=1
1 1
1S A B  
B

104. TPS Quiz
17-18

105. Overflow/Underflow Detection

106. Numerical Overflow/Underflow
2’s complement number
We have S=A+B
Range of sum
Overflow occurs if
Underflow occurs if
1 1
2 2 1
n n
S
 
   
1
2 1
n
S

 
1
2
n
S



107. Example: Overflow
Let n=4, Range is
Let A=$7, B=$7, then S=$7+
$7=$E, but $E=%1110 = -2, so
Overflow has occurred.
8 7S  
3 3
2 2 1S   

108. 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
So, overflow is the same as “wrap around.”
8,9,A,B,C,D,E,F,0,1,2,3,4,5,6,7

109. 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.

110. Example: Underflow
Let’s examine this more closely
-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7
+6
So, underflow is the same as “wrap around.”
+1

111. 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

112. Examination of MSB
bacinSCoVExplanation
000000A+B < 2
n-1
(OK)
001101A+B>2
n-1
-1 (overflow)
010100-A+B (OK)
011010-A+B (OK)
100100A-B (OK)
101010A-B (OK)
110011-A-B< -2
n-1
(underflow)
111110-A-B > -2
n-1
(OK)
a,b are the MSBs of A and B. cin is carry in; cout=carry out

113. Overflow/Underflow Detection
We find
1 1 , 1 1 1 , 1n n in n n n in n
V a b c a b c
     
 

114. Overflow/Underflow Detection
, 1 , 1in n out n
V c c
 
 
You can also use
That is, if for the MSB carry_in is
not equal to carry_out, overflow or
underflow has occurred.

115. TPS Quiz
19-20

116. Comparators

117. Equal Comparator
Design a logic circuit which will
compute
F0 = (A = B)

118. 2-bit Equal Comparator Truth Table
b1b0a1a0F0
00001
00010
00100
00110
01000
01011
01100
01110

119. 2-bit Equal Comparator Truth Table
b1b0a1a0F0
10000
10010
10101
10110
11000
11010
11100
11111

120. Solution
  0 1 1 0 0
F a b a b  
You can show,

121. N-bit Equal Comparator
   0 1 1 1 1 0 0n n
F a b a b a b
 
   

122. Not Equal Comparator
Design a logic circuit which will
compute
F = (A <> B)
F = (A = B)
i.e. Just invert our Equal Comparator circuit

123. Magnitude Comparator
Design a logic circuit which will
compute
F2 = (A>B)
F1 = (A<B)
Let’s develop a truth table for 2-bits

124. 2-bit Magnitude (unsigned) Comparator
Truth Table
b1b0a1a0F2F1
000000
000110
001010
001110
010001
010100
011010
011110

125. 2-bit Magnitude (unsigned) Comparator
Truth Table
b1b0a1a0F2F1
100001
100101
101000
101110
110001
110101
111001
111100

126. You can show
2 1 1 0 1 0 1 0 0
F ab abb aab  
1 1 1 1 0 0 0 1 0
F ab aab abb  

127. TPS Quiz
21

128. Arithmetic Logic Units (ALUs)

129. Arithmetic Logic Unit (ALU)
ALU
A[n-1,,0]
B[n-1..0]
F
S[m-1..0]
A,B are data inputs of n bits each in depth
S is a control input. We have 2
m
operations
F is the output

130. Example
Let n=4,m=3
We have A[3..0] and B[3..0]
With m=3, we have 2
3
= 8 operations
Let’s look at a possible function table

131. Function Table
s2s1s0Function
000F=AB
001F=A+B (logical OR)
010F=NOT A
011F=A XOR B
100F=A+B (Arithmetic)
101F=A-B
110F=A + 1
111F=A - 1

132. 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
19
2
(361) rows and 8 outputs
Too complex. Let’s explore another
alternative using a “system” or modular
approach

133. 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:

134. ALU Design
Logic
Module
Arithmetic
Module
2x1
MUX
S[2]
AB
A
A
B
F
A
B
F
S[1..0]
S[1..0]
B
F
F

135. ALU Design S2=0
Logic
Module
Arithmetic
Module
2x1
MUX
S[2]
AB
A
A
B
F
A
B
F
S[1..0]
S[1..0]
B
F
F
With S2=0, F is the output from
the logic module

136. ALU Design S2=1
Logic
Module
Arithmetic
Module
2x1
MUX
S[2]
AB
A
A
B
F
A
B
F
S[1..0]
S[1..0]
B
F
F
With S2=1, F is the output from
the arithmetic module

137. Logic Module Design

138. Function Table for Logic Module
S2=0
s2s1s0Function
000F=AB
001F=A+B (logical OR)
010F=NOT A
011F=A XOR B
We can use a 4x1 mux to
implement this module

139. Logic Module Design
OR
NOT
XOR
AND
A
B
C
D
4
X
1
F
S[1..0]
S1S0
A
A
B
F
A
B
F
A
B
F
A F
B

140. Logic Module Design
OR
NOT
XOR
AND
A
B
C
D
4
X
1
F
S[1..0]
S1S0
A
A
B
F
A
B
F
A
B
F
A F
B
AND Operation
S[1..0]=00
0 0
F=AB

141. Logic Module Design
OR
NOT
XOR
AND
A
B
C
D
4
X
1
F
S[1..0]
S1S0
A
A
B
F
A
B
F
A
B
F
A F
B
OR Operation
S[1..0]=01
0 1
F=A+B

142. Logic Module Design
OR
NOT
XOR
AND
A
B
C
D
4
X
1
F
S[1..0]
S1S0
A
A
B
F
A
B
F
A
B
F
A F
B
NOT Operation
S[1..0]=10
1 0
F=A

143. Logic Module Design
OR
NOT
XOR
AND
A
B
C
D
4
X
1
F
S[1..0]
S1S0
A
A
B
F
A
B
F
A
B
F
A F
B
XOR Operation
S[1..0]=11
1 1
F=A XOR B

144. What do these logic modules
look like?

145. AND Module
AND
A
B
F

146. OR Module

147. NOT Module
NOTA F

148. XOR Module

149. Arithmetic Module
Let’s use our ADD/SUB Module

150. Add/Sub Circuit Module
Add/Sub
Module
A
B
S
Add
A
B
Add
S

151. Function Table for Arithmetic Ops
s2s1s0Function
100F=A+B (Arithmetic)
101F=A-B
110F=A + 1
111F=A - 1
Note:
S0 can be use to indicate Addition or Subtraction.
S1 can be use to indicate the B data input

152. Arithmetic Module Design
Add/Sub
Module
S0
A
B
Add
S
S
2
X
1
A
B
F
VDD
S1
B
A
S

153. Arithmetic Module Design
Add/Sub
Module
S0
A
B
Add
S
S
2
X
1
A
B
F
VDD
S1
B
A
S
0
0
F=A+B
S[1..0]=00

154. Arithmetic Module Design
Add/Sub
Module
S0
A
B
Add
S
S
2
X
1
A
B
F
VDD
S1
B
A
S
1
0
F=A-B
S[1..0]=01

155. Arithmetic Module Design
Add/Sub
Module
S0
A
B
Add
S
S
2
X
1
A
B
F
VDD
S1
B
A
S
0
1
F=A+1
S[1..0]=10

156. Arithmetic Module Design
Add/Sub
Module
S0
A
B
Add
S
S
2
X
1
A
B
F
VDD
S1
B
A
S
1
1
F=A-1
S[1..0]=11

157. Overall Design
We have

158. ALU Design
Logic
Module
Arithmetic
Module
2x1
MUX
S[2]
AB
A
A
B
F
A
B
F
S[1..0]
S[1..0]
B
F
F

159. Logic Module Design
OR
NOT
XOR
AND
A
B
C
D
4
X
1
F
S[1..0]
S1S0
A
A
B
F
A
B
F
A
B
F
A F
B

160. Arithmetic Module Design
Add/Sub
Module
S0
A
B
Add
S
S
2
X
1
A
B
F
VDD
S1
B
A
S

161. Total Design
OR
NOT
XOR
AND
A
B
C
D
4
X
1
F
S[1..0]
Add/Sub
Module
A
S
S0
A
B
Add
S
B
S
F
2
X
1
S2
S
2
X
1
A
B
F
VDD
S1S0
S1
A B
A
B
F
A
B
F
A
B
F
A F
Logic Module
Arithmetic Module

162. End of Chapter 4