Combinational logic
3. Combinational Logic
3.1 Boolean Implementation of Arithmetic Functions
ELEE08015 Digital System Design 2
1
Additional Reading:
Textbook (Donzellini et. al.): Section 2.1, 2.2, 2.3, 3.6, 3.9.1, 3.9.2, 3.9.3
Note that the material presented in the course notes, videos, and exercise sets should be
considered as the main source for notations, formulations, and design principles while the
textbook material should be only considered as complementary.
Combinational logic
Carry = A . B
Sum = A . B +A . B = A⊕B
Combinational Logic for Binary addition
● Suppose we want to design a circuit to add two
single bit numbers A and B
– 0 and 1 now signify numerical values zero andone
A B Carry Sum
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
Truth table Boolean expression
ELEE08015 Digital System Design 2
2
Combinational logic
Sum = A . B + A . B
Binary Half Adder
● Logic gate
implementations of
binary half adder:
B
A
Sum
Sum
Carry
Carry
A
B
Equivalent to:
Carry = A . B
Sum = A⊕B
ELEE08015 Digital System Design 2
3
Combinational logic
Full addition
● Add two unsigned n-bit binary natural numbers:
n−1 :0 n− 1 n− 2 1 0A = {A , A , ... A , A }
and
Bn− 1 : 0 = {B n− 1 , B n− 2 , ... B1 , B0 }
representing
An− 1 2
n −1 + An− 2
n− 2 1
1 02 + ... + A 2 + A 2
0
and
Bn− 1 2
n −1 + Bn− 2
n− 2 1
1 02 + ... + B 2 + B 2
0
ELEE08015 Digital System Design 2
4
Combinational logic
4-bit Full Addition Example
● Add two unsigned 4-bit binary natural numbers:
A3 :0 = {A3 , A2 , A1 , A0} and B 3 :0 = {B 3 , B 2 , B1 , B0}
representing
and
Example:
A 3 2 1 0
3 :0 = 11D = {1, 0, 1, 1} = 1×2 + 0×2 + 1×2 + 1×2
B 3 2 1 0
3 :0 = 7D = {0, 1, 1, 1} = 0×2 + 1×2 + 1×2 + 1×2
A3 23 + A2 22+ A1 21 + A0 20
B3 23 + B2 22+ B1 21 + B0 20
ELEE08015 Digital System Design 2
5
Combinational logic
● Example: 11 + 7 = 18
D D D
●
●
●
●
● Full addition requires input carry
and output carry
Addends are 4-bits, but result
requires 5-bits (overflow)
1−bit Full Addition
4 3 2 1 01● 8 = {1, 0, 0, 1, 0 }= 1× 2 + 0× 2 + 0× 2 + 1× 2 + 0× 2
D
ELEE08015 Digital System Design 2
6
A B Cin Cout Sum
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
Full Adder Truth Table:
Combinational logic
Synthesising Truth Table: Karnaugh map
ELEE08015 Digital System Design 2
7
• A Karnaugh map is a table of cells with each cell representing one minterm (or maxterm).
• Maps for two variables have four cells, for three variables eight cells, for four variables
sixteen cells and so on.
• The cells are laid out so that moving from one cell to any adjacent cell results in a
change in one variable, i.e., hamming distance of 1 between codewords.
• Where a minterm is to be included in the logic function a 1 is written in the cell.
Otherwise a 0 is written in or it is left blank. Don’t cares can be also included and treated
as 1 or 0 as appropriate!
• Thus, any two adjacent cells that both contain a 1 represent terms that differ in one
variable and can be combined as: !. # + !. %# = !. # + %# = !
• The map can be inspected for groups of ones and
their minimised form can be written.
• The minimisation relies on combining adjacent 1s into
groups as large as possible of given the group has a
size of power of 2 and a rectangular shape.
• Note that the maps have cyclic property and thus the
groups can be rolls over from left end to the right and
so on.
BC
A 00 01 11 10
0 1 1 0 1
1 1 1 0 0 A.C
B
3-variable Karnaugh Map
Combinational logic
Karnaugh Map
ELEE08015 Digital System Design 2
8
Consider the following map for two variables. All four
minterms are present and given a truth table can be entered
in the map. Now assume the Kmap for truth table below: B
A 0 1
0 A.B A.B
1 A.B A.B
Truth table Truth table applied to map
A B F
0 0 1
0 1 1
1 0 0
1 1 1
B
A 0 1
0 1 1
1 0 1
• We can now draw loops round groups of 1s in
the map to represent the mimimised terms.

