CS 221

LOGIC DESIGN
Fall 2014

1 By Wessam El-Behaidy
Assistant Professor ,
Computer Science Department
REMEMBER OUR RULES

2
 COMBINATIONAL LOGIC
3 Lecture 8
REMEMBER
 This chapter includes the most important
standard combinational circuits:
 Adders, Subtractors, Comparators, Decoders,
Encoders, and Multiplexers
 We will know their internal design and the
functionality of each.
 But, remember our aim is to know how to
think to design a circuit

Remember
4
 2n outputs
n-inputs
nxm

...
DECODERS decoder

 A Decoder:
 Is a popular combinational logic building block
 It converts input binary number to one high output

 2‐input decoder
 Has four possible input binary numbers
So, it has four outputs, one for each possible
input binary number

1 0 0 0
1 1 0 0 0 1 0 0
0 0 1 0

Section 4.9
1 0 1 0
0 0 0 1 5
 2n outputs
n-inputs
nxm

...
DECODERS decoder

 Decoders are called n-to-m line decoders, where

m<=2n.
 A particular application of this decoder is:

Binary-to-octal conversion;
 inputs : binary representation and
 outputs : its correspondence in octal representation.

Section 4.9
6
 3-inputs D0
3x8

...
3-TO-8 LINE DECODER decoder
D7
 3 input variables =? outputs
 23=8 outputs

Section 4.9
D0= x’y’z’, D1=x’y’z, D2=x’yz’, D3=x’yz 7
D4= xy’z’ D5=xy’z D6= xyz’ D7=xyz
DECODERS

Section 4.9
The output whose value is equal to 1 represents the minterm 8
equivalent of the binary number currently available in the input lines
DECODER WITH ENABLE INPUT
Decoder with enable E
– if E=0, Outputs all 0 – if E=1, Regular behavior

E i0 i1 d0 d1 d2 d3
0 x x 0 0 0 0
1 0 0 1 0 0 0

Section 4.9
1 0 1 1
9
1 1 0 1
1 1 1 1
DECODERS WITH NAND GATES
 Since NAND is AND with inverted output, it
becomes economical to generate the decoder
minterms in their complemented form.
 So, the output whose value is equal to 0
represents the minterm equivalent of the binary
number currently available in the input lines.

0 1 1 1
1 0 1 1
1 1 0 1
1 1

Section 4.9
1 0
10

So, minterm is the 0

 How to design?
Know internal ?

DECODER WITH ENABLE INPUT (CONT.)

 Two-to-four line decoder with enable input
constructed with NAND gates. The decoder is
enabled when E=0

Section 4.9
Remember, minterm is the 0 11

D0= E’A’B’, D1=E’A’B, D2=E’AB’, D3=E’AB

 How to use as a
block
4-TO-16 LINE DECODER
The 4-to-16 line decoder with
two 3-to-8 line decoder with
enable inputs
 When w=0,
 the top decoder is enabled
and the other is disabled
 The bottom decoder outputs
all 0’s and the top eight
outputs generate minterms
0000 to 0111
 When w=1,
 the bottom decoder is enabled
and the other is disabled

Section 4.9
 The top decoder outputs all
0’s and the bottom eight 12
outputs generate minterms
1000 to 1111
 How to use as a
block

BOOLEAN FUNCTION IMPLEMENTATION

 Since any Boolean function can be expressed in
sum of minterms form:
 A decoder with an external OR gate provides an
implementation of the function
 Ex: Full-adder functions
S(x,y,z)= Σ(1,2,4,7) C(x,y,z)=Σ(3,5,6,7)

Section 4.9
13

Full-adder with a decoder

NOTES
 A function with a long list of minterms requires an
OR gate with large number of inputs
 If the number of minterms >2n/2, then F ’ can be
expressed with fewer minterms
 In this case, NOR gate is used. Since the sum is
complemented and the normal output is generated
 If NAND gates are used for decoder implementation,
 The external gates must be NAND gates instead of OR
gates
 This is because two-level NAND gate is equivalent to a

Section 4.9
two-level AND-OR circuit
14
ENCODERS
 An encoder
 It is a digital circuit that performs the inverse operation
of a decoder
 It has 2n inputs lines and n output lines

 An example of an encoder is:

 Octal-to-binary conversion, it has:
 8 inputs : the octal code and
 3 outputs : the corresponding binary number

 It is assumed that only one input has a value of 1 at

any given time

Section 4.10
1 D0
0 D1 y 0
x 15
0 D2 0
0 D3
OCTAL TO BINARY ENCODER

 It can be implemented with 3 OR gates

