Chapter 4

Combinational Logic

4-1

Outline
! Combinational Circuits
! Analysis and Design Procedures
! Binary Adders
! Other Arithmetic Circuits
! Decoders and Encoders
! Multiplexers

4-2

1
Combinational v.s Sequential Circuits
! Logic circuits may be combinational or sequential
! Combinational circuits:
! Consist of logic gates only
! Outputs are determined from the present values of inputs
! Operations can be specified by a set of Boolean functions
! Sequential circuits:
! Consist of logic gates and storage elements
! Outputs are a function of the inputs and the state of the
storage elements
! Depend not only on present inputs, but also on past values

! Circuit behavior must be specified by a time sequence of

inputs and internal states
4-3

Combinational Circuit (1/2)

! A combinational circuit consists of
! Input variables
! Logic gates
! Output variables

4-4

2
Combinational Circuit (2/2)
! Each input and output variable is a binary signal
! Represent logic 1 and logic 0
! There are 2 n possible binary input combinations for
n input variable
! Only one possible output value for each possible
input combination
! Can be specified with a truth table
! Can also be described by m Boolean functions, one
for each output variable
! Each output function is expressed in terms of n input
variables
4-5

Outline
! Combinational Circuits
! Analysis and Design Procedures
! Binary Adders
! Other Arithmetic Circuits
! Decoders and Encoders
! Multiplexers

4-6

3
Analysis Procedure
! Analysis: determine the function that the circuit
implements
! Often start with a given logic diagram
! The analysis can be performed by
! Manually finding Boolean functions
! Manually finding truth table
! Using a computer simulation program
! First step: make sure that circuit is combinational
! Without feedback paths or memory elements
! Second step: obtain the output Boolean functions or
the truth table
4-7

Output Boolean Functions (1/3)

Step 1:
! Label all gate outputs that are a function of input variables

! Determine Boolean functions for each gate output

F2 = AB + AC + BC
T1 = A + B + C
T2 = ABC

4-8

4
Output Boolean Functions (2/3)
Step 2:
! Label the gates that are a function of input variables and

previously labeled gates

! Find the Boolean function for these gates

T3 = F 2 T1
F1 = T3 + T2

4-9

Output Boolean Functions (3/3)

Step 3:
! Obtain the output Boolean function in term of input variables

! By repeated substitution of previously defined functions

F1 = T3 + T2 = F 2 T1 + ABC

= (AB + AC + BC) (A + B + C) + ABC

= (A + B )(A + C )(B + C ) (A + B + C) + ABC

= (A + B C )(AB + AC + BC +B C) + ABC

= A BC + A B C + AB C + ABC

4-10

5
Truth Table
! To obtain the truth table from the logic diagram:
1. Determine the number of input variables
For n inputs:
! 2 n possible combinations
! List the binary numbers from 0 to 2 n-1 in a table
2. Label the outputs of selected gates
3. Obtain the truth table for the outputs of those gates
that are a function of the input variables only
4. Obtain the truth table for those gates that are a
function of previously defined variables at step 3
! Repeatedly until all outputs are determined
4-11

Truth Table for Fig. 4-2

A B C F2 F2
T1 T2 T3 F1

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

0 1 1 1 0 1 0 0 0

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

1 1 1 1 0 1 1 0 1

4-12

6
Design Procedure
! Design procedure:
! Input: the specification of the problem
! Output: the logic circuit diagram (or Boolean functions)
! Step 1: determine the required number of inputs and
outputs from the specification
! Step 2: derive the truth table that defines the required
relationship between inputs and outputs
! Step 3: obtain the simplified Boolean function for each
output as a function of the input variables
! Step 4: draw the logic diagram and verify the
correctness of the design
4-13

Code Conversion Example

Input BCD Output Excess-3 Code
! Convert from BCD
code to Excess-3 code A B C D w x y z

