Digital Design

CS302
R e f : D ig it a l D e s ig n . M . M o r r i s Ma n o , a nd M ic h a e l D .
Cil e tti . Pe a r so n, FI F T H ED I TI O N , 2 0 1 3
Combinational
Logic
CHAPTER 4 (PART2)
4.6 DECIMAL ADDER
A decimal adder requires a minimum of nine
inputs and five outputs, since
◦ four bits are required to code each decimal
digit and
◦ the circuit must have an input and output carry
Since each input digit does not exceed 9, the
output sum cannot be greater than 19 (9 + 9 + 1),
the 1 in the sum being an input carry

Chapter 4- 3
Binary-Coded Decimal BCD
The code most
commonly used for the
decimal digits is the
straight binary
assignment.
This scheme is called
binary‐coded decimal
and is commonly
referred to as BCD.

Chapter 4-
4
Binary-Coded Decimal BCD
Suppose we add the BCD digits as if they were
binary numbers. Then the binary sum will
produce a result in the range from 0 to 19.

Chapter 4- 5
BCD Adder
In binary, this range will be from 0000 to 10011.
In BCD, it is from 0000 to 1 1001, with the first 1
being a carry and the next four bits being the BCD
sum.
This condition occurs when the sum is greater than
or equal to 16.
Although the other four bits are less than 1001, the
binary sum requires a correction because of the
carry by adding 0110 (6 =16-10).

Chapter 4- 6
BCD Adder
The addition of two n‐digit unsigned BCD numbers
follows the same procedure.
Consider the addition of 184 + 576 = 760 in BCD:

Chapter 4- 7
BCD Adder
BCD adder : performs operations on number
stored in B C D form.
- Four Xi (input): X8 , X 4 , X 2 , X1
- Four Yi (addend input): Y8 , Y4 , Y2 , Y1
◦ The sum will be stored in Z8 , Z4 , Z2 , Z1

The basic adder consists of base-16 addition

Chapter 4- 10
 4.7 Binary Multiplier
For J multiplier bits and K multiplicand bits, we
need (J x K) AND gates and (J - 1) K-bit adders to
produce a product of J + K bits.

J=3, K=4       B3 B2 B1 B0
        A2 A1 A0
(12) AND gates       A0B3 A0B2 A0B1 A0B0
(2) 4-bit adders     A1B3 A1B2 A1B1 A1B0  
  A2B3 A2B2 A2B1 A2B0    
C6 C5 C4 C3 C2 C1 C0

Chapter 4- 11
Chapter 4- 12
Chapter 4- 13
4.8 MAGNITUDE
COMPARATOR
A magnitude comparator is a combinational circuit
that compares two numbers A and B and
determines their relative magnitudes.

The outcome of the comparison is specified by

Chapter 4-
14
Build a one-bit comparator
B 0 1
A A>B : AB'
0 A=B A<B
A=B : A'B' + AB
1 A>B A=B
A<B : A'B

A
A>B

B A=B

A<B

Chapter 4- 15
Four-bit comparator
Consider two numbers, A and B , with four digits each.
A = A3 A2 A1 A0 and B = B3 B2 B1 B0
The two numbers are equal if all pairs of significant digits are equal:
A3 = B3 , A2 = B2 , A1 = B1, and A0 = B0 .
When the numbers are binary, the digits are either 1 or 0, and the
equality of each pair of bits can be expressed logically with an
exclusive-NOR function as
xi = Ai Bi + Ai ' Bi ' = Ai' Bi NOR Ai Bi ' for i = 0, 1, 2, 3
where xi = 1 only if the pair of bits in position i are equal

Chapter 4-
16
Four-bit comparator
For equality to exist, all xi variables must be equal to 1, a
condition that dictates an AND operation of all variables:
(A = B)= x3 x2 x1 x0
To determine whether A is greater or less than B , we inspect
the relative magnitudes of pairs of significant digits, starting
from the most significant position.
If the two digits of a pair are equal, we compare the next
lower significant pair of digits.
The comparison continues until a pair of unequal digits is
reached.

Chapter 4-
17
Four-bit comparator
To determine whether A is greater or less than B , we inspect the
relative magnitudes of pairs of significant digits, starting from the
most significant position.
If the two digits of a pair are equal, we compare the next lower
significant pair of digits.
The comparison continues until a pair of unequal digits is reached.
If the corresponding digit of A is 1 and that of B is 0, we conclude
that A > B. If the corresponding digit of A is 0 and that of B is 1, we
have A < B. The sequential comparison can be expressed logically by
the two Boolean functions
(A > B ) = A3 B’3 + x3 A2 B’2 + x3 x2 A1 B’1 + x3 x2 x1 A0 B’0
(A < B ) = A’3 B3 + x3 A’2 B2 + x3 x2 A’1 B1 + x3 x2 x1 A’0 B0
Chapter 4- 18
 Four-bit comparator
