Transcript Chapter 3 Combinational Logic

Chapter 3 Combinational Logic
?
Digital Design Lab.
Digital Design Lab
 3.1 Logic Primitive Gates
 AND function
(a)
(b)
(c)
Figure 1 Logic symbols and wave forms for the AND
function: (a) AND gate, (b) NAND gate, and (c) NOR gate.
?
Digital Design Lab.
Digital Design Lab
2
 Or function
(a)
(b)
(c)
Figure 2 Logic symbols and wave forms for the OR function.
?
Digital Design Lab.
Digital Design Lab
3
 Exclusive-OR function
(a)
(b)
Figure 3 Exclusive-OR function: (a) logic diagram and
waveforms, and (b) symbol for the exclusive-OR logic function.
?
Digital Design Lab.
Digital Design Lab
4
 Exclusive-NOR function
(a)
(b)
Figure 4 Exclusive-NOR function: (a) logic diagram and
waveforms, and (b) symbol for the exclusive-NOR logic function.
?
Digital Design Lab.
Digital Design Lab
5
x1
x2
z1
x1
x2
z1
x1
x2
z1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
0
Table 1 Truth Table for the AND Gate
Table 2 Truth Table for the OR Gate
Table 3 Truth Table for the Exclusive-OR Function
x1
x2
z1
x1
x2
z1
x1
x2
z1
0
0
1
0
0
1
0
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
Table 4 Truth Table for the NAND Gate
Table 5 Truth Table for the NOR Gate
?
Digital Design Lab.
Table 6 Truth Table for the Exclusive-NOR Function
Digital Design Lab
6
 Fan-In
 Logic gates for the AND and OR functions can be extended to
accommodate more than two variables; that is more than two
inputs.
 The number of inputs available at a logic gate is called the fanin.
 Current technology allows for gates with a large number of
inputs.
Figure 5 Increasing the fan-in capability of an AND gate
?
Digital Design Lab.
Digital Design Lab
7
 Fan-Out
 The fan-out of a logic gate is the maximum number of inputs
that the gate can drive and still maintain acceptable voltage and
current levels.
 That is, the fan-out defines the maximum load that the gate can
handle.
Figure 6 Example of fan-out
?
Digital Design Lab.
Digital Design Lab
8
 Propagation Delay




This is the time associated with a logic circuit that is
defined as the time interval between an input change and
the resulting output change, either from a logic 1 to a logic
0 or vice versa.
Also associated with propagation delay is the rise time and
fall time of a signal.
The rise time of a signal is the time required to go from a
logic 0 to a logic 1 voltage level.
The fall time of a signal is the time required to go from a
logic 1 to a logic 0 voltage level.
?
Digital Design Lab.
Digital Design Lab
9
Figure 7 Example of propagation delay
?
Digital Design Lab.
Digital Design Lab
10
 3.1.1 Wired-AND and Wired-OR Operations
 Additional logic functions can be realized by wiring together
the outputs of certain types of logic gates.
 The wired-logic function is not a physical gate, but only a
