Digital Logic Design Lecture Notes 1.ppt

DLD Lecture notes.ppt

1. Number Systems
EEE365
Digital Logic Design
Dr.Quazi Delwar Hossain
Chittagong University of Engineering and Technology

2. Introduction to Number Systems & Codes
Digital & Analog systems, Numerical representation, Digital number systems,
Binary to Decimal conversions, Decimal to Binary conversions, Hexa-decimal
number systems, BCD code, The Gray code, Alphanumeric codes, Parity method
for error detection, Octal & Hexa-decimal numbers, Complements.
1
St
Cycle

3. Data can be Data can be analoganalog or or digitaldigital
 Analog data refers to information that is continuous
 Analog data take on continuous values
 Analog signals can have an infinite number of values in a range
 Digital data refers to information that has discrete states
 Digital data take on discrete values
 Digital signals can have only a limited number of values
In data communications, we commonly use
periodic analog signals and non-periodic digital signals.
ANALOG AND DIGITAL

4. ANALOG & DIGITAL SYSTEMS
An Analog system contains devices that manipulate
physical quantities that are represented in analog form.
 In an analog system, the quantities can vary over a
continuous range of values.
 For example, the amplitude of the output signal to the
speaker in a radio receiver can have any value between zero
and its maximum limit.
 Other common analog systems are audio amplifiers,
magnetic tape recording and playback equipment and a
simple light dimmer switch.

5. More over, a 1 can be encoded as a positive voltage and
a 0 as zero voltage.
 A digital signal can have more than two levels.
 In this case, we can send more than 1 bit for each level.
A Digital system is a combination of devices designed to
manipulate logical information or physical quantities that
are represented in digital form; that is, the quantities can
take on only discrete values.
These devices are most often electronic, but they can
also be mechanical, magnetic or pneumatic.
Some of the more familiar digital systems include digital
computers, calculator, Digital audio and video equipment
and telephone system etc.
Continue………………

6. ADC and DAC Converters
•Analog-to-Digital Converter (ADC)
–Produces digitized version of analog signals
–Analog input => Digital output
•Digital-to-Analog Converter (DAC)
–Regenerate analog signal from digital form
–Digital input => Analog output
•Our focus is on digital systems only
–Both input and output to a digital system are digital signals
Analog-to-Digital
Converter (ADC)
Digital-to-Analog
Converter (DAC)
Digital System
input digital
signals
output digital
signals
input analog
signals
output analog
signals

7. DIGITAL SYSTEMS

8. DIGITAL SYSTEM STRUCTURE

9. Digital Signal
Analog Signal

10. Advantages of Digital Techniques
 Very much easier to design.
 Information storage is easy.
 Accuracy and precision are easier to maintain throughout
the system.
 Operation can be programmed.
Less affected by noise.
More circuits can be fabricated on IC chips.
Limitations of Digital Techniques:
 The real world is analog
Processing digitized signals takes time.

11. How do Computers Represent Digits?
•Binary digits (0 and 1) are used instead of decimal digits
•Using electric voltage
–Used in processors and digital circuits
–High voltage = 1, Low voltage = 0
•Using electric charge
–Used in memory cells
–Charged memory cell = 1, discharged memory cell = 0
•Using magnetic field
–Used in magnetic disks, magnetic polarity indicates 1 or 0
•Using light
–Used in optical disks, surface pit indicates 1 or 0
High = 1
Low = 0
Unused
V
o
lt
a
g
e

L
e
v
e
l

12. Binary Numbers
•Each binary digit (called a bit) is either 1 or 0
•Bits have no inherent meaning, they can represent …
–Unsigned and signed integers
–Fractions
–Characters
–Images, sound, etc.
•Bit Numbering
–Least significant bit (LSB) is rightmost (bit 0)
–Most significant bit (MSB) is leftmost (bit 7 in an 8-bit number)
10011101
2
7
2
6
2
5
2
4
2
3
2
2
2
1
2
0
01234567
Most
Significant Bit
Least
Significant Bit

13. Decimal Value of Binary Numbers
•Each bit represents a power of 2
•Every binary number is a sum of powers of 2
•Decimal Value = (d
n-1  2
n-1
) + ... + (d
1  2
1
) + (d
0  2
0
)
•Binary (10011101)
2
=
10011101
2
7
2
6
2
5
2
4
2
3
2
2
2
1
2
0
01234567
Some common
powers of 2
2
7
+ 2
4
+ 2
3
+ 2
2
+ 1 = 157

14. Different Representations of Natural Numbers
XXVIIRoman numerals (not positional)
27Radix-10 or decimal number (positional)
11011
2Radix-2 or binary number (also positional)
Fixed-radix positional representation with n digits
Number N in radix r = (d
n–1
d
n–2
. . . d
1
d
0
)
r
N
r Value = d
n–1×r
n–1
+ d
n–2×r
n–2
+ … + d
1×r + d
0
Examples:(11011)
2 =
(2107)
8
=
Positional Number Systems
1×2
4
+ 1×2
3
+ 0×2
2
+ 1×2 + 1 = 27
2×8
3
+ 1×8
2
+ 0×8 + 7 = 1095

