Chapter 3

Combinational Logic
Design
M. Morris Mano, Charles R. Kime. (2015). Logic and computer design fundamentals (5th ed.). Pearson.

1
Contents

1. Combinational Functional Blocks

2. Rudimentary Logic Functions
3. Decoding
4. Encoding
5. Selecting

2
Contents

6. Iterative Combinational Circuits

7. Binary Adders
8. Binary Subtraction
9. Binary Adder-Subtractor

3
1. Combinational Functional Blocks

• Corresponding to each of the functions is a combinational

circuit implementation called a functional block.
• In the past, functional blocks were packaged as small-scale-
integrated (SSI), medium-scale integrated (MSI), and large-
scale-integrated (LSI) circuits.
• Today, they are often simply implemented within a very-
large-scale-integrated (VLSI) circuit.
4
2. Rudimentary Logic Functions

• Functions of a single variable X

• Four different functions are possible

Value Transferring Inverting Value

fixing fixing
5
Multiple-bit Rudimentary Functions

• Multiple-bit functions as vectors of single-bit functions

• We can order the four functions with F3 as the most significant bit and F0
the least significant bit, providing the vector F = (F3, F2, F1, F0).
• Suppose that F consists of
rudimentary functions F3 = 0,
F2 = 1, F1 = A, and F0 = A.
Then we can write F as the
vector (0, 1, A, A).
A wide line is used to represent
a bus which is a vector signal.
6
Multiple-bit Rudimentary Functions

• In (b) of the example, F = (F3, F2, F1, F0) is a bus.

• The bus can be split into
individual bits as shown
in (b)
• Sets of bits can be split from
the bus as shown in (c)
for bits 2 and 1 of F.
• The sets of bits need not be
continuous as shown in (d)
for bits 3, 1, and 0 of F.

7
Enabling

• Enabling permits an input signal to pass through to

an output.
• Disabling blocks an input signal from passing
through to an output, replacing it with a fixed value.
• The value on the output when it is disable can be Hi-Z, 0 ,
or 1. (disabled value)

Figure (a) : Disabled value is 0

If EN is 1, the input X reaches the output (enabled).
If EN is 0 (disabled) , the output is fixed at 0.

Figure (b) : Disabled value is 1

If EN is 1, the input X reaches the output (enabled).
If EN is 0 (disabled) , the output is fixed at 1. 8
Enabling
• Example 3-5. Car Electrical Control using
Enabling
• The problem: In most automobiles, the lights, radio,
and power windows operate only if the ignition
switch is turned on. In this case, the ignition switch
acts as an “enabling” signal. Suppose that we model
this automotive subsystem using the following
variables and definitions:
• Input Switches (inputs)
• Ignition switch IG: Value 0 if off and value 1 if on
• Light switch LS: Value 0 if off and value 1 if on
• Radio switch RS: Value 0 if off and value 1 if on
• Power window switch WS: Value 0 if off and value 1 if on
• Accessory Control (outputs)
• Lights L: Value 0 if off and value 1 if on
• Radio R: Value 0 if off and value 1 if on
• Power windows W: Value 0 if off and value 1 if on

9
3. Decoding

• Decoding is the conversion of an n-bit input code to an m-bit

output code with n ≤ m ≤ 2n, such that each valid input code
word produces a unique output code.
• Circuits that perform decoding are called decoders.
• 1-to-2-Line Decoder

10
3. Decoding

• 2-to-4-Line Decoder

𝐴1 𝐴0

Note that the 2-4-line decoder

made up of 2 1-to-2-line
decoders and 4 AND gates. 11
3. Decoding

• 3-to-8-Line Decoder
A2 A1 A0 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
12
Decoder and Enabling Combinations

• See truth table below for function

• Note use of X’s to denote both 0 and 1
• Combination containing two X’s represent
four binary combinations
• Alternatively, can be
viewed as distributing
value of signal EN to 1
of 4 outputs
• In this case, called a
demultiplexer

