CHAPTER FOUR

COMBINATIONAL CIRCUIT DESIGN

 4.1 Analyses and Design procedures
 4.2 Popular arithmetic and logical combinational
circuits
4.3 Decoders/Encoders and MUXes

0 / 65
 Combinational Circuits

 Output is function of input only

i.e. no feedback

Combinational
n inputs • • m outputs
• Circuits •
• •


When input changes, output may change (after a delay)

1 / 65
 Combinational Circuits

 Analysis
● Given a circuit, find out its function
A
B
C
A
F1
?
B
C
A
B

?
● Function may be expressed as:
A
F2
C

B
C

♦ Boolean function
♦ Truth table

Design
● Given a desired function, determine its circuit
● Function may be expressed as:
♦ Boolean function
?
♦ Truth table

2 / 65
 To obtain the output Boolean functions from
a logic diagram, we procced as folIows:
1. Label all gate outputs that are a function of input variables
with arbitrary symbols-but with meaningful names.
Determine the Boolean functions for each gate output.
2. Label the gates that are a function of input variables and
previously labeled gates with other arbitrary symbols. Find
the Boolean functions for these gates.
3. Repeat the process outlined in step 2 until the outputs of the
circuit are obtained.
4. By repeated substitution of previously defined functions,
obtain the output Boolean functions in terms of input
variables.

3 / 65
 Analysis Procedure

 Boolean Expression Approach

A
B
F1
C T2=ABC
A T1=A+B+C
B T3=AB'C'+A'BC'+A'B'C
C
A
B F’2=(A’+B’)(A’+C’)(B’+C’)

A
F2
C
F2=AB+AC+BC
B
C
F1=AB'C'+A'BC'+A'B'C+ABC
F2=AB+AC+BC
4 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =0 0 0 0 0 0
0 0
B =0
F1
C =0
A =0 0
B =0 0
C =0
1
A =0 0
B =0

A =0 0 0
F2
C =0

B =0 0
C =0

5 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =0 0 0 0 0 0
0 1
B =0 0 0 1 1 0
F1
C =1
A =0 1
B =0 1
C =1
1
A =0 0
B =0

A =0 0 0
F2
C =1

B =0 0
C =1

6 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =0 0 0 0 0 0
0 1
B =1 0 0 1 1 0
F1
C =0
0 1 0 1 0
A =0 1
B =1 1
C =0
1
A =0 0
B =1

A =0 0 0
F2
C =0

B =1 0
C =0

7 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =0 0 0 0 0 0
0 0
B =1 0 0 1 1 0
F1
C =1
A =0
0 1 0 1 0
1 0 0 1
B =1 0 1 1
C =1
0
A =0 0
B =1

A =0 0 1
F2
C =1

B =1 1
C =1

8 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =1 0 0 0 0 0
0 1
B =0 0 0 1 1 0
F1
C =0
A =1
0 1 0 1 0
1 1
B =0 0 1 1 0 1
C =0 1 0 0 1 0
1
A =1 0
B =0

A =1 0 0
F2
C =0

B =0 0
C =0

9 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =1 0 0 0 0 0
0 0
B =0 0 0 1 1 0
F1
C =1
A =1
0 1 0 1 0
1 0
B =0 0 1 1 0 1
C =1 1 0 0 1 0
0
A =1 0 0 1
B =0
1 0 1

A =1 1 1
F2
C =1

B =0 0
C =1

10 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =1 0 0 0 0 0
0 0
B =1 0 0 1 1 0
F1
C =0
A =1
0 1 0 1 0
1 0
B =1 0 1 1 0 1
C =0 1 0 0 1 0
0
A =1 1
B =1
1 0 1 0 1
1 1 0 0 1
A =1 0 1
F2
C =0

B =1 0
C =0

11 / 65
 Analysis Procedure

 Truth Table Approach A B C F1 F2