symbol that represents the logical function obtained by the
wired connection.
Figure 8 Wired-OR circuit for the function z1 = x1x2` + x3x4 using
TTL NAND gates.
?
Digital Design Lab.
Digital Design Lab
11
 3.1.2 Three-State Logic
 Three-state logic is used primarily to connect logical devices to
a common bus structure.
 A three-state device can be a gate, a buffer, or a logic macro
function.
 A three-state circuit is one in which the output exhibits three
states under control of an enable input:
 (1) a logic 0 state if the input is a logic 0 and the enable
input is asserted.
 (2) a logic 1 state if the input is a logic 1 and the enable
input is asserted.
 (3) a high-impedance state if the enable input is deasserted,
which effectively removes the device from the bus.
?
Digital Design Lab.
Digital Design Lab
12
(a)
(b)
Figure 8 Three-state devices: (a) buffer and (b) inverter.
?
Digital Design Lab.
Digital Design Lab
13
 3.1.3 Functionally Complete Gates
 Both NAND and NOR gates have the unique characteristic that
they can express any Boolean function; that is, they can
represent the functions AND, OR, and NOT.
 Thus, NAND and NOR gates are classified as functionally
complete gates or universal gates.
 Using Boolean algebra, it can be shown that the NAND
gate can generate the NOT function, as follows:

(x1x1)` = x1` + x1` = x1`
Using Boolean algebra, it can be shown that the NOR gate
can generate the NOT function, as follows:
(x1+ x1)` = x1`x1` = x1`
?
Digital Design Lab.
Digital Design Lab
14
(a)
(b)
Figure 9 NAND and NOR gates to implement the NOT (invert)
function: (a) NAND gate and (b) NOR gate.
(a)
(b)
Figure 10 NAND gate to implement the AND function: (a)
active-low output and (b) active – high output.
?
Digital Design Lab.
Digital Design Lab
15
(a)
(b)
Figure 11 NOR gate to implement the AND function: (a) active-low inputs
with active-high output and (b) active-high inputs with active-high output.
(a)
(b)
Figure 12 NAND gate to implement the OR function: (a) active-low inputs
with active-high output and (b) active-high inputs with active-high output.
?
Digital Design Lab.
Digital Design Lab
16
(a)
(b)
Figure 13 NOR gate to implement the OR function: (a) active-high inputs
with active-low output and (b) active-high inputs with active-high output.
?
Digital Design Lab.
Digital Design Lab
17
 3.2 Logic Macro Functions
 Logic macro functions are those circuits that consist of
several logic primitives to form larger more complex
functions.
 Combinational logic macros include circuits such as
multiplexers, decoders, encoders, comparators, adders,
subtractors, array multipliers, array dividers, and error
detection and correction circuits.
 Sequential logic macros include circuits such as: SR latches; D
and JK flip-flops; counters of various module, including countup and count-down counters; registers, including shift registers;
and sequential multipliers and dividers.
?
Digital Design Lab.
Digital Design Lab
18
 3.2.1 Multiplexers
 A multiplexer is a logic macro device that allows digital
information from two or more data inputs to be directed to a
single output.
Figure 14 Logic diagram for a 4:1 multiplexer
?
Digital Design Lab.
Digital Design Lab
19
z1 = s1`s0`d0 + s1`s0d1 + s1s0`d2 + s1s0d3
s1
s0
d3
d2
d1
d0
z1
0
0
−
−
−
0
0
0
0
−
−
−
1
1
0
1
−
−
0
−
0
0
1
−
−
1
−
1
1
0
−
0
−
−
0
1
0
−
1
−
−
1
1
1
0
−
−
−
0
1
1
1
−
−
−
1
(a)
(b)
Table 7 Truth Table for the 4:1
Figure 14 ANSI/IEEE Std. 91-1984 symbols for
Multiplexer
multiplexers: (a) 2:1 multiplexer, (b) 4:1 multiplexer.
?
Digital Design Lab.
Digital Design Lab
20
 Example
 There is a one-to-one correspondence between the data input
numbers di of a multiplexer and the minterm locations in a
Karnaugh map.
Figure 15 One-to-one correspondence between a Karnaugh
map and a multiplexer.
z1 = x1`x2 + x1x2` + x1x2
= x 1+ x2
?
Digital Design Lab.
Digital Design Lab
21
 Linear-select multiplexers
 The multiplexer examples described thus far have been
classified as linear-select multiplexers, because all of the
variables of the Karnaugh map coordinates have been utilized
as the select inputs for the multiplexer.
(a)
(b)
Figure 16 Linear-select multiplexer using x3 as a mapentered variable: (a) Karnaugh map and (b) a multiplexer
?
Digital Design Lab.
Digital Design Lab
22
 Nonlinear-select multiplexers
 If the number of unique entries in a Karnaugh map satisfies the
expression of Equation, where u is the number of unique
entries and p is the number of select inputs, then at most a(2p ÷
2):1 multiplexer will satisfy the requirements. This is referred
to as a nonlinear-select multiplexer.
1 < u ≥ (2p ÷ 2)
?
Digital Design Lab.
Digital Design Lab
23
 Example


The Karnaugh map shown in Figure 17 has only two
unique entries plus “don’t care” entries.
Since there are only two distinct entries, a 2:1 Karnaugh
map can be used to implement the function.
Figure 17 Karnaugh map for Example.
?
Digital Design Lab.
Digital Design Lab
24

Table 8 tabulates the entries in the map and indicates how
variables x2 and x3 can be assigned to the select inputs of
the multiplexer, where the “don’t care” entries in minterm
locations 1 and 5 are assigned a value of 0.
x1
x2
x3
z1
0
0
0
0
0
0
1
−(0)
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
−(0)
1
1
0
0
1
1
1
0
Table 8 Illustrating the Use
of a Nonlinear-Select
Multiplexer for Figure 17
Figure 18 A 2:1 nonlinear-select multiplexer to
implement the logic of Figure 17
?
Digital Design Lab.
Digital Design Lab
25
 3.2.2 Decoders
 A decoder is a combinational logic macro that is characterized
by the following property: For every valid combination of
inputs, a unique output is generated.
 In general, a decoder has n binary inputs and m mutually
exclusive outputs, where 2n ≥ m.
/DX specifies a
demultiplexer./
Figure 19 An n:m decoder.
?
Digital Design Lab.
Digital Design Lab
26
 2:4 decoder
Figure 20 Logic symbol for a 2:4 decoder
Inputs
Outputs
x1
x2
z0
z1
z2
z3
Minterm
Decoding
Function
0
0
1
0
0
0
x1`x2`
0
1
0
1
0
0
x1`x2
1
0
0
0
1
0
x1x2`
1
1
0
0
0
1
x1x2
Table 9 Truth Table for the 2:4 Decoder of
Figure 20
?
Digital Design Lab.
Digital Design Lab
27
 3:8 decoder
x1
x2
x3
z0
z1
z2
z3
z4
z5
z6
z7
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
1
Table 10 Truth Table for the 3:8 Decoder of
Figure 21
Figure 21 A binary-to-octal decoder
?
Digital Design Lab.
Digital Design Lab
28
Figure 22 Internal logic for the binary-to-octal decoder of Figure 21
?
Digital Design Lab.
Digital Design Lab
29
 3.2.3 Encoders
 An encoder is a macro logic circuit with n mutually exclusive
inputs and m binary outputs, where n ≤ 2m.
 The inputs are mutually exclusive to prevent errors from
appearing on the outputs.
 The outputs generate a binary code that corresponds to the
active input value.
 The function of an encoder can be considered to be the inverse
of a decoder; that is, the mutually exclusive inputs are encoded
into a corresponding binary number.
 An encoder is also referred to as a code converter.
?
Digital Design Lab.
Digital Design Lab
30
Figure 23 An n:m encoder or code converter
 In the label of Figure 23, X corresponds to the input code and
Y correspond to the output code.
 The general qualifying label X/Y is replaced by the input and
output codes, respectively.
 Only one input xi is asserted at a time.
 The decimal value of xi is encoded as a binary number which is
specified by the m outputs.
?
Digital Design Lab.
Digital Design Lab
31
 8:3 encoder
x0
x1
x2
x3
x4
x5
x6
x7
z1
z2
z3
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
1
1
1
Table 11 Truth Table for an Octal-ToBinary Encoder
Figure 24 An octal-to-binary
endcoder
?
Digital Design Lab.
Digital Design Lab
32
Figure 25 Logic diagram for an 8:3 encoder
?
Digital Design Lab.
Digital Design Lab
33
 Priority encoder
 Where more than one input can be active at a time. Then a
priority must be established to select and encode a particular
input. This is referred to as a priority encoder.
x0
x1
x2
x3
x4
x5
x6
x7
z1
z2
z3
1
0
0
0
0
0
0
0
0
0
0
−
1
0
0
0
0
0
0
0
0
1
−
−
1
0
0
0
0
0
0
1
0
−
−
−
1
0
0
0
0
0
1
1
−
−
−
−
1
0
0
0
1
0
0
−
−
−
−
−
1
0
0
1
0
1
−
−
−
−
−
−
1
0
1
1
0
−
−
−
−
−
−
−
1
1
1
1
Table 12 Octal-To-Binary Priority Encoder
?
Digital Design Lab.
Digital Design Lab
34
 3.2.4 Comparators
 A comparator is a logic macro circuit that compares the
magnitude of two n-bit binary numbers X1 and X2.
 Therefore, there are 2n inputs and three outputs that indicate
the relative magnitude of the two numbers.
 The outputs are mutually exclusive, specifying X1 < X2, X1 =
X2, or X1 > X2.
Figure 26 General block diagram of a comparator.
?
Digital Design Lab.
Digital Design Lab
35
 Consider tow 3-bit unsigned operands X1 = x11x12x13 and X2 =
x21x22x23, where x13 and x23 are the low order bits of X1 and X2,
respectively.
 (X1 < X2) = x11`x21 + (x11 ⊕ x21)` x12`x22 + (x11 ⊕ x21)`(x12
⊕ x22)`x13`x23
 (X1 = X2) = (x11 ⊕ x21)`(x12 ⊕ x22)`(x13 ⊕ x23)`
 (X1 > X2) = x11x21` + (x11 ⊕ x21)`x12x22` + (x11 ⊕ x21)` +