13
Structural Verilog Description of 2–to–4-Line
Decoder

A1_n

A0_n
N0

N1

N2

N3 14
Dataflow Verilog Description of 2–to–4-Line
Decoder

A1_n

A0_n
N0

N1

N2

N3 15
Decoder-Based Combinational Circuits

• Since any Boolean function can be expressed as a sum of

minterms, one can use a decoder to generate the minterms
and combine them with an external OR gate to form a sum-
of-minterms implementation.
• In this way, any combinational circuit with n inputs and m
outputs can be implemented with an n–to–2n-line decoder
and m OR gates.

16
Decoder-Based Combinational Circuits

• For example: Decoder and Or-gate implementation of a

Binary Adder Bit

17
4. Encoding

• An encoder is a digital function that performs the inverse

operation of a decoder.
• An encoder has 2n (or fewer) input lines and n output lines.
The output lines generate the binary code corresponding to
the input value.

18
4. Encoding

• An example of an encoder is the octal-to-binary encoder.

19
Priority Encoder

• A priority encoder is a
combinational circuit that
implements a priority function.
• The operation of the priority
encoder is such that if two or
more inputs are equal to 1 at the
same time, the input having the
highest priority takes
precedence.
• The valid output designated by V
is set to 1 only when one or more
of the inputs are equal to 1. Among the 1s that appear, it selects
the most significant input position.
20
5. Selecting

• Selecting of data or information is a critical function in digital

systems and computers
• Circuits that perform selecting have:
• A set of information inputs from which the selection is made
• A single output
• A set of control lines for making the selection
• Logic circuits that perform selecting are called multiplexer.
Selecting can also be done by three-state logic or transmission
gates.
21
Multiplexers

• A multiplexer is a combinational circuit that selects binary

information from one of many input lines and directs the
information to a single output line.
• The selection of a particular input line is controlled by a set
of input variables, called selection inputs.
• Normally, there are 2n input lines and n selection inputs
whose bit combinations determine which input is selected.
22
2-to-1-Line Multiplexer

• The single selection variable S has two values: (n = 1)

• S = 0 selects input I0
• S = 1 selects input I1
• The equation:
Y = SI0 + SI1

23
2-to-1-Line Multiplexer

• The single selection variable S has two values: (n = 1)

• S = 0 selects input I0
• S = 1 selects input I1
• The equation:
Y = SI0 + SI1

24
2n-to-1-Line Multiplexer

• In general, for an 2n-to-1-line multiplexer:

• n-to-2n-line decoder
• 2n x 2 AND-OR

25
4-to-1-Line Multiplexer

• 2-to-22-line decoder
• 22  2 AND-OR

26
Structural Verilog Description for a 4-to-1-Line
Multiplexer

Not_S[0]

Not_S[1] D[0]
N[0]

D[1]
N[1]

D[2]

N[2]
D[3]
N[3]

27
Dataflow Verilog Description for a 4-to-1-Line
Multiplexer

28
6. Iterative Combinational Circuits

• Arithmetic functions
• Operate on binary vectors
• Use the same subfunction in each bit position
• Can design functional block for subfunction and repeat to obtain
functional block for overall function
• Cell - subfunction block
• Iterative array - a array of interconnected cells
• An iterative array can be in a single dimension (1D) or multiple
dimensions
29
6. Iterative Combinational Circuits

30
6. Binary Adders

• Half-Adder (HA) is an arithmetic circuit that generates the sum of

two binary digits.
• The circuit has two inputs and two outputs.
• Full-Adder (FA) is a combinational circuit that forms the
arithmetic sum of three input bits.
• The circuit has three inputs and two outputs.
• Ripple Carry Adder, an iterative array to perform binary addition.

31
Half Adder

• A half adder is an arithmetic circuit that generates the sum