A =1 0 0 0 0 0
1 1
B =1 0 0 1 1 0
F1
C =1
A =1
0 1 0 1 0
1 0
B =1 0 1 1 0 1
C =1 1 0 0 1 0
0
A =1 1
B =1
1 0 1 0 1
1 1 0 0 1
A =1 1 1
C =1
F2 1 1 1 1 1
B =1 1
C =1 B B
0 1 0 1 0 0 1 0
A 1 0 1 0 A 0 1 1 1
C C

F1=AB'C'+A'BC'+A'B'C+ABC F2=AB+AC+BC
12 / 65
 Design Procedure

 Given a problem statement:

● Determine the number of inputs and outputs
● Derive the truth table
● Simplify the Boolean expression for each output
● Produce the required circuit

Example:
Design a circuit to convert a “BCD” code to “Excess 3” code

 4-bits  4-bits
 0-9 values
?  Value+3

13 / 65
 Design Procedure

 BCD-to-Excess 3 Converter
C C
A B C D w x y z
1 1 1
0 0 0 0 0 0 1 1
1 1 1 1
0 0 0 1 0 1 0 0 B B
x x x x x x x x
0 0 1 0 0 1 0 1 A A
1 1 x x 1 x x
0 0 1 1 0 1 1 0
D D
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0 w = A+BC+BD x = B’C+B’D+BC’D’
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0 C C
1 0 0 0 1 0 1 1 1 1 1 1
1 0 0 1 1 1 0 0 1 1 1 1
1 0 1 0 x x x x x x x x
B x x x x
B
A 1 x x
A 1 x x
1 0 1 1 x x x x
1 1 0 0 x x x x D D
1 1 0 1 x x x x
1 1 1 0 x x x x y = C’D’+CD z = D’
1 1 1 1 x x x x 14 / 65
 Design Procedure

 BCD-to-Excess 3 Converter
A B C D w x y z A
0 0 0 0 0 0 1 1 w
0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1 x
B
0 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1 C y
1 0 0 1 1 1 0 0
1 0 1 0 x x x x
D z
1 0 1 1 x x x x
1 1 0 0 x x x x
1 1 0 1 x x x x w = A + B(C+D) y = (C+D)’ + CD
1 1 1 0 x x x x x = B’(C+D) + B(C+D)’ z = D’
1 1 1 1 x x x x 15 / 65
Seven-Segment Decoder
a
w x y z abcdefg
w a
0 0 0 0 1111110 b
0 0 0 1 0110000 x c f b
? d g
0 0 1 0 1101101 y e
0 0 1 1 1111001 z f
g
0 1 0 0 0110011 e c
0 1 0 1 1011011 BCD code
0 1 1 0 1011111
0 1 1 1 1110000 y d
1 0 0 0 1111111 1 1 1
1 0 0 1 1111011 1 1 1
1 0 1 0 xxxxxxx x x x x
x
1 0 1 1 xxxxxxx w 1 1 x x
1 1 0 0 xxxxxxx z
1 1 0 1 xxxxxxx
1 1 1 0 xxxxxxx a = w + y + xz + x’z’ b=...
c=...
1 1 1 1 xxxxxxx
d=...
16 / 65
 Binary Adder

 Half Adder x S
y HA
C
● Adds 1-bit plus 1-bit
● Produces Sum and Carry x
+ y
───
x y C S C S
0 0 0 0
0 1 0 1 x S
1 0 0 1
1 1 1 0
y C

17 / 65
 Binary Adder

 Full Adder x S
y FA
z C
● Adds 1-bit plus 1-bit plus 1-bit
● Produces Sum and Carry x
+ y
y + z
x y z C S ───
0 1 0 1
0 0 0 0 0 C S
0 0 1 0 1 x 1 0 1 0
z
0 1 0 0 1
S = xy'z'+x'yz'+x'y'z+xyz = x  y  z
0 1 1 1 0
y
1 0 0 0 1
0 0 1 0
1 0 1 1 0
x 0 1 1 1
1 1 0 1 0
z
1 1 1 1 1 C = xy + xz + yz
18 / 65
 Binary Adder

 Full Adder S = xy'z'+x'yz'+x'y'z+xyz = x  y  z