15. Other Number Systems
•Binary Number System: Radix = 2
–Only two digit values: 0 and 1
–Numbers are represented as 0s and 1s
•Octal Number System: Radix = 8
–Eight digit values: 0, 1, 2, …, 7
•Decimal Number System: Radix = 10
–Ten digit values: 0, 1, 2, …, 9
•Hexadecimal Number Systems: Radix = 16
–Sixteen digit values: 0, 1, 2, …, 9, A, B, …, F
–A = 10, B = 11, …, F = 15
•Octal and Hexadecimal numbers can be converted easily
to Binary and vice versa

16. Octal and Hexadecimal Numbers
•Octal = Radix 8
•Only eight digits: 0 to 7
•Digits 8 and 9 not used
•Hexadecimal = Radix 16
•16 digits: 0 to 9, A to F
•A=10, B=11, …, F=15
•First 16 decimal values
(0 to15) and their values
in binary, octal and hex.
Memorize table
Decimal
Radix 10
Binary
Radix 2
Octal
Radix 8
Hex
Radix 16
0 0000 0 0
1 0001 1 1
2 0010 2 2
3 0011 3 3
4 0100 4 4
5 0101 5 5
6 0110 6 6
7 0111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F

17. Binary, Octal, and Hexadecimal
Binary, Octal, and Hexadecimal are related:
Radix 16 = 2
4
and Radix 8 = 2
3
Hexadecimal digit = 4 bits and Octal digit = 3 bits
Starting from least-significant bit, group each 4 bits into
a hex digit or each 3 bits into an octal digit
Example: Convert 32-bit number into octal and hex
497A61BE Hexadecimal
32-bit binary00101001111001010110100011010111
42632550353 Octal

18. The conversion is done as follows:
1)If the number has a radix point then separate the
number into an integer part and a fraction part, since the
two parts must be converted differently.
2)The conversion of a decimal integer part to a number in
base r is done by dividing the integer part and all
successive quotients by r and accumulating the remainders.
3)The conversion of a decimal fraction part to a number
in base r is done by multiplying the fractional parts by r and
accumulating integers.
Conversion from Decimal to base r

19. Convert Decimal to Binary
•Repeatedly divide the decimal integer by 2
•Each remainder is a binary digit in the translated value
•Example: Convert 37
10
to Binary
37 = (100101)
2
least significant bit
most significant bit
stop when quotient is zero

20. Convert Decimal to Binary

21. Convert Decimal to Octal
Convert decimal (153.513)
10
to Octal
The Octal number is (231.406517)
8

22. Converting Decimal to Hexadecimal
422 = (1A6)
16
stop when
quotient is zero
least significant digit
most significant digit
Repeatedly divide the decimal integer by 16
Each remainder is a hex digit in the translated value
Example: convert 422 to hexadecimal
To convert decimal to octal divide by 8 instead of 16

23. Convert Binary (base 2) to Decimal (base 10)
Convert base 5 to Decimal (base 10)
Convert Octal (base 8) to Decimal (base 10)
Convert Hexadecimal (base 16) to Decimal (base 10)
Conversion from base r to Decimal
The conversion of a number in base r to decimal number (base 10) is
done by expanding the number in power series and adding all the terms as
shown below:

24. Other Conversions

25. Second Cycle
Analysis & synthesis of digital logic circuits
Basic logic functions
OR operation with OR gates, AND operation with AND gates, NOR operation
with NOR gates, Describing logic circuits algebraically, Evaluating logic circuit
outputs, Implementing circuits from Boolean expressions, NOR gates & NAND
gates.
Boolean Algebra
Boolean theorems, Demorgan’s Theorems, Universality of NAND gates & NOR
gates

26. DIGITAL LOGIC GATESDIGITAL LOGIC GATES

27. Boolean functions are implemented in digital computer
circuits called gates.
A gate is an electronic device that produces a result
based on two or more input values.
–In reality, gates consist of one to six transistors, but
digital designers think of them as a single unit.
–Integrated circuits contain collections of gates suited
to a particular purpose.
Logic gatesLogic gates

28. Electronic gates require a power supply.
Gate Input’s are driven by voltage having two nominal
values.
The Output of a gate provides two nominal values of
voltage.
There is always a Time Delay between an input being
applied and the output responding.
Point’s Need To UnderstandPoint’s Need To Understand

29. Different Types of Logic gatesDifferent Types of Logic gates
Digital systems are said to be constructed by using
gates. These gates are --
AND GATE
OR GATE
NOT GATE
NAND GATE
NOR GATE
Ex-OR GATE
Ex-NOR GATE

30. Truth TablesTruth Tables

Used to describe the functional behavior of a Boolean
expression and/or Logic circuit.

Each row in the truth table represents a unique combination
of the input variables.
For n input variables, there are 2
n
rows.

The output of the logic function is defined for each row.

Each row is assigned a numerical value, with the rows listed
in ascending order.

The order of the input variables defined in the logic
function is important.

31. AND GateAND Gate
 The AND gate is an electronic circuit that gives a high
output only if all its inputs are high.
A dot(.) is used to show the AND operation.
Truth table
2 Input AND gate
A B Z=A.B
0 0 0
0 1 0
1 0 0
1 1 1
Circuit Symbol
A
B
AND
Z=A.B