! The 6 input 0 0 0 0 0 0 1 1
combinations not 0 0 0 1 0 1 0 0
listed are don’t cares 0 0 1 0 0 1 0 1
! These values have no 0 0 1 1 0 1 1 0
meaning in BCD 0 1 0 0 0 1 1 1
! We can arbitrary 0 1 0 1 1 0 0 0
assign them to 1 or 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
1 0 0 1 1 1 0 0

4-14

7
Maps for Code Converter (1/2)
! The six don’t care minterms (10~15) are marked with X

4-15

Maps for Code Converter (2/2)

4-16

8
Logic Diagram for the Converter
! There are various possibilities for a logic diagram that
implements a circuit
! A two-level logic diagram may be obtained directly from
the Boolean expressions derived by the maps
! The expressions may be manipulated algebraically to use
common gates for two or more outputs
! Reduce the number of gates used

z=D

y = CD + C D = CD + (C + D)

x = B C + B D + BC D = B (C + D) + BC D

= B ( C + D) + B(C + D)

w = A + BC + BD = A + B(C + D)
4-17

Logic Diagram for the Converter

C + D is commonly used
to implement the three outputs

4-18

9
Outline
! Combinational Circuits
! Analysis and Design Procedures
! Binary Adders
! Other Arithmetic Circuits
! Decoders and Encoders
! Multiplexers

4-19

Adder
! The most basic arithmetic operation is the
addition of two binary digits
! When both augend and addend bits are equal to 1,
the binary sum consists of two digits (1 + 1 = 10)
! The higher significant bit of this result is called a carry
! A combination circuit that performs the addition
of two bits is half adder
! A adder performs the addition of 2 significant bits
and a previous carry is called a full adder

4-20

10
Half Adder
! Half adder
! Inputs: x and y
! Outputs: S (for sum) and C (for carry)

x y C S
S = x y + xy

0 0 0 0
C = xy
0 1 0 1
1 0 0 1
1 1 1 0

4-21

Implementation of a Half Adder

4-22

11
Full Adder
x y z C S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

x, y: the two significant bits to be added

C
z: the carry from the previous position
4-23

Implementation of a Full Adder

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

4-24

12
Implementation of a Full Adder
! A full adder can be implemented with two half adders
and an OR gate

S=z Ƨ Ƨ
(x y)
C = z (xy ' + x ' y) + xy
= xy ' z + x ' yz + xy
= z '(xy ' + x 'y) + z(xy ' + x ' y) '
= xy ' z + x ' yz + xyz + xyz '
= z '(xy ' + x 'y) + z(xy + x ' y ')
= xy ' z ' + x 'y z ' +xyz + x ' y ' z
= xz + yz + xy
4-25

Binary Adder
! A binary adder produces the arithmetic sum of two binary
numbers
! Can be constructed with full adders connected in cascade
! The output carry from each full adder is connected to input
carry of the next full adder in the chain
! n-bit binary ripple carry adder is connected by n FAs

4-26

13
4-bit Adder Example
! Consider two binary number A = 1011 and B = 0011

Subscript i : 3 2 1 0
Input carry 0 1 1 0 Ci
Augend 1 0 1 1 Ai
Addend 0 0 1 1 Bi
Sum 1 1 1 0 Si
Output carry 0 0 1 1 Ci+1

4-27

Carry Propagation
! As in a combinational circuit, the signal must propagate
through the gates before the correct output sum is
available in the output terminals
! The total propagation time is equal to the propagation
delay of a typical gate times the number of levels in
the circuit
! The longest propagation delay in a adder is the time
that carry propagate through the full adders
! Each bit of the sum output depends on the value of the
input carry
! The value of Si will be in final value only after the input
carry Ci has been propagated
4-28

14
Full Adder with P and G
! The full adder can be redrawn with two internal signals
P (propagation) and G (generation)
! The signal from input carry Ci to output carry Ci+1
propagates through an AND and a OR gate (2 gate levels)
! For n-bit adder, there are 2n gate levels for the carry to
propagate from input to output

4-29

Carry Propagation
! The carry propagation time is a limiting factor on
the speed with which two numbers are added
! All other arithmetic operations are implemented by
successive additions
! The time consumed during the addition is very critical
! To reduce the carry propagation delay
! Employ faster gates with reduced delays
! Increase the equipment complexity
! Several techniques for reducing the carry propagation
time in a parallel adder
! The most widely used technique employs the principle of
carry lookahead
4-30