x C = xy + xz + yz
y
z
x
y x
x z y
x S z S
y
z
x
x
x y
y y y
z x
x z C
y z
y
z x C
z
z
y
z

19 / 65
 Binary Adder

 Full Adder
x S
y HA HA

z C

x
S

y
C

20 / 65
 Binary Adder
x3x2x1x0 y3y2y1y0
c3 c2 c1 .
+ x3 x2 x1 x0
Carry + y3 y2 y1 y0
Cy Binary Adder C0 Propagate ────────
Addition Cy S3 S2 S1 S0
S3S2S1S0

x3 x2 x1 x0
y3 y2 y1 y0
0

FA FA FA FA

C4 C3 C2 C1
S3 S2 S1 S0
21 / 65
 Binary Adder

 Carry Propagate Adder

x7 x6 x5 x4 x3 x2 x1 x0
y7 y6 y5 y4 y3 y2 y1 y0

A3 A2 A1 A0 B3 B2 B1 B0 A3 A2 A1 A0 B3 B2 B1 B0

Cy CPA C0 Cy CPA C0 0

S3 S2 S1 S0 S3 S2 S1 S0

S7 S6 S5 S4 S3 S2 S1 S0

22 / 65
 Carry propagation
● When the correct outputs are available
● The critical path counts (the worst case)
● (A1, B1, C1) → C2 → C3 → C4 → (C5, S4)
● When 4-bits full-adder → 8 gate levels (n-bits: 2n gate
levels)

Figure 4.10 Full Adder with P and G Shown

23 / 65
 Parallel Adders
 Reduce the carry propagation delay
● Employ faster gates
● Look-ahead carry (more complex mechanism, yet faster)
● Carry propagate: Pi = AiBi
● Carry generate: Gi = AiBi
● Sum: Si = PiCi
● Carry: Ci+1 = Gi+PiCi
● C0 = Input carry
● C1 = G0+P0C0
● C2 = G1+P1C1 = G1+P1(G0+P0C0) = G1+P1G0+P1P0C0
● C3 = G2+P2C2 = G2+P2G1+P2P1G0+ P2P1P0C0

24 / 65
 Carry Look-ahead Adder (1/2)

 Logic diagram

Fig. 4.11 Logic Diagram of Carry Look-ahead Generator

25 / 65
 Carry Look-ahead Adder (2/2)

4-bit carry-look
ahead adder
● Propagation delay
of C3, C2 and C1 are
equal.

Fig. 4.12 4-Bit Adder with Carry Look-ahead

26 / 65
 BCD Adder

 4-bits plus 4-bits + x3 x2 x1 x0

+ y3 y2 y1 y0
 Operands and Result: 0 to 9 ────────
Cy S3 S2 S1 S0
X +Y x3 x2 x1 x0 y3 y2 y1 y0 Sum Cy S3 S2 S1 S0
0+0 0 0 0 0 0 0 0 0 =0 0 0 0 0 0
0+1 0 0 0 0 0 0 0 1 =1 0 0 0 0 1
0+2 0 0 0 0 0 0 1 0 =2 0 0 0 1 0

0+9 0 0 0 0 1 0 0 1 =9 0 1 0 0 1
1+0 0 0 0 1 0 0 0 0 =1 0 0 0 0 1
1+1 0 0 0 1 0 0 0 1 =2 0 0 0 1 0

1+8 0 0 0 1 1 0 0 0 =9 0 1 0 0 1
1+9 0 0 0 1 1 0 0 1 =A 0 1 0 1 0 Invalid Code
2+0 0 0 1 0 0 0 0 0 =2 0 0 0 1 0

9+9 1 0 0 1 1 0 0 1 = 18 1 0 0 1 0 Wrong BCD Value

0001 1000 27 / 65
 BCD Adder