Section 4.10
z = D1 + D 3 + D5 + D7
y = D 2 + D 3 + D6 + D 7
x = D 4 + D 5 + D6 + D 7 16
 But, it has some limitations
OCTAL TO BINARY ENCODER:
LIMITATIONS

 This encoder has some limitations:

1. It is assumed that only one input can be active at
any given time,
 If 2 inputs are active simultaneously, the output produces
an undefined combination
 To resolve this  higher priority with higher subscript

2. A output with all 0’s is generated when all the input

are 0;
 But this output is the same as when D0 is equal to 1
 To resolve this,  one more output is used to indicate

Section 4.10
whether at least one input is equal to 1.
17
 How to design?
Know internal ?

PRIORITY ENCODER
 A priority encoder is an encoder circuit that
overcomes the limitations of octal-to-binary encoder
previously implemented.

Section 4.10
18
 How to design?
Know internal ?

PRIORITY ENCODER(CONT.)

Section 4.10
19
MULTIPLEXERS
 A multiplexer (MUX) is a combinational circuit that
 selects binary information from one of many input lines
and
 directs it to a single output line.

 It is also called a
Data selector

 There are:
 2n input lines

Section 4.11
 n selection lines whose bit combinations
determine which input is selected, and 20
 Single output
TWO-TO-ONE MULTIPLEXER
It has:
 2 inputs, 1 selection and 1 output

S Y
0 I0
1 I1

Y= S’I0 + SI1

Section 4.11
How to design?
Know internal ? 21
 I0
I1 4x1 Y
I2 MUX
FOUR-TO-ONE MULTIPLEXER I3

It has:
 4 inputs, 2 selection and 1 output
S1 S0

Section 4.11
Y= S1’S0’I0 + S1’S0I1 + S1S0’I2
+ S1S0I3 How to design?22
Know internal ?
MULTIPLEXER WITH ENABLE INPUT
 As decoder, multiplexer may have an enable input:
 When E=0, the outputs are disabled
 When E=1, normal multiplexer

E S1 S0 Y
0 x X All 0’s I0
I1 4x1 Y
1 0 0 I0 I2 MUX
1 0 1 I1 I3

1 0 1 I2

Section 4.11
1 1 1 I3 E S1 S0 23
 How to use as a
block

QUADRUPLE 2-TO-1 LINE MULTIPLEXER

 The circuit has 4 MUXs,
 Each MUX:
 select one of two input lines: A0 or B0
 Output Y0

 Selection line S selects one MUX from the 4 MUXs.

 It can be seen as a circuit that selects one of two 4-bit

numbers
 The enable input E must be active for normal
operation.

Section 4.11
24
QUADRUPLE 2-TO-1 LINE MULTIPLEXER
(CONT.) A0 2x1
B0 MUX Y0
 The unit is
enabled when E=0
If S=0, the four A
inputs have a path
A1 2x1
B1 MUX Y1
to the four outputs
If S=1, the four B
inputs have a path
to the four outputs
A2 2x1
 When E=1, the B2 MUX Y2
outputs are all 0’s
regardless the
value of S
A3

Section 4.11
2x1
B3 MUX Y3
25

E S
 How to use as a
block

BOOLEAN FUNCTION IMPLEMENTATION

 Example1: F(x,y,z)=Σ(1,2,6,7)

Section 4.11
26
The first n-1 variables are applied to selection inputs and we evaluate
the output as a function of the last variable
 How to use as a
BOOLEAN FUNCTION IMPLEMENTATION block
(CONT.)
 Example2: F(A, B, C, D)=Σ(1,3,4,11,12,13,14,15)

Section 4.11
27
MULTIPLEXER WITH A DECODER
 A 2n-to-1 line multiplexer is constructed from:
 An n-to-2n decoder
 AND gate for each 2n input lines
 An OR gate

try to solve it?

Section 4.11
28
DEMULTIPLEXER
0
 Demultiplixer is
Fig: 4.19
A circuit that receives information from a single line
and directs it to one of 2n output lines.
 The decoder with enable input can function as a
demultiplexer.
 The decoder in fig. 4.9 can function D0 1
0
E D1 1
as 1-to-4 line demultiplexer, when:
D2 0
 E is taken as data input D3
S1S0 1
 A and B as selection inputs
 Because decoder and demultiplexer operations 1 0
are obtained from the same circuit, a decoder

Section 4.9
with enable input is referred to as a decoder-
29
demultiplexer
 THANKS
We covered from:
Ch.4 (sec. 4.74.11)
Skip: three- state gates in sec. 4.11
30
Ch4. Solve prob. 20, 21, 23, 25-27, 29-30, 31-35