Digital Design I
Lecture 7 – Combinational Logic
Asst. Prof. Dr. Ertuğrul SAATÇI
Binary Adder-Subtractor
Binary Adder
A binary adder is a digital circuit that produces the arithmetic sum
of two binary numbers.
It can be constructed with full adders connected in cascade, with
the output carry from each full adder connected to the input carry
of the next full adder in the chain.
Interconnection of four full adder (FA) circuits to provide a 4-bit
binary ripple carry adder. (Input carry C0 ripples through the FAs)
MSB LSB
1
Binary Adder-Subtractor
Binary Adder
The augend bits of A and the addend bits of B are shown by
subscript numbers from right to left, with subscript 0 denoting the
least significant bit (LSB) and subscript 3 denoting the most
significant bit (MSB).
Consider two binary numbers A = 1011 and B = 0011. Their sum
S = 1110 is formed with the four bit adder as follows:
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
An n bit adder requires n full adders with each output carry
connected to the input carry of the next higher-order full adder.
Binary Adder-Subtractor
Carry Propagation
In any adder, the signal must propagate through the gates
before the correct output sum is available at the output.
The total propagation time is equal to the propagation delay of
a typical gate times the number of gate levels in the circuit.
The longest propagation delay time in an adder is the time it
takes the carry to propagate through the full adders.
Only after the carry propagates and ripples through all stages
will the last output S3 and carry C4 settle to their final correct
value.
2
Binary Adder-Subtractor
Carry Propagation
From the circuit of the full adder, it can be seen that the signal
from the input carry Ci to the output carry Ci+1 propagates through
an AND gate and an OR gate, which constitute two gate levels.
If there are four full adders in the binary adder, the output carry C4
would have 2×4 = 8 gate levels from C0 to C4.
For an n bit adder, there are 2n gate levels for the carry to
propagate from input to output.
Binary Adder-Subtractor
Carry Propagation
The carry propagation time is a limiting factor on the speed
with which two numbers are added.
Although the adder will always have some value at its output
terminals, the output will not be correct unless the signals are
given enough time to propagate through the gates connected
from the inputs to the outputs.
Solution is to increase the equipment complexity in such a way
that the carry delay time is reduced.
There are several techniques for reducing the carry
propagation time in a parallel adder. The most widely used one
is carry lookahead.
3
Binary Adder-Subtractor
Carry Propagation
Consider the circuit of the full adder, if we define two new
binary variables:
Pi = AiBi
Gi = AiBi
the output sum and carry can be expressed as
Si = PiCi
Ci+1 = Gi+PiCi
Gi is called a carry generate and it produces a carry of 1 when
both Ai and Bi are 1, regardless of the input carry Ci.
Pi is called a carry propagate because it is the term associated
with the propagation of the carry from Ci to Ci+1.
Binary Adder-Subtractor
Carry Propagation
If we write the Boolean functions for the carry outputs of each
stage and substitute for each Ci its value from the previous
equations:
C0 = input carry
C1 = G0+P0C0
C2 = G1+P1C1 = G1+P1(G0+P0C0) = G1+P1G0+P1P0C0
C3 = G2+P2C2 = G2+P2G1+P2P1G0+ P2P1P0C0
Since the Boolean function for each output carry is expressed
in sum of products, each function can be implemented with one
level of AND gates followed by an OR gate.
4
Binary Adder-Subtractor
Carry Propagation
The carry lookahead
generator
implementation of the
three Boolean functions
for C1, C2 and C3:
Note that C3 does not
have to wait for C2 and
C1 to propagate.
In fact, C3 is
propagated at the
same time as C1 and
C2.
Binary Adder-Subtractor
Carry Propagation
The construction of a 4-bit
adder with carry lookahead
scheme:
The output of the first XOR
gate generates the Pi variable,
and the AND gate generates
the Gi variable.
The carries are propagated
through the carry lookahead
generator and applied as
inputs to the second XOR
gate.
All output carries are
generated after a delay
through two levels of gates.
10
5
Binary Adder-Subtractor
Binary Subtractor
The circuit subtracting A-B consists of an adder with inverters
placed between each data input B and corresponding input of
the full adder.
The input carry C0 must be equal to 1 during the subtraction.
The operation performed becomes:
A + the 1’s complement of B + 1
This is equal to
A + the 2’s complement of B
For unsigned numbers, this gives
• (A-B) if A B or
• the 2’s complement of (B-A) if A < B
For signed numbers, the result is (A-B) provided that there is no
overflow.
11
Binary Adder-Subtractor
Binary Subtractor
The addition and subtraction operations can be combined into
one circuit with one common binary adder.
This is done by including an XOR gate with each full adder.
The mode input M controls the operation. When M=0 the circuit
is an adder, and when M=1 the circuit becomes an subtractor.
12
6
Binary Adder-Subtractor
Overflow
When two unsigned numbers are added, an overflow is detected
from the end carry out of the most significant position.
The leftmost bit of the signed numbers always represents the
sign and negative numbers are in 2’s complement form.
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.
An overflow cannot occur after an addition if one number is
positive and the other is negative, since the result is smaller
than the larger of the two original numbers.
An overflow may occur if the two numbers added are both
positive or both negative.
13
Binary Adder-Subtractor
Overflow
Two signed binary numbers (+70 and +80) are stored in two 8-bit
registers (each register can accommodate from +127 to -128):
Carries: 01 Carries: 10
+70 0 1000110 -70 1 0111010
+80 0 1010000 -80 1 0110000
+150 1 0010110 -150 0 1101010
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.
The output V of the binary adder-subtractor circuit detects an
overflow if the numbers are signed. After an addition or subtraction
• If V=0, there is no overflow and the n-bit result is correct.
• If V=1 then an overflow occurred. The (n+1)th bit is the actual
sign and has been shifted out of position.
14
7
Decimal Adder
Computers, that perform arithmetic operations directly in the
decimal number system, represent decimal numbers in binary
coded form.
An adder must employ arithmetic circuits that accept coded
decimal numbers and present results in the same code.
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.
15
Decimal Adder
BCD Adder
Consider the arithmetic addition of two decimal digits in BCD,
together with an input carry from a previous stage.
Since each input digit does not exceed 9, the output sum cannot
be greater than 9 + 9 + 1 = 19, the 1 in the sum being an input
carry.
When binary sum is greater than 1001, the addition of binary 6
(0110) to binary sum converts it to correct BCD representation
and also produces an output carry as required.
Carry 1 1
+9 1001 Result 0001 0011
+9 1001 +6 0110
+19 0001 0011 +19 0001 1001
Wrong 1 3 Correct 1 9
16
8
Decimal Adder
BCD Adder
Suppose we apply two BCD digits to a 4-bit binary adder.
The adder will produce a result in binary that ranges from 0 to 19.
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 0 0 1 0 0 0 0 1 0 2
0 0 0 1 1 0 0 0 1 1 3
0 0 1 0 0 0 0 1 0 0 4
0 0 1 0 1 0 0 1 0 1 5
0 0 1 1 0 0 0 1 1 0 6
0 0 1 1 1 0 0 1 1 1 7
0 1 0 0 0 0 1 0 0 0 8
0 1 0 0 1 0 1 0 0 1 9
17
Decimal Adder
BCD Adder
Binary Sum BCD Sum Decimal
K Z8 Z4 Z2 Z1 C S8 S4 S2 S1
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
When the binary sum is equal to or less than 1001, the corresponding
BCD number is identical, and therefore no conversion is needed.
18
9
Decimal Adder
BCD Adder
When the binary sum is greater than 1001, a non-valid BCD
representation is obtained.
The logic circuit that detects the necessary correction can be
derived from the table.
From the table, it is obvious that
• A correction is needed when the binary sum has an output carry
K=1.
• The other six combinations from 1010 through 1111 that need a
correction have a 1 in position Z8.
• To distinguish them from binary 1000 and 1001, which also have a 1
in position Z8, we specify further that either Z4 or Z2 must have a 1.
The condition for a correction and an output carry:
C = K + Z8 Z 4 + Z 8 Z 2
when C=1, it is necessary to add 0110 to the binary sum and
provide an output carry for the next stage.
19
Decimal Adder
BCD Adder
A BCD adder that adds two
BCD digits and produces a
sum digit in BCD.
The two decimal digits,
together with input carry,
are first added in the top
4-bit adder to produce the
binary sum.
When the output carry is
equal to 0, nothing is
added to the binary sum.
When it is equal to 1,
binary 0110 is added to
the binary sum through
the bottom 4-bit adder.
A decimal parallel adder
that adds n decimal digits
needs n BCD adder stages.
20
10
Binary Multiplier
Multiplication of binary numbers is performed in the same way as in
decimal numbers.
Multiplicand is multiplied by each bit of the multiplier starting from
the least significant bit (LSB).
Each such multiplication forms a partial product and successive
partial products are shifted one position to the left.
The final product is obtained from the sum of the partial products.
B1 B0 multiplicand
A1 A0 multiplier
A0B1 A0B0
A1B1 A1B0
C3 C2 C1 C0
21
Binary Multiplier
Consider the multiplication of two
2-bit numbers
B1B0 multiplicand bits
A1A0 multiplier bits
C3C2C1C0 product bits
B1 B0
A1 A0
A0B1 A0B0
A1B1 A1B0
C3 C2 C1 C0
The multiplication of two bits is
identical to an AND operation.
The partial products can be
implemented with AND gates.
The two partial products are added
with two half adder circuits.
22
11
Binary Multiplier
Usually there are more bits in the partial products and it is necessary
to use full adders to produce the sum of the partial products.
B3 B2 B1 B0 multiplicand
A2 A1 A0 multiplier
A0B3 A0B2 A0B1 A0B0 level 0
A1B3 A1B2 A1B1 A1B0 level 1
A2B3 A2B2 A2B1 A2B0 level 2
C6 C5 C4 C3 C2 C1 C0
A bit of multiplier is ANDed with each bit of the multiplicand.
The binary output in each level of AND gates is added with the partial
product of the previous level to form a new partial product.
The last level produces the product.
Note that the LSB bit of the product does not have to go through an
adder since it is formed by the output of the first AND gate.
23
Binary Multiplier
A multiplier circuit that multiplies a
binary number of 4 bits (B3B2B1B0)
by a number of 3 bits (A2A1A0).
For K multiplicand and J multiplier
bits we need (K×J) AND gates and
(J-1) K-bit adders to produce a
product of J+K bits.
In the example K=4 and J=3, we
need
• 12 AND gates
• two 4-bit adders
• to produce a product of 7 bits.
24
12
Magnitude Comparator
A magnitude comparator is a combinational circuit that compares
two numbers, A and B, and determines their relative magnitudes.
The outcome is specified by three binary variables:
• (A > B) greater than
• (A < B) less than
• (A = B) equal
The circuit for comparing two n-bit numbers has 22n entries in truth
table and becomes too cumbersome even with n=3.
An algorithm is a procedure that specifies a finite set of steps that, if
followed, give the solution to a problem.
A comparator can be designed by means of an algorithmic
procedure.
The algorithm is a direct application of the procedure a person uses
to compare the relative magnitudes of two numbers.
25
Magnitude Comparator
The Algorithm
Consider two numbers, A and B, with four digits each:
A = A3A2A1A0
B = B3B2B1B0
The two numbers are equal if all pairs of significant digits are equal:
A3 = B3 and A2 = B2 and A1 = B1 and A0 = B0
The equality relation of each pair of bits can be expressed
logically with an XNOR function as
xi = AiBi + A’iB’i for i=0,1,2,3
where xi = 1 only if both bits in position i are equal.
For the equality condition to exist, all xi variables must be equal
to 1. This dictates an AND operation of all variables:
(A=B) = x3x2x1x0
26
13
Magnitude Comparator
The Algorithm
To determine if A is greater than or less than B,
The relative magnitudes of pairs of significant digits starting from
the most significant position is compared.
If the two digits are equal, we compare the next lower significant
pair of digits.
This comparison continues until a pair of unequal digits is
reached. In this case, if the corresponding digits
• A = 0 and B = 1, then A < B
• A = 1 and B = 0, then A > B
The sequential comparison can be expressed logically by the two
Boolean functions:
(A > B) = A3B’3 + x3A2B’2 + x3x2A1B’1 + x3x2x1A0B’0
(A < B) = A’3B3 + x3A’2B2 + x3x2A’1B1 + x3x2x1A’0B0
27
Magnitude Comparator
The Circuit
Logic diagram of the 4-bit
magnitude comparator.
xi = AiBi + A’iB’i for i=0,1,2,3
(A=B) = x3x2x1x0
(A > B) = A3B’3 + x3A2B’2 +
x3x2A1B’1 + x3x2x1A0B’0
(A < B) = A’3B3 + x3A’2B2 +
x3x2A’1B1 + x3x2x1A’0B0
28
14