X +Y x3 x2 x1 x0 y3 y2 y1 y0 Sum Cy S3 S2 S1 S0 Required BCD Output Value

9+0 1 0 0 1 0 0 0 0 =9 0 1 0 0 1 0 0 0 0 1 0 0 1 =9
9+1 1 0 0 1 0 0 0 1 = 10 0 1 0 1 0 0 0 0 1 0 0 0 0 = 16 
9+2 1 0 0 1 0 0 1 0 = 11 0 1 0 1 1 0 0 0 1 0 0 0 1 = 17 
9+3 1 0 0 1 0 0 1 1 = 12 0 1 1 0 0 0 0 0 1 0 0 1 0 = 18 
9+4 1 0 0 1 0 1 0 0 = 13 0 1 1 0 1 0 0 0 1 0 0 1 1 = 19 
9+5 1 0 0 1 0 1 0 1 = 14 0 1 1 1 0 0 0 0 1 0 1 0 0 = 20 
9+6 1 0 0 1 0 1 1 0 = 15 0 1 1 1 1 0 0 0 1 0 1 0 1 = 21 
9+7 1 0 0 1 0 1 1 1 = 16 1 0 0 0 0 0 0 0 1 0 1 1 0 = 22 
9+8 1 0 0 1 1 0 0 0 = 17 1 0 0 0 1 0 0 0 1 0 1 1 1 = 23 
9+9 1 0 0 1 1 0 0 1 = 18 1 0 0 1 0 0 0 0 1 1 0 0 0 = 24 

+6

28 / 65
 BCD Adder

 Correct Binary Adder‟s Output (+6)

● If the result is between „A‟ and „F‟
● If Cy = 1

S3 S 2 S1 S0 Err
S1
0 0 0 0 0

1 0 0 0 0 1 1 1 1
S2
1 0 0 1 0 S3 1 1
1 0 1 0 1 S0
1 0 1 1 1
1 1 0 0 1
Err = S3 S2 + S3 S1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
29 / 65
BCD Adder
x3 x2 x1 x0 y3 y2 y1 y0

A3 A2 A1 A0 B3 B2 B1 B0
Cy Binary Adder Ci 0
S3 S2 S1 S0

Err

0 0

A3 A2 A1 A0 B3 B2 B1 B0
Cy Binary Adder Ci 0
S3 S2 S1 S0

Cy S3 S2 S1 S0
30 / 65
 Binary Subtractor

 Use 2‟s complement with binary adder

● x – y = x + (-y) = x + y’ + 1

x3 x2 x1 x0 y3 y2 y1 y0

A3 A2 A1 A0 B3 B2 B1 B0
Cy Binary Adder Ci 1
S3 S2 S1 S0

F3 F2 F1 F0

31 / 65
 Binary Adder/Subtractor

 M: Control Signal (Mode)

● M=0  F = x + y x3 x2 x1 x0 y3 y2 y1 y0 M
● M=1  F = x – y

A3 A2 A1 A0 B3 B2 B1 B0
Cy Binary Adder Ci
S3 S2 S1 S0

F3 F2 F1 F0

32 / 65
 Overflow

 Unsigned Binary Numbers

x x2 x1 x0
3
y3 y2 y1 y0
0

FA FA FA FA

Carry C4 C3 C2 C1
S3 S2 S1 S0
 2‟s Complement Numbers
x3 x2 x1 x0
y3 y2 y1 y0
0

FA FA FA FA

Overflow C4 C3 C2 C1
S3 S2 S1 S0

33 / 65
 Magnitude Comparator

 Compare 4-bit number to 4-bit number

● 3 Outputs: < , = , >
● Expandable to more number of bits

x3  A3 B3  A3 B3 A3A2A1A0 B3B2B1B0

x2  A2 B2  A2 B2
Magnitude
x1  A1 B1  A1 B1 Comparator
x0  A0 B0  A0 B0
A<B A=B A>B
( A  B)  x3 x2 x1 x0
( A  B)  A3 B3  x3 A2 B2  x3 x2 A1 B1  x3 x2 x1 A0 B0
( A  B)  A3 B3  x3 A2 B2  x3 x2 A1 B1  x3 x2 x1 A0 B0
34 / 65
Magnitude Comparator
A3
x3