32. Summary of the AND gatesSummary of the AND gates
 The AND operation is performed the same as ordinary
multiplication of 1s and 0s.
 An AND gate is a logic circuit that performs the AND
operation on the circuit’s input.
An AND gate output will be 1 only for the case when all
inputs are 1; for all other cases, the output will be 0.
The expression Z=A.B is read as “Z equals A AND B.”

33. OR GateOR Gate
 The OR gate is an electronic circuit that gives a high
output. One or more of its inputs are high.
A plus (+) is used to show the OR operation.
Truth table
2 Input OR gate
A B Z=A+B
0 0 0
0 1 1
1 0 1
1 1 1
A
B
OR
Z=A+B
Circuit Symbol

34. Summary of the OR gatesSummary of the OR gates
 The OR operation produces a result (output) of 1
whenever any input is a1. Otherwise the output is 0.
 An OR gate is a logic circuit that performs an OR
operation on the circuit’s input.
The expression Z=A+B is read as “Z equals A OR B.”

35. NOT GateNOT Gate
 The NOT gate is an electronic circuit that produces an
inverted version of the input at its output.
 More commonly called an Inverter.
Truth tableCircuit Symbol
NOT GATE
A A
0 1
1 0
A A

36. NAND GateNAND Gate
 The NAND gate which is to NOT - AND gate.
Truth table
Circuit Symbol

A.B
A
B
NAND
2 Input NAND gate
A B A.B
0 0 1
0 1 1
1 0 1
1 1 0

37. NOR GateNOR Gate
 The NOR gate which is to NOT - OR gate.
Truth table
2 Input NOR gate
A B A+B
0 0 1
0 1 0
1 0 0
1 1 0
Circuit Symbol
A+BA
B
NOR

38. EX-OR GateEX-OR Gate
 The Exclusive –OR gate is a circuit which will give a high
output.An encircled plus sign() is used to show the EX-OR
operation.
Truth table
Circuit Symbol
A  B
A
B
EX-OR
2 Input EXOR gate
A B A B
0 0 0
0 1 1
1 0 1
1 1 0

39. EX-NOR GateEX-NOR Gate
 The Exclusive –NOR gate is circuit does the opposite to the
EX-NOR gate. The symbol is an EX-NOR gate with a small
circle on the output. The small circle represents inversion.
Truth table
2 Input EXNOR gate
A B A B
0 0 1
0 1 0
1 0 0
1 1 1
Circuit Symbol
A  B
A
B
EX-NOR

40. NAND and NOR are known as universal gates because
they are inexpensive to manufacture and any Boolean
function can be constructed using only NAND or only
NOR gates.
Universal GatesUniversal Gates

42. Boolean ExpressionsBoolean Expressions

Boolean expressions are composed of

Literals – variables and their complements

Logical operations

Examples

F = A.B'.C + A'.B.C' + A.B.C + A'.B'.C'

F = (A+B+C').(A'+B'+C).(A+B+C)

F = A.B'.C' + A.(B.C' + B'.C)
literals logic operations

43. Boolean ExpressionsBoolean Expressions

Boolean expressions are realized using a network
(or combination) of logic gates.
Each logic gate implements one of the logic
operations in the Boolean expression
Each input to a logic gate represents one of the
literals in the Boolean expression
f
A
B
logic operationsliterals

44. Boolean ExpressionsBoolean Expressions

Boolean expressions are evaluated by

Substituting a 0 or 1 for each literal.

Calculating the logical value of the expression.

A Truth Table specifies the value of the Boolean
expression for every combination of the variables
in the Boolean expression.

For an n-variable Boolean expression, the truth
table has 2
n
rows (one for each combination).

45. Boolean AlgebraBoolean Algebra

George Boole developed an algebraic description for
processes involving logical thought and reasoning.
Became known as Boolean Algebra

Claude Shannon later demonstrated that Boolean
Algebra could be used to describe switching circuits.
Switching circuits are circuits built from devices that
switch between two states (e.g. 0 and 1).
Switching Algebra is a special case of Boolean
Algebra in which all variables take on just two
distinct values

Boolean Algebra is a powerful tool for analyzing and
designing logic circuits.

46. Basic Laws and TheoremsBasic Laws and Theorems
Commutative Law A + B = B + A A.B = B.A
Associative Law A + (B + C) = (A + B) + CA . (B . C) = (A . B) . C
Distributive Law A.(B + C) = AB + AC A + (B . C) = (A + B) . (A + C)
Null Elements A + 1 = 1 A . 0 = 0
Identity A + 0 = A A . 1 = A
A + A = A A . A = A
Complement A + A' = 1 A . A' = 0
Involution A'' = A
Absorption (Covering) A + AB = A A . (A + B) = A
Simplification A + A'B = A + B A . (A' + B) = A . B
DeMorgan's Rule (A + B)' = A'.B' (A . B)' = A' + B'
Logic Adjacency (Combining) AB + AB' = A (A + B) . (A + B') = A
Consensus AB + BC + A'C = AB + A'C (A + B) . (B + C) . (A' + C) = (A + B) . (A' + C)
Idempotence