A>B

A<B
A A A A
A3 A2 A1 A0
A>B A>B A>B A>B
B3 B B2 B B1 B B0 B
A=B A=B A=B A=B A=B
1 EN EN EN EN

Page 192,
4.1 a,b, 4.2, 4.3, 4.4, 4.6 a, 4.7 a, 4.8 a, 4.9, 4.10

Chapter 4-
19
(A < B ) = A’3 B3 + x3 A’2 B2 + x3 x2
A’1 B1 + x3 x2 x1 A’0 B0

(A > B ) = A3 B’3 + x3 A2 B’2 + x3 x2

(A = B)= x3 x2 x1 x0

Chapter 4-
20
4.9 DECODERS
A decoder converts binary information from n
input lines to a maximum of 2n output lines.

The decoders presented here are called n-to-m-

Purpose: generate the 2n (or fewer) mintems of n

Chapter 4- 21
Chapter 4- 22
Chapter 4- 23
Some decoders are constructed with NAND gates.
Decoders include one or more enable inputs to control the
circuit operation

A+B+E

A+B'+E

A'+B+E

The decoder is enabled when E=0

Chapter 4-
24
Decoder - Demultiplexer
A decoder with enable input can function as a
demultiplixer
A demultiplixer circuit that receives information from a
single Line and directs it to one of 2n possible outputs
lines
The selection of a specific output is controlled by the bit
combination of n selection lines.
The preceding decoder can function as a one-to-four-
line demultiplexer when E is taken as a data input line
and A and B are taken as the selection inputs.

Chapter 4- 25
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 outputs generate minterms 1000 to 1111,
while the outputs of the top decoder are all 0’s.

Chapter 4- 26
Combinational Logic Implementation
Implementing a combinational circuit by means of
a decoder and OR gates requires that
◦ the Boolean function be expressed as a sum of
minterms.
◦ A decoder is then chosen that generates all the
minterms of the input variables.
◦ The inputs to each OR gate are selected from the
decoder outputs according to the list of minterms of
each function.

Chapter 4-
27
Full Adder

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

Chapter 4- 28
4.10 ENCODERS
Encoding - the opposite of decoding - the
conversion of an m-bit input code to a n-bit output
code with n £ m £ 2n such that each valid code
word produces a unique output code
Circuits that perform encoding are called encoders
An encoder has 2n (or fewer) input lines and n
output lines which generate the binary code
corresponding to the input values

Chapter 4- 29
z = D1+ D3 + D5 + D7
y = D2 + D3 + D6 + D7
x = D4 + D5 + D6 + D7,

Chapter 4- 30
Priority Encoder
A priority encoder is an encoder circuit that
includes the 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 will take precedence.

Chapter 4- 31
Priority Encoder

Chapter 4- 32
 4.11 MULTIPLEXERS
A multiplexer selects information from an input line and
directs the information to an output line
Normally, a multiplexer has
1. 2n inputs (I2n - 1, … I0), ( 2n information)
2. n control inputs (S0 , …, Sn - 1) (selection inputs),
and
3. one output Y
A multiplexer can be designed to have m information
inputs with m <= 2n as well as n selection inputs
Chapter 4- 33
2-to-1-Line Multiplexer
Since 2 = 21, n = 1
The single selection variable S has two values:
◦ S = 0 selects input I0
◦ S = 1 selects input I1

Y = I0 S’+ SI1

Chapter 4-
34
4-to-1-line multiplexer
Each of the four inputs, I0 through I3, is applied to one
input of an AND gate.
Selection lines S1 and S0 are decoded to select a
particular AND gate.
The outputs are applied to a single OR gate .
A multiplexer is also called a data selector , since it
selects one of many inputs and steers the binary
information to the output line.

Chapter 4-
35
Chapter 4-
36
In general, a 2n -to-1-line multiplexer is constructed from an
n -to-2n decoder by adding 2n input lines to it, one to each
AND gate.

The outputs of the AND gates are applied to a single OR

Chapter 4-
37
 Boolean Function Implementation
it was shown that a decoder can be used to implement
Boolean functions by employing external OR gates.
The minterms of a function are generated in a
multiplexer by the circuit associated with the selection
inputs.
The individual minterms can be selected by the data
inputs, thus providing a method of implementing a
Boolean function of n variables with a multiplexer that
has n selection inputs and 2n data inputs, one for each
minterm.
Chapter 4-
38
Chapter 4- 39
4.1 , 4.2, 4.4, 4.5, 4.6 a, 4.7a, 4.9,4.10
4.11,4.12,4.12(a),4.15, 4.16 (first part)
4.21, 4.23
4.25  4.28,4.31, 4.32
Ngw:1 , 4.2, 4.4, 4.5, 4.6 a, 4.7a, 4.9,4.10
4.11,4.12,4.12(a),4.15, 4.16 (first part)
4.21, 4.23

Chapter 4-
40