B3

A2
x2

B2

A1 (A<B)
x1

B1

A0
x0 (A>B)

B0
(A=B)

35 / 65
 Magnitude Comparator

x7 x6 x5 x4 x3 x2 x1 x0
y7 y 6 y5 y4 y 3 y2 y1 y 0

A3 A2 A1 A0 B3 B2 B1 B0 A3 A2 A1 A0 B3 B2 B1 B0
0 I(A>B) I(A>B)
1
Magnitude Magnitude
I(A=B) I(A=B)
I(A<B)
Comparator I(A<B)
Comparator
0
A<B A=B A>B A<B A=B A>B

A<B A=B A>B

36 / 65
37 / 65
38 / 65
39 / 65
 Decoders

 A decoder is a combinational circuit that converts

binary information from n input lines to a
maximum of 2n unique output lines.
 A decoder is a combinational circuit that changes a
code into a set of signals
 If the n-bit coded information has unused
combinations, the decoder may have fewer than 2n
outputs.

40 / 65
 Decoders
Extract “Information” from the code
Only one
 Binary Decoder lamp will
turn on
● Example: 2-bit Binary Number

0 1
x1 0
Binary
x0 0 Decoder 0
0

41 / 65
 Decoders

 2-to-4 Line Decoder

Y3

y3 Y2

Decoder
I1 Binary
y2
y1 Y1
I0 y0
Y0

I1 I0 Y3 Y2 Y1 Y0
I1
0 0 0 0 0 1 I0
0 1 0 0 1 0
Y3  I1 I 0 Y2  I1 I 0
1 0 0 1 0 0
1 1 1 0 0 0 Y1  I1 I 0 Y0  I1 I 0
42 / 65
 Decoders

 3-to-8 Line Decoder Y7  I 2 I1 I 0

Y6  I 2 I1 I 0
Y7 Y5  I 2 I1 I 0
Y6
Y5 Y4  I 2 I1 I 0
Decoder
Binary

I2 Y4 Y3  I 2 I1 I 0
I1 Y3
I0 Y2 Y2  I 2 I1 I 0
Y1 Y1  I 2 I1 I 0
Y0
Y0  I 2 I1 I 0

I2
I1
I0
43 / 65
 Decoders

 “Enable” Control Y3

Y3

Decoder
I1 Y2
Binary Y2
I0 Y1
E Y1
Y0
Y0
E I1 I0 Y3 Y2 Y1 Y0
0 x x 0 0 0 0
I1
1 0 0 0 0 0 1 I0
E
1 0 1 0 0 1 0
1 1 0 0 1 0 0
1 1 1 1 0 0 0
44 / 65
 Decoders

 Expansion I2 I 1 I0

I2 I1 I0 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 Y3 Y7

Decoder
I0

Binary
0 1 0 0 0 0 0 0 1 0 0 Y2 Y6
I1 Y1 Y5
0 1 1 0 0 0 0 1 0 0 0 E
1 0 0 0 0 0 1 0 0 0 0 Y0 Y4
1 0 1 0 0 1 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0 Y3 Y3

Decoder
I0

Binary
1 1 1 1 0 0 0 0 0 0 0 Y2 Y2
I1 Y1 Y1
E Y0 Y0

45 / 65
 Decoders

 Active-High / Active-Low
I1 I0 Y 3 Y 2 Y 1 Y 0 I1 I0 Y 3 Y 2 Y 1 Y 0
0 0 0 0 0 1 0 0 1 1 1 0
0 1 0 0 1 0 0 1 1 1 0 1
1 0 0 1 0 0 1 0 1 0 1 1
Y3
1 1 1 0 0 0 1 1 0 1 1 1
Y2

Y1
Y3 Y3
Decoder

I1 I1 Decoder
Binary