F = A.B +A.B +A.B
= A.B +B. A +A( )
= A.B +B
= A +BB
A
• Hence F = A + B directly from the
map. We know how to reduce the
function using Boolean algebra too:B
A 0 1
0 1 1
1 0 1
Combinational logic
A B Cin Cout
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
C
in
B⋅C in
00 01 11 10 A ⋅B
0 0 0 1 0
1 0 1 1 1
A⋅C in
Truth table
Karnaugh map
A B
C = A ⋅ B+A ⋅ C + B ⋅ C
out in in
Boolean expression
Karnaugh map for Cout
ELEE08015 Digital System Design 2
9
Combinational logic
Karnaugh map for Sum
0 1 0 1
1 0 1 0
C
in
00 01 11 10
0
1
A B Cin Sum
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Karnaugh map
A B
Truth table Boolean expression
Sum = A ⋅ B ⋅ C i n +A ⋅ B ⋅C i n +A ⋅ B ⋅C i n + A ⋅ B ⋅ C i n
ELEE08015 Digital System Design 2
10
Combinational logic
Simplified expression for Sum
● Using Boolean algebra:
ELEE08015 Digital System Design 2
11
Combinational logic
Full adder circuit #1
A
B
C
in
Sum
C
out
Sum = A ⊕ B ⊕ Cin
C = A ⋅ B + A ⋅ C + B ⋅ C
out in in
ELEE08015 Digital System Design 2
12
Combinational logic
Full adder circuit #2
Sum = A ⊕ B ⊕ C
in
C = A ⋅ B + A ⋅ C + B ⋅ C
out in in
C = A ⋅ B + (A ⊕ B ) . C
out in
● Full adder can be
made from 2-half
adders and a 2-
input OR gate
C
A
B
in
C
out
C
out
Sum
Sum
C
in
A
B
Sum
Half Adder
Carry
Sum
Half Adder
Carry
ELEE08015 Digital System Design 2
13
Combinational logic
4-bit ripple carry adder
Full addition of A3 :0 = {A3 , A2 , A1 , A0} and B3 :0 = {B3 , B2 , B1 , B0}
generating S 3 :0 = {S3 , S 2 , S1 , S 0}
A
3
B
3
A
2
B
2
A
1
B
1
A
0
B
0
+
S
0
+
S
1
+
S
2
+
S
3
C
in
C
out
Sum is generated as the carry ripples through the chain of adders
ELEE08015 Digital System Design 2
14
Full adder symbol
+
An Bn
CinCout
Sn
Combinational logic
Ripple Carry Adder Delay
●
●
●
Depends on number of logic stages traversed
Function of applied input signals A and B
n-1 : 0 n-1 : 0
– For some input signals no rippling occurs
– For other signals, carry has to ripple from the least
significant bit (lsb) to the most significant bit (msb)
Critical Path: worst case propagation delay over
all possible input patterns
ELEE08015 Digital System Design 2
15
Combinational logic
Ripple Carry Adder Critical Path
●
●
●
Critical path occurs when
– Carry generated at the lsb position propagates all the way to the msb position
– Carry consumed at msb position to produce the sum
Propagation delay from Cin to Cout : tcarry
Propagation delay from Cin to Sum: tsum
Assume that both the delay from input signals
A0 (or B0) to Cout,0 for the lsb, and the Cin to
Cout delay for all other bits equal to tcarry .
ELEE08015 Digital System Design 2
16
Adder Truth Table: Carry Status
A B Cin Cout Sum Carry Status
0 0 0 0 0 Delete
0 0 1 0 1 Delete
0 1 0 0 1 Propagate
0 1 1 1 0 Propagate
1 0 0 0 1 Propagate
1 0 1 1 0 Propagate
1 1 0 1 0 Generate
1 1 1 1 1 Generate
– Critical path length linearly proportional
to N – increasingly significant for adders
with wide data paths
– Priority is to optimise tcarry rather
than tsum as tsum has minor
influence on total delay, tadder .
Combinational logic
Example: Critical Path
Derive values of inputs An-1:0 and Bn-1:0 so that worst case delay is obtained for
ripple carry adder
– Carry generated in lsb position. If Cin,0 is 0, both A0 and B0 = 1 (see truth table,
Generate Carry Status row)
– All other stages in Propagate mode (see truth table), hence either Ai = 1 or Bi= 1
– Set up a 0 → 1 transition on the msb sum bit:achieved by setting both An-1:0 and
Bn-1:0 to 0 (or 1).
ELEE08015 Digital System Design 2
17
For an 8-bit addition the following values of A7:0 and B7:0 set up a worst case delay:
A = { 0, 0, 0, 0, 0, 0, 0, 1}, B= { 0, 1, 1, 1, 1, 1, 1, 1}
Carry ripples through addition:
Combinational logic
Subtraction
● Use ripple carry adder to perform subtraction by taking advantage
of the following observation:
●
●
●
●
Create the code for -B from the input +B and then add to A to (-B)
Use two's complement notation to represent negative numbers.
S = A− B is the same as S = A+ ( − B)
ELEE08015 Digital System Design 2
18
Two's Complement
code mapping for
4-bit codewords:
Decimal 2's Complement Decimal 2's Complement
0 0000 0 0000
1 0001 -1 1111
2 0010 -2 1110
3 0011 -3 1101
4 0100 -4 1100
5 0101 -5 1011
6 0110 -6 1010
7 0111 -7 1001
8 - -8 1000
Combinational logic
Forming the Two's Complement #1
● Given a decimal number M , form an n-bit two's
D
complement representation:
●
●
●
●
●
D
M negative: write the n-bit binary code
M n− 1 :0 = { mn− 1 , mn− 2 , ... ,m1 , m0}
Check that n is large enough to represent M :
D
−2 n −1 ≤ M < 2n−1
D
M positive: write the n-bit binary code M
D n-1: 0
n2 − M D∣ ∣
ELEE08015 Digital System Design 2
19
Combinational logic
Example: Method #1
●
●
●
●
●
Form the 5-bit two's complement M for -12 :
Check range of 5-bit two's complement number:
−24 ≤ M < 24
D
−16 ≤ MD < 16
Number is negative, so two' complement code is:
n2 − M D∣ ∣
52 − −12 D∣ ∣ = 32D D D− 12 = 20 = 10100
4: 0 D
ELEE08015 Digital System Design 2
20
Combinational logic
Forming the Two's Complement #2
●
●
●
Alternative method to previous example.
Same method as before except when M negative
D
M negative:
D
– write the n-bit binary code M for ∣M D∣
n-1: 0
– invert all bits of M (i.e. take the one's complement)
n-1: 0
– add 1 to the result of the complement operation giving
two's complement result
ELEE08015 Digital System Design 2
21
Combinational logic
Example: Method #2
●
●
●
●
●
Form the 5-bit two's complement M for -12 :
4: 0 D
Check range of 5-bit two's complement number:
−2 4 ≤ M < 24
D
−16 ≤ MD < 16
Number is negative, so two's complement code is:
∣M D ∣= ∣−12D∣= 12D = 01100
take the complement: 10011
add 1: 10011 +1 = 10100
ELEE08015 Digital System Design 2
22
Combinational logic
Two's Complement Properties
●
●
Two's complement negative numbers have 1 as their most significant bit
Any two's complement number can have its sign changed by
complementing and adding 1.
ELEE08015 Digital System Design 2
23
Two's Complement Addition
Use 4-bit two's complement numbers. Number range:
●
●
i.e. -8 to +7
Add +3 to +4 :
D D
– result correct!
−2 n −1 ≤ M D < 2
n−1
−2 3 ≤ M < 23
D
− 8 ≤ MD < 8
Combinational logic
Another Addition Example
●
●
Use 4-bit two's complement numbers.
Add +5 to +6 :
D D
– result out of 4-bit two's complement
range
– result interpreted as a two's complement
number is -5 which is incorrect!
D
– overflow has occurred
out of range
ELEE08015 Digital System Design 2
24
Combinational logic
Further Examples
despite overflow!
despite overflow! out of range
ELEE08015 Digital System Design 2
25
Combinational logic
Two's Complement Overflow
● Two overflow cases
– negative numbers:
●
●
– and positive numbers:
–
● Overflow detected by
noting msb has changed:
out of range
out of range
Overflow = An−1 ⋅ Bn−1 ⋅ Sn − 1 + An−1 ⋅ Bn− 1 ⋅S n−1
ELEE08015 Digital System Design 2
26
Combinational logic
Overflow
A B Cin Cout Sum Overflow
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 0 1 0
0 1 1 1 0 0
1 0 0 0 1 0
1 0 1 1 0 0
1 1 0 1 0 1
1 1 1 1 1 0
Overflow = Cin ⊕ Cout
● Overflow signal truth table aids logic
simplification:
ELEE08015 Digital System Design 2
27
Combinational logic
Binary Subtraction
●
●
● Any two's complement number can have its sign changed by
complementing and adding 1.
ELEE08015 Digital System Design 2
28
4-bit Subtracter
A
3
B
3
A
2
B
2
A
1
B
1
A
0
B
0
C = 1
in,0
C
out,3
+ + + +
S S S S
3 2 1 0
Overflow
– Complement the bits of B and
add 1 to form -B anduse the
full adder to perform A + (-B)
i.e. subtraction.
Combinational logic
1-bit Adder/Subtracter
● Use an Ex-OR gate as
a selectable inverter:
+
A
n
B
n
S
n
C
in
C
out
bit
invert
bit
invert
B
n Ex-OR
0 0 0
0 1 1
1 0 1
1 1 0
ELEE08015 Digital System Design 2
29
Combinational logic
4-bit Adder/Subtracter
A
3
A
2
A
1
A
0
C
out,3 +
S
3
+
S
2
+
S
1
+
S
0
B
3
B
2
B
1
B
0
Overflow
bit
invert
bit = 0 :adder
invert
bitinvert = 1 : subtracter
ELEE08015 Digital System Design 2
30
Combinational logic
3. Combinational Logic
3.2 CMOS Implementation of Boolean Functions
ELEE08015 Digital System Design 2
31
Additional Reading:
Textbook (Donzellini et. al.): Sections 2.4 and 2.5
Textbook (Ashenden): Section B1.5
Note that the material presented in the course notes, videos, and exercise sets should be
considered as the main source for notations, formulations, and design principles while the
textbook material should be only considered as complementary.
Combinational logic
CMOS technology
● Complementary Metal Oxide Semiconductor
technology (CMOS)
– dominant integrated circuit technology
– implements digital circuits with high noise immunity
and low static power consumption
– implements analogue circuits and image sensors
– technology development over many decades has
provided ever smaller transistors
– current microprocessors contain hundreds of millions
of CMOS logic gates (transistors) on a single chip.
ELEE08015 Digital System Design 2
32
Combinational logic
Switches in CMOS technology
●
●
Two fundamental transistor/switch types: NMOS
and PMOS transistors.
NMOS transistor
– ON/closed when control G = hi
– Poor conduction if A/B signals hi
– Good conduction of A/B signals lo
– Hence used in pull-down networks.
–
● NMOS transistors cannot be used to connect to V
dd
G
A
B
ELEE08015 Digital System Design 2
33
Combinational logic
Switches in CMOS technology
● PMOS transistor
– ON/closed when control G = lo
– Good conduction if A/B signals hi
– Hence used in pull-up networks.
– Poor conduction of A/B signals lo
●
● PMOS transistors cannot be used to connect to 0V.
G
A
B
ELEE08015 Digital System Design 2
34
Combinational logic
CMOS inverter (NOT gate)
●
●
M1
M2
out
out
in
in
in hi: M1 OFF, M2 ON, out lo
in lo: M1 ON, M2 OFF, out hi
V dd
0V
R1
SW 0
V dd
R0
0V
SW 1
out
ELEE08015 Digital System Design 2
35
Combinational logic
CMOS inverter waveforms
●
●
●
●
Ideal input signal
Output signal with
propagation delay, rise
and fall time.
Virtually no power
consumption for static
signals.
Power consumed
when signals change.
V dd
0V
V dd
0V
Imax
0 A
out
in
I
time (S)
ELEE08015 Digital System Design 2
36
Combinational logic
CMOS NAND gate #1
● Output F lo (connected to 0V)
only when both inputs are hi.
A B F
0 0 1
0
1
1
1
0
1
1
1
0
F = A . B
FA
B F
B
A
V dd
0V
Pull− up
network
ELEE08015 Digital System Design 2
37
Combinational logic
CMOS NAND gate #2
● Output F hi (connected to V )
dd
when either input is lo.
A B F
0 0 1
0
1
1
1
0
1
1
1
0
FA
B F
A B
V dd
0V
Pull− down
network
ELEE08015 Digital System Design 2
38
Combinational logic
CMOS NAND gate #3
● Complete circuit
– When PMOS transistors
connect F to V , NMOS
dd
transistors do not connect to
0V (and vice-versa).
– No short circuit between V
dd
and 0V.
F
V dd
0V
A
B
F = A . B
ELEE08015 Digital System Design 2
39
Combinational logic
3-input CMOS NAND gate
A B C F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
V dd
F
A
B
C
F = A . B . C 0V
ELEE08015 Digital System Design 2
40
Combinational logic
CMOS NOR gate #1
F
BA
V dd
0V
Pull−up
network
● Output F lo (connected to 0V)
when either inputs is hi.
A B F
0 0 1
0
1
1
1
0
1
0
0
0
A
B
F
F = A + B
ELEE08015 Digital System Design 2
41
Combinational logic
CMOS NOR gate #2
● Output F hi (connected to V )
dd
when both inputs are lo.
B
A
V dd
A B F
0 0 1
0 1 0
1 0 0
1 1 0
A
B
F
F
Pull− down
network
0V
ELEE08015 Digital System Design 2
42
Combinational logic
CMOS NOR gate #3
● Complete circuit
– When PMOS transistors
connect F to V , NMOS
dd
transistors do not connect to
0V (and vice-versa).
– No short circuit between V
dd
and 0V.
V dd
B
A
F
F = A + B
0V
ELEE08015 Digital System Design 2
43
Combinational logic ELEE08015 Digital System Design 2
44
3-input CMOS NOR gate
V dd
B
A
F
C
A B C F
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0
F = A + B + C 0V
Combinational logic
CMOS AND gate
● Not possible to
implement AND
function with simple
pull-up and pull-down
network
B
A
V dd
F
A
B
F
FA
B
0V
ELEE08015 Digital System Design 2
45
Combinational logic
CMOS OR gate
● Not possible to
implement OR
function with simple
pull-up and pull-down
network
V dd
FB
A
A
B
F
FA
B
0V
ELEE08015 Digital System Design 2
46
Combinational logic
Number of transistors per gate
●
●
●
Different gates require different numbers of
transistors:
– 4 transistors for 2-input NAND and 2-input NOR
– 6 transistors for 2-input AND and 2-input OR
Therefore in a CMOS implementation of a
Boolean expression it is more efficient to use
NAND/NOR gates
De Morgan's laws can usually be used to convert
expressions into forms using NAND and NOR.
ELEE08015 Digital System Design 2
47
Combinational logic
Example #1
● Define the minimum number of CMOS
transistors required to implement the following
Boolean expression using NOR-only design:
F = A . B Apply De Morgan
F = A + B
A
B
F
8 transistors 6 transistors
A
B
F
ELEE08015 Digital System Design 2
48
Combinational logic
Example #2
●
F = A . B + C . D
Minimise the number of CMOS transistors
required using NAND-only design:
Apply De Morgan
F = A . B . C . D
A
B
C
F
A
B
C
F
D D
18 transistors 12 transistors
ELEE08015 Digital System Design 2
49
Combinational logic
NAND versus NOR
●
●
●
●
●
PMOS transistors have less drive strength than
NMOS transistors (for a given geometry)
– a majority carrier mobility issue
NAND gates: PMOS in parallel, NMOS in series
NOR gates: PMOS in series, NMOS in parallel
NOR gate slower: weaker PMOS transistors in
series (whereas in parallel in a NAND gate).
NAND gate faster than a NOR gate and typically
occupies less area than a NOR gate.
ELEE08015 Digital System Design 2
50
Combinational logic
General CMOS gates
●
●
●
Complex CMOS gates may be constructed for
general logic functions
The gate is composed of two networks
– A pull-down network composed of NMOS transistors
connecting the output to 0V
– A pull-up network composed of PMOS transistors
connecting the output to V
dd
The gate may have an inverter after the pull-
down/pull-up gate.
ELEE08015 Digital System Design 2
51
Combinational logic
General CMOS gates
n
n− inputs
n− inputs
0V
V dd
Pull−up
network
n−PMOS
out (o u t. )
n−NMOS
Pull−down
network
in
ELEE08015 Digital System Design 2
52
●
●
Equal number of NMOS and PMOS transistors
Every NMOS transistor has an equivalent PMOS transistor
connected to the same input
• Series pull-down
NMOS correspond to
parallel pull-up
PMOS
• Parallel pull-down
NMOS correspond
to series pull-up
PMOS
Combinational logic
Important rule
●
●
M1
M2
outin
PMOS transistors cannot be used to connect to 0V
NMOS transistors cannot be used to connect to V
V dd
Wrong !!
0V
dd
ELEE08015 Digital System Design 2
53
Combinational logic
Boolean expression must be of the form: F = (SOP)
Bar over whole term indicates an inverter is not
needed at output of pull-up/pull-down network
No bar indicates the need for an inverter at the
output of the pull-up/pull-down network
– Use inverse of the SOP expression to derive the pull-
up/pull-down network
SOP: Sum Of Products
Form of Boolean expression
●
●
●
●
ELEE08015 Digital System Design 2
54
Combinational logic
F = (A.B)+C
Pull-down network
implementation:
– Connect F to 0V when A is hi
AND B is hi OR C is hi
Example #1
● Sketch a CMOS transistor
network to implement the
Boolean expression:
●
●
B
A
V dd
0V
F
C
Pull− up
network
ELEE08015 Digital System Design 2
55
Combinational logic
F = (A+B).C
Connect F to V when A is lo
dd
Example #1
(continued)
● Pull-up network: rearrange
expression using De Morgan:
●
●
OR B is lo AND C is lo.
V dd
BA
C
F
Pull−down
network
0V
ELEE08015 Digital System Design 2
56
Combinational logic
F = (A.B)+C
Example #1
(continued)
● Complete gate V ddBA
C
F
A
C
B
0V
ELEE08015 Digital System Design 2
57
Combinational logic
F = (A+B).C
Pull-down network
implementation:
– Connect F to 0V when A
is hi OR B is hi AND C
is hi
Example #2
● Sketch a CMOS transistor
network to implement the
Boolean expression:
●
●
A B
V dd
0V
F
C
Pull− up
network
ELEE08015 Digital System Design 2
58
Combinational logic
F = (A.B)+C
Example #2
(continued)
● Pull-up network: rearrange
expression using De Morgan:
●
●
dd
Connect F to V when A is lo
AND B is lo OR C is lo.
V dd
F
B
A C
Pull−down
network
0V
ELEE08015 Digital System Design 2
59
Combinational logic
F = (A+B).C
Example #2
(continued)
● Complete gate V dd
0V
F
B
A C
BA
C
ELEE08015 Digital System Design 2
60