47. DeMorgan's LawsDeMorgan's Laws

Can be stated as follows:
The complement of the product (AND) is the
sum (OR) of the complements.

(X.Y)' = X' + Y'
The complement of the sum (OR) is the
product (AND) of the complements.

(X + Y)' = X' . Y'

Easily generalized to n variables.

Can be proven using a Truth table

48. Proving DeMorgan's LawProving DeMorgan's Law
(X . Y)' = X' + Y'

49. DeMorgan's TheoremsDeMorgan's Theorems
x
1
x
2
x
1
x
2
x
1
x
2
x
1
x
2
+ = (a)
x
1
x
2
+ x
1
x
2 = (b)
x
1
x
2
x
1
x
2
x
1
x
2
x
1
x
2

50. Importance of Boolean AlgebraImportance of Boolean Algebra

Boolean Algebra is used to simplify Boolean expressions.
–Through application of the Laws and Theorems
discussed

Simpler expressions lead to simpler circuit realization,
which, generally, reduces cost, area requirements, and
power consumption.

The objective of the digital circuit designer is to design
and realize optimal digital circuits.

51. Algebraic SimplificationAlgebraic Simplification

Justification for simplifying Boolean expressions:
–Reduces the cost associated with realizing the
expression using logic gates.
–Reduces the area (i.e. silicon) required to
fabricate the switching function.
–Reduces the power consumption of the circuit.

In general, there is no easy way to determine when a
Boolean expression has been simplified to a minimum
number of terms or minimum number of literals.
–No unique solution

52. Algebraic SimplificationAlgebraic Simplification

Boolean (or Switching) expressions can be
simplified using the following methods:
1.Multiplying out the expression.
2.Factoring the expression.
3.Combining terms of the expression.
4.Eliminating terms in the expression.
5.Eliminating literals in the expression
6.Adding redundant terms to the expression.

53. Examples

54. Minterms

A minterm, for a function of n variables, is a
product term in which each of the n variables
appears once.

Each variable in the minterm may appear in its
complemented or uncomplemented form.

For a given row in the Truth table, the
corresponding minterm is formed by
Including variable x
i
, if x
i
= 1
Including the complement of x
i
, if x
i
= 0
For all n variables
in the function F.

55. MintermsMinterms

56. MaxtermsMaxterms

A Maxterm, for a function of n variables, is a sum
term in which each of the n variables appears once.

Each variable in the Maxterm may appear in its
complemented or uncomplemented form.

For a given row in the Truth table, the
corresponding Maxterm is formed by
Including the variable x
i
, if x
i
= 0
Including the complement of x
i
, if x
i
= 1

57. MaxtermsMaxterms

58. Standard Forms for
Boolean Expressions

Sum-of-Products (SOP)
Derived from the Truth table for a function by
considering those rows for which F = 1.
The logical sum (OR) of product (AND) terms.
Realized using an AND-OR circuit.

Product-of-Sums (POS)
Derived from the Truth table for a function by
considering those rows for which F = 0.
The logical product (AND) of sum (OR) terms.
Realized using an OR-AND circuit.

59. Sum-of-ProductsSum-of-Products

Any function F can be represented by a sum of minterms,
where each minterm is ANDed with the corresponding
value of the output for F.
F = ∑ (m
i
. f
i
)
where m
i
is a minterm
and f
i
is the corresponding functional
output
Only the minterms for which f
i
= 1 appear in the
expression for function F.
F = ∑ (m
i
) = ∑ m(i)
shorthand notation
Denotes the logical
sum operation

60. Sum-of-ProductsSum-of-Products
AND
AND
OR
X.Y
Y' + X'YZ' + XY
product term
sum
Product Term = Logical ANDing of literals
Sum = Logical ORing of product terms

61. Sum-of-ProductsSum-of-Products

Use the Distributive Laws to multiply out a Boolean
expression.

Results in the Sum-of-Products (SOP) form.
not in SOP form
F = (A + B).(C + D).(E)
F = (A.C + A.D + B.C + B.D).(E)
F = A.C.E + A.D.E + B.C.E + B.D.E
Product terms are
of single variables
H = A.B.(C + D) + ABE

62. Examples Examples
AnsweAnswe
r:r:
The function has three variables, A, B, and C. The first term A is missing
two variables; therefore:

63. Product-of-Sums (POS)Product-of-Sums (POS)

64. Product-of-SumsProduct-of-Sums

Any function F can be represented by a product of
Maxterms, where each Maxterm is ANDed with the
complement of the corresponding value of the
output for F.
F = Π (M
i
. f '
i
)
where M
i
is a Maxterm
and f '
i
is the complement of the
corresponding functional output
Only the Maxterms for which f
i
= 0 appear
in the expression for function F.
F = Π (M
i
) = Π M(i)
shorthand notation
Denotes the logical
product operation

65. Product-of-SumsProduct-of-Sums
OR
OR
AND
X' + Y + Z
X.(Y' + Z).(X' + Y + Z)
product term
sum term
Sum Term = Logical ORing of variables
Product = Logical ANDing of sum terms

66. Product-of-SumsProduct-of-Sums

