CO U RS E : D IGI TAL D E S I G N A N D
CO M P U T E R ORGANIZATION
C O U R S E CODE : BCS302
Module 1: Introduction to Digital Design: Binary Logic,
Basic Theorems And Properties Of Boolean Algebra, Boolean
Functions, Digital Logic Gates, Introduction, The Map
Method, Four-Variable Map, Don’t-Care Conditions, NAN D
and N O R Implementation, Other Hardware Description
Language – Verilog Model of a simple circuit.
Text Book : M. Morris Mano & Michael D. Ciletti, Digital
Design With an Introduction to Verilog Design, 5e, Pearson
Education
Topic No: 1.9, 2.4, 2.5, 2.8, 3.1, 3.2, 3.3, 3.5, 3.6, 3.9
B I NA RY L O G I C A N D GATES
▪ What are Binary variables ?
▪ What are Logical operators ?
▪ Name the Basic logical operators
▪ What are Logic gates?
▪ What is Boolean Algebra?
QUESTIO
N
D raw the Logic diagram and write the TT for all
Basic gates
I N T EG R AT E D C I RC U I T (IC)
▪ An integrated circuit (IC), sometimes called
a chip, microchip or microelectronic circuit,
is a semiconductor wafer on which
thousands or millions of tiny resistors,
capacitors, diodes and transis tors are
fabricated.
B I NA RY L O G I C A N D
GATES
▪ Binary variables take on one of two values.
▪ Logical operators operate on binary values and
binary variables.
▪ Basic logical operators are the logic functions
AND, OR and NOT.
▪ Logic gates implement logic functions.
▪ Boolean Algebra: a useful mathematical system
for specifying and transforming logic functions.
▪ We study Boolean algebra as foundation for
designing and analyzing digital systems!
B I NA RY
VARIABLES
▪ Recall that the two binary values have
different names:
✓ True/False
✓ On/Off
✓ Yes/No
✓ 1/0
▪ We use 1 and 0 to denote the two
values.
▪ Variable identifier examples:
✓ A, B, y, z, or X 1 for now
✓ R E S E T, STA RT _ I T, or ADD1 later
LOGICAL
OPERATIONS
O The three basic logical operations are:
● AND
● OR
● N OT
O A N D is denoted by a dot (·).
O O R is denoted by a plus (+).
O N OT is denoted by an overbar ( ¯ ), a single
quote mark (') after, or (~) before the variable.
8
NOTATION E X A M P L E S
9
O P E R ATO R DEFINITIONS
▪ Operations are defined on the values
“ 0" and "1" for each operator:
TRUTH
TABLES
O Truth table - a tabular listing of the
values of a function for all possible
combinations of values on its arguments
O Write the Truth tables for the basic logic
operations:
TRUTH
TABLES
O Truth table - a tabular listing of the values of a function
for all possible combinations of values on its arguments
O Example: Truth tables for the basic logic operations:
AND OR N OT
X Y Z = X·Y X Y Z = X+Y X Z=
0 0 0 0 0 0 X
0 1 0 0 1 1 0 1
1 0 0 1 0 1 1 0
1 1 1 1 1 1
QUESTIONS
1. What is the difference between binary logic and
binary arithmetic?
2. What is 1+1 in binary logic and binary
arithmetic?
•An arithmetic variable designates a number that may
consist of many digits.
• logic variable is always either 1 or
0.
binary arithmetic: 1 + 1 = 2 (read“one plus one is equal
to 2”), whereas in binary logic, we have 1 + 1 = 1 (read
“one O R one is equal to one”).
LOGIC
GATES
O Logic gates are electronic circuits that operate on one
or more input signals to produce an output signal.
O Electrical signals such as voltages or currents exist
as analog signals having values over a given
continuous range, say, 0 to 3 V
O In a digital system these voltages are interpreted to
be either of two recognizable values, 0 or 1
O The gates are blocks of hardware that produce the
equivalent of logic‐1 or logic‐0 output signals if input
logic requirements are satisfied
LOGIC
GATES
LOGIC
GATES
O The gates are blocks of hardware that produce the
equivalent of logic‐1 or logic‐0 output signals if input
logic requirements are satisfied
BAS I C T H E O R E M S A N D P RO P E RT I E S
OF BOOLEAN ALGEBRA
O This important property of Boolean algebra is called
the duality principle and states that every algebraic
expression deducible from the postulates of Boolean
algebra remains valid if the operators and identity
elements are interchanged.
O If the dual of an algebraic expression is desired, we
simply interchange O R and A N D operators and
replace 1’s by 0’s and 0’s by 1’s
BASIC THEOREMS AND POSTULATES
BASIC THEOREMS AND POSTULATES
O T H E O R E M 1(a): x + x = x.
BOOLEAN FUNCTIONS
O Boolean algebra is an algebra that deals with binary
variables and logic operations.
O A Boolean function described by an algebraic
expression consists of binary variables, the constants 0
and 1, and the logic operation Symbols.
O For a given value of the binary variables, the function
can be equal to either 1 or 0.
B O O L E A N F U N C T I O N S (C ONT ’)
O A Boolean function can be represented in a truth
table. The number of rows in the truth table is 2 n ,
where n is the number of variables in the function
O The truth table for
B O O L E A N F U N C T I O N S (C ONT ’)
O A Boolean function can be transformed from an algebraic
expression into a circuit diagram composed of logic gates
connected in a particular structure.
O The logic‐circuit diagram (also called a schematic) for F1 is
shown in Fig. 2.1
B O O L E A N F U N C T I O N S (C ONT ’)
O There is only one way that a Boolean function can be
represented in a truth table.
O However, when the function is in algebraic form, it can
be expressed in a variety of ways, all of which have
equivalent logic.
O The particular expression used to represent the
function will dictate the interconnection of gates in the
logic‐circuit diagram.
O By manipulating a Boolean expression according to
the rules of Boolean algebra, it is sometimes possible
to obtain a simpler expression for the same function
and thus reduce the number of gates in the circuit and
the number of inputs to the gate.
B O O L E A N F U N C T I O N S (C ONT ’)
O Consider the following Boolean function,
Draw a electronic circuit for F 2
B O O L E A N F U N C T I O N S (C ONT ’)
O Simplify F 2
Draw the Electronic circuit for F 2
B O O L E A N F U N C T I O N S (C ONT ’)
O Compare the circuit diagrams before and after Simplification
O Each circuit implements the same identical function, but
the one with fewer gates and fewer inputs to gates is
preferable because it requires fewer wires and components.
O In general, there are many equivalent representations of a
logic function.
O Finding the most economic representation of the logic is an
important design task.
DIG ITA L L O G I C G AT E S
O Boolean functions are expressed in terms of AND, OR,
and N OT operations, it is easier to implement a
Boolean function with these type of gates.
O the possibility of constructing gates for the other logic
operations is of practical interest.
O Factors to be weighed in considering the construction
of other types of logic gates are:
(1)the feasibility and economy of
producing the gate with physical components
(2) the possibility of extending the gate to more than two inputs
(3)the basic properties of the binary operator, such as commutativity
and associativity
(4)the ability of the gate to implement Boolean functions alone or
in conjunction with other gates .
E X T E N S I O N TO M U LT I P L E
INPUTS
O The gates except for the inverter and buffer—can be
extended to have more than two inputs.
O A gate can be extended to have multiple inputs
if the binary operation it represents is commutative
and associative.
O The A N D and O R operations, defined in
Boolean algebra, possess these two properties.
O The difficulty with the NA N D and N O R operators is
that they are not associative
O To overcome this difficulty, we define the multiple N O R
(or NAND) gate as a complemented O R (or AND) gate
PO S IT IV E A ND N E G AT I V E L O G I C
(CONT’)
O The binary signal at the inputs and outputs of any
gate has one of two values, except during
transition.
O One signal value represents logic 1 and the other
logic 0.
O Since two signal values are assigned to two logic
values, there exist two different assignments of
signal level to logic value, as shown in Fig. 2.9 .
PO S IT IV E A ND N E G AT I V E L O G I C
(CONT’)
O Choosing the high‐level H to represent
logic 1 defines a positive logic system.
O Choosing the low‐level L to represent logic 1 defines
a negative logic system.
PO S IT IV E A ND N E G AT I V E L O G I C
(CONT’)
K-
MAPS
TERMINOLOGY
O Minterm
O Maxterm
QUESTIO
N
Write down theTruth table and identify the Minterms
and Maxterms for the expression:
TERMINOLOGY
O Sum of Product
O Product of sum
O Notational representation of f 1 = Sigma(1,4,7)
2-VA R I A B L E K - MA P S
O A K-map is a diagram made up of squares, with
each square representing one minterm of the
function that is to be minimized.
O There are four minterms for two variables; hence,
the map consists of four squares, one for each
minterm
2-VARIABLE K-MAPS (CONT’)
O If we mark the squares whose minterms belong to a
given function, the two-variable map becomes
another useful way to represent any one of the 16
Boolean functions of two variables.
O Represent the following function on a K-Map
2-VARIABLE K-MAPS
(CONT’)
O A group of two adjacent 1’s can be paired, and the
variable occurring in its complimented and un-
complimented form will be eliminated.
QUESTION
Obtain simplified expressions in each of the K-
map.
3-VA R I A B L E K-M A P S
O There are eight minterms for three binary
variables; therefore, the map consists of eight squares.
O the minterms are arranged, not in a binary
sequence, but in a sequence similar to the Gray code
O The characteristic of this sequence is
that only one bit changes in value from
one adjacent
column to the next
3-VA R I A B L E K-M A P S (CONT’)
3-VA R I A B L E K-M A P S (CONT’)
4-VA R I A B L E K-M A P S
O The map for Boolean functions of four binary
variables (w, x, y, z) is shown in Fig below
4-VA R I A B L E K-M A P S (CONT’)
O In choosing adjacent squares in a map, we must
ensure that
(1) all the minterms of the function
are covered when we combine the squares
(2) the number of terms in the expression is
minimized
(3) There are no redundant terms (i.e.,
minterms already covered by other terms).
O Sometimes there may be two or more
expressions that satisfy the simplification criteria.
4-VA R I A B L E K-M A P S (CONT’)
O A prime implicant is a product term obtained by
combining the maximum possible number of
adjacent squares in the map.
O If a minterm in a square is covered by only one prime
implicant, that prime implicant is said to be essential.
O The prime implicants of a function can be
obtained from the map by combining all possible
maximum numbers of squares
4-VA R I A B L E K-M A P S (CONT’)
O A single 1 on a map represents a prime implicant if it is
not adjacent to any other 1’s.
O Two adjacent 1’s form a prime implicant, provided that
they are not within a group of four adjacent squares.
O Four adjacent 1’s form a prime implicant if they are not
within a group of eight adjacent squares, and so on.
O The essential prime implicants are found by looking at
each square marked with a 1 and checking the number
of prime implicants that cover it.
O The prime implicant is essential if it is the only
prime implicant that covers the minterm
O Octets Quadruples Pairs Single
QUESTION
Find all the prime implicants of
QUESTION
Simplify:
P ROD UC T- OF-S U M S S I M P L IF I C AT I O N
O The 1’s placed in the squares of the map represent the
minterms of the function.
O The minterms not included in the standard sum-of-
products form of a function denote the complement of
the function.
O The complement of a function is represented in the map
by the squares not marked by 1’s.
O If we mark the empty squares by 0’s and combine them
into valid adjacent squares, we obtain a simplified sum-
of-products expression of the complement of the function
(i.e., of F represented as F / ).
O The complement of F / gives us back the function F ‘in
product-of-sums form (a consequence of De-Morgan’s
theorem)