Binary
Y2 Y2 Y0

Y1 Y1
I0 Y0 I0 Y0 I1
I0

46 / 65
 Implementation Using Decoders

 Each output is a minterm Binary

Decoder
All minterms are produced
Y7
Sum the required minterms Y6
Y5
x I2 Y4
y I1 Y3
Example: Full Adder
z I0 Y2
S(x, y, z) = ∑(1, 2, 4, 7) Y1
Y0
C(x, y, z) = ∑(3, 5, 6, 7)

S C 47 / 65
 Implementation Using Decoders

Binary Binary
Decoder Decoder

Y7 Y7
Y6 Y6
Y5 Y5
x I2 Y4 x I2 Y4
y I1 Y3 y I1 Y3
z I0 Y2 z I0 Y2
Y1 Y1
Y0 Y0

S C
S C
48 / 65
 Encoders

 Put “Information” into code Only one

switch
 Binary Encoder should be
● Example: 4-to-2 Binary Encoder activated
at a time
x1

x3 x2 x1 y1 y0
x2 y1
Binary 0 0 0 0 0
Encoder y0 0 0 1 0 1
x3
0 1 0 1 0
1 0 0 1 1

49 / 65
 Encoders

 Octal-to-Binary Encoder (8-to-3)

I7
I7 I6 I5 I4 I3 I2 I1 I0 Y2 Y1 Y0 I6
I5

Encoder
0 0 0 0 0 0 0 1 0 0 0 Y2

Binary
0 0 0 0 0 0 1 0 0 0 1 I4 Y1
0 0 0 0 0 1 0 0 0 1 0 I3 Y0
0 0 0 0 1 0 0 0 0 1 1 I2
0 0 0 1 0 0 0 0 1 0 0 I1
0 0 1 0 0 0 0 0 1 0 1 I0
0 1 0 0 0 0 0 0 1 1 0 I7
1 0 0 0 0 0 0 0 1 1 1 I6 Y2
I5
Y2  I 7  I 6  I 5  I 4 I4
I3 Y1
Y1  I 7  I 6  I 3  I 2 I2
I1
Y0  I 7  I 5  I 3  I1 I0 Y0
50 / 65
 Priority Encoders

 4-Input Priority Encoder

I3

Encoder
V

Priority
I3 I2 I 1 I0 Y1 Y0 V I2 Y1
0 0 0 0 0 0 0 I1 Y0
0 0 0 1 0 0 1 I0
0 0 1 x 0 1 1
0 1 x x 1 0 1
I3 Y0
1 x x x 1 1 1
I2
Y1 I1 I1
Y1  I 3  I 2 Y1
1 1 1 1
1 1 1 1
I2 Y0  I 3  I 2 I1
I3 I0 V
V  I 3  I 2  I1  I 0
1 1 1 1
I0

51 / 65
Encoder / Decoder Pairs

Binary Binary
Encoder Decoder

I7 Y7
I6 Y6
I5 Y5
Y2 I2 Y4
I4 Y1 I1 Y3
I3 Y0 I0 Y2
I2
I1 Y1
I0 Y0

52 / 65
Multiplexers

S1 S0 Y I0
0 0 I0 I1
MUX Y
0 1 I1 I2
1 0 I2 I3
S1 S0
1 1 I3
53 / 65
 Multiplexers

 2-to-1 MUX
I0
I0 Y
MUX Y
I1 I1
S
S
I0
 4-to-1 MUX I1
Y
I0 I2

I1 I3
MUX Y
I2
I3
S1 S0
S1 S0
54 / 65
 Multiplexers

 Quad 2-to-1 MUX A 3

Y3
A2
x3 I0 Y2
y3 MUX Y A1
I1 Y1
S
A0
Y0
x2 I0 B3
y2 MUX Y
I1
S B2
A3
B1 A2
x1 I0
MUX Y
A1
Y3
B0 A0
y1 I1 Y
MUX 2
S Y1
B3 Y0
B2
x0 I0
MUX Y
S E
B1
y0 I1 B0
S S E