Use the Distributive Laws to factor a Boolean
expression.

Results in the Product-of-Sums (POS) form.
not in POS form
F = V.W.Y + V.W.Z + V.X.Y + V.X.Z
F = (V).(W.Y + W.Z + X.Y + X.Z)
F = (V).(W + X).(Y + Z)
Sum terms are
of single variables
H = (A+B).(C+D+E) + CE

67. SOP and POSSOP and POS

Any function F may be implemented as either a Sum-of-
Products (SOP) expression or a Product-of-Sums (POS)
expression.

Both forms of the function F can be realized using logic
gates that implement the basic logic operations.

However, the two logic circuits realized for the function F
do not necessarily have the same cost.

Objective: minimize the cost of the designed circuit
Compare the cost of the SOP realization with
that of the POS realization

68. Converting between SOP and POSConverting between SOP and POS

The sum-of-products (SOP) form of a Boolean
expression can be converted to its corresponding
product-of-sums (POS) form by factoring the
Boolean expression.

The product-of-sums (POS) form of a Boolean
expression can be converted to its corresponding
sum-of-products (SOP) form by multiplying out
the Boolean expression.

69. Examples Examples

70. Karnaugh MapKarnaugh Map

71. What are Karnaugh maps?What are Karnaugh maps?
•Karnaugh maps provide an alternative way of
simplifying logic circuits.
•Instead of using Boolean algebra simplification
techniques, you can transfer logic values from a
Boolean statement or a truth table into a Karnaugh
map.
•The arrangement of 0's and 1's within the map helps
you to visualize the logic relationships between the
variables and leads directly to a simplified Boolean
statement.

72. Product of Sums Simplification (1/3)Product of Sums Simplification (1/3)
•All previous examples are in sum-of-products form (F =
A’B’E’ + ACE + BD’E )
 How to obtain the product-of-sum form
–Simplified F' in the form of sum of products
–Apply DeMorgan's theorem F = (F ')'
–F': sum of products => F : product of sums

73. Simplify F(A,B,C,D) = ∑(0,1,2,5,8,9,10) in product of sums
Minterms marked ‘0’s
represent F’
F=B’D’+B’C’+A’C’D
Combine ‘0’ terms for F’
F’ = ∑(3,4,6,7,11,12,13,14,15)
= AB + CD + BD’
By DeMorgan,
F = (A’+B’)(C’+D’)(B’+D)
Product of Sums Simplification (2/3)Product of Sums Simplification (2/3)
sum of products  product of
sums

74. Product of Sums Simplification (3/3)Product of Sums Simplification (3/3)
F=B’D’+B’C’+A’C’D F = (A’+B’)(C’+D’)(B’+D)
Sum-of-Product (SOP) Product-of-Sum (POS)

75. Truth Table Truth Table  MAP MAP  Standard Standard
Ex. Table 3-2
(a) SOP
F(x,y,z) =  (1,3,4,6)
= x’z + xz’
x y z F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
(b) POS
F’(x,y,z) =  (0,2,5,7)
= xz + x’z’
F(x,y,z)=(x’+z’)(x+z)
(b) Combine 0’s
Truth Table → Map → Standard forms
(a) Combine 1’s

76. don’t care!don’t care!
•You don’t always need all 2
n
input combinations in an n-variable function.
–If you can guarantee that certain input combinations never occur.
–If some outputs aren’t used in the rest of the circuit.
•We mark don’t-care outputs in truth tables and K-maps with Xs.
•Within a K-map, each X can be considered as either 0 or 1. You should pick
the interpretation that allows for the most simplification.
xyzf(x,y,z)
000 0
001 1
010 X
011 0
100 0
101 1
110 X
111 1

77. Don’t Care ConditionsDon’t Care Conditions
•A don’t care condition, marked by (X) in the truth table,
indicates a condition where the design doesn’t care if the
output is a (0) or a (1).
•A don’t care condition can be treated as a (0) or a (1) in a K-
Map.
•Treating a don’t care as a (0) means that you do not need to
group it.
•Treating a don’t care as a (1) allows you to make a grouping
larger, resulting in a simpler term in the SOP equation.

78. Don’t-care ConditionsDon’t-care Conditions
•the function is NOT specified for the minterms
•6 combinations are unspecified in 4-bit BCD (1010-
1111)
•those don’t care inputs won’t occur in real circuit
•include the don’t-care minterms with either 1 or 0
–depends on which combination gives the simplest
expression (less gates ?lower cost ?)

79. Ex.3-9 Simplify F(w,x,y,z) = (1,3,7,11,15)
which has the don’t care conditions d(w,x,y,z) = ∑ (0,2,5)

•Sum of products
Combine 1’s: F = yz + w’x’z
Combine 1’s and some X’s
Simplification with donSimplification with don’’t care Conditionst care Conditions
Product of sums
Combine 0’s & some
X’s
F’ = z’ + wy’
F = z(w’ + y)(i) F = yz + w’x’ (ii) F = yz + w’z