(x11 ⊕ x21)`(x12 ⊕ x22)`x13x23`

(X1 = X2) if (X1 < X2)` AND (X1 > X2)`
?
Digital Design Lab.
Digital Design Lab
36
 Analysis of Combinational Logic
 The analysis of combinational logic requires determining the
function of a given logic circuit by obtaining one or more of
the following entities: the equation, truth table, Karnaugh map,
or wave forms.
 The analysis procedure involves obtaining the equation for the
output of each gate or logic macro function as an expression of
the inputs, then applying those equations to the following gate
in the network until the output equation is obtained for the
logic circuit.
 The +/− symbols that precede an input or output variable
indicate the active voltage level of the variable. Thus, +x1 or
−x1 indicates that variable x1 is active at a high or low voltage
level, respectively.
?
Digital Design Lab.
Digital Design Lab
37
 Example

z1 = x1(x2 + x3`x4) + x3x4
Figure 26 Logic diagram for Example
?
Digital Design Lab.
Digital Design Lab
38

z1 = x1x2 + x1x3`x4 + x3x4
Figure 27 Karnaugh map for Equation

z1 = (x1 +x3)(x1 + x4)(x2 + x4)
?
Digital Design Lab.
Digital Design Lab
39
 3.4 Synthesis of Combinational Logic
 Synthesis of combinational logic consists of translating a set of
network specifications into minimized Boolean equations and
then generating a logic diagram from the equations using the
logic primitives.
 Truth tables are also important techniques that are used to
generate equations.
 The synthesis procedure is relatively straightforward.
?
Digital Design Lab.
Digital Design Lab
40
 Example

z1 = x1x3`x4 + [(x1 + x2)` + x3]` + (x2 ⊕ x4`)`
= x1x3`x4 + (x1 ` x2` + x3)` + x2 x4` + x2`x4
= x1x3`x4 + (x1 + x2) x3` + x2 x4` + x2`x4
= x1x3`x4 + x1 x3` + x2 x3` + x2 x4` + x2`x4
Figure 28 Karnaugh map for Equation
?
Digital Design Lab.
Digital Design Lab
41

z1 = (x1 + x2 + x4) ( x2 + x3` + x4) (x2` + x3` + x4`)
Figure 29 NOR gate implementation for Equation
?
Digital Design Lab.
Digital Design Lab
42