1

II Semester Course
Digital Logic Design
UNIT – I Number Systems: Binary, octal, decimal, hexadecimal number systems,
conversion of numbers from one radix to another radix, r’s, (r-1)’s complements,
signed binary numbers, addition and subtraction of unsigned and signed
numbers, weighted and unweighted codes.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 2

CONVERTING ONE NUMBER SYSTEM TO ANOTHER 2. Convert a Decimal Number to Binary, Octal, and Hexadecimal using the
example 45 10
1.Converting a Binary Number into Decimal, Octal, and Hexadecimal Using an
Example.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 3

3. Convert an Octal Number to Binary, Decimal, and Hexadecimal using 4. Convert a Hexadecimal Number to Binary, Octal, and Decimal using
the example 57 8 the example 2F 16

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 4

Numeral systems conversion table r’s complement

Decimal Binary Octal Hexadecimal
Base-10 Base-2 Base-8 Base-16 The r’s complement is a mathematical method used in number systems like
decimal and binary to represent negative numbers and perform subtraction
0 0 0 0 by addition. It is widely applied in computer systems for operations in
1 1 1 1 different bases.
2 10 2 2
3 11 3 3 Definition:
4 100 4 4
5 101 5 5 The r’s complement of a number in base r is calculated as:
6 110 6 6
7 111 7 7 r n−N
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
16 10000 20 10
17 10001 21 11
18 10010 22 12
19 10011 23 13
20 10100 24 14
21 10101 25 15
22 10110 26 16
23 10111 27 17
24 11000 30 18
25 11001 31 19
26 11010 32 1A
27 11011 33 1B
28 11100 34 1C
29 11101 35 1D
30 11110 36 1E
31 11111 37 1F
32 100000 40 20

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 5

(r-1)’s complements:

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 6

Signed binary numbers & unsigned binary numbers

Signed and unsigned binary numbers refer to how binary numbers represent
values, specifically whether or not they include the ability to represent
negative values.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 7

Example 1:

Add 1101 (13 in decimal) and 1010 (10 in decimal).

1101
+ 1010
--------------
10111 (23 in decimal)

Example 2 (With Carry):

Add 1011(11 in decimal) and 1111 (15 in decimal).
1011
+ 1111
--------------
11010 (26 in decimal)

Addition and Subtraction of Unsigned Binary Numbers

Unsigned binary arithmetic operates on numbers that represent only non-

negative values. Here's how addition and subtraction work:

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 8

Example 1: Addition and Subtraction of Signed Binary Numbers

Subtract 1010 (10 in decimal) from 1101 (13 in decimal).
1101 Signed binary numbers can represent both positive and negative values, and
- 1010 their arithmetic follows specific rules depending on the representation
-------------- method used. The 2's complement representation is the most common for
0011 (3 in decimal) signed arithmetic.

1. Addition of Signed Binary Numbers

Example 2 (With Borrow):

Subtract 1011 (5 in decimal) from 1000 (8 in decimal).

Rules for Signed Addition:
1000
1. Perform binary addition as you would with unsigned numbers.
- 0101
2. If the result exceeds the range of the signed number, overflow
-------------
occurs. Overflow is detected when:
0011 (3 in decimal) o Two positive numbers produce a negative result, or
o Two negative numbers produce a positive result.

Overflow in Unsigned Arithmetic Example 1: Positive + Positive

• Addition: Overflow occurs if the result exceeds the maximum value Add +5 (0101) and +3 (0011) in a 4-bit system:
represent able by the given number of bits.
o Example: Adding 1111 (15 in decimal) and 0001 (1 in 0101 (+5)
decimal) in a 4-bit system results in 100001000010000, + 0011 (+3)
which exceeds the 4-bit range (0–15).
• Subtraction: Underflow occurs if you attempt to subtract a larger -----------------------------
number from a smaller number, which isn't valid in unsigned 1000 (+8, no overflow)
arithmetic.
Example 2: Negative + Negative
Example of Overflow: Add −5 (101110111011) and −3 (1101) in a 4-bit system:
For a 4-bit system: 1011 (-5)
1111 (15)
+ 0001 (1) + 1101 (-3)
---------------------------------- --------------------------
10000 (Overflow: result exceeds 4 bits)
11000 (Ignore the carry, result is 1000 = -8)

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 9

Example 3: Mixed Signs 0011→1101

Add +5 (0101) and −3 (1101) in a 4-bit system: Add it to −5:
0101 (+5) 1011 (-5)
+ 1101 (-3)
+ 1101 (-3)
-----------------------
---------------------- 10000 (Ignore the carry, result is 1000 = -8)
0010 (+2, no overflow) Example 3: Positive - Negative

Subtract −3 (1101) from +5 (0101):