80. Some You Group, Some You Don’tSome You Group, Some You Don’t
V
X 0
1 0
0 0
X 0
C C
B A
B A
BA
BA
C A
This don’t care condition was treated as a (1).
This allowed the grouping of a single one to
become a grouping of two, resulting in a simpler
term.
There was no advantage in treating this
don’t care condition as a (1), thus it was
treated as a (0) and not grouped.

81. Example: Seven Segment DisplayExample: Seven Segment Display
ABCDe
000001
100010
200101
300110
401000
501010
601101
701110
810001
910010
X X
X X
X X
X X
X X
X X
Table for e
CD
AB
00011110
00 1 0 0 1
01 0 0 0 1
11X X X X
10 1 0 X X
CD’ + B’D’
Assumption: Input
represents a legal
digit (0-9)
Input: digit encoded as 4 bits: ABCD
a
f
g
e
b
c
d

82. Example: Seven Segment DisplayExample: Seven Segment Display
ABCDa
000001
100010
200101
300111
401000
501011
601101
701111
810001
910011
X X
X X
X X
X X
X X
X X
a
f
g
e
b
c
d
Table for a
A + C + BD + B’D’
CD
AB
00011110
00 1 1 1
01 1 1 1
11X X X X
10 1 1 X X

83. BCD Display (1/6)BCD Display (1/6)

84. BCD Display (2/6)BCD Display (2/6)

85. BCD Display (3/6)BCD Display (3/6)

86. a = w + y + x’z’ + xz
b = y’ + xz’
c = w + y’z’ + yz + x’z’
d = w + xy’ + yz’ + x’y
e = yz’ + x’z’ + w’x’y’
f = w + x + y’z’ + yz
g = x’z’ + yz’ + x’y + xy’z
BCD Display (4/6)BCD Display (4/6)

87. BCD Display (5/6)BCD Display (5/6)

88. NAND gate implementation
BCD Display (6/6)BCD Display (6/6)

89. NAND & NOR Implementation (1/2) NAND & NOR Implementation (1/2)
•NAND / NOR
–basic gates used in all IC digital logic families
–Need conversion from AND/OR/NOT into
NAND/NOR
•Compare with AND/OR
–Digital circuits are frequently constructed with
NAND/NOR rather than with AND/OR gates.
–NAND and NOR gates are easier to fabricate with
electronic components than AND/OR
–Cheaper (lower cost) and faster (less delay)

90. NAND & NOR Implementation (2/2) NAND & NOR Implementation (2/2)
Real delay
depends on
the VLSI
process tech.
.35
.25
.18
.13 um
.09  90 nm

91. NANDNAND
•A “universal” gate
–any digital system can be implemented with it
•AND, OR, NOT can be obtained from NAND gates
NAND
x y (xy)’
0 0
1
0 1
1
1 0
1
1 1
0
One-input
NAND
x x’
0 1
1 0
=

92. Two Graphic Symbols for NAND GateTwo Graphic Symbols for NAND Gate
•2 equivalent graphic symbols for NAND gate
–either is acceptable

93. Two-Level Implementation with NANDTwo-Level Implementation with NAND
•Boolean function in sum of products form (AND-OR)
•DeMorgan’s theorem
F = AB + CD = ((AB)’(CD)’)’ // 2-level NAND implementation
•“AND-OR” diagram → “NAND-NAND” (all NAND diagram)

(AB)’
(CD)’
= ((AB)’(CD)’)’
AB
CD
AB+CD
=
= (AB)’’+(CD)’’
=AB+CD

94. If the single literal is complemented, it
can be connected directly to an input of
the 2nd level NAND gate.
2-Level NAND Implementation2-Level NAND Implementation
Ex 3-10 Implement F(x,y,z)=∑(1,2,3,4,5,7)
with NAND gates
1. Simplify F(x,y,z) in sum of products by
means of “map”.
2. Draw a NAND gate for each product term
with at least 2 literals.
3. Draw a single NAND gate in the 2nd level
with inputs coming from outputs of 1st
level.
4. A term with a single literal requires an
inverter in the 1st level.
3
2
4
1

95. 4-Level NAND Circuits4-Level NAND Circuits
•convert AND-OR into all-NAND by
–AND-OR  AND-invert - invert-OR
–insert an inverter if a bubble is not complemented by
another bubble in the same line
F = A(CD + B) + BC’

96. 3-Level of Gating3-Level of Gating
Ex.2 F = (AB’ + A’B)(C+D’)

97. NOR ImplementationNOR Implementation
•A universal gate
•The dual of NAND
–All procedures/rules for NAND are dual of the
corresponding procedures/rules for NOR
•NOT OR AND implemented with NOR
NOR
x y (x+y)’
0 0
1
0 1
0
1 0
0
1 1
0
One-input
NOR
x x’
0 1
1 0

98. Graphic Symbols for NOR GateGraphic Symbols for NOR Gate
•Two graphic symbols

99. 2-level NOR Implementation 2-level NOR Implementation
•Requirement
–the Boolean function in product of sums
•map  combining 0’s  complementing
•“OR-AND” diagram → all-NOR diagram
“NOR-NOR”
•Multilevel implementation – similar to
the one for NAND

100. 2-level NOR Implementation 2-level NOR Implementation
Example: F = (A + B)(C + D)E
Fig. 3.26
Implementing
F = (A + B)(C + D)E