15
Carry Propagation & Generation

carry propagate : Pi = Ai Ƨ Bi S i = P i Ƨ Ci
carry generate : Gi = AiBi Ci+1 = Gi + PiCi

4-31

Carry Lookahead Generator

C0 = input carry
C1 = G0 + P0C0
C2 = G1 + P1C1
= G1 + P1(G0 + P0C0)
= G1 + P1G0 + P1P0C0
C3 = G2 + P2C2
= G2 + P2G1 + P2P1G0 + P2P1P0C0

4-32

16
Carry Lookahead Adder
" All output carries are
generated after a delay
through two levels of
gates
" Output S1 to S3 can have
equal propagation delay
times

4-33

Outline
! Combinational Circuits
! Analysis and Design Procedures
! Binary Adders
! Other Arithmetic Circuits
! Decoders and Encoders
! Multiplexers

4-34

17
Binary Subtractor
! A – B can be done by taking the 2’s complement of B
and adding it to A ---> A – B = A + (-B)
! 2’complement can be obtained by taking the 1’complement
and adding on to the least significant pair of bits
! A - B = A + (B’ + 1)
! The circuit for subtraction A – B consists of an adder
with inverter placed between each data input B and
the corresponding input of the full adder
! The input carry C0 must be equal to 1

4-35

4-bit Adder-Subtractor
! M=0 (Adder)
! Input of FA is A and B (B Ƨ 0 = B), and C 0 is 0
! M=1 (Subtractor)
! Input of FA is A and B’ (B Ƨ 1 = B’), and C 0 is 1
x y x Ƨy
0 0 0
y
0 1 1
1 0 1 y’
1 1 0

(overflow)
4-36

18
Overflow
! An overflow occurs when two number of n digits
each are added and the sum occupies n+1 digits
! When two unsigned numbers are added, an overflow
is detected from the end carry out of the most
significant position
! When two signed numbers are added, the sign bit is
treated as part of the number and the end carry does
not indicate an overflow
! Extra overflow detection circuits are required
! An overflow can only occur when two numbers added
are both positive or both negative
4-37

Overflow Example
The two carry bits are different !!

Carries : 0 1 Carries : 1 0
+70 0 1000110 -70 1 0111010
+80 0 1010000 -80 1 0110000
-------- ---------------- -------- ----------------
+150 1 0010110 (-106) -150 0 1101010 (+106)
(010010110) (101101010)

Overflow

4-38

19
Overflow Detection
! An overflow condition can be detected by observing
the carry into the sign bit position and the carry out
of the sign bit position
! If these two carries are not equal, and overflow has
occurred
! If the output V is equal to 1, an overflow is detected

4-39

Adder-Subtractor Circuit
! Unsigned
! C bit detects a carry after addition or a borrow after
subtraction
! Signed
! V bit detects an overflow
0: no overflow; 1: overflow

4-40

20
Decimal Adder
! A decimal adder requires a minimum of 9 inputs
and 5 outputs
! 1 digit requires 4-bit
! Input: 2 digits + 1-bit carry
! Output: 1 digit + 1-bit carry
! BCD adder
! Perform the addition of two decimal digits in BCD,
together with an input carry from a previous stage
! The output sum cannot be greater than 19 (9+9+1)

4-41

Derivation of BCD Adder

Binary Sum BCD Sum Decimal
K Z8 Z4 Z2 Z1 C S8 S4 S2 S1
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1
………… ………… ……
0 1 0 1 0 1 0 0 0 0 10
0 1 0 1 1 1 0 0 0 1 11
0 1 1 0 0 1 0 0 1 0 12
0 1 1 0 1 1 0 0 1 1 13
0 1 1 1 0 1 0 1 0 0 14
0 1 1 1 1 1 0 1 0 1 15
1 0 0 0 0 1 0 1 1 0 16
1 0 0 0 1 1 0 1 1 1 17
1 0 0 1 0 1 1 0 0 0 18
1 0 0 1 1 1 1 0 0 1 19
4-42