S
55 / 65
 Multiplexers

 Quad 2-to-1 MUX

A3
Y3 A3
A2
Y2 A2
A1 A1
Y1 Y3
A0
Y0
A0 Y2
MUX
B3 Y1
B3
B2 Y0
B2
B1 B1
B0 B0
S E
Extra
Buffers
S E
56 / 65
 Implementation Using Multiplexers

 Example
F(x, y) = ∑(0, 1, 3)

x y F I0
1
0 0 1 1 I1
MUX Y F
0 1 1 0 I2
1 0 0 1 I3
S1 S0
1 1 1
x y

57 / 65
 Implementation Using Multiplexers

 Example
F(x, y, z) = ∑(1, 2, 6, 7)
0 I0
x y z F 1 I1
0 0 0 0 1 I2
0 0 1 1 0 I3
Y F
0 1 0 1 0 I4 MUX
0 1 1 0 0 I5
1 I6
1 0 0 0
1 I7
1 0 1 0 S2 S1 S0
1 1 0 1
1 1 1 1 x y z

58 / 65
 Implementation Using Multiplexers

 Example
F(x, y, z) = ∑(1, 2, 6, 7)

x y z F
0 0 0 0 z I0
F=z z I1 F
0 0 1 1
MUX Y
0 1 0 1 0 I2
F=z 1 I3
0 1 1 0 S1 S0
1 0 0 0
F=0 x y
1 0 1 0
1 1 0 1
F=1
1 1 1 1
59 / 65
 Implementation Using Multiplexers

 Example
F(A, B, C, D) = ∑(1, 3, 4, 11, 12, 13, 14, 15)
A B C D F
0 0 0 0 0
F=D
D I0
0 0 0 1 1
0 0 1 0 0
D I1
F=D
0 0 1 1 1 D I2
0 1 0 0 1
0 1 0 1 0
F=D 0 I3
0 MUX Y F
0 1 1 0 0
F=0 I4
0 1 1 1 0 D
1 0 0 0 0
I5
1 0 0 1 0 F=0 1 I6
1 0 1 0 0
1 0 1 1 1
F=D 1 I7
1 1 0 0 1 S2 S1 S0
F=1
1 1 0 1 1
1 1 1 0 1 F=1
1 1 1 1 1 A B C
60 / 65
 Multiplexer Expansion

 8-to-1 MUX using Dual 4-to-1 MUX

I0 I0
I1 I1
MUX Y
I2 I2
I3 I3
S 1 S0 I0
MUX Y Y
I1
I0 S
I4
I5 I1
MUX Y
I6 I2
I7 I3
S 1 S0

1 0 0
S2 S1 S0 61 / 65
 DeMultiplexers

Y3
Y2
I DeMUX Y
1

S S Y0
1 0

Y3

Y2 S1 S0 Y3 Y2 Y1 Y0
I
Y1 0 0 0 0 0 1
Y0
0 1 0 0 1 0
1 0 0 1 0 0
S1 1 1 1 0 0 0
S0
62 / 65
Multiplexer / DeMultiplexer Pairs

MUX DeMUX

I7 Y7
I6 Y6
I5 Y5
I4 Y4
Y I Y3
I3
I2 Y2
I1 Y1
I0 Y0

S 2 S1 S0 S2 S1 S0

Synchronize
x2 x1 x0 y2 y1 y0
63 / 65
DeMultiplexers / Decoders

Y3 Y3

Decoder
I1

Binary
Y2 Y2
I DeMUX Y I0 Y1
1
E Y0
S S Y0
1 0

E I1 I0 Y3 Y2 Y1 Y0
S1 S0 Y3 Y2 Y1 Y0 0 x x 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 1
0 1 0 0 1 0 1 0 1 0 0 1 0
1 0 0 1 0 0 1 1 0 0 1 0 0
1 1 1 0 0 0 1 1 1 1 0 0 0

64 / 65