101. 3-level NOR Implementation 3-level NOR Implementation
Example: F = (AB +AB)(C + D)
Fig. 3.27 Implementing F = (AB +AB)(C + D) with NOR gates

102. Different ImplementationsDifferent Implementations

103. AND-OR-INVERT FunctionsAND-OR-INVERT Functions
•Implement the circuit with AND-NOR or NAND-AND
•AND-NOR = NAND-AND F = (AB+CD+E)’

104. Example of Function Implementations (1/2)Example of Function Implementations (1/2)
F’ = x’y + xy’ + z
• F = (x’y + xy’+ z)’
(combining 1’s)
(combining 0’s)

105. OR-AND-INVERT FunctionsOR-AND-INVERT Functions
•Implement the circuit with OR-NAND or NOR-OR
•OR-NAND = NOR-OR F = [(A+B)(C+D)E)]’

106. Example of Function Implementations (2/2)Example of Function Implementations (2/2)
F = x’y’z’ + xyz’
F’=(x+y+z)(x’+y’+z) F = [(x+y+z)(x’+y’+z)]’
(combining 1’s)
(combining 0’s)

107. Three-Input Circuit Three-Input Circuit
Mir has three girl friends. He want to design an alarm.
w= x'yz + xy'z+ xyz' + xyz
simplification
z x y
00 01 11 10
0
1
1
1 11
z x y
00 01 11 10
0
1
1
1 11w= xy + yz+ xz
Ring the alarm when more than one girl come.
XYZW
0000
0010
0100
0111
1000
1011
1101
1111
input
output

108. Three-Input Circuit Three-Input Circuit
z x y00 01 11 10
0
1
1
1 11
w= xy + yz+ xz
XYZW
0000
0010
0100
0111
1000
1011
1101
1111
input
output
x
z
y
xy
yz
xz
o
x
z
y oLow cost
Less delay

109. Exclusive-OR (Ex-OR)Exclusive-OR (Ex-OR)
•Exclusive-OR (Ex-OR)
x y = xy’ + x’y
•x=1 or y=1 but not both
•different inputs  output = 1
•only one input equal to 1  output = 1
•Exclusive-NOR
(x ʘ y) = xy + x’y’
•same inputs (both=1 or both=0) output = 1
⇒
•Ex-OR is the complement of Exclusive-NOR
[proof] (x y)’ = (xy’+x’y)’ = (x’+y)(x+y’)
= xy +x’y’
Ex-OR
x y x♁y
0 0
0
0 1
1
1 0
1
1 1
0
Ex-NOR
x y (x♁y)’
0 0
1
0 1
0
1 0
0
1 1
1

110. Properties of Ex-ORProperties of Ex-OR
x 0 = x
x 1 = x’
x x = 0
x x’ = 1
x y’ = x’ y = (x y)’
•x,y’ different? x,y same?
≣
x y = y x
•x,y different? y,x different?
≣
(x y) z = x (y z) = x y z
•an odd number of variables equal to 1  Ex-OR
function = 1
Ex-OR
x y x♁y
0 0 0
0 1 1
1 0 1
1 1 0

111. Implementation of Ex-ORImplementation of Ex-OR
•Multiple-input exclusive-OR
–is difficult to fabricate.
•Even a two-input Ex-OR
–is usually constructed with other
types of gates
•Implementation
(a) 2 INV, 2 AND, 1 OR
(b) 4 NAND
•(xy)’ = (x’+y’)
•(x’+y’)x + (x’+y’)y = xy’+ x’y
(xy)’=(x’+y’)
xy’
x’y

112. Odd FunctionOdd Function
•An odd function = 1 when an odd number of variables is
equal to 1
•The multiple-variable exclusive-OR operation is defined
as an odd function
•due to the requirement that an odd number of
variables be equal to 1  Ex-OR function = 1,
•3-variable Ex-OR
•= sum of 4 minterms 001, 010, 100, 111
•Each of these binary numbers has an odd number
of 1’s
•n-variable Ex-OR
•= sum of 2
n-1
minterms
•whose binary numbers have an odd number of 1’s

113. Even FunctionEven Function
•An even function = 1 when an even number (or none) of
variables is equal to 1.
•Complement of an odd function.

114. Three-Variable Ex-OR FunctionThree-Variable Ex-OR Function
F = A B C (odd)  G = (A B C)’ (even)
= (AB’+A’B)C’ + (AB+A’B’)C
= (1,2,4,7)

115. Four-variable Ex-OR FunctionFour-variable Ex-OR Function
•F = A B C D (odd)  G = (A B C D)’ (even)

116. Parity Generation & CheckingParity Generation & Checking
•Ex-OR functions are useful in
–Error-detection and correction circuits
•Parity generator
–the CKT that generates the parity bit in the transmitter.
•Parity checker
–the CKT that checks the parity in the receiver.
•a even parity bit: P = xyz
•even parity check: C = xyzP
•C=1: an odd number of data bit error
•C=0: correct or an even # of data bit error

117. Parity Generation and CheckingParity Generation and Checking
Transmitter
Receiver
When C=1, odd errors!
When C=0, no error or
even errors