21
BCD Adder
! When the binary sum is equal to or less than 1001b
! BCD Sum = Binary Sum
! C=0
! When the binary sum is greater than 1001b
! BCD Sum = Binary Sum + 0110b
! C=1
Z8Z4
Z2Z1 00 01 11 10

00 1

01 1
C = K + Z8Z4 + Z8Z2
11 1 1

10 1 1
4-43

Block Diagram of a BCD Adder

C = K + Z8Z4 + Z8Z2

If C =1 , it is necessary
to add 0110 to binary sum
4-44

22
Binary Multiplier

For a J*K bits multiplier , we need:

(J * K) AND gates
(J – 1) K-bit adders
to produce a product of J+K bits

4-45

4-Bit By 3-Bit Binary Multiplier

B3 B2 B1 B0
A2 A1 A0
0 B3A0 B2A0 B1A0 B0A0
carryout
B3A1 B2A1 B1A1 B0A1

carryout B3A2 B2A2 B1A2 B0A2

C6 C5 C4 C3 C2 C1 C0

We need 12 AND gates

and two 4-bit adders to
produce a product of 7 bits
4-46

23
Magnitude Comparator
! Equal (A = B)
! A3=B3 and A2=B2 and A1=B1 and A0=B0
Xi = 1 means
Xi = AiBi + Ai’Bi’ for i = 0,1,2,3 Ai and Bi are equal !!
! (A=B) = X3X2X1X0
! Greater (A > B) or Less (A < B)
! Comparison start from the MSB
! If the two digits are equal, compare the next lower digits
! Continues until a pair of unequal digits is reached
! A is 1 and B is 0 => A > B

! A is 0 and B is 1 => A < B

(A > B) = A3B3’ + X3A2B2’+ X3X2A1B1’ + X3X2X1A0B0’

(A < B) = A3 ’ B3 + X3A2’ B2+ X3X2A1’ B1 + X3X2X1A0’ B0
4-47

4-Bit Magnitude Comparator

4-48

24
Outline
! Combinational Circuits
! Analysis and Design Procedures
! Binary Adders
! Other Arithmetic Circuits
! Decoders and Encoders
! Multiplexers

4-49

Decoder
! A circuit that coverts binary information from n
input lines to a maximum of 2n unique output lines
! May have fewer than 2n outputs
! A n-to-m-line decoder (m ≤ 2n):
! Generate the m minterns of n input variables
! For each possible input combination, there is only
one output that is equal to 1
! The output whose value is equal to 1 represents the
minterm equivalent of the binary number presently
available in the input lines

4-50

25
3-to-8-Line Decoder
! The 3 inputs are decoded
into 8 outputs
! Each represent one of the
minterms of the inputs
variables

Inputs Outputs
x y z D0 D1 D2 D3 D4 D5 D6 D7
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
4-51

2-to-4-Line Decoder with Enable

! Some decoders are constructed with NAND gates
! Generate minterms in their complement form
! An enable input can be added to control the operation
! E=1: disabled
! None of the outputs are equal to 0

4-52

26
Demultiplexer
! A circuit that receives information from a single line
and directs it to one of 2n possible output lines
! A decoder with enable input can function as a
demultiplexer
! Often referred to as a decoder/demultiplexer

data input
selection

4-53

Construct Larger Decoders

! Decoders with enable inputs can be
connected together to form a larger
decoder
! The enable input is used as the
most significant bit of the selection
signal
! w=0: the top decoder is enabled

! w=1: the bottom one is enabled

! In general, enable inputs are a

convenient feature for standard
components to expand their
numbers of inputs and outputs

4-54

27
Combinational Logic Implementation
! A decoder provides the 2n minterms of n input variables
! Can be used to form any combinational circuits with extra OR

gates (sum of minterms)

! A function having a list of k minterms can be expressed in its
complemented form F’ with 2n – k minterms
! If k > 2 /2, F’ will have fewer minterms (fewer OR gates)
n