of two binary digits. The circuit has two inputs and two
outputs.
• We assign the symbols X and Y to the two inputs and S (for “sum”)
and C (for “carry”) to the outputs.
X 0 0 1 1
+Y +0 +1 +0 +1
CS 00 01 01 10
32
Half Adder
X 0 0 1 1
+Y +0 +1 +0 +1
CS 00 01 01 10

Y Y
S C
0 1 0 1
0 1 0
X X
1 1 1 1

K-Maps
33
Full Adder

• A full adder is similar to a half adder, but includes a carry-in

bit from lower stages. Like the half-adder, it computes a
sum bit, S and a carry bit, C. Z 0 0 0 0
• For a carry-in Z of 0 X 0 0 1 1
+Y +0 +1 +0 +1
CS 00 01 01 10
Z 1 1 1 1
• For a carry-in Z of 1 X 0 0 1 1
+Y +0 +1 +0 +1
34
CS 01 10 10 11
Full Adder
Z 0 0 0 0
YZ
X 0 0 1 1 S
00 01 11 10
+Y +0 +1 +0 +1 0 1 1
X
CS 00 01 01 10 1 1 1
Z 1 1 1 1 YZ
X 0 0 1 1 C
00 01 11 10
+Y +0 +1 +0 +1 0 1
X
CS 01 10 10 11 1 1 1 1

35
Binary Ripple Carry Adder Description Subscript Name
3210
Carry In 0110 Ci
Augend 1011 Ai
• Example: 4-bit ripple carry adder Addend 0011 Bi
• A four-bit Ripple Carry Adder made Sum 1110 Si
from four 1-bit Full Adders Carry out 0011 Ci+1

C0 is assumed
to be zero, or
we can use a
half adder for
A0 and B0
36
full_adder

37
8. Binary Subtraction

• Unsigned numbers are all positive integers including zero.

• M–N
1. Subtract the subtrahend N from the minuend M; result is n bits
2. If no end borrow occurs, then M ≥ N, and the result is a non-negative number
and correct.
3. If an end borrow occurs, then N > M, and the difference M - N + 2n, is subtracted
from 2n, and a minus sign is appended to the result.
• Subtraction of a binary number from 2n to obtain an n-digit result is
called taking the 2s complement of the number. So in step 3, we are
taking the 2s complement of the difference M - N + 2n.

38
8. Binary Subtraction

• 0 1 End Borrow
1001 0100
- 0111 - 0111
00010 1101
Step 3
10000
- 1101
(-) 0011

39
Complements

• There are two types of complements for each base-r system: the radix complement, and the
diminished radix complement.
• Diminished Radix Complement of N
• (r - 1)’s complement for radix r
• 1’s complement for radix 2
• Defined as (rn - 1) – N
• Obtained by complementing each individual bit (bitwise NOT).

• Radix Complement
• r’s complement for radix r
• 2’s complement in binary
• Defined as rn – N
• Is the 1's complement plus 1, a fact that can be used in designing hardware

40
Unsigned Subtraction with 2’s Complement

• The subtraction of two n-digit unsigned numbers, M - N, in binary can

be done as follows:
1. Add the 2s complement of the subtrahend N to the minuend M. This performs
M + (2n - N) = M - N + 2n.
2. If M ≥ N, the sum produces an end carry, 2n. Discard the end carry, leaving
result M - N.
3. If M < N, the sum does not produce an end carry, since it is equal to 2n - (N - M),
the 2s complement of N - M. Perform a correction, taking the 2s complement of
the sum and placing a minus sign in front to obtain the result - (N - M).

41
Unsigned Subtraction with 2’s Complement

• Find 010101002 – 010000112

Carry 1
01010100 01010100
– 01000011 2’s complement + 10111101
00010001
• The carry of 1 indicates that no correction of the result is
required.
42
Unsigned Subtraction with 2’s Complement

• Find 010000112 – 010101002

Carry 0
01000011 01000011
– 01010100 2’s complement + 10101100
11101111 2’s complement 00010001

