DIGITAL SYSTEMS AND COMPUTER ORGANIZATION
Text Book:
Stephen Brown and Zvonko Vranesic, Fundamentals of Digital
Logic with Verilog Design (3e), Tata McGraw Hill 2014
Logic Gates
• Digital circuits are hardware components that manipulate binary
information.
• The circuits are implemented using transistors and interconnections in
complex semiconductor devices called integrated circuits.
• Each basic circuit is referred to as a logic gate
Truth Tables
x x’
0 1
1 0
• AND gate gives high output if and only if all of its inputs
are high
• OR gate output is LOW if and only if all of its inputs are
LOW.
A B Q A B Q
0 0 1 0 0 1
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 1 1 0
NAND NOR
• NAND gate gives LOW output if and only if all of its
inputs are HIGH
• OR gate output is HIGH if and only if all of its inputs are
LOW.
Exclusive OR (XOR)
XOR gate output is HIGH if it has odd number of HIGH inputs.
The complement operation can be applied to a single variable
or to more complex operations.
For example, if
f (x1, x2) = x1 + x2
then the complement of f is
f’(x1, x2) = (x1 + x2)’
Precedence of Operations
• In the absence of parantheses, operation in a logic expression must be
performed in the order: NOT, AND and OR.
• Given f=a.b+a’.b’
first, a’ and b’ are calculated, then ab and a’b’ and finally ab+a’b’
Minterms
For a function of n variables, a product term in which each
of the n variables appears once, either in uncomplemented
or complemented form is called a minterm.
For a given row of the truth table, the minterm is formed by
including xi if xi = 1 and by including xi’ if xi = 0.
Maxterms
• A sum term that contains all the variables in
complemented or uncomplemented from is called a
maxterm.
Sum-of-Products and Product-of-Sums Forms
If a function f is specified in the form of a truth table, then
an expression that realizes f can be obtained by considering
either the rows in the table for which f = 1, or by
considering the rows for which f = 0.
Sum-of-Products Form
Any function f can be represented by a sum of minterms that
correspond to the rows in the truth table for which f = 1.
Example:
f
A logic expression consisting of product (AND) terms
that are summed (ORed) is said to be in the sum-of
products (SOP) form. If each product term is a minterm,
then the expression is called a canonical sum-of-
products for the function f
The cost of a logic circuit is the total number of
gates plus the total number of inputs to all gates in
the circuit.
The cost of the previous network is 13, because
there are five gates and eight inputs to the gates.
The previous function f can also be specified as
f (x1, x2, x3) =σ (m1,m4,m5,m6)
or even more simply as
f (x1, x2, x3) =σ m(1, 4, 5, 6)
Product of Sums
Example:
An alternative way of specifying our sample function is
or more simply
• A logic expression consisting of sum (OR) terms
that are the factors of a logical product (AND) is
said to be of the product-of-sums (POS) form.
• If each sum term is a maxterm, then the expression
is called a canonical product-of-sums for the given
function.