! NOR gates are used instead for implementing F’

S(x,y,z) = (1,2,4,7)
C(x,y,z) = (3,5,6,7)

4-55

Encoder
! A circuit that performs the inverse operation of a decoder
! Have 2 (or fewer) input lines and n output lines
n

! The output lines generate the binary code of the input positions
! Only one input can be active at any given time
! An extra output may be required to distinguish the cases that
D0 = 1 and all inputs are 0
Inputs Outputs
D0 D1 D2 D3 D4 D5 D6 D7 x y z
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 z = D1 + D 3 + D5 + D7
0 0 1 0 0 0 0 0 0 1 0 y = D2 + D 3 + D 6 + D 7
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0 x = D4 + D 5 + D 6 + D 7
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
4-56

28
Priority Encoder
! An encoder circuit that includes the priority function
! If two or more inputs are equal to 1 at the same time, the input
having the highest priority will take precedence
! In the following truth table:
! D3 > D2 > D1 > D0

! The X’s in output columns represent don’t-care conditions

! The X’s in input columns are useful for representing a truth

table in condensed form

Inputs Outputs
D0 D1 D2 D3 x y V
0 0 0 0 X X 0
1 0 0 0 0 0 1
V=0:
X 1 0 0 0 1 1 no valid inputs
X X 1 0 1 0 1
X X X 1 1 1 1 4-57

Implement a Priority Encoder

x = D2 + D 3
y = D3 + D1D’2
V = D0 + D 1 + D 2 + D 3

4-58

29
Outline
! Combinational Circuits
! Analysis and Design Procedures
! Binary Adders
! Other Arithmetic Circuits
! Decoders and Encoders
! Multiplexers

4-59

Multiplexer
! A circuit that selects binary information from one of many input
lines and directs it to a single output lines
! Have 2 input lines and n selection lines
n

! Act like an electronic switch (also called a data selector )

! For the following 2-to-1-line multiplexer:

! S=0 # Y = I0 ; S=1 # Y = I1

4-60

30
4-to-1-Line Multiplexer
! The combinations of S0
and S1 control each AND
gates
! Part of the multiplexer
resembles a decoder
! To construct a multiplexer:
! Start with an n-to-2
n

decoder
! Add 2 input lines, one
n

to each AND gate

! The outputs of the decoder !!
AND gates are applied
to a single OR gate
4-61

Quadruple 2-to-1-Line Multiplexer

! Multiplexers can be combined
with common selection
inputs to provide multiple-bit
selection logic
! Quadruple 2-to-1-line
multiplexer:
! Four 2-to-1-line multiplexers

! Each capable of selecting

one bit of the 2 4-bit inputs

! E: enable input

E=1: disable the circuit

(all outputs are 0)

4-62

31
Boolean Function Implementation
! A multiplexer is essentially a decoder with an external OR gate
! Can be used to implement Boolean functions without extra logic

! To implement a Boolean function of n variables:

! Use a multiplexer with n - 1 selection inputs

! The first n – 1 variables are connected to

the selection inputs

! The remaining variable is used for

the data inputs

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

4-63

Implementing a 4-Input Function

F(A,B,C,D) = logic 0: connected to ground
(1,3,4,11,12,13,14,15) logic 1: connected to Vdd (5V)

can be 0, 1, the variable, or its complement

4-64

32
Three-State Gate
! A circuit that exhibits three states
! logic 1, logic 0, and high-impedance (z)

! The high-impedance state acts like an open circuit (disconnected)

! The most commonly used three-state gate is the buffer gate
! C=0 # disabled (high-impedance) ; C=1 # enabled (pass)

! Can be used at the output of a function without altering the

internal implementation

4-65

Implementation with 3-State Gates

! A large number of three-state gate outputs can be connected with
wires to form a common line (bus) without logic conflicts
! Very convenient for implementing some circuits (ex: multiplexer)

! Only one buffer can be in the active state at any given time

! One way to ensure that no more

than one control input is active
at any given time is to use a
decoder

4-66

33