• The carry of 0 indicates that a correction of the result is required.

• The result: -00010001

43
Signed Integers

• Positive numbers and zero can be represented by unsigned n-digit, radix r numbers.
We need a representation for negative numbers.
• To represent a sign (+ or –) we need exactly one more bit of information (1 binary
digit gives 21 = 2 elements which is exactly what is needed).
• Since computers use binary numbers, by convention, the most significant bit is
interpreted as a sign bit:
• s an–2 … a2a1a0
where:
s = 0 for Positive numbers
s = 1 for Negative numbers
and ai = 0 or 1 represent the magnitude in some form.

44
Signed Integers

• Signed-Magnitude – here the n – 1 digits are interpreted as a

positive magnitude.
• Signed-Complement – here the digits are interpreted as the rest
of the complement of the number. There are two possibilities
here:
• Signed 1's Complement
• Uses 1's Complement Arithmetic
• Signed 2's Complement
• Uses 2's Complement Arithmetic

45
Signed Integers

• r = 2, n = 3 Number Sign-Mag. 2’s Comp.

+3 011 011
• We need a sign bit with 2’s +2 010 010
complements to distinguish +1 001 001
between positive and negative +0 000 000
-0 100 ---
numbers.
-1 101 111
-2 110 110
-3 111 101
-4 --- 100
46
Signed 2’s Complement Arithmetic

• Addition:
1. Add the numbers including the sign bits, discarding a carry out of the
sign bits
2. If the sign bits were the same for both numbers and the sign of the
result is different, an overflow has occurred.
3. The sign of the result is computed in step 1.
• Subtraction:
• Take the 2’s complement of the subtrahend (including the sign bit) and add it to the
minuend (including the sign bit). A carry out of the sign bit position is discarded.

47
Signed 2’s Complement Arithmetic

• Example 1: 1101 (-3)

+0011 (+3)
0000

• Example 2: 1101 (-3) 1101 (-3)

2’s comp.
-0011 (+3) + 1101 (-3)
1010 (-6)
48
2’s Complement Adder/Subtractor

• Subtraction can be done by addition of the 2’s complement.

• 1. Complement each bit (1's Complement.)
• 2. Add 1 to the result.
• The circuit shown computes A + B and A – B:
• For S = 1, subtract, B3 A3 B2 A2 B1 A1 B0 A0

the 2’s complement

of B is formed by using S
XORs to form the 1’s
comp and adding the 1
applied to C0.
• For S = 0, add, B is
passed through
unchanged FA
C3
FA
C2
FA
C1
FA
C0

49
C4 S3 S2 S1 S0
Overflow Detection

• Overflow occurs if n + 1 bits are required to contain the result from an n-bit
addition or subtraction
• Unsigned numbers
• When two unsigned numbers are added, an overflow is detected from the end carry
out of the most significant position. In unsigned subtraction, the magnitude of the
result is always equal to or smaller than the larger of the original numbers, making
overflow impossible.
• Signed Numbers
• Overflow can occur for:
• Addition of two operands with the same sign
• Subtraction of operands with different signs

50
Overflow Detection

• Examples: 8-bit signed numbers

Overflow Overflow

• 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, an overflow has occurred.
If V = 0 after a signed
addition or subtraction, it
indicates that no overflow
has occurred and the result
is correct. If V = 1, then an
51
overflow has occurred.
Verilog HDL Models of Adders
hs

hc tc

52
Behavioral Verilog for a 4-Bit Ripple Carry
Adder

• The + represents addition and the {}

represents an operation called
concatenation.
• The operation + performed on wire
data types is unsigned.
• Concatenation combines two signals into a single signal having its number of bits
equal to the sum of the number of bits in the original signals.
• In the example, {C4,S} represents the signal vector
C4 S[3] S[2] S[1] S[0]
with 1 + 4 = 5 signals.
• Note that C4, which appears on the left in the concatenation expression, appears on the left in
the signal listing

53