2. Subtraction of Signed Binary Numbers
• Take the 2's complement of -3:
Subtraction can be performed using the 2's complement method:
1101→0011
1. Take the 2's complement of the number to be subtracted (negate it).
2. Add it to the first number. • Add it to +5:
3. If there's a carry out, ignore it.
0101 (+5)
Example 1: Positive - Positive + 0011 (+3)

Subtract +3(0011) from +5(0101in a 4-bit system: -----------------------

• Take the 2's complement of +3 1000 (+8)
0011→1101
Weighted and Unweighted Codes
• Add it to +5
In digital systems, codes are used to represent information in binary form.
0101 (+5) These codes are categorized as weighted or unweighted, depending on
+ 1101 (-3) whether the individual digits in the code carry a positional weight.
----------------------
0010 (+2) 1. Weighted Codes

Example 2: Negative - Positive • Definition: Each position in the binary representation has a fixed
weight assigned to it.
Subtract +3 (0011) from −5 (1011): • The value of the code is determined by summing the products of the
digit values and their respective weights.
• Take the 2's complement of +3:

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 10

Characteristics: 3. Includes codes like Gray Code, Excess-3 Code (can also be
weighted), and ASCII.
1. Fixed positional weights are assigned (e.g., 1, 2, 4, 8 in binary).
2. Useful for arithmetic operations like addition and subtraction. Examples of Unweighted Codes:
3. Includes well-known codes like Binary, Decimal, and BCD (Binary-
Coded Decimal). 1. Gray Code:
o Adjacent numbers differ by only one bit.
o Example: Decimal 0 to 7 in Gray Code:

0 → 000
1 → 001
2 → 011
3 → 010
4 → 110
5 → 111
6 → 101
7→ 100
2. ASCII (American Standard Code for Information Interchange):
o Represents characters as binary codes.
o Example: Letter 'A' = 100000110000011000001 in ASCII.

3. Hamming Code:
o Used for error detection and correction.
o Does not assign weights but introduces parity bits to ensure
data integrity.

2. Unweighted Codes Applications:

• Definition: No fixed weights are assigned to the digits in the code. 1. Weighted Codes:
• The code does not depend on positional weights but follows specific o Arithmetic calculations in computers.
rules or patterns. o Representing numerical data (e.g., BCD in digital clocks and
calculators).
Characteristics: 2. Unweighted Codes:
o Gray Code: Encoder and sensor data to avoid errors during
1. Do not have positional weight for digits. transitions.
2. Often used for error detection, error correction, or specific o ASCII: Character representation in text processing.
applications. o Hamming Code: Error correction in communication systems.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 11

UNIT – II
Logic Gates and Boolean Algebra: NOT, AND, OR, universal gates,
X-OR and X-NOR gates, Boolean laws and theorems, complement AND Gate
and dual of a logic function, canonical and standard forms, two In the AND gate, the output of an AND gate attains state 1 if and only if all
level realization of logic functions using universal gates, the inputs are in state 1.
minimizations of logic functions (POS and SOP) using Boolean
theorems, K-map (up to four variables), don’t care conditions. Basic The Boolean expression of AND
Logic Gates gate is Y = A.B
****************************************************************** The truth table of a two-input AND
Logic gates: Logic gates are used to carry out logical operations on basic gate is given as
single or multiple binary inputs and give one binary output. In simple
terms, logic gates are the electronic circuits in a digital system
Types of Basic Logic Gates A B Y
There are several basic logic gates used in performing operations in digital
systems. The common ones are
0 0 0
• OR Gate
• AND Gate
• NOT Gate
0 1 0
OR Gate
In an OR gate, the output of an OR gate attains state 1 if one or more 1 0 0
inputs attain state 1.
1 1 1
The Boolean expression of the
OR gate is Y = A + B, read as Y
equals A ‘OR’ B.
NOT Gate
The truth table of a two-input In a NOT gate, the output of a NOT gate attains state 1 if and only if the
OR basic gate is given as input does not attain state 1.

The Boolean expression is

A B Y
Y=A¯
0 0 0 It is read as Y equals NOT A.

The truth table of NOT gate is as follows

0 1 1 A Y

1 0 1 0 1

1 1 1
1 0

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 12

When connected in various combinations, the three gates (OR, AND and A B Y
NOT) give us basic logic gates, such as NAND and NOR gates, which are
the universal building blocks of digital circuits.
0 0 1
NAND Gate
0 1 0
This basic logic gate is the combination of AND and NOT gates.

The Boolean expression of the 1 0 0

NAND gate is
1 1 0
---
Y=A.B
Exclusive-OR gate (XOR Gate)
The truth table of a NAND gate
is given as In an XOR gate, the output of a two-input XOR gate attains state 1 if one
adds only input and attains state
A B Y 1.

The Boolean expression of the

0 0 1 XOR gate is
A.B¯+A¯.B
0 1 1 or
Y=A⨁B
1 0 1 The truth table of an XOR gate is

1 1 0

A B Y
NOR Gate
0 0 0
This gate is the combination of OR and NOT gates.

0 1 1

The Boolean expression of the 1 0 1

NOR gate is

Y=A+B― 1 1 0
The truth table of a NOR gate is
as follows

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 13

Commutative P+Q=Q+P P.Q = Q.P

Law
Exclusive-NOR Gate (XNOR Gate) Associative Law P + (Q + R) = (P + Q) P.(Q.R) = (P.Q).R
In the XNOR gate, the output is in state 1 when both inputs are the same, +R
that is, both 0 or both 1. Distributive Law P + QR = (P + Q).(P + P.(Q + R) = P.Q +
R) P.R
The Boolean expression of the
XNOR Inversion Law (A’)’ = A (A’)’ = A
gate De Morgan’s Law (P + Q)’ = (P)’.(Q)’ (P.Q)’ = (P)’ + (Q)’

Identity Law
The truth table of an XNOR gate In the Boolean Algebra, we have identity elements for both
is given below AND(.) and OR(+) operations. The identity law state that in
boolean algebra we have such variables that on operating
A B Y with AND and OR operation we get the same result, i.e.
• A + 0 = A
0 0 1 • A.1 = A
Commutative Law
0 1 0 Binary variables in Boolean Algebra follow the commutative
law. This law states that operating boolean variables A and B
1 0 0 is similar to operating boolean variables B and A. That is,
• A. B = B. A
1 1 1 • A + B = B+ A
Associative Law
Associative law state that the order of performing Boolean
Boolean laws and theorems operator is illogical as their result is always the same. This
can be understood as,
Boolean laws and theorems that play a crucial role in digital • ( A . B ) . C = A . ( B . C )
logic and circuit design: • ( A + B ) + C = A + ( B + C)
Laws for Boolean Algebra Distributive Law
The basic laws of the Boolean Algebra are added in the table Boolean Variables also follow the distributive law and the
added below, expression for Distributive law is given as:
Law OR form AND form A . ( B + C) = (A . B) + (A . C)
Identity Law P+0=P P.1 = P Inversion Law
Idempotent Law P+P=P P.P = P

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 14

Inversion law is the unique law of Boolean algebra this law The first law states that the complement of the product of the
states that, the complement of the complement of any
variables is equal to the sum of their individual complements
number is the number itself.
(A’)’ = A of a variable.
Apart from these other laws are mentioned below:
AND Law The truth table that shows the verification of De Morgan’s
AND law of the Boolean algebra uses AND operator and the First law is given as follows:
AND law is,
• A . 0 = 0
• A . 1 = A A B A’ B’ (A.B)’ A’+B’
• A . A = A
0 0 1 1 1 1
OR Law
OR law of the Boolean algebra uses OR operator and the OR 0 1 1 0 1 1
law is,
• A + 0 = A 1 0 0 1 1 1
• A + 1 = 1
• A + A = A 1 1 0 0 0 0
The last two columns show that (A.B)’ = A’+B’.
Boolean algebra Theorems
Hence, De Morgan’s First Law is proved.
The two important theorems which are extremely used in
Boolean algebra are De Morgan’s First law and De Morgan’s De Morgan’s Second Law:
second law. These two theorems are used to change the
De Morgan’s Second law states that (A+B)’ = A’. B’.
Boolean expression. This theorem basically helps to reduce
the given Boolean expression in the simplified form. These two The second law states that the complement of the sum of
De Morgan’s laws are used to change the expression from one variables is equal to the product of their individual
form to another form. Now, let us discuss these two theorems complements of a variable.
in detail.
The following truth table shows the proof for De Morgan’s
De Morgan’s First Law: second law.

De Morgan’s First Law states that (A.B)’ = A’+B’.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 15

the same input combination, and vice versa. Think of it as

flipping the output values of the function's truth table.
A B A’ B’ (A+B)’ A’. B’ • Truth Table Perspective: Imagine a truth table for
your function F. To create the truth table for F', simply
invert every output value in the F column. All 0s
0 0 1 1 1 1 become 1s, and all 1s become 0s.
• Algebraic Manipulation (De Morgan's Laws): De
Morgan's laws provide the key to finding the
0 1 1 0 0 0 complement of a Boolean expression algebraically. They
are:
o (A + B)' = A'B': The complement of a sum is equal
1 0 0 1 0 0 to the product of the complements.
o (AB)' = A' + B': The complement of a product is
equal to the sum of the complements.
1 1 0 0 0 0
These laws are crucial for simplifying complex Boolean
expressions and finding their complements. You apply
The last two columns show that (A+B)’ = A’. B’. them recursively until you've negated all individual
variables.
Hence, De Morgan’s second law is proved.
• Example:
The other theorems in Boolean algebra are complementary
theorem, duality theorem, transposition theorem, redundancy Let's say F(A, B) = AB + A'B. Let's find F':
theorem and so on. All these theorems are used to simplify
1. Apply De Morgan's to the main OR: F' = (AB + A'B)' =
the given Boolean expression. The reduced Boolean (AB)'(A'B)'
expression should be equivalent to the given Boolean 2. Apply De Morgan's to each term: F' = (A' + B')(A + B')
expression. 3. Expand (if needed): F' = A'A + A'B' + BA + BB' = 0 +
A'B' + AB + 0 = AB + A'B' (Notice this is the same as the
1. Complement (Negation) original function in this specific example. This demonstrates a
concept called involution: (F')' = F. The complement of the
The complement of a Boolean function, denoted as F' (or complement is the original function.)
sometimes ¬F or overline F), represents the opposite of the Circuit Perspective: If you have a logic circuit that
original function. If the original function F outputs 1 for a implements F, you can create a circuit for F' by simply adding
given input combination, its complement F' will output 0 for an inverter (NOT gate) at the output of the F circuit.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 16

2. Dual sum (POS).

The dual of a Boolean function, denoted as F^D Boolean functions expressed as a sum of minterms or
(or sometimes F*), is obtained by interchanging the roles of product of maxterms are said to be in canonical form.
AND and OR operators, as well as the constants 0 and 1. It's
a structural transformation of the Boolean expression. Standard Form – A Boolean variable can be expressed in
either true or complementary forms. In standard form
• Rules for Finding the Dual: Boolean function will contain all the variables in either true
1. Replace each AND operator (.) with an OR form or complemented form while in canonical number of
operator (+). variables depends on the output of SOP or POS.
2. Replace each OR operator (+) with an AND A Boolean function can be expressed algebraically from a
operator (.). given truth table by forming a :
3. Replace each 0 with a 1. • minterm for each combination of the variables that
4. Replace each 1 with a 0. produces a 1 in the function and then takes the OR of all
• Example: those terms.
• maxterm for each combination of the variables that
Let's take the same function F(A, B) = AB + A'B and find produces a 0 in the function and then takes the AND of
its dual, F^D: all those terms.

1. Original: F = AB + A'B Truth table representing minterm and maxterm –

2. Apply the dual rules: F^D = (A +
B)(A' + B)
• Important Note: The dual of a function is not the same
as its complement. They are distinct concepts.

Canonical and Standard Form

Canonical Form – In Boolean algebra, the Boolean function
can be expressed as Canonical Disjunctive Normal Form
known as minterm and some are expressed as Canonical
Conjunctive Normal Form known as maxterm.
In Minterm, we look for the functions where the output
results in “1” while in Maxterm we look for functions where
the output results in “0”.
We perform the Sum of minterm also known as the Sum of
products (SOP). From the above table it is clear that minterm is expressed in
We perform Product of Maxterm also known as Product of product format and maxterm is expressed in sum format.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 17

Sum of minterms – Two Level Implementation of Logic Gates

The minterms whose sum defines the Boolean function are
those which give the 1’s of the function in a truth table. The term “two-level logic” refers to a logic design that uses no
Since the function can be either 1 or 0 for each minterm, and more than two logic gates between input and output. This
since there are 2^n minterms, one can calculate all the does not mean that the entire design will only have two logic
functions that can be formed with n variables to be (2^(2^n)). gates, but it does mean that the single path from input to
It is sometimes convenient to express a Boolean function in output will only have two logic gates.
its sum of minterm form. In two-level logic, irrespective of the total number of logic
gates, the maximum number of logic gates that can be
Product of maxterms – cascaded between any input and output is two. The outputs
When dealing with Boolean algebra, the product of maxterms of first-level logic gates are connected to the inputs of second-
is a handy way to express how combinations of inputs lead level logic gates in this configuration.
to a result of 0. Maxterms basically tell us which
combinations of inputs won’t give us a 1 as an output. They The primary logic gates used in two-level logic design:
are the opposite of minterms, which tell us when we get a 1. • AND Gate: Outputs true (1) only if all inputs are true.
• Example – Express the Boolean function F = A + B’C as • OR Gate: Outputs true (1) if at least one input is true.
standard sum of minterms. • NAND Gate: Outputs true (1) unless all inputs are true.
o Solution – • NOR Gate: Outputs true (1) only if all inputs are false.
A = A(B + B’) = AB + AB’
This function is still missing one variable, so Example of two-level logic implementation
A = AB(C + C’) + AB'(C + C’)
= ABC + ABC’+ AB’C + AB’C’
The second term B’C is missing one variable;
hence,
B’C = B’C(A + A’)
= AB’C + A’B’C
Combining all terms, we have
F = A + B’C
= ABC + ABC’ + AB’C + AB’C’ + AB’C + A’B’C
But AB’C appears twice, and
according to theorem 1 (x + x = x), it is possible
to remove one of those occurrences. Rearranging An Example of Two-level implementation
the minters in ascending order, we finally obtain
F = A’B’C + AB’C’ + AB’C + ABC’ + ABC
= m1 + m4 + m5 + m6 + m7 We explore four logic gates in two-level logic implementation:
SOP is represented as Sigma(1, 4, 5, 6, 7) AND Gate, OR Gate, NAND Gate, and NOR Gate. There are a
total of 16 two-level logic combinations if we choose one of

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 18

these four gates at the first level and one at the second level. OR-OR Implementation
These are The output of an OR-OR
AND-AND, AND-OR, AND-NAND, AND-NOR, gate combination is the Logic
OR-AND, OR-OR, OR-NAND, OR-NOR, Function OR. With this combination,
NAND-AND, NAND-OR, NAND-NAND, NAND-NOR, the OR function can be implemented
NOR-AND, NOR-OR, NOR-NAND, NOR-NOR. with several inputs.
OR-OR implementation
Each two-level combination implements a separate logic
function. These 16 combinations are divided into two The outputs of first-level logic gates: F1=A+B and F2=C+D.
categories. These outputs are applied as inputs of the second level, so the
1. Degenerative form of logic gate Combination output of the second level is F=F1+F2 which means
2. Non-Degenerative form of logic gate Combination F=A+B+C+D.
AND-NAND Implementation
Degenerative form AND gate are present in the
Degenerative form occurs when the output of a two-level logic first level of this logic
realization can be achieved with only one logic gate. The implementation, while NAND
advantage of degenerative form is that the number of inputs gates are present in the
of single Logic gate increases which results in the increment second level. An example of
of fan-in of logic gates. AND-NAND logic realization
In those 16 combinations, there are 8 degenerate forms. is shown in the diagram
Below are instances of each of these degenerate types. below.

AND-AND Implementation
Because the entire function AND-NAND Implementation
results in an AND function of all
the inputs, this AND-AND gate
The outputs of first-level logic gates: F1=AB and F2=CD.
combination is a degenerate
These outputs are applied as inputs of the second level, so the
form.
output of the second level is F= (F1F2)’ which means
F=(ABCD)’.
AND-AND Implementation OR-NOR Implementation
OR-NOR combination of gates results in NOR logic function.
And this degenerate form can be used for the NOR function
The outputs of first-level logic gates: F1=AB and F2=CD. with multiple inputs.
These outputs are applied as inputs of the second level, so the
output of the second level is F=F1F2, which means F=ABCD.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 19

NOR-NAND Implementation
Because the NOR-NAND combination also produces an OR
function, it is likewise a degenerate form. The following is an
example of it with a diagram;

OR-NOR Implementation

The outputs of first-level logic gates: F1=A+B and F2=C+D.

These outputs are applied as inputs of the second level, so the NOR-NAND Implementation
output of the second level is F=(F1+F2)’ which means
F=(A+B+C+D)’.
NAND-NOR Implementation The outputs of first level logic gates: F1=(A+B) ‘ and
The outcome function of NAND-NOR in two-level logic is AND F2=(C+D)’. These outputs are applied as inputs of the second
logic. The following is its expression and schematic: level, so the output of the second level is F=(F1.F2)’ which
means F=((A+B)'(C+D)’)’.
NAND-OR Implementation
This combination, like the AND-NAND combination, produces
a NAND logic function.

NAND-NOR Implementation

The outputs of first level logic gates: F1=(AB) ‘ and F2=(CD)’.

These outputs are applied as inputs of the second level, so the NAND-OR Implementation
output of the second level is F=(F1+F2)’ which means
F=((AB)’+(CD)’)’.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 20

The outputs of first level logic gates: F1=(AB) ‘ and F2=(CD)’.

These outputs are applied as inputs of the second level, so the
output of the second level is F=(F1+F2) which means
F=((AB)’+(CD)’)=(ABCD)’.
NOR-AND Implementation
This combination is identical to the OR-NOR combination
since this combination similarly results in a NOR function.

AND-OR Implementation

The outputs of first-level logic gates: F1=AB and F2=CD.

These outputs are applied as inputs of the second level, so the
output of the second level is F=(F1+F2) which means
F=(AB+CD).
NAND-NAND Implementation
NOR-AND Implementation NAND is a universal gate, and its NAND-NAND combination,
like the AND-OR combination, is used to produce the Sum of
Product form.
The outputs of first level logic gates: F1=(A+B) ‘ and
F2=(C+D)’. These outputs are applied as inputs of the second
level, so the output of the second level is F=(F1.F2) which
means F=((A+B)'(C+D)’)=(A+B+C+D)’.
Non-Degenerative form
A non-degenerative form occurs when the output of a two-
level logic realization cannot be achieved using a single logic
gate. Non-degenerate forms are two-level logic combinations
that implement the Sum of Product form or the Product of
Sum form.
In those 16 combinations, there are 8 non-degenerate forms. NAND-NAND Implementation
Below are instances of each of these non-degenerate types.
AND-OR implementation
The outputs of first-level logic gates: F1=(AB)’ and F2=(CD)’.
The first level gate in a While-OR combination is an AND gate,
These outputs are applied as inputs of the second level, so the
and the second level gate is an OR gate. As shown in the
output of the second level is F=(F1.F2)’ which means
diagram below, this combination implements the Sum of
F=(AB)+(CD).
Product (SOP) form.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 21

OR-AND Implementation The outputs of first-level logic gates: F1=(A+B)’ and F2=(C+D)’.
The first level gate in an OR-AND combination is an OR gate, These outputs are applied as inputs of the second level, so the
and the second level gate is an AND gate. The Product of Sum output of the second level is F=(F1+F2)’ which means
form is implemented with an OR-AND combination. F=((A+B)’+(C+D)’)’=(A+B)(C+D).
AND-NOR Implementation
The AND-NOR combination is used to implement the AND-
OR-INVERT compound logic (AOI).

OR-AND Implementation

AND-NOR Implementation
The outputs of first-level logic gates: F1=(A+B) and F2=(C+D).
These outputs are applied as inputs of the second level, so the
output of the second level is F=(F1.F2) which means The outputs of first-level logic gates: F1=(AB) and F2=(CD).
F=(A+B)(C+D). These outputs are applied as inputs of the second level, so the
NOR-NOR Implementation output of the second level is F=(F1+F2)’ which means
NOR is also a universal gate and its NOR-NOR combination F=(AB+CD)’.
can be used to implement the Product of Sum form. NAND-AND Implementation
The AND-OR-INVERT (AOI) form can also be implemented
using NAND-AND.

NOR-NOR Implementation

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 22

NAND-AND Implementation

The outputs of first-level logic gates: F1=(AB)’ and F2=(CD)’.

These outputs are applied as inputs of the second level, so the
output of the second level is F=(F1F2) which means
F=(AB)'(CD)’=(AB+CD)’.
OR-NAND Implementation
The OR-NAND form is used to implement the OR-AND-
INVERT compound logic (OAI).

NOR-OR Implementation

The outputs of first-level logic gates: F1=(A+B)’ and F2=(C+D)’.

These outputs are applied as inputs of the second level, so the
output of the second level is F=(F1+F2), which means
F=(A+B)’+(C+D)’=[(A+B)(C+D)]’.

Minimization of Boolean Functions

OR-NAND Implementation As discussed in the “Representation of Boolean
Functions” every Boolean function can be expressed as a sum
The outputs of first-level logic gates: F1=(A+B) and F2=(C+D). of minterms or a product of maxterms. Since the number of
These outputs are applied as inputs of the second level, so the literals in such an expression is usually high, and the
output of the second level is F=(F1F2)’ which means complexity of the digital logic gates that implement a Boolean
F=[(A+B)(C+D)]’. function is directly related to the complexity of the algebraic
NOR-OR Implementation expression from which the function is implemented, it is
The NOR-OR combination, like the OR-NAND combination, is preferable to have the most simplified form of the algebraic
used to build OR-AND-INVERT compound logic (OAI). expression. The process of simplifying the algebraic
expression of a Boolean function is called minimization.
Minimization is important since it reduces the cost and
complexity of the associated circuit.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 23

The circuits associated with above expressions is –

It is clear from the above image that the minimized version of

the expression takes a less number of logic gates and also
reduces the complexity of the circuit substantially.
Minimization is hence important to find the most economic Minimization using K-Map –
The Algebraic manipulation method is tedious and
equivalent representation of a boolean function.
cumbersome. The K-Map method is faster and can be used
Minimization can be done using Algebraic Manipulation or K-
to solve boolean functions of upto 5 variables.
Map method
Example 2 – Consider the same expression from example-1
Minimization using Algebraic Manipulation –
This method is the simplest of all methods used for and minimize it using K-Map.
minimization. It is suitable for medium sized expressions
• Solution – The following is a 4 variable K-Map of the
involving 4 or 5 variables. Algebraic manipulation is a
given expression.
manual method, hence it is prone to human error.
Common

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 24

o The SOP minimal expression is: (f = BC’ + BD’ +

A’C’D + AB’CD)

Let's delve deeper into the concepts of the complement and

dual of a logic function.

Don’t Care Conditions:

• A “Don’t Care” condition represents an invalid input

combination.
• It can be denoted by a cross (X) or minus (-) in the K-
Map.
• Don’t Care conditions allow us to:
o Replace empty cells with valid groupings.
o Form larger groups than without considering
Don’t Care cells.
o Simplify the expression further.

Example:

Let’s consider an example using a 2-variable K-Map:

Given function: (f = m(1, 5, 6, 11, 12, 13, 14) + d(4))

1. Create the K-Map:

o Fill in the cells based on the given minterms and
Don’t Care condition.
o Group adjacent 1s.
2. Write the simplified expression:

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 25

UNIT – III Disadvantages of Combinational Circuits

Combinational Logic Circuits – 1: Design of half adder, full • Limited Functionality: Is not able to perform operations
adder, half subtractor, fullsubtractor, ripple adders and that need historical information or sequence details.
subtractors. • Complexity with Increased Inputs: It becomes difficult
to design combinational circuits when there are many
*********************************************************************
inputs.
What is Combinational Circuit? Points to Remember on Combinational Logic Circuit:
1. Output depends upon the combination of inputs.
A combinational circuit is a kind of digital electronic circuit
2. Output is a pure function of present inputs only i.e.,
of which outputs depend on the present inputs and have no
Previous State inputs won’t have any effect on the output.
connections to the past inputs. These circuits do such tasks
Also, It doesn’t use memory.
as additions, subtractions and logically AND, OR
3. Inputs are called Excitation from circuits and outputs are
and NOR circuits. The key characteristics of combinational
called Responses of combinational logic circuits.
circuits include:
Classification of Combinational Logic Circuits:
• No Memory Elements: The output is dependent solely on
1. Arithmetic:
the current policy inputs.
• Adders
• Immediate Response: Good input differs from its output
• Subtractors
and bad input differs from its output.
• Multipliers
• Examples: The most commonly encountered examples
• Comparators
are adders, multiplexers and encoders.
2. Data Handling:
• Multiplexers
• DeMultiplexers
• Encoders and Decoders
3. Code Converters:
• BCD to Excess-3 code and vice versa
• BCD to Gray code and vice versa
• Seven Segment
Advantages of Combinational Circuits Design of Half Adders and Full Adders:
• A combinational logic circuit that performs the addition of
• Simplicity: It is easier to design and implement more so
because it lacks memory elements mainly. two single bits is called Half Adder.
• A combinational logic circuit that performs the addition of
• Speed: Operational at a faster rate as the output
automatically adjusts with the changes in inputs. three single bits is called Full Adder.
• Resource Efficiency: Generally it needs far fewer
components as compared to its equivalent sequential
circuits.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 26

1. Half Adder: Truth Table of Half Adder:

• It is a arithmetic combinational logic circuit designed to

perform addition of two single bits.
• It contain two inputs and produces two outputs.
• Inputs are called Augend and Added bits and Outputs are
called Sum and Carry.

Next Step is to draw the Logic Diagram. To draw Logic

Diagram, We need Boolean Expression, which can be
Let us observe the addition of single bits,
obtained using K-map (karnaugh map). Since there are two
0+0=0
output variables ‘S’ and ‘C’, we need to define K-map for each
0+1=1 output variable.
K-map for output variable Sum ‘S’:
1+0=1
1+1=10
Since 1+1=10, the result must be two bit output. So, Above
can be rewritten as,
0+0=00
0+1=01
1+0=01
K-map is of Sum of products form. The equation obtained
1+1=10
is
The result of 1+1 is 10, where ‘1’ is carry-output (Cout) and ‘0’ S = AB' + A'B
is Sum-output (Normal Output).
which can be logically written as,
S = A xor B

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 27

K-map for output variable Carry ‘C’: 4. Useful for Basic Operations: Suitable for single-bit
binary addition.

Disadvantages:

1. No Carry Input Handling: Cannot process a carry from

a previous stage, limiting its use in multi-bit addition.
2. Limited Functionality: Restricted to adding only two
The equation obtained from K-map is, bits.
3. Not Suitable for Multi-bit Addition: Requires
C = AB additional circuits to perform complex additions.
Using the Boolean Expression, we can draw logic diagram as 4. Less Practical for Large Operations: Full adders are
follows.. preferred for multi-bit calculations.

2. Full Adder:

• To overcome the above limitation faced with Half adders,

Full Adders are implemented.
• It is a arithmetic combinational logic circuit that performs
addition of three single bits.
• It contains three inputs (A, B, Cin) and produces two
outputs (Sum and Cout).
• Where, Cin -> Carry In and Cout -> Carry Out

Limitations: Adding of Carry is not possible in Half adder.

Advantages:

1. Simple Design: Uses only two logic gates (XOR and

AND), making it easy to implement.
2. Fast Computation: Minimal gate delay due to its
simple structure.
3. Low Power Consumption: Requires fewer components,
reducing power usage.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 28

Truth table of Full Adder: K-map Simplification for output variable ‘Cout‘

The equation obtained is,

Cout = BCin + AB + ACin

Logic Diagram of Full Adder:

K-map Simplification for output variable Sum ‘S’ :

The equation obtained is,

S = A'B'Cin + AB'Cin' + ABC + A'BCin'
The equation can be simplified as,
S = B'(A'Cin+ACin') + B(AC + A'Cin')
S = B'(A xor Cin) + B (A xor Cin)'
S = A xor B xor Cin

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 29

Advantages: Truth Table of Half Subtractor:

1. Handles Carry Input: Supports carry from the previous

stage, enabling multi-bit addition.
2. Scalable for Large Operations: Multiple full adders can
be cascaded for n-bit addition.
3. Accurate Addition: Ensures correct sum and carry
outputs.
4. Essential for Digital Arithmetic: Used in
microprocessors, ALUs, and other computational
circuits.

Disadvantages:

1. More Complex than Half Adder: Requires three logic

gates (XOR, AND, OR), increasing circuit complexity. K-map Simplification for output variable ‘D’:
2. Propagation Delay: When cascaded in a ripple carry
adder, carry propagation slows down computation.
3. Higher Power Consumption: More gates lead to
increased power usage.
4. Not Optimal for High-Speed Addition: Advanced
adders like Carry Look-Ahead Adders are preferred for
faster processing.

3. Half Subtractor:

The equation obtained is,

• It is a combinational logic circuit designed to perform the D = A'B + AB'

subtraction of two single bits. which can be logically written as,
• It contains two inputs (A and B) and produces two
outputs (Difference and Borrow-output). D = A xor B

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 30

K-map Simplification for output variable ‘Bout‘ : Advantages:

1. Simple Design: Uses only two gates (XOR and AND

with NOT).
2. Fast Computation: Minimal delay due to fewer gates.
3. Low Power Consumption: Requires fewer components.
4. Useful for Single-bit Subtraction: Works well for
simple operations.

Disadvantages:

1. No Borrow Input Handling: Cannot process borrow

The equation obtained from above K-map is, from a previous stage.
2. Limited Functionality: Only subtracts two bits
Bout = A'B
without borrow.
Logic Diagram of Half Subtractor:
3. Not Suitable for Multi-bit Subtraction: Requires
additional circuits for larger numbers.
4. Less Practical for Complex Operations: Full
subtractors are preferred.

4. Full Subtractor:

• It is a Combinational logic circuit designed to perform

subtraction of three single bits.
• It contains three inputs(A, B, Bin) and produces two
outputs (D, Bout).
• Where, A and B are called Minuend and Subtrahend bits.
• And, Bin -> Borrow-In and Bout -> Borrow-Out

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 31

Truth Table of Full Subtractor: K-map Simplification for output variable ‘Bout‘ :

The equation obtained is,

Bout = BBin + A'B + A'Bin
Logic Diagram of Full Subtractor:

K-map Simplification for output variable ‘D’ :

The equation obtained from above K-map is,

D = A'B'Bin + AB'Bin' + ABBin + A'BBin'
which can be simplified as,
D = B'(A'Bin + ABin') + B(ABin + A'Bin')
D = B'(A xor Bin) + B(A xor Bin)'
D = A xor B xor Bin

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)

 32

Applications:
1. For performing arithmetic calculations in electronic
calculators and other digital devices.
2. In Timers and Program Counters.
3. Useful in Digital Signal Processing.

Advantages:

1. Handles Borrow Input: Supports borrow from the

previous stage.
2. Scalable for Multi-bit Subtraction: Can be cascaded
for larger operations.
3. Accurate Subtraction: Provides correct difference and
borrow.
4. Essential in Digital Circuits: Used in ALUs and
microprocessors.

Disadvantages:

1. More Complex than Half Subtractor: Requires three

logic gates.
2. Propagation Delay: Slower when cascaded for multi-bit
operations.
3. Higher Power Consumption: Uses more gates,
increasing power usage.
4. Not Optimal for High-Speed Subtraction: Advanced
subtractor designs are preferred.

GANGI REDDY KRISHNAM M.SC (COMPUTER SCIENCE),(Ph.D)