118. Combinational Logic Combinational Logic
CircuitsCircuits

119. Design ProcedureDesign Procedure
 The problem is stated.
The number of available input variables and required output variables is
determined.
The input and output variables are assigned letter symbols.
The truth table that defines the required relationships between inputs and
outputs is derived.
The simplified Boolean function for each output is obtained.
The logic diagram is drawn.

120. The practical design method would have to consider such constraints as ---
 Minimum number of gates
 Minimum number of inputs to a gate.
 Minimum propagation time of the signal through the circuit.
 Minimum number of interconnections and
 Limitations of the driving capabilities of each gate.
Design ProcedureDesign Procedure

121. Combinational Circuits- Half Adder CircuitCombinational Circuits- Half Adder Circuit
•Combinational logic circuits
give us many useful devices.
•One of the simplest is the
half adder, which finds the
sum of two bits.
•We can gain some insight as
to the construction of a half
adder by looking at its truth
table, shown at the right.

122. •As we see, the sum can be found using the XOR operation
and the carry using the AND operation.
Combinational Circuits - Half Adder CircuitCombinational Circuits - Half Adder Circuit
Sum (S)=x’y + xy’
Carry (C)=xy

123. •We can change our half
adder into to a full adder by
including gates for
processing the carry bit.
•The truth table for a full
adder is shown at the right.
Combinational Circuits- Full Adder CircuitCombinational Circuits- Full Adder Circuit
zz

124. •How can we change the
half adder shown below to
make it a full adder?
Combinational Circuits- Full Adder Combinational Circuits- Full Adder
CircuitCircuit

125. Combinational CircuitsCombinational Circuits
•Just as combined half adders to make a full adder, full adders
can connected in series.
•The carry bit “ripples” from one adder to the next; hence, this
configuration is called a ripple-carry adder.
Today’s systems employ more efficient adders.

126. Combinational Circuits-Full Adder CircuitCombinational Circuits-Full Adder Circuit
•Here’s completed full adder.

127. Combinational Circuits- Half Subtractor Circuit
•Combinational logic circuits
give us many useful devices.
•Another simplest circuit is
the half-subtractor, which
finds the subtract of two bits.
•We can gain some insight as
to the construction of a half
subtractor by looking at its
truth table, shown at the
right.

128. •As we see, the sum can be found using the XOR operation
and the carry using the AND operation.
Combinational Circuits - Half Subtractor Combinational Circuits - Half Subtractor
CircuitCircuit
Difference (D)=x’y + xy’
Borrow (B)=x’y

129. Combinational Circuits-Full Subtractor Combinational Circuits-Full Subtractor
CircuitCircuit
Here’s completed full subtractor.

130. Code ConversionCode Conversion
•BCD code to Excess-3 code

131. K-Maps for conversionK-Maps for conversion

132. Circuit for conversionCircuit for conversion

133. Combinational MSI CircuitsCombinational MSI Circuits
•Decoders are another important type of combinational
circuit.
•Among other things, they are useful in selecting a
memory location according a binary value placed on the
address lines of a memory bus.
•Address decoders with n inputs can select any of 2
n

locations.
This is a block
diagram for a
decoder.

134. 3 x 8 Decoder
Truth table of a 3-to-8 line Decoder

135. •This is what a 3-to-8 decoder looks like on the inside.
3 x 8 Decoder

136. •This is what a 2-to-4 decoder looks like on the inside.
2 x 4 Decoder

137. •Implement a full-adder circuit with a decoder and two or Gate.
Example
From the truth table of the full-adder circuit , we obtain the
functions for this circuit in sum of minterms:
Truth Table for Full-Adder
Circuit

138. Circuit Diagram
A full-adder circuit with a decoder and two OR Gate.

139. •This is what a 2-to-4 decoder looks like on the inside.
2-to--4 line decoder with enable gate

140. Example
 Construction of 4 x 16 Decoder using two 3 x 8 Decoder

141. Encoder
An encoder is a digital circuit that performs the inverse operation of a decoder. An
encoder has 2
n
lines and n output lines.
The output lines generate the binary code corresponding to the input value.
Truth table of Octal-to –Binary Encoder

142. Octal-to- Binary Encoder
Output Boolean Function

143. A multiplexer does just the opposite
of a decoder.
It selects a single output from
several inputs.
The particular input chosen for
output is determined by the value of
the multiplexer’s control lines.
To be able to select among n inputs,
log
2
n control lines are needed.
Block Diagram for a
Multiplexer.
Multiplexer

144. •This is what a 4-to-1 multiplexer looks like on the inside.
S
1
S
0
Y
0 0 I
0
0 1 I
1
1 0 I
2
1 1 I
3
4 x 1 Multiplexer

145. BCD Adder

146. Block Diagram of a BCD Adder

148. Combinational CircuitsCombinational Circuits
•This shifter
moves the bits
of a nibble one
position to the
left or right.
 If S = 0, in which direction do the input bits shift?

149. De-multiplexer
A de-multiplexer is a circuit that receives information on a single line and transmit
this information on one of 2
n
possible output lines.
The selection of a specific output line is controlled by the bit values of n selection
lines.
Decoder with an Enable De-multiplexer