Unit-1 Introduction to Digital

Electronics

-Mrs. Radhika V. Kulkarni

Assistant Professor, Dept. of Information Technology,
Pune Institute of Computer Technology, Pune.

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
 DISCLAIMER
This presentation is created as a reference material for
the students of SE-IT, PICT (AY 2022-23 Sem-1).
It is restricted only for the internal use and any circulation
is strictly prohibited.

RVK-LDCO-Unit-1 2
 Syllabus
UNIT – I Introduction To Digital Electronics
• Digital Logic families: Digital IC Characteristics; TTL: Standard TTL characteristics,
Operation of TTL NAND gate; CMOS: Standard CMOS characteristics, operation of
CMOS NAND gate; Comparison of TTL & CMOS.
• Signed Binary number representation and Arithmetic: Sign Magnitude, 1’s
complement & 2’s complement representation, unsigned Binary arithmetic
(addition, subtraction, multiplication, and division), subtraction using 2’s
complement; IEEE Standard 754 Floating point number representations.
• Codes: Binary , BCD, octal , hexadecimal , Excess-3 , Gray code & their conversions
• Logic minimization: Representation of logic functions: logic statement, truth table,
SOP form, POS form; Simplification of logical functions using K-Maps up to 4
variables.
• Case Study:1) CMOS 4000 series ICs 2) practical applications of various codes in
computers 3) four basic arithmetic operations using floating point numbers in a
calculator.

RVK-LDCO-Unit-1 3
 Contents
1.1-Basics of Digital Electronics
1.2-Logic Gates
1.3-Number System-Basics
1.4-Signed Binary Representation
1.5-Binary Arithmetic
1.6-Floating Point Representation
1.7-Codes
1.8-IC Logic Families
1.9-TTL Logic Family
1.10-CMOS Logic Family
1.11-Logic Minimization

RVK-LDCO-Unit-1 4
 1.1 Basics of Digital Electronics

-Mrs. Radhika V. Kulkarni

Assistant Professor, Dept. of Information Technology,
Pune Institute of Computer Technology, Pune.

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
 Electronics Circuits & Systems
• Two broad categories:
1. Analog circuit:
• Voltage and current take infinite values within the specific range
(vary continuously ).
• E.g. audio amplifier, signal generators, electric motors, speed
controllers, power supplies, radio frequency transmitters and
receivers etc.

2. Digital circuit:
• Voltage and current take discrete and finite values.
• Known as logic circuit as it follow a set of logic rules.
• Also known as switching circuit as voltage levels instantaneously
switch from one value to another.
• E.g. digital speedometers, all modern digital circuits
RVK-LDCO-Unit-1 6
 Digital Waveforms
• Digital waveforms vary between the LOW and HIGH levels
and are made up of a series of pulses.
• A positive going pulse:
– It goes from a normally LOW logic level to a HIGH level and then back
again.
• A negative going pulse:
– It goes from a normally HIGH logic level to a LOW level and then back
again.
HIGH HIGH
Rising or Falling or Falling or Rising or
leading edge trailing edge leading edge trailing edge

LOW LOW
t0 t1 t0 t1

(a) Positive–going pulse (b) Negative–going pulse

RVK-LDCO-Unit-1 7
 Digital Circuits
• Two broad categories:
1. Combinational circuit:
• Output is dependent only on the present inputs.
• Does not have memory.

2. Sequential circuit:
• Output is dependent on the present inputs and the present state
of the circuit (i.e. the past inputs).
• Has memory.
• Sequential circuit = combinational circuit + memory.
• Subcategories:
1. Synchronous: State transition occurs only when inputs are applied with
the clock pulse.
2. Asynchronous: State transition occurs any time the inputs are applied

RVK-LDCO-Unit-1 8
 Advantages of Digital Circuits
• Easier to design and versatile:
– Uses only two levels-HIGH & LOW
– The exact numerical values are not important as they have only logical
significance.
– Need only Boolean algebra and has few basic operations
– Variety of programs can be designed to modify the system operations

• Greater accuracy and precision:

– Can be easily expanded to handle more digits by adding more digital circuits.

• Smaller effect of fluctuations in the characteristics of the

components, ageing of components, temperature, and noise
etc.
RVK-LDCO-Unit-1 9
 Advantages of Digital Circuits (cont..)
• Digital circuits have capability of memory
– Highly suitable for computers, calculators, watches, telephones, etc.
– Information storage is easy.

• More digital circuitry can be fabricated on IC (Integrated

Circuit) chips.
– A wide range of ICs for various operations.
– ICs are highly reliable, accurate, small in size and the speed of operation is
very high.
– In an IC logic family, availability of numerous ICs with similar electrical
characteristics makes the design and development of digital systems very
simple and also reduces interfacing problems.
– Also, a variety of logic families facilitates the system design optimization
considering the trade-off of power and speed.
RVK-LDCO-Unit-1 10
 Disadvantages of Digital Circuits
• The real world is analog.

• Digital circuits make a digital approximation to an inherent

analog quantity.

• Conversions between analog to digital and digital to analog

cause increased processing time and the complex system.

• Disadvantages of digital circuits are outweighed by the

various advantages.

RVK-LDCO-Unit-1 11
 Functions of Digital Logic
1. Arithmetic operations:
– Adder, subtracter, multiplier, divider circuits
2. Encoding:
– Conversion of a digit/alphabet/special character to some binary code
3. Decoding:
– Conversion of a binary code to unique outputs (numbers/symbols).
4. Multiplexing:
– N-to-1 device that takes several inputs and allows only one of them to get
through to the output.
5. Demultiplexing:
– 1-to-N device that takes a single input and distributes it over several
outputs.
6. Comparison:
– Outputs the result of comparison of two input quantities.

RVK-LDCO-Unit-1 12
 Functions of Digital Logic (cont..)
7. Code conversion:
– Converts information coded in one form to another form.
8. Storage:
– Stores and shift information(data). Uses registers for the same.
9. Counting:
– Counts the number of input pulses. Uses flip-flops to build the counters.
10. Frequency Division:
– Divides a signal f by N using mod N counters.
11. Data Transmission:
– Transfers binary data (representing the voltage levels) at the outputs of a
sending circuit which are fed to the inputs of a receiving circuit .
– Two types:
1) Serial: All bits are transmitted sequentially.
2) Parallel: All bits are transmitted simultaneously.
RVK-LDCO-Unit-1 13
 1.2 Logic Operations & Gates

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
 Boolean Algebra
• George Boole was an English mathematician,
philosopher and logician who worked in the fields
of differential equations, probability and algebraic
logic.

• He introduced an algebraic system of logic known

as “Boolean Algebra” in 1854.

• In Boolean Algebra,
– the values of the variables are the truth values true (or 1) and false (or 0)
– the main operations of Boolean algebra are the conjunction (AND) denoted as
∧ (or •), the disjunction (OR) denoted as ∨ (or +), the negation (not) denoted
as ¬(or ‘).

• Boolean algebra thus formally describes logical operations in the

same way that elementary algebra describes numerical operations.
RVK-LDCO-Unit-1 15
Boolean Algebraic Theorems

RVK-LDCO-Unit-1 16
 Logic AND Operation
• A logic gate is a physical implementation of a Boolean function

• Logic AND is a boolean function F of two variables (A, B).

– Y= F(A,B) = A • B or Y= F(A,B) = AB
– When both the inputs are '1', then the output
is is '1’.
– (0 • 0) = 0, (0 • 1) = 0, (1 • 0) = 0, (1 • 1) = 1

• AND operation can be viewed as two switches in series:

RVK-LDCO-Unit-1 17
 Logic OR Operation
• Logic OR is a boolean function F of two variables (A, B).
– Y= F(A,B) = A + B
– When either of the inputs is '1', then
the output is '1’.
– (0 + 0) = 0, (0 + 1) = 1, (1 + 0) = 1, (1 + 1) = 1

• OR operation can be viewed as two switches in parallel:

RVK-LDCO-Unit-1 18
 Logic NOT Operation
• Logic NOT is an inverse or complement operation that replaces a
Boolean value with its complement.

• It is a boolean function F of a single variable (A).

– Y= F(A) = A’ or Y= F(A) = ~A or Y= F(A) = Ā
– 0’ = 1 , 1’ = 0

RVK-LDCO-Unit-1 19
 Logic NAND Operation
• The NAND gate symbol is the same as the AND with a circle on the
output to indicate that the output is inverted.
• It is a boolean function F of two variables (A, B).
– X= F(A,B) = ~(A • B) or X= F(A,B) = (AB)’
– When both the inputs are '1', then the output is ‘0’.
– (0 • 0)’ = 1, (0 • 1)’ = 1, (1 • 0)’ = 1, (1 • 1)’ = 0

• Also known as a Universal Gate because they can be used to

produce the other basic Boolean functions.

RVK-LDCO-Unit-1 20
 Logic NOR Operation
• The NOR gate symbol is the same as the OR with a circle on the
output to indicate that the output is inverted.
• It is a boolean function F of two variables (A, B).
– X= F(A,B) = ~(A + B) or X= F(A,B) = (A+B)’
– When both the inputs are ‘0', then the output is ‘1’.
– (0 + 0)’ = 1, (0 + 1)’ = 0, (1 + 0)’ = 0, (1 + 1)’ = 0

• Also known as a Universal Gate because they can be used to

produce the other basic Boolean functions.

RVK-LDCO-Unit-1 21
 Universal Gates: NAND & NOR
• In the most widely used IC technologies (e.g. CMOS, NMOS, TTL), a
NAND gate requires less silicon area than an AND or OR gate.
• In most IC technologies, it is easier to make a gate with inversion
than without it.

• Logic functions using

NAND gate :

• Logic functions using

NOR gate :

RVK-LDCO-Unit-1 22
Logic functions using NAND gate

RVK-LDCO-Unit-1 23
Logic functions using NOR gate

RVK-LDCO-Unit-1 24
 Logic XOR Operation
• The XOR function is a boolean function F of two variables (A,
B).
– Y= F(A,B) = A Å B = A B + AB
– It means : A OR B, but NOT BOTH
– When both the inputs have different values, then the output is ‘1’.
– (0 Å 0) = 0, (0 Å 1) = 1, (1 Å 0) = 1, (1 Å 1) = 0
– (A Å 0) = A, (A Å 1) = Ā (or A’)

• Strictly speaking, XOR gates do not exist for more than two
inputs.

RVK-LDCO-Unit-1 25
 Logic X-NOR Operation
• The X-NOR function is the complement of the XOR function.

• It is a boolean function F of two variables (A, B).

– Y= F(A,B) = AꙩB = A ⊕ B = A B + AB = A B + AB
– When both the inputs have same values, then the output is ‘1’.
– (0 ꙩ 0) = 1, (0 ꙩ 1) = 0, (1 ꙩ 0) = 0, (1 ꙩ 1) = 1

• Strictly speaking, X-NOR gates do not exist for more than two
inputs.

RVK-LDCO-Unit-1 26
 Logic Gate IC
• Logic gates are usually embedded in Integrated Circuits ICs, sometimes
referred as Chips.
• According to its complexity, ICs are classified as
– SSI (Small Scale Integration): 1-11 gates on a single chip
– MSI (Medium Scale Integration): 12-99 gates on a single chip
– LSI (Large Scale Integration): 100-9,999 gates on a single chip
– VLSI (Very Large Scale Integration): 10,000-99,999 gates on a single chip
– ULSI(Ultra Large Scale Integration): More than1,00,000 gates on a single chip

• Logic gates ICs may be TTLs type or CMOS

type, both require a power supply of +5v
and a 'ground’ in addition to the logic inputs.

• Some of the manufacturers of gate ICs:

– Texas Instruments (www.ti.com)
– Philips (www.philips.com)
– Fairchild semiconductor (www.fairchildsemi.com)
RVK-LDCO-Unit-1 27
 1.3 Number System-Basics

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Computer organization and architecture, designing for performance” by William Stallings ,
Prentice Hall , Eighth edition
3. “Computer organization” , Hamacher and Zaky, Fifth Edition
4. http://WilliamStallings.com/COA6e.html
 Information Representation
• Numbers are important to computers.
– Represent information precisely.
– Can be processed.
• Bit (Binary digit): 0 and 1
– Represent false and true in logic.
– Represent the low and high states in electronic devices.
• Other units
– Byte: 8 bits
– Nibble: 4 bits (seldom used)
– Word: Multiples of byte (e.g. 1 byte, 2 bytes, 4 bytes, 8 bytes, etc.)
depending on the architecture of the computer system.
• N bits can represent up to 2N values.
– E.g. 2 bits à represent up to 4 values (00, 01, 10, 11); 3 bits à rep. up to 8 values
(000, 001, …, 110, 111)
• To represent M values, log2M bits are required.
– E.g. 32 values à requires 5 bits; 1024 values à requires 10 bits.
RVK-LDCO-1.3 29
 Number System
• A number is a collection of digits generally having two parts-
integer and fractional, separated by a radix point(×).

where, N is a number
b is a radix or base of the number system
n is a number of digits in integer part
m is a number of digits in fractional part
dn-1 is the most significant bit/digit (MSB/MSD)
d-m is the least significant bit/digit (LSB/LSD)
0 £ ( di or d-f) £ b-1

RVK-LDCO-1.3 30
 Characteristics of Commonly Used
Number Systems
Number Radix or Symbol Used Weight Assigned Example
Systems Base (b) (di or d-f) (bi or b-f)
i -f
Binary 2 0, 1 2i 2-f 1001.11
Octal 8 0, 1, 2, 3, 4, 5, 6, 7 8i 8-f 2563.56

Decimal 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 10i 10-f 8934.85

Hexadecimal 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, 16i 16-f A4D9.67

C, D, E, F

• E.g. (46)10=(101110)2=(56)8=(2E)16

RVK-LDCO-1.3 31
 Number Conversions To Decimal
• Use Positional Weights bi or b-f
– where b is a radix (or base), i is bit position in the integer part and f is a bit
position in the fractional part.
• Binary to Decimal:
e.g. (10110.11)2 =1x24 + 0x23 + 1x22 + 1x21 + 0x20 + 1x2-1 + 1x2-2
= 16 + 0 + 4 + 2 + 0+0.5+0.25
= (22.75)10
• Octal to Decimal:
e.g. (653.71)8 =6x82 + 5x81 + 3x80 + 7x8-1 + 1x8-2
= 96 + 40 + 3 + 0.875+0.016
= (139.891)10
• Hexadecimal to Decimal:
e.g. (D5B.C3)16 =13x162 + 5x161 + 11x160 + 12x16-1 + 3x16-2
= 3328 + 80 + 11 + 0.75+0.0117
= (3419.7617)10
RVK-LDCO-1.3 32
 Number Conversions of Decimal
• Method 1: Sum-of-Weights
E.g. (18.75)10 = 16 + 2 + 0.5 + 0.25 = 24 + 21 + 2-1 + 2-2 = (10010.11)2

• Method 2: Repeated Division or Multiplication by Radix

– Repeated Division-by-radix (or base b): For Integer part
• To convert a decimal integers to binary/octal/hexadecimal , use successive
division by respective radix (b=2 or 8 or 16) until the quotient is 0.
• The remainders form the answer, with the first remainder as the least
significant bit (LSB) and the last as the most significant bit (MSB).

– Repeated Multiplication-by-radix (or base b): For Fractional part

• To convert decimal fractions to binary/octal/hexadecimal, use repeated
multiplication by respective radix (b=2 or 8 or 16) until the fractional product
is 0 (or until the desired number of decimal places).
• The carried digits (or carries) produce the answer, with the first carry as the
MSB, and the last as the LSB.

RVK-LDCO-1.3 33
 Example of Decimal to Binary
• By Repeated Division or Multiplication by Radix:
E.g. (43.3125)10 = (?)2

(43.3125)10 = (101011.0101)2
RVK-LDCO-1.3 34
 Conversion Between Different Bases
• In general, conversion between bases can be done via
decimal:

• Shortcuts for conversion between bases 2, 8, 16

– BinaryàOctal: partition in groups of 3 bits from LSB & add necessary
0s at MSB.
E.g. (1101111)2 =(001 101 111)2 = (157)8 ; (74)8 =(111 100)2

– BinaryàHexadecimal: partition in groups of 4 bits from LSB & add

necessary 0s at MSB.
E.g. (1101111)2 =(0110 1111)2 = (6F)16 ; (C7)16 =(1100 0111)2
RVK-LDCO-1.3 35
 1.4 Signed Binary Representation

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Computer organization and architecture, designing for performance” by William Stallings ,
Prentice Hall , Eighth edition
3. “Computer organization” , Hamacher and Zaky, Fifth Edition
4. http://WilliamStallings.com/COA6e.html
 Signed Binary Representation
• Unsigned numbers: only non-negative values.
• Signed numbers: include both positive and
negative values.
• There are 3 common representations for signed
binary numbers:
1. Sign-Magnitude
2. 1’s Complement
3. 2’s Complement

RVK-LDCO-1.4 37
 Sign-Magnitude Representation
• In n-digit number
– Left most bit (MSB) is sign bit
– Remaining n-1 bits represent magnitude
– 0 means positive
– 1 means negative

• Negated value of a number is obtained by just changing a sign bit.

– E.g. 0110100 è +1101002 = +5210
1110100 è -1101002 = -5210

• Range: -2n –1 - 1 through 2n –1 - 1

– E.g. Range for 8-bit numbers: -12710 to +12710

• Drawbacks:
– Need to consider both sign and magnitude in arithmetic operations
– Two representations of Zero: 00000000 = +010 and
10000000 = -010
RVK-LDCO-1.4 38
 1’s Complement Representation
• Essential technique to negate a value: invert all the bits (replace 0
by 1 and 1 by 0).
– E.g. +1210 = 000011002 and
-1210 = 111100112

• The most significant (left-most) bit still represents the sign.

– 0 for positive
– 1 for negative.

• Range: -2n –1 - 1 through 2n –1 - 1

– E.g. Range for 8-bit numbers: -12710 to +12710

• Two representations for Zeros: 00000000 = +010 and

11111111 = -010
RVK-LDCO-1.4 39
 1’s Complement Representation (cont..)
• The negated value of a given a decimal number X which can be
expressed as an n-bit binary number, can be obtained in 1’s-
complement representation using:
-X = 2n – X – 1

• E.g. (1210)=(00001100)2, its negated value can be expressed as an 8-

bit binary number in 1’s-complement as below:
(-1210)= 28 – 12 – 1 (calculation in decimal)
= 24310
= 111100111’s

(i.e. +1210 = 000011002 and

-1210 =111100112 in 1’s-complement representation.)

RVK-LDCO-1.4 40
 2’s Complement Representation
• Essential technique to negate a value: invert all the bits (replace 0
by 1 and 1 by 0) and add 1 to it.
– E.g. +1210 = 000011002 and its negation using 2’s complement is given as
below:

• The most significant (left-most) bit still represents the sign.

– 0 for positive
– 1 for negative.

• Range: -2n –1 through 2n –1 - 1

– E.g. Range for 8-bit numbers: -12810 to +12710

RVK-LDCO-1.4 41
 2’s Complement Representation (cont..)
• The negated value of a given a decimal number X which can be
expressed as an n-bit binary number, can be obtained in 2’s-
complement representation using:
-X = 2n – X
• E.g. (1210)=(00001100)2, its negated value can be expressed as an 8-
bit binary number in 2’s-complement as below:
(-1210)= 28 – 12 (calculation in decimal)
= 24410
= 111101002’s

(i.e. +1210 = 000011002 and

-1210 =111101002 in 2’s-complement representation.)

RVK-LDCO-1.4 42
 2’s Complement Representation (cont..)
• Negation Special Case 1:
010 = 00000000
Bitwise not = 11111111
Add 1 to LSB = + 1
Result = 100000000 Carry is ignored, so -0 = 0 is correct.

• Negation Special Case 2:

-12810 = 10000000
Bitwise not = 01111111
Add 1 to LSB = + 1
Result = 10000000 Sign bit is not changed,
so -(-128) = +128 is wrong
RVK-LDCO-1.4 43
Geometric Depiction of 2’s
Complement Integers

RVK-LDCO-1.4 44
 Geometric Depiction of 2’s Complement
Integers (cont..)
• When the numbers are laid out on a circle, the two’s complement of
any number is horizontally opposite that number (indicated by
dashed horizontal lines).

• Starting at any number on the circle, we can add positive k (or

subtract negative k) to that number by moving k positions clockwise,
and we can subtract positive k (or add negative k) from that number
by moving k positions counterclockwise.

• If an arithmetic operation results in traversal of the point where the

endpoints are joined, an incorrect answer is given (overflow).

RVK-LDCO-1.4 45
 2’s Compliment Representation(cont..)
• Conversion between lengths:
– Positive number pack with leading zeros
E.g. +18 = 00010010; +18 = 00000000 00010010 (For 16-bit)
– Negative numbers pack with leading ones
E.g. -18 = 10010010; +18 = 11111111 10010010 (For 16-bit)
– i.e. pack with MSB (sign bit)

• Benefits:
– One representation of zero
– Arithmetic works easily
– Negating is fairly easy

RVK-LDCO-1.4 46
2’s Complement Binary and Decimal Conversion Using
a Value Box

RVK-LDCO-1.4 47
 Comparisons
4-bit system
Positive values Negative values
Value Sign-and- 1s 2s Value Sign-and- 1s 2s
Magnitude Comp. Comp. Magnitude Comp. Comp.
+7 0111 0111 0111 -0 1000 1111 -
+6 0110 0110 0110 -1 1001 1110 1111
+5 0101 0101 0101 -2 1010 1101 1110
+4 0100 0100 0100 -3 1011 1100 1101
+3 0011 0011 0011 -4 1100 1011 1100
+2 0010 0010 0010 -5 1101 1010 1011
+1 0001 0001 0001 -6 1110 1001 1010
+0 0000 0000 0000 -7 1111 1000 1001
-8 - - 1000

RVK-LDCO-1.4 48
 Complement on Fractions
• We can extend the idea of complement on
fractions.
• Examples:
– Negate 0101.01 in 1’s-complement
Answer: 1010.10
– Negate 0101.01 in 2’s-complement
Answer: 1010.11

RVK-LDCO-1.4 49
 1.5 Binary Arithmetic

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Computer organization and architecture, designing for performance” by William Stallings ,
Prentice Hall , Eighth edition
3. “Computer organization” , Hamacher and Zaky, Fifth Edition
4. http://WilliamStallings.com/COA6e.html
Unsigned Binary Arithmetic
 Unsigned Binary Addition
• Addition ( A + B):
– Perform binary addition on the two numbers using following rules.
Augend Addend Sum Carry Result
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 0 1 10

– Examples: 4-bit system

3 0011 5 0101
+ 6 + 0110 + 15 + 1111
---- à ----- ---- à ------
9 1001 20 10100
---- ----- ---- ------

RVK-LDCO-1.5 52
 Unsigned Binary Addition(cont..)
• Examples: 8-bit system
(1)(1)(1)
(1)(1)(1)(1)(1)(1)(1) ß(Carries)
85 0 1 0 1 0 1 0 1
+ 255 + 1 1 1 1 1 1 1 1
+ 140 + 1 0 0 0 1 1 0 0
+ 21 + 0 0 0 1 0 1 0 1
----- -------------------------
501 1 1 1 1 1 0 1 0 1
----- -------------------------

• Observations:
– If the number of 1s to be added in a column is even then the sum bit is 0.
– If the number of 1s to be added in a column is odd then the sum bit is 1.
– Every pair of 1s produces a carry (1) to be added to the next higher bit column.
RVK-LDCO-1.5 53
 Unsigned Binary Subtraction
• Subtraction ( A - B):
– Perform binary subtraction on the two numbers using following rules.
Minuend Subtrahend Difference Borrow
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0

– Examples: 4-bit system

8 1000 13 1101
- 4 - 0100 - 6 - 0110
---- à ------ ---- à -----
4 0100 7 0111
---- ------ ---- -----

RVK-LDCO-1.5 54
 Unsigned Binary Multiplication
• Multiplication (A x B):
– Perform binary multiplication of the two numbers same as decimal
numbers multiplication.
– Needs double length result.
– Each partial product is either 0 (if a multiplier bit is 0) or exactly same as
the multiplicand (if a multiplier bit is 1).
– Example: 4-bit system
11 1011 ß Multiplicand
x 9 x 1001 ß Multiplier
---- à ----------
99 1011
---- + 0000* ß Partial Products
+ 0000**
+ 1011***
----------
1100011 ß Final Product
----------
RVK-LDCO-1.5 55
 Unsigned Binary Division
• Division (A / B):
– Perform binary division of the two numbers same as decimal numbers
division.
– Example: 4-bit system
13 ß Quotientà 01101
11/ 147 ß Dividend Divisor à 1011/10010011
-11 - 1011
37 ß Partial remainders à 001110
-33 -1011
4 ßRemainder 001111
-1011
Remainder à 0100

Dividend = Quotient x Divisor + Remainder

147 = 13 x 11 + 4
à 10010011 = 1101 x 1011 + 100
RVK-LDCO-1.5 56
1’s Complement Addition/Subtraction
 Overflow
• Signed numbers are of a fixed range.
– 4-bit 1’s-complement system: Range of value: -710 to 710
– 4-bit 2’s-complement system: Range of value: -810 to 710

• If the result of addition/subtraction goes beyond this range, an

overflow occurs.

• When overflow occurs, the ALU must signal this fact so that no
attempt is made to use the result.

• Overflow Rule: If 2 numbers are added, and they are both +ve or
both -ve, then overflow occurs iff the result has the opposite sign.
– positive + positive à negative
– negative + negative à positive

• Overflow can occur whether or not there is a carry.

RVK-LDCO-1.5 58
 1’s Complement Addition/Subtraction
• Algorithm for addition (A + B):
1. Perform binary addition on the two numbers.
2. If there is a carry out of the MSB, add 1 to the result and then
ignore carry .
3. Check for overflow. Overflow occurs if result is opposite sign of A
and B.

• Algorithm for subtraction (A – B): A – B = A + (-B)

1. Take 1’s-complement of B.
2. Add the 1’s-complement of B to A.
Thus, we only need addition and complement circuits.

RVK-LDCO-1.5 59
1’s Complement Addition/Subtraction (cont..)
• Examples: 4-bit system (Range: -710 to +710)
+3 0011 +5 0101
+ +4 + 0100 + -5 + 1010
---- ------- ---- -------
+7 0111 -0 1111
---- ------- ---- -------

-2 1101 -3 1100
+ -5 + 1010 + -7 + 1000
---- ------ ---- -------
-7 10111 -10 10100
---- + 1 ---- + 1
carry ------ carry & -------
1000 Overflow à 0101
------ -------
(Discard the result)
RVK-LDCO-1.5 60
2’s Complement Addition/Subtraction
 2’s Complement Addition/Subtraction
• Algorithm for addition (A + B):
1. Perform binary addition on the two numbers.
2. Ignore the carry out of the MSB.
3. Check for overflow. Overflow occurs if the ‘carry in’ and ‘carry
out’ of the MSB are different, or if result is opposite sign of A
and B.

• Algorithm for subtraction (A – B): A – B = A + (-B)

1. Take 2’s-complement of B.
2. Add the 2’s-complement of B to A.
Thus, we only need addition and complement circuits.
RVK-LDCO-1.5 62
2’s Complement Addition/Subtraction (cont..)
• Examples: 4-bit system (Range: -810 to +710)
+3 0011 +4 0100
+ +4 + 0100 + -7 + 1001
---- ------- ---- -------
+7 0111 -3 1101
---- ------- ---- -------

+6 0110 -2 1110
+ -3 + 1101 + -6 + 1010
---- ------- ---- -------
+3 10011 -8 11000
---- ------- ---- -------
Ignore carry Ignore carry

RVK-LDCO-1.5 63
2’s Complement Addition/Subtraction (cont..)
• Examples: 4-bit system (Range: -810 to +710)

-3 1101 +5 0101
+ -6 + 1010 + +6 + 0110
---- ------- ---- -------
-9 10111 +11 1011
---- ------- ---- -------
Ignore carry No carry, but
Overflow à 0111 Overflow à 1011

(Discard the result) (Discard the result)

RVK-LDCO-1.5 64
 1.6 IEEE 754 Standard for Floating
Point Representation
Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Computer organization and architecture, designing for performance” by William Stallings ,
Prentice Hall , Eighth edition
3. “Computer organization” , Hamacher and Zaky, Fifth Edition
4. http://WilliamStallings.com/COA6e.html
 Real Numbers
• These are the numbers with fractions.
– E.g. (1001.1010)2 = 23 + 20 +2-1 + 2-3 =(9.625)10

• The position of the binary point is variable and is automatically

adjusted as computation proceeds.

• In such a case, the binary point is said to float, and the numbers
are called floating-point numbers.

• As the position of the binary point in a floating-point number is

variable, it must be given explicitly in the floating-point
representation.

RVK-LDCO-1.6 66
 Floating Point Number
• By convention, when the decimal point is placed to the right of the
first (nonzero) significant digit, the number is said to be normalized.
– E.g. 6.0247 x 1023, 6.6254 x10-27, -1.0341 x 102 etc.

• The base, 10, in the scale factor is fixed. So no need to mention it

explicitly in the machine representation of a floating-point number.

• The sign, the significant digits, and the exponent in the scale factor
constitute the representation.

• Hence a floating-point number representation is one in which a

number is represented by its sign, a string of significant digits,
commonly called the mantissa, and an exponent to an implied base
for the scale factor.

RVK-LDCO-1.6 67
 Sign bit
Floating Point Number (cont..)
Biased Significand or Mantissa
Exponent

• Floating Point (FP) Number = Sign(+/-) Significand x Bexponent

• The base B is implicit and need not be stored because it is the
same for all numbers .

• Normalization:
– FP numbers are usually normalized i.e. exponent is adjusted so that leading
bit (MSB) of mantissa is 1.
– Since it is always 1 there is no need to store it.(e.g. 1.101x2101)
– Mantissa field actually represents the fractional part of the mantissa.

RVK-LDCO-1.6 68
 Signs for Floating Point Numbers
• Mantissa is stored in 2’s compliment representation.

• Exponent is in excess or biased notation.

– Instead of the signed exponent, E, ±ve value actually stored in the
exponent field is an unsigned integer E’.
– A fixed value, called the bias, is subtracted from the field to get the true
exponent value.
– Typically, the bias equals (2k-1 -1)where k is the number of bits in the
binary exponent.
– E.g. For 8-bit exponent field, pure value ranges from 0 to 255.
– With a bias of (28-1 -1)= (27 -1)= 127 ; E' = E + 127
– Excess-127 format;
– 0 ≤ E’≤ 255; the range of E' for normal values is 1≤ E’ ≤ 254.
– Hence the range of true/actual exponent is: -126 ≤ E ≤ 127.
RVK-LDCO-1.6 69
 IEEE Standard 754
• Standard for floating point storage
• Single Precision Format:
– 32bits: 1 bit Sign, 8 bits Exponent, 23 bits Mantissa.
– Bias of (28-1 -1)= (27 -1)= (128-1)=127 ; E' = E + 127
– Excess-127 format

• Double Precision Format:

– 64bits: 1bit Sign, 11 bits Exponent, 52 bits Mantissa
– Bias of (211-1 -1)= (210 -1)= (1024-1)= 1023 ; E' = E + 1023
– Excess-1023 format
• Extended formats (both mantissa and exponent) for
intermediate results
RVK-LDCO-1.6 70
 IEEE 754 Format
• Single Precision format:

• Double Precision format:

RVK-LDCO-1.6 71
 Single Precision Floating Point Examples
• The sign is stored in the first bit of the word.
• The first bit of the true significant is always 1 and need not be
stored in the significant field.
• The value 127 is added to the true exponent to be stored in the
exponent field.
• The base is 2, need not be stored in exponent field.

RVK-LDCO-1.6 72
 Single Precision Floating Point Examples (cont..)
Q. Represent -0.09375 in IEEE754 format.
Ans.- The sign is negative, therefore our number will start with a 1.
– Now , ignoring the sign, convert 0.09375 to binary:

– Normalized format (0.00011)2=1.1 x 2-4

– Now rewrite -4 in “excess 127” form: -4 + 127 = 123 and 12310= 11110112 .
– But since this contains only 7 bits, we rewrite it with 8-bits as : 011110112
– Hence, -0.09375 will be represented in 32-bit IEEE 754 format as below:
S E’ M
1 01111011 10000000000000000000000
RVK-LDCO-1.6 73
Double Precision Floating Point Examples (cont..)
Q. Represent -0.09375 in IEEE754 Double Precision format.
Ans.- The sign is negative, therefore our number will start with a 1.
– Now , ignoring the sign, convert 0.09375 to binary:

– Normalized format (0.00011)2=1.1 x 2-4

– Now rewrite -4 in “excess 1023” form: -4 + 1023 = 1019 and 101910=
11111110112 . But since this contains only 10 bits, we rewrite it with 11-bits as :
011111110112
– Hence, -0.09375 will be represented in 64-bit IEEE 754 format as below:
S E’ M (52-bit)
1 01111111011 10000000000000000000000…0
RVK-LDCO-1.6 74
 FP Range
• 2’s complement integer: from -231 to 231-1 for all 232 different
numbers.
• Single Precision Floating Point representation:
− Negative numbers between: -(2 - 2-23)x 2128 and -2-127
− Positive numbers between: 2-127 and (2 - 2-23) x 2128

RVK-LDCO-1.6 75
Density of Floating Point Numbers

RVK-LDCO-1.6 76
 FP Exceptions
• Exponent overflow: A positive exponent exceeds the
maximum possible exponent value. In some systems, this
may be designated as +infinity or -infinity.

• Exponent underflow: A negative exponent is less than

the minimum possible exponent value (e.g.-200 is less
than -127 ). This means that the number is too small to
be represented, and it may be reported as 0.

RVK-LDCO-1.6 77
 FP Exceptions (cont..)
• Significand underflow: In the process of aligning
significands, digits may flow off the right end of the
significand. As we shall discuss, some form of
rounding is required.

• Significand overflow: The addition of two

significands of the same sign may result in a carry
out of the most significant bit. This can be fixed by
realignment.

RVK-LDCO-1.6 78
 1.7 Codes

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Digital Design”, M Morris Mano, Prentice Hall, Third Edition
3. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
 Codes
• Codes represent numbers/ alphabets/special characters in a binary
form for processing and transmission in digital systems.

• They are also used for error detection and correction in digital
systems.

• There are variety of codes. E.g. Binary, BCD, Excess-3, Gray, ASCII
etc.

• Though all codes represent the information in binary format, its

interpretation is completely based on the coding scheme used to
represent that information.
– E.g. (01001001)2 = (73)10
(01001001)BCD = (49)10
(01001001)XS-3 = (16)10
RVK-LDCO-1.7 80
 Different Codes
• Straight Binary Code
• Decimal Codes
– BCD (Binary Coded Decimal) Code
– Excess-3 Code
• Gray Code
• Octal Code
• Hexadecimal Code
• Alphanumeric Codes
– ASCII - American Standard Code for Information Interchange
– EBCDIC - Extended BCD Interchange Code
• Error Detection Codes
– Parity Bit
• Error Correction Codes
– Hamming Code
RVK-LDCO-1.7 81
 Decimal Codes
• Decimal numbers are favored by humans. Binary
numbers are natural to computers. Hence, conversion
is required.

• If little calculation is required, we can use some

coding schemes to store decimal numbers, for data
transmission purposes.

• Examples: BCD (or 8421), 2421, Excess-3 etc.

• Each decimal digit is represented as a 4-bit code.

RVK-LDCO-1.7 82
 BCD (Binary Coded Decimal) Code
• BCD is a convention for mapping binary numbers to decimal
numbers.
• When the decimal numbers are represented in BCD, each decimal
digit is represented by the equivalent BCD code.
– Decimal numbers 0 to 9 are represented by their natural 4-bit binary
equivalent.
• It is also known as 8-4-2-1 code.
• It is a weighted code as specific weights are assigned to the bit
positions.
• E.g. BCD Representation of (6349)10 is obtained as below:
6 3 4 9
0110 0011 0100 1001
• Some codes are unused, like 1010BCD, 1011BCD, … 1111BCD. These
codes are considered as errors.
RVK-LDCO-1.7 83
 BCD Code (Cont..)
• Easy to convert, but arithmetic Decimal
BCD
operations are more complicated. digit
• Suitable for interfaces such as keypad 0 0000
inputs. 1 0001
2 0010
• Examples of conversion between BCD 3 0011
values and decimal values: 4 0100
– (7093)10 = (0111 0000 1001 0011)BCD
5 0101
– (1001 0100 0111 0010)BCD = (9472)10
6 0110
• Note that BCD is not equivalent to
7 0111
binary.
– E.g.: (234)10 = (11101010)2 8 1000
(234)10 = (0010 0011 0100)BCD 9 1001
RVK-LDCO-1.7 84
 Excess-3 Code
• The excess-3 code is obtained by adding 3 (0011) to the
corresponding BCD equivalent binary number.
– E.g. (4)10 = (0100)BCD = 0100+ 0011 =(0111)XS-3

RVK-LDCO-1.7 85
 Excess-3 Code (cont..)
• Excess-3 have a self-complementing property. 0: 0011
– 1’s complement of the coded number yields 9’s 1: 0100
complement of the number itself.
– E.g. (4)10 = (0111)XS-3 . 2: 0101
Its 1’s complement =(1000) and 3: 0110
9‘s complement of (4)10 =(5)10= (1000)XS-3. 4: 0111
5: 1000
– Useful property when doing arithmetic operations 6: 1001
with signed complement representation. 7: 1010
8: 1011
9: 1100
• Note: 9’s complement of a decimal no. is obtained by
subtracting each digit of that decimal no. from 9. The
10’s compliment of a decimal no is obtained by adding
a 1 to its 9’s compliment.
– E.g. (42)10 = 99-42= (57)9’s = 57+1= (58)10’s

RVK-LDCO-1.7 86
 Gray Code
• The Gray code is unweighted and is not an arithmetic code.
– There are no specific weights assigned to the bit positions.
• It is a unit distance cyclic code.
– It exhibits only a single bit change from one code word to the next in sequence.
– This property is important in many applications, such as shaft position
encoders.
• Not restricted to decimal digits: n bits à 2n values.
• Good for error detection.
• It is a reflective code and can be constructed using this property as given
below.
i. A 1-bit Gray code has two code words 0 and 1 representing decimal numbers
0 and 1 respectively
ii. An n-bit (n ≥2) Gray code will have first 2n-1 Gray codes of (n-1)-bits written in
order with a leading 0 appended.
iii. The last 2n-1 Gray codes will be equal to the Gray code words of an (n -1)- bit
Gray code, written in reverse order (assuming a mirror placed between first
2n-1 and last 2n-1 Gray codes) with a leading 1 appended.
RVK-LDCO-1.7 87
 Gray Code (cont..)
• Construction of n-bit Gray code:
n=1 n=2 n=3 n=4
Decimal Gray Decimal Gray Decimal Gray Decimal Gray
0 0 0 00 0 000 0 0000
1 1 1 01 1 001 1 0001
2 11 2 011 2 0011
3 10 3 010 3 0010
4 110 4 0110
5 111 5 0111
6 101 6 0101
7 100 7 0100
8 1100
9 1101
10 1111
11 1110
12 1010
13 1011
14 1001
RVK-LDCO-1.7 15 1000 88
 Gray Code (cont..)
• Ex.1 Convert (1001)2 to Gray Code.
• Soln:
– Right Shift the original binary number by one bit
and XOR it with the original binary number.
1001
Å 0100 (Right shifted1001 by a single bit)
--------
1101 (XOR Result)

RVK-LDCO-Unit-1 89
 Octal Code
• It is a 3-bit binary code.
• Each of the octal digits 0 through 7 is coded into 3-bit
straight binary number.
• Used for binary inputs in digital computers,
microprocessors etc.
• BinaryàOctal: partition in groups of 3 bits from LSB &
add necessary 0s at MSB.
– E.g. (1101111)2 =(001 101 111)2 = (157)8 ;
(74)8 =(111 100)2

RVK-LDCO-1.7 90
 Hexadecimal Code
• It is a 4-bit binary code.
• Each of the hexadecimal digits 0 through 9 and A
through F is coded into 4-bit straight binary number.
• Used for binary inputs in digital computers,
microprocessors etc.
• BinaryàHexadecimal: partition in groups of 4 bits from
LSB & add necessary 0s at MSB.
E.g. (1101111)2 =(0110 1111)2 = (6F)16 ;
(C7)16 =(1100 0111)2

RVK-LDCO-1.7 91
 Different Codes
Decimal Binary Octal Hexadecimal BCD Excess-3 Gray
0 0000 0: 000 0: 0000 0000 0011 0000
1 0001 1: 001 1: 0001 0001 0100 0001
2 0010 2: 010 2: 0010 0010 0101 0011
3 0011 3: 011 3: 0011 0011 0110 0010
4 0100 4: 100 4: 0100 0100 0111 0110
5 0101 5: 101 5: 0101 0101 1000 0111
6 0110 6: 110 6: 0110 0110 1001 0101
7 0111 7: 111 7: 0111 0111 1010 0100
8 1000 8: 1000 1000 1011 1100
9 1001 9: 1001 1001 1100 1101
10 1010 A: 1010 1111
11 1011 B: 1011 1110
12 1100 C: 1100 1010
13 1101 D: 1101 1011
14 1110 E: 1110 1001
15 1111 F: 1111 1000
RVK-LDCO-1.7 92
 Codes Conversion Example
Q. Convert (28)10 into following codes:
1) Binary , 2) BCD, 3) Octal, 4) Hexadecimal, 5) Excess-3, 6) Gray

Ans. 1) Binary : Using repeated division by 2 the given decimal

number can be converted into binary code as : (28)10 = (11100)2.

2) BCD : Representing each digit of the given number by the

equivalent 4-bit BCD/8421 code the given decimal number can
be converted into BCD code as : (28)10 = (0010 1000)BCD .

3) Octal : Using repeated division by 8 the given decimal

number can be converted octal number and then into 3-bit octal
code as : (28)10 = (34)8 = 011 100.
RVK-LDCO-1.7 93
 Codes Conversion Example (cont..)
4) Hexadecimal : Using repeated division by 16 the given decimal
number can be converted hexadecimal number and then into
4-bit hexadecimal code as : (28)10 = (1C)8 = 0001 1100.

5) Excess-3 : Representing each digit of the given number by the

equivalent 4-bit Excess-3 code the given decimal number can
be converted into Excess-3 code as : (28)10 = (0101 1011)XS-3.

6) Gray : To represent a decimal number 28 total 5-bit Gray code

is needed. So constructing a 5-bit Gray code the given decimal
number can be converted into 5-bit Gray code as :
(28)10 = (11100)2
11100
Å01110 (Right shifted given number by one bit)
--------------
10010 Thus, (28)10 = (10010)Gray.

RVK-LDCO-1.7 94
 1.8 Logic Families

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Digital Design”, M Morris Mano, Prentice Hall, Third Edition.
3. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
 Digital Logic Families
• The circuit technology of digital ICs is referred to as a digital logic
family.
• It specifies a group of compatible ICs with the same logic levels and
supply voltages for performing various logic functions.
• Each logic family has its own basic electronic circuit upon which
more complex digital circuits and components are developed.
– E.g. a NAND, NOR, or inverter gate.
• Among them, the most important are TTL and CMOS.
– TTL (Transistor-Transistor Logic), made of bipolar transistors. It is called
transistor–transistor logic because the logic function and amplification is
performed by transistors.

– CMOS (Complementary Metal Oxide Semiconductor) made from MOSFET

transistors. In the modern world, CMOS is the dominant technology used to
construct digital circuit components, especially large-scale integrated circuits.
RVK-LDCO-1.8 96
 Digital Logic Families
(in chronological order)
• RTL: Resistor-Transistor Logic earliest,
now obsolete
• DTL: Diode-Transistor Logic
• TTL: Transistor-Transistor Logic widely used
• ECL: Emitter-coupled Logic high-speed operation
• MOS: Metal-Oxide Semiconductor compact
• CMOS: Complementary MOS
– Low power dissipation, currently the MOST DOMINANT
• BiCMOS: Bipolar CMOS
– CMOS and TTL for additional current/speed
• GaAs: Gallium-Arsenide very high-speed operation
 Characteristics of Digital ICs
• While working with digital IC's, one should be familiar, not only with
their logical operation, but also with their operational characteristics
as mentioned below:
1. Speed of operation,
2. Power dissipation,
3. Figure of merit,
4. Current and voltage parameters,
5. Fan-out,
6. Noise immunity,
7. Operating temperature range,
8. Power supply requirements, and
9. Flexibilities available

• The logic families differ from each other primarily in output current
capability, power dissipation, propagation delay time, and operating
power supply voltage.
RVK-LDCO-1.8 98
 1. Speed of Operation
• It is specified in terms of propagation delay.

• Ideally changes to the inputs of a gate would be reflected at the

output immediately, but in reality there is a slight delay.

• Propagation delay is the time that it takes a gate to switch logic

levels.

• Logic gates often have a different propagation delay switching from

LOW to HIGH than from HIGH to LOW, so two types of delay are
defined:
– tpLH = Propagation delay when the OUTPUT switches from LOW to HIGH
– tpHL = Propagation delay when the OUTPUT switches from HIGH to LOW
– The ‘LH’ (low to high) and the ‘HL’ (high to low) part refer to OUTPUT change,
NOT to input change

RVK-LDCO-1.8 99
 1. Speed of Operation (cont..)
• The transitions themselves are not instantaneous, so they are
defined as being at the 50% point of the voltage levels of i/p and
o/p waveforms.
• Propagation delay:

1
t p = (t pHL + t pLH )
2

• The propagation delay of a gate limits the frequency at which it can

be operated.
• The greater the propagation delay, the lower the maximum
frequency.
• Thus, a higher speed circuit is one that has a smaller propagation
delay.
RVK-LDCO-1.8 100
 2. Power Dissipation
• It is the amount power dissipated in an IC.

• It is specified in milliwatts (mW).

• Generally, as propagation delays decrease (increased speed), the

power consumption and related heat generation increase.

• A logic gate draws current from the DC Supply voltage source

– When the gate is in the HIGH output state, an amount of current designated
by ICCH is drawn.
– In the LOW output state, a different amount of current, ICCL is drawn.

• When a gate is pulsed, its output switches back and forth between
HIGH and LOW and the amount of supply current varies between
ICCH and ICCL.
RVK-LDCO-1.8 101
 2. Power Dissipation (cont..)
• The average power dissipation depends on the duty cycle and is
usually specified for a duty cycle of 50%
– When the duty cycle is 50%, the output is HIGH half the time and LOW the
other half
• The average supply current = ICC = (ICCH + ICCL)/2
• The Average Power Dissipation PD of a gate =
PD = VCCICC = VCC × (ICCH + ICCL)/2
• Power Dissipation in a TTL circuit is essentially constant over its
range of operating frequencies.
• Power Dissipation in CMOS, however, is frequency dependent. It is
extremely low under (dc) conditions and increases as the frequency
increases. RVK-LDCO-1.8 102
 2. Power Dissipation Example
Q. A certain gate draws 2 mA when its output is HIGH and 3.6 mA
when its output is LOW. What is its average power dissipation if
VCC is 5 V and the gate is operated on a 50% duty cycle?

Solution:
ICC = (ICCH + ICCL)/2 = (2 mA + 3.6 mA)/2 = 2.8 mA
PD = VCC × ICC = 5 V * 2.8 mA = 14 mW

RVK-LDCO-1.8 103
 3. Figure of Merit
• It is defined as the product of speed and power.
• It provides a basis for the comparison of logic circuits when
both propagation delay and power dissipation are important
considerations in the selection of the type of logic to be used in
a certain application.
• It is specified in pico joules (pJ).
– The speed is expressed in terms of propagation delay time specified in
nanoseconds (ns).
– The power is expressed in milliwatts (mW).
• The figure of merit (pJ) = propagation delay time(ns) x power (mW)
• The lower the speed-power product, the better is the logic circuit.
RVK-LDCO-1.8 104
 3. Figure of Merit Example
Q. A certain IC has an average propagation delay of 10 ns and its power
dissipation is of 5mW. What is its figure of merit?

Solution:
Given data:
• An average propagation delay of 10 ns
• An average power dissipation of 5 mW
Hence,
The figure of merit = speed x power
= (10 ns) x (5 mW)
= 50 pJ

RVK-LDCO-1.8 105
 4. Current and Voltage Parameters
• While the ideal voltage in TTL circuits are 0 V (logic 0) and +5 V
(logic 1), the typical, or observed, voltages are different in practice.
• It is important to know what tolerances must be observed in order
to guarantee the correct operation of a digital circuit.
• Four particular quantities are of interest in specifying the tolerance:
1. VIHmin: The minimum input voltage which will be accepted as a logic 1
2. VILmax: The maximum input voltage which will be accepted as a logic 0
3. VOHmin: The minimum output voltage representing a logic 1 state
4. VOLmax: The maximum output voltage representing a logic 0 state
• E.g.

For instance, if input to a 74LS04 NOT gate is at greater than or equal to 2.0 V, it
will be considered "high", and so the output should be "low", i.e. at a voltage
less than or equal to 0.5 V.
RVK-LDCO-1.8 106
 4. Current and Voltage Parameters (cont..)
• For each logic family, you should notice that the output voltage
limits are more strict than the input voltage limits
– This is to provide noise immunity to the devices
– Values outside the given range are not allowed – indeterminate region

• VOL(max) is lower than VIL(max)

to allow for noise and signal
deterioration.
• Similarly VOH(min) is higher than
VIH(min).

RVK-LDCO-1.8 107
 4. Current and Voltage Parameters (cont..)
• Similar to that of voltage limits, there are limits to the i/p and o/p
currents of each individual gate.
• Four particular quantities are of interest in specifying the tolerance:
1. IIHmin: The minimum input current which must be supplied by a driving
source to guarantee the input will be high (logic 1).
2. IILmin: The minimum input current which must be supplied by a driving
source to guarantee the input will be low (logic 0).
3. IOHmax: The maximum current which the gate can sink through its output still
keep the output (logic 1).
4. IOLmax: The maximum current which the gate can sink through its output and
still keep the output low (logic 0).

RVK-LDCO-1.8 108
 4. Current and Voltage Parameters (cont..)
• According to IEEE standards, currents are directed into devices. So,
– If a current in a specification is positive, it is entering the device
– If a current in a specification is negative, it is leaving the device
• Current sinking and sourcing rates are important while designing
circuits. These ratings determine the current capacity to drive
external devices.
• Current Sourcing
– It is the amount of current that
the driving gate produces as
outgoing current that flow into
the load gate
• Current Sinking
– It is the amount of incoming
current that the driving gate
receives from the loaded gate
• Most of the TTL can sink up to
16 mA and source 250 µA
RVK-LDCO-1.8 109
 5. Fan-Out
• Fan-In: Number of input signals to a gate NAND gate with
a Fan-in of 8
– Not an electrical property
– Function of the manufacturing process
• Fan-Out: Number of similar gates which can be driven by a gate
– Usually specified as standard loads within a single family
– e.g., An input to an inverter in the same family
• For TTL devices, the number of standard loads is limited by the
amount of input current each load requires as compared to the
current that the driving gate can deliver. It is generally considered to
be the smaller of the following two items:

RVK-LDCO-1.8 110
 5. Fan-Out (cont..)
• It may have to compute based on current drive requirements when
mixing families
– Although mixing families is not usually recommended
• An illustration of fan-out and the associated source and sink currents

RVK-LDCO-1.8 111
 5. Fan-Out Example 1
Q. How many 74ALS00 NAND gate inputs can be driven by a 74ALS00
NAND gate outputs ?
Solution:
Referring to data sheet of 74ALS00, the maximum values of
IOH = 0.4 mA, IOL = 8 mA, IIH = 20 µA, and IIL = 0.1 mA
Hence, Fan-out (high) = IOH(max) / IIH (max)
= 0.4 mA/20 µ A
= 400 µ A/20 µ A = 20
Fan-out (low) = IOL(max) / IIL(max) = 8 mA/0.1 mA = 80,
The overall fan-out = fan-out (high) or fan-out (low) whichever is
lower
Hence, overall fan-out = 20
Note: If the fan-out has a fractional part, it should be dropped. In
other words, you should always round down when calculating fan-
out.
RVK-LDCO-1.8 112
 5. Fan-Out Example 2
Q. A unit load for some particular logic family is as follows:
1 UL = 50 µA HIGH state
= 1 mA LOW state
Determine the fan-in and fan-out for a gate in this family that has
the following parameters:
IOH = 400 µA
IOL = 10mA
IIH = 150 µA
IIL = 4 mA
Solution: Fan-in = 150/50 = 3 UL or 4/1 = 4 UL
Therefore, fan-in = 3 or 3 UL
Fan-out = 400/50 = 8 UL or 10/1 = 10 UL
Therefore, fan-out = 8 or 8 UL

RVK-LDCO-1.8 113
 5. Fan-out for CMOS Devices
• It is worth noting that fan-out is much higher for CMOS
devices than for TTL devices
– IIL and IIH are extremely small for CMOS devices (< 1 µA)

• Calculating fan-out as we did for TTL devices might yield

a fan-out of 4000 for CMOS, compared to 10 for standard
TTL

• However, the input capacitance of CMOS gates affects

propagation delay, so increased fan-out results in
increased delay

RVK-LDCO-1.8 114
 6. Noise Immunity
• Noise is the unwanted voltage that might add to the output of
one gate.

• This may cause the voltage at the input to a logic circuit to drop
below VIH or rise above VIL into the indeterminate or “illegal”
region to produce undesired operation.

• In order not to be adversely affected by noise, a logic circuit

must have the ability to tolerate noise signals which is referred
to as the noise immunity.

RVK-LDCO-1.8 115
 6. Noise Immunity (cont..)
• A measure of a circuit’s noise immunity is called the noise margin,
which is expressed in volts.

• There are 2 values of noise margin specified for a given logic

circuit: the HIGH level noise margin (VNH) and the LOW level noise
margin (VNL).

• These parameters are defined by the following equations:

VNH = HIGH level noise margin = VOH(min) – VIH(min)
VNL = LOW level noise margin = VIL(max) – VOL(max)

RVK-LDCO-1.8 116
 6. Noise Immunity Example
Q. Given the following parameters, calculate the noise margin of
74LS series.

Solution:
High Level Noise Margin, VNH = VOH(min) - VIH(min)
= 2.7 V - 2.0 V = 0.7 V

Low Level Noise Margin, VNL = VIL(max) - VOL(max)

= 0.8 V - 0.4 V = 0.4 V
117
 7. Operating Temperature Range
• It is the range of temperature in which an IC works properly.
• The accepted temperature ranges are:
– 0 °C to +70 °C for consumer and industrial applications
– -55 °C to +125 °C for military applications

8. Power Supply Requirements

• The power supply voltage(s) and the amount of power supply
needed by an IC are vital characteristics essential to select the
proper power supply.

RVK-LDCO-1.8 118
 9. Flexibilities Available
• The breadth of the series: Type of various logic functions available
in the series
• Popularity of the series: The manufacturing cost of an IC is inversely
proportional to the number of ICs manufactured. When a large
number of ICs of one type are manufactured, the cost per function
will be very small and it will be easily available through multiple
sources.
• Wired-logic capability: Without any extra hardware the additional
logic functions can be performed by connecting outputs together
• Availability of complement outputs: It eliminates the need of
additional inverters.
• Type of output: Passive pull-up, active pull-up, open-collector/drain
and tristate.

RVK-LDCO-1.8 119
 Interfacing Logic Families

• To achieve optimum performance in a digital system, devices from

more than one logic family can be used, taking advantages of the
superior characteristics and function availability of each family for
different parts of the system
• When interfacing logic families, several considerations must be
made
– The output voltage level of one family must be high and low enough to
meet the input requirements of the receiving family
– Also, the output current capability of the driving gate (IOL, IOH) must be high
enough for the input draw of the receiving gate or gates (IIL, IIH)

RVK-LDCO-1.8 120
 Interfacing Logic Families (Cont.)
• For such an arrangement to
operate properly the following
conditions are required to be
satisfied:
1. VOH (Driving) ³ VIH (Load)
2. VOL (Driving) £ VIL (Load)
3. –IOH (Driving) ³ N × IIH (Load)
4. IOL (Driving) ³ –N × IIL (Load)

RVK-LDCO-1.8 121
 Interfacing Logic Families- Example
Q. Find the number of low power 74-series TTL
gates which can be driven from a 74 C-series
CMOS gate. Given the specification are as
follows:

RVK-LDCO-1.8 122
Interfacing Logic Families- Example (Cont..)
Solution: Since condition 1 & 2 are satisfied
VOH (Driving) ³ VIH (Load) ü
VOH (CMOS) = 4.5 V ³ VIH (TTL) = 2.0 V
VOL (Driving) £ VIL (Load) ü
VOL (CMOS) = 0.5 V £ VIL (TTL) = 0.7 V
–IOH (Driving) ³ N × IIH (Load)
–IOH (CMOS) = 100 µA ³ N × IIH (TTL) = N × 10 µA
Þ N = 10
IOL (Driving) ³ –N × IIL (Load)
IOL (CMOS) = 360 µA ³ –N × IIL (TTL) = N × 180 µA
Þ N = 2. !Therefore, a 74 C-series CMOS gate can drive only two
74-series low power TTL gates
123
 Data Sheets
• Different manufacturers prepare data sheets slightly differently,
but the same types of information are found in all of them. In
some form, most data sheets should contain the following
information:
– Description
• What the device is
– Features
• How this device differs from other similar ones, by this manufacturer or others
– Pin Configuration
• How electrical connections are made to the chip

RVK-LDCO-1.8 124
 Data Sheet (Cont.)
– Internal Schematic
• Functionally, how the inside appears (Physical appearance may be nothing like
it)
– Absolute Maximum Ratings
• Limits of conditions under which the device can survive. (It may only function
correctly over a much smaller range of conditions)
– Recommended Operating Conditions
• Limits of conditions under which the device can function correctly
– Electrical Characteristics
• Parameters for use when the chip is operating within normal limits
– Sample Circuits
• Examples of how the device might be hooked up in a circuit. Extremely useful

RVK-LDCO-1.8 125
 1.9 Transistor-Transistor Logic (TTL)
Family

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Digital Design”, M Morris Mano, Prentice Hall, Third Edition.
3. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
4. https://www.youtube.com/watch?v=7ukDKVHnac4
Transistor-Transistor Logic (TTL)
 The Bipolar Junction Transistor
• The bipolar junction transistor (BJT) is the active switching
element used in all TTL circuits.
• The 3 terminals for a BJT are the collector, base, and emitter.
• BJT has 2 junctions: the base-emitter and the base-collector.

The symbol for NPN BJT

RVK-LDCO-1.9 128
 The Ideal Switching Action of the BJT
• Consider a bipolar transistor in logic circuits
– Produces the two logic levels
– It is operated in either two states
1. Fully conducting state/saturated/turned on/short circuit
2. Fully non-conducting state/cut-off state/open switch

129
 Transistor-Transistor Logic (TTL)
• In TTL, logic gates are built only around transistors.
• TTL was developed in 1965.
• Through the years basic TTL has been improved to meet
performance requirements. There are many versions or families of
TTL. For example
– Standard TTL
– High Speed TTL (twice as fast, twice as much power)
– Low Power TTL (1/10 the speed, 1/10 the power of “standard" TTL)
– Schottky TTL etc. (for high-frequency uses; prevents transistor saturation )
• Typically, all TTL logic families have three configurations for outputs
– Totem pole output
– Open collector output
– Tristate output

RVK-LDCO-1.9 130
TTL Evolution

RVK-LDCO-1.9 131
TTL Evolution (cont..)

RVK-LDCO-1.9 132
 Part Numbers
• Part numbers for 7400 TTL series logic devices often use the
following naming convention

SN 74 ALS 245 A package type, quality

grade, etc. (varies
widely by manufacturer)

manufacturer temperature range logic subfamily device

SN = Texas Instruments 74 - commercial LS - Low Power Schottky hundreds of different
DM = Fairchild 54 – military (extended) AS - Advanced Schottky devices in each family
ALS - Advanced Low
Power Schottky

RVK-LDCO-1.9 133
 Characteristics of TTL Family

TTL Series name Prefix Fan- Power Speed Figure of

out Dissipation(mW) (ns) Merit (pJ)

Standard TTL 74/54 10 10 9 90

Low Speed TTL 74/54L 20 1 33 33
High Speed TTL 74/54H 10 22 6 132
Schottky 74/54S 10 19 3 57
Low-Power Schottky 74/54LS 20 2 9.5 19
Advanced Schottky 74/54AS 40 10 1.5 15
Advanced Low-Power 74/54ALS 20 1 4 4
Schottky
Fast 74/54F 20 4 3 12

RVK-LDCO-1.9 134
Voltage Specification of TTL IC Families

RVK-LDCO-1.9 135
Current Specification of TTL IC Families

RVK-LDCO-1.9 136
Operation of TTL NAND Gate
 Operation of TTL NAND gate
• Transistor Q1 is a three-emitter NPN transistor, which is equivalent
to three NPN transistors with their base and emitter terminals tied
together.
• The three emitters are the three inputs of the NAND gate.
– In TTL technology multiple emitter transistors are used for the input devices.

RVK-LDCO-1.9 138
Operation of TTL NAND gate (cont..)

RVK-LDCO-1.9 139
 Operation of TTL NAND gate (cont..)
• Condition1: At least one input is LOW:
– The E-B junction of Q1 corresponding to the LOW i/p is forward biased and it
starts conducting. Thus it makes the voltage at point B1, VB1 =0.2V + 0.7V=
0.9V. This voltage is insufficient to forward bias the B-C junction of Q1 and
to conduct Q2 and Q3. Hence Q2 and Q3 remain OFF. Therefore voltage at
point C3 =Y=V (1) =VCC.

• Condition2: All inputs are HIGH:

– All E-B junctions of Q1 corresponding to all HIGH i/p are reverse biased and
do not conduct. Since B1 is connected to Vcc (5V) through RB1, the B-C
junction of Q1 is forward biased. Q1 acts in active inverse mode, making IC1
flows in reverse direction i.e. to base B2 of transistor Q2 making it ON and
hence transistor Q3 also enters in the saturation mode (ON). Therefore
voltage at point C3 =Y=V (0) =0.2V.

RVK-LDCO-1.9 140
 Operation of TTL NAND gate (cont..)
• Condition3: The circuit is operating in Condition2 and suddenly one of
the i/p becomes LOW:
– The E-B junction of Q1 corresponding to the LOW i/p is forward biased making
voltage at point B1, VB1 =0.2V + 0.7V= 0.9V. Q2 and Q3will be turned OFF when the
stored base charge is removed. The B-C junction of Q1 is reverse biased making Q1
operate in normal active mode. This large collector current IC1 helps in the removal
stored base charge in transistors Q2 and Q3 and improves the speed of circuit.

• The speed of the circuit can be improved by decreasing RC3 which

decreases the time constant (RC3×C0) with which the o/p capacitance
charges from logic level 0 to 1.
• However, such reduction in RC3 increases IC3 causing more power
dissipation and would make it more difficult for Q3 to saturate( as it
needs increased IB3.)
• This limitation is overcome by Active Pull-up or Totem-Pole output
configuration.
RVK-LDCO-1.9 141
Totem-Pole Configuration
 Totem Pole Output
• Below is the circuit of a totem-pole NAND gate, which has got
three stages
– Input Stage
– Phase Splitter Stage
– Output Stage

Standard TTL NAND gate

RVK-LDCO-1.9 143
 Totem Pole Output (Cont.)
• Diodes D2 and D3 are protection diodes used to limit negative input
voltages. When there is large negative voltage at input, the diode
conducts and shorting it to the ground.

diode equivalent for Q1

• Q2 provides complementary voltages for the output transistors Q3

and Q4.
• The combination of Q3 and Q4 forms the output circuit often
referred to as a totem pole arrangement (Q4 is stacked on top of Q3)
– In such an arrangement, either Q3 or Q4 conducts at a time depending
upon the logic status of the inputs
• Diode D1 ensures that Q4 will turn off when Q2 is on (HIGH input)
• The output Y is taken from the top of Q3.
RVK-LDCO-1.9 144
 Totem Pole Output (Cont.)
1. A and B both low: both B-E junctions of Q1 are forward biased. Hence D1 and D2 will
conduct to force the voltage at point C to 0.2+0.7=0.9V. This voltage is insufficient to
forward bias B-E junction of Q2. Hence Q2 remains OFF. Therefore its collector voltage
rises to VCC. As Q3 is operating in emitter follower mode, output Y will be pulled up to high
voltage Y= 1.

2. Either A or B low: If any one input is connected to ground with other left open or
connected to VCC the corresponding diode (D1 or D2) will conduct. This will pull down
voltage at C to 0.2+0.7=0.9V. This voltage is insufficient to turn on Q2 so it remains OFF. So
collector voltage of Q2 will be equal to VCC. This voltage acts as base voltage for Q3. As Q3
acts as an emitter follower, output Y will be pulled up to high voltage Y= 1.

3. A and B both high: If both A and B are connected to then both diodes D1 and D2 will be
reverse biased and do not conduct. Therefore D3 is forward biased and base current is
supplied to transistor Q2 via R1 and D3. As Q2 conducts, the voltage at X will drop down and
Q3 will be OFF, whereas voltage at Z will increase to turn ON Q4. As Q4 goes into saturation,
the output voltage Y will be pulled down to low. Y = 0.

RVK-LDCO-1.9 145
 TTL Logic States Analysis

When a transistor
is ON it acts like a
closed switch and
when a transistor
is OFF it acts like
an open switch

• LOW output • HIGH output

RVK-LDCO-1.9 146
Advantages of Totem Pole Output Configuration

• The features of this arrangement are

– Low power consumption
– Fast switching
– Low output impedance in both the HIGH and LOW output
states.

RVK-LDCO-1.9 147
Open Collector Configuration
 Open Collector Outputs
• In the open-collector configuration the circuit elements associated with Q3
in the totem-pole circuit are missing and the collector of Q4 is left open-
circuited, hence the name open-collector .
• An open-collector output can present a logic LOW output.
• Since there is no internal path from the output Y to the supply voltage VCC
, the circuit cannot present a logic HIGH on its own.
• For the same, an external pull-up resistor, Rp is being used as shown
below.

RVK-LDCO-1.9 149
 Advantages of Open Collector Outputs
• Though open-collector gates require the additional pull-up resistor
in order to function properly, it has several advantages over totem-
pole configuration.

1. Wired-ANDing - Open-collector outputs can be tied directly

together which results in the logical ANDing of the outputs. Thus
the equivalent of an AND gate can be formed by simply connecting
the outputs.
Use this symbol to
Indicates open
collector output

RVK-LDCO-1.9 150
 Advantages of Open Collector Outputs (Cont.)
2. Increased current levels - Standard TTL gates with totem-pole
outputs can only provide a HIGH current output of 0.4 mA and a
LOW current of 1.6 mA. Many open-collector gates have
increased current ratings.
3. Different voltage levels - A wide variety of output HIGH voltages
can be achieved using open-collector gates. This is useful in
interfacing different logic families that have different voltage and
current level requirements

• The big disadvantage of open-collector gates is their slow

switching speed. This is because the value of pull-up resistor is in
kW, which results in a relatively long time-constants.

RVK-LDCO-1.9 151
 Comparison of Totem Pole and Open
Collector Output

• The major advantage of using a totem-pole connection is that it offers

low-output impedance in both the HIGH and LOW output states.

RVK-LDCO-1.9 152
Tristate Configuration
 Tristate (Three-State) Logic Outputs
• Tristate combines advantage of high-speed operation of the
totem-pole configuration and wired ANDing of the open
collector configuration.

• It is called the tristate TTL, as it allows three possible output

states: HIGH, LOW, and HIGH impedance (Hi-Z).

• Tri-state gates have additional circuitry via which the gate

outputs can be enabled or disabled.

• This is very useful in digital systems where devices communicate

via common wires called busses. Only one device can talk at a
time; the others are disabled.
RVK-LDCO-1.9 154
 Tristate (Three-State) Logic Outputs
• For the symbol and truth table, IN is the data IN OUT
input, and EN, the additional enable input to
control. EN
This requires two inputs:
input and enable
• For EN = 0, regardless of the value on IN
(denoted by X), the output value is Hi-Z.
• For EN = 1, the output value follows the input
value.

• Variations:
EN is to make output Hi-Z
– Data input, IN, can be inverted
or follow input
– Control input, EN, can be inverted by addition of
"bubbles" to signals

RVK-LDCO-1.9 155
 Hi-Impedance Outputs
• Tristate gate utilize the high-speed operation of
the totem-pole arrangement when input enabled.
• Permit outputs to be connected together.
• What is a Hi-Z value?
– Both transistor are turned off in the totem-pole
arrangement
– This means that, looking back into the circuit, the
output appears to be disconnected (open circuit)

An equivalent
circuit for the
tristate output in
the high-Z state
RVK-LDCO-1.9 156
 1.10 CMOS Family

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Digital Design”, M Morris Mano, Prentice Hall, Third Edition.
3. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
4. https://www.youtube.com/watch?v=stM8dgcY1CA
 CMOS Logic Family
• Complementary metal oxide semiconductor (CMOS) replaced TTL
devices in the 90’s due to advances in the design of MOS circuits
made in mid 80’s.
• Advantages:
– Operate with a wider range of voltages that any other logic
family.
– Has high noise immunity.
– Dissipates very low power at low frequencies.
– It requires an extremely low driving current.
– High fanout.
• Disadvantages:
– Power consumption increases with frequency.
– Susceptible to ESD - electro-static discharges.
RVK-LDCO-1.10 158
CMOS Logic
 CMOS Technology
• MOS stands for Metal Oxide Semiconductor
– Uses FETs
• MOS can be classified into three sub-families:
– PMOS (P-channel)
– NMOS (N-channel)
– CMOS (Complementary MOS, most common)

• The concept of CMOS was introduced in 1963 but become

common until the 1980’s.
• CMOS still dominates digital IC design today.
• CMOS circuits take advantage of the fact that both n-channel and
p-channel devices can be fabricated on the same substrate.
• CMOS circuits consist of both types of MOS devices interconnected
to form logic functions.
RVK-LDCO-1.10 160
 MOSFET Circuit Symbols
• The gate of a MOS transistor controls the flow of the current
between the drain and the source.
• The MOS transistor can be viewed as a simple ON/OFF switch.

RVK-LDCO-1.10
161
 Transistors in Series/Parallel
nMOS in Series nMOS in Parallel
a a a a
Path between Path between
X X:X points a and b points a and b
exists if both X Y X:X Y:Y exists if either
X and Y are 1 X or Y are 1
Y Y:Y à X•Y à X+Y
b b b b

pMOS in Series pMOS in Parallel

a a a a Path between
Path between
X X:X’ points a and b
points a and b X Y X:X Y:Y exists if either
exists if both
X or Y are 0
X and Y are 0
Y à X’+Y’
Y:Y’ à X’•Y’ b b
b b

RVK-LDCO-1.10 162
 CMOS Logic
• CMOS gates are built around the technology of the basic CMOS
inverter
– Transistors come in complementary pairs

• Two Transistors are enhancement mode MOSFETs

– N-Channel with its source grounded
– P-Channel with its source connected to +V

• Input: gates connected together Vdd

• Output: drains connected g
s
PMOS
d
in out
In Out
d
Symbol
NMOS
g
s

RVK-LDCO-1.10 163
 CMOS Sub-Families
• 40xx : Original CMOS family.
– Fairly slow, but it has a low power dissipation.
• 74HCxx : High speed CMOS.
– Better current sinking and sourcing than 40xx. It uses voltage supply
between 2 and 6 volts.
– Higher voltage →higher speed.
– Lower voltage →lower power consumption.
• 74HCTxx : High speed CMOS, TTL compatible.
– Better current sinking and sourcing than 40xx. It uses voltage supply of 5V.
Compatible with TTL family.
• 74ACxx : Advanced CMOS.
– Very fast. It can source and sink high currents. Not TTL compatible.
• 74ACTxx : Advanced CMOS, TTL compatible.
– Same as 74ACxx, but it is compatible with TTL family.
RVK-LDCO-1.10 164
CMOS Evolution

RVK-LDCO-1.10 165
Operation of CMOS NAND Gate
 Operation of CMOS NAND gate
• Figure shows a 2-input CMOS
NAND gate.

A B pMOS1 pMOS2 nMOS1 nMOS2 Y

0 0 ON ON OFF OFF 1
0 1 ON OFF OFF ON 1
1 0 OFF ON ON OFF 1
1 1 OFF OFF ON ON 0

RVK-LDCO-1.10 167
 Operation of CMOS NAND gate (Cont..)
• Case-1 : A – Low & B – Low
– As A and B both are low, both the pMOS will be ON and both the nMOS will
be OFF. So the output Y will get two paths through two ON pMOS to get
connected with Vdd. The output will be charged to the Vdd level. The output
line will not get any path to the GND as both the nMOS are OFF. So, there is
no path through which the output line can discharge. The output line will
maintain the voltage level at Vdd; so, Y=1.

• Case-2 : A – Low & B – High

– A – Low: pMOS1 – ON; nMOS1 – OFF
– B – High: pMOS2 – OFF; nMOS2 – ON
– pMOS1 and pMOS2 are in parallel. Though pMOS2 is OFF, still the output line
will get a path through pMOS1 to get connected with Vdd. nMOS1 and nMOS2
are in series. As nMOS1 is OFF, so Y will not be able to find a path to GND to
get discharged. This in turn results the Y to be maintained at the level of Vdd;
so, Y=1.
RVK-LDCO-1.10 168
 Operation of CMOS NAND gate (Cont..)
• Case-3 : A – High & B – Low
– VA – High: pMOS1 – OFF; nMOS1 – ON
– VB – Low: pMOS2 – ON; nMOS2 – OFF
– The explanation is similar as case-2. Y=1 .

• Case-4 : VA – High & VB – High

– VA – High: pMOS1 – OFF; nMOS1 – ON
– VB – High: pMOS2 – OFF; nMOS2 – ON
– In this case, both the pMOS are OFF. So, Y will not find any path to get
connected with Vdd. As both the nMOS are ON, the series connected nMOS
will create a path from Y to GND. Since, the path to ground is established,
Y will be discharged; so, Y=0.
• In all the 4 cases we have observed that Y is following the
exact pattern as in the truth table for the corresponding
input combination. RVK-LDCO-1.10 169
 Pros and Cons of MOS Digital ICs
• The Pros:
– Simple
– Inexpensive to fabricate
– Higher integration
– Consumes little power

• The Cons:
– Static-electricity damage
– Slower than TTL

RVK-LDCO-1.10 170
TTL Vs CMOS
 TTL Vs CMOS
• TTL circuits utilize BJTs while CMOS circuits utilize FETs.
• CMOS allows a much higher density of logic functions in a single
chip compared to TTL.
• TTL circuits consumes more power compared to CMOS circuits at
rest.
• CMOS chips are a lot more susceptible to static discharge compared
to TTL chips.
• There are CMOS chips that have TTL logic and are meant as
replacements for TTL chips.
• TTL is good for
– Where you have a good power supply
– Where you want high speed
• CMOS 4000 is good for
– Battery equipment
RVK-LDCO-1.10 172
– Where speed is not so important
A Comparison of Some Common Logic
Families

RVK-LDCO-1.10 173
 1.11 Logic Minimization

Sources:
1. “Modern Digital Electronics”, R.P. Jain, Tata McGraw-Hill , Third Edition.
2. “Digital Design”, M. Morris Mano, Prentice Hall, Third Edition
3. “Fundamentals of Digital Circuits”, A. Anand Kumar, PHI, Second Edition.
 Logic Function Simplification
• Why to simplify?
– Simpler expression uses less logic gates
– Thus: cheaper, less power, faster (sometimes)
• Simplification techniques:
– Algebraic Simplification
• Simplify Boolean functions by means of basic identities and theorems
• Requires skill and it lacks specific rules to predict each succeeding step in the
minimization process
– Karnaugh Maps
• A graphical technique for simplifying an expression
• A more orderly process with well-defined steps compared with the trial-and-error
process sometimes used in algebraic simplification
• Always able to produce a minimum expression
• Limited to 5 or 6 variables
– Quine-McCluskey
• Suitable for automation
• Can handle many variables (but computationally intensive)
– Variable Entered Mapping (VEM) Technique
• Used to increase the effective size of K-map.
• It facilitates a smaller map to handle large number of variables.
RVK-LDCO-1.11 175
SOP and POS Forms
 Representation of Logical Functions
• Logical functions are represented by logical variables with binary
values 0 or 1
• Standard representation of logical functions can be of two forms:
– Sum-of-Products (SOP) Form
• A Boolean function expressed as the ORing of ANDed variables
• E.g. 1) AB + AC’ + BC, 2) XY’Z + X’Y’Z + XYZ, 3) XY’ + X’Y’Z + XZ
– Product-of-Sums (POS) Form
• A Boolean function expressed as the ANDing of ORed variables
• E.g. 1) (A+B) (A+C’) (B+C), 2) (X+Y’+Z) (X’ +Y’+Z) (X+Y+Z),
3) (X+Y’) (X’ +Y’+Z) (X+Z)
– Note: Logical functions can be represented in any form but , these 2 forms
are conventionally suitable for circuit designing.

• If each term in SOP or POS forms contains all the literals then these
are known as standard or canonical SOP or POS respectively.
– E.g. Standard SOP: XY’Z + X’Y’Z + XYZ
RVK-LDCO-1.11 177
Standard POS: (X+Y’+Z) (X’ +Y’+Z) (X+Y+Z)
 Minterm
• Each individual term in a standard SOP form is known as minterm.
• A minterm is a special product of literals, in which each input
variable appears exactly once.

• A function with n variables has 2n minterms (since each variable can

appear complemented or not)
– E.g. A three-variable function, such as f(x,y,z), has 23 = 8 minterms namely:
1) x’y’z’ 2) x’y’z 3) x’yz’ 4) x’yz 5) xy’z’ 6) xy’z 7) xyz’ 8) xyz

• A Boolean function expressed as the disjunction (ORing) of its

minterms is said to be in the Disjunctive Normal Form (DNF)
– E.g. f = (x.y’.z)+(x’.y.z)+(x.y.z)+( x’.y’.z’)
RVK-LDCO-1.11 178
 Maxterm
• Each individual term in a standard POS form is known as maxterm.
• A maxterm is a special sum of literals, in which each input variable
appears exactly once.

• A function with n variables has 2n maxterms (since each variable can

appear complemented or not)
– E.g. A three-variable function, such as f(x,y,z), has 23 = 8 maxterms namely: 1)
x+y+z 2) x+y+z’ 3) x+y’+z 4) x+y’+z’ 5) x’+y+z 6) x’+y+z’ 7) x’+y’+z 8) x’+y’+z’

• A Boolean function expressed as the conjunction (ANDing) of its

maxterms is said to be in the Conjunctive Normal Form (CNF).
– E.g. f = (x+y’+z).(x’+y+z).(x+y+z).( x’+y’+z’)
RVK-LDCO-1.11 179
 Minterm & Maxterm
• Each minterm/ maxterm is true for exactly one combination of inputs.

E.g. Minterm &

Maxterm for
4 variables

[ Minterm: mi
0-> Complemented: e.g. A’
1-> Uncomplemented: e.g. A

Maxterm: Mi
0-> Uncomplemented: e.g. A
1-> Complemented: e.g. A’

i is decimal equivalent of the

natural binary number
corresponding to the minterm
or the maxterm.]
RVK-LDCO-1.11 180
 Sum of Minterms Form
• Every function can be written as a sum of minterms, which is a
special kind of sum of products form i.e. a standard SOP.
• The sum of minterms form for any function is unique.
• If you have a truth table for a function, you can write a sum of
minterms expression just by picking out the rows of the table
where the function output is 1.

• f = x’y’z’ + x’y’z + x’yz’ + x’yz + xyz’

= m0 + m1 + m2 + m3 + m6
= Sm(0,1,2,3,6)
• f’ = xy’z’ + xy’z + xyz
= m4 + m5 + m7
= Sm(4,5,7)
• f’ contains all the minterms not in f.
RVK-LDCO-1.11 181
 Product of Maxterms Form
• Every function can be written as a product of maxterms, which is a
special kind of product of sum form i.e. a standard POS.
• The product of maxterms form for any function is unique.
• If you have a truth table for a function, you can write a product of
maxterms expression just by picking out the rows of the table
where the function output is 0.

• f = (x’+y+z) (x’+y+z’) (x’+y’+z’)

= M4 + M5 + M7
= ∏M(4,5,7)

• f’ = (x+y+z)( x+y+z’) x+y’+z) (x+y’+z’)(x’+y’+z)

= M0 + M1 + M2 + M3 + M6
= ∏M (0,1,2,3,6)
• f’ contains all the maxterms not in f.
RVK-LDCO-1.11 182
K-Maps
 Description of K-map and Terminology
• A Karnaugh map(K-map) is a matrix consisting of rows and columns
that represent the output values of a Boolean function.
– Each possible state of the input variables corresponds uniquely to one of
the cells
– The corresponding output state is written in each cell

• It is a powerful visual tool to simplify and manipulate logical

expressions having up to 5-6 variables

• K-map can be of two forms

– Sum-of-Product (SOP) Form
– Product-of-Sum (POS) Form

• Objectives:
– The fewest possible product terms and literals in case of SOP on K-map
– The fewest possible sum terms and literals in case of POS on K-map
RVK-LDCO-1.11 184
 Re-arranging the Truth Table
• A 2-variable function has 22 = 4 possible minterms. We can re-
arrange these minterms into a K-map.

• Now we can easily see which minterms contain common literals

– Minterms on the left and right columns contain y’ and y respectively
– Minterms in the top and bottom rows contain x’ and x respectively

RVK-LDCO-1.11 185
 Re-arranging the Truth Table (Cont.)
• A 3-variable function has 23 = 8 possible minterms. We can re-
arrange these minterms into a K-map.

• E.g. For a 3-variable expression with inputs x, y, z, the arrangement

of minterms is more tricky:

YZ
00 01 11 10
0 m0 m1 m3 m2
X
1 m4 m5 m7 m6

RVK-LDCO-1.11 186
 3-Variables K-Maps
• There are 8 minterms for 3 variables (a, b, c). Therefore, there
are 8 cells in a 3 variable K-map
b b
bc bc
a 00 01 11 10 a 00 01 11 10
0 a'b'c' a'b'c a'bc a'bc' 0 m0 m1 m3 m2
OR
a ab'c' ab'c abc abc' a m4 m5 m7 m6
1 1

c c

Note Gray code sequence

• Above arrangement ensures that minterms of adjacent cells

differ by just one variable both horizontally and vertically (so
that the unifying theorem may apply: a + a' = 1)

RVK-LDCO-1.11 187
 3-Variables K-Maps (Cont.)
• There is wrap-around in the K-map:
– a'b'c' (m0) is adjacent to a'bc' (m2)
– ab'c' (m4) is adjacent to abc' (m6)

bc
a 00 01 11 10
0 m0 m1 m3 m2

1 m4 m5 m7 m6

• Each cell in a 3-variable K-map has 3 adjacent neighbours. In

general, each cell in an n-variable K-map has n adjacent
neighbours

RVK-LDCO-1.11 188
 3-Variables K-Maps (Cont.)
• It is possible to arrange the 8 minterms for 3 variables (a, b, c) in
this way!
a
a
a a
bc 0 1 bc 0 1
a'b'c' ab'c' m0 m4
00 00

01 a'b'c ab'c 01 m1 m5
c OR c
11 m3 m7
11 a'bc abc
b b
10 m2 m6
10 a'bc' abc'

RVK-LDCO-1.11 189
 4-Variables K-maps
• There are 16 cells in a 4-variable (e.g. w, x, y, z) K-map:

y
yz
wx 00 01 11 10
00 m0 m1 m3 m2

01 m4 m5 m7 m6
x
m12 m13 m15 m14
11
w
m8 m9 m11 m10
10
z

RVK-LDCO-1.11 190
 4-Variables K-maps (Cont.)
• There are 2 wrap-arounds: a horizontal wrap-around and a
vertical wrap-around

• Every cell thus has 4 neighbours. For example, the cell

corresponding to minterm m0 has neighbours m1, m2, m4
and m8
yz y
wx
m0 m1 m3 m2

m4 m5 m7 m6
x
m12 m13 m15 m14
w
m8 m9 m11 m10

RVK-LDCO-1.11 191
Logic Minimization Using K-Maps
 Adjacencies

• Adjacencies on three and four-variable maps

RVK-LDCO-1.11 193
 Why the Funny Ordering?
• With this ordering, any group of 2, 4 or 8 adjacent squares on the
map contains common variables that can be factored out
x’y’z + x’yz
= x’z(y’ + y)
= x’z • 1
= x’z

• "Adjacency" includes wrapping around the left and right sides:

x’y’z’ + xy’z’ + x’yz’ + xyz’
= z’(x’y’ + xy’ + x’y + xy)
= z’(y’(x’ + x) + y(x’ + x))
= z’(y’+y)
= z’

• We’ll use this property of adjacent squares to do our simplifications.

RVK-LDCO-1.11 194
 Simplification of SOP using K-map
• In a K-map, each cell containing a '1' corresponds to a minterm of
a given function F
• Based on the Unifying Theorem:
A + A = 1 or A+A’ =1
• Pairs of adjacent 1s
– Remember that adjacent squares differ by only one variable
– Hence the combination of 2 adjacent squares has the form P( A + A)
– This can be simplified (from before) to just P

• Each group of adjacent cells containing ‘1’ then corresponds to a

simpler product term of F
– Grouping 2 adjacent squares eliminates 1 variable,
– Grouping 4 squares eliminates 2 variables,
– Grouping 8 squares eliminates 3 variables, and so on.

• In general, grouping 2n squares eliminates n variables

RVK-LDCO-1.11 195
 Remarks about Groups
• Groups of minterms/maxterms must be:
1. 0 & 1 are never grouped,(1-1 are grouped in case of minterms and 0-0
are grouped in case of maxterms )
2. Rectangular (Horizontal/Vertical) and
3. Have size in powers of 2’s (i.e. 1, 2, 4, 8, 16 etc.)
4. Each group should be as large as possible.
Otherwise they are invalid groups. Some examples of invalid
groups are:

1 1 1 1

1 1 1 1

1 1 1

1 1 1 1 1

RVK-LDCO-1.11 196
 Prime Implicants & Essential Prime
Implicants
• To find the simplest (minimal) SOP expression from a K-map, you
need to obtain:
– Minimum number of literals per product term; and
– Minimum number of product terms.

• Achieved through K-map using

– Bigger groupings of minterms (prime implicants) where possible; and
– No redundant groupings (look for essential prime implicants)

• Implicant: a product term that could be used to cover minterms

of the function.

RVK-LDCO-1.11 197
 PIs and EPIs (cont..)
• Prime Implicant (PI): a product term obtained by combining the
maximum possible number of minterms from adjacent squares in
the map. (That is, it is the biggest grouping possible.)
• Always look for prime implicants in a K-map.
1 1 1 1 1 1
1 1 1 1 1 1
O P

• No redundant groups: 1 1 1 1

1 1 1 1

1 1 O 1 1
P
1 1 1 1

Essential prime implicants

RVK-LDCO-1.11 198
 PIs and EPIs (cont..)
• Essential prime implicant (EPI): a prime implicant that includes at
least one minterm that is not covered by any other prime implicant.

1 1 1 1

P
1 1 1 1

1 1
O 1 1

1 1 1 1

Essential prime implicants

RVK-LDCO-1.11 199
 PIs & EPIs (cont..)
1. PIs-1,2,3,4,5,6 : CD+BC’D+A’BD+A’C+AD+A’BC’D
C’D’ C’D CD CD’
2. PIs-1,2,3,4,5: CD+BC’D+A’BD+A’C+AD
3. PIs- 1,4,5,6 : CD+A’C+AD+A’BC’D A’B’ 1 1

4. PIs-1,2,4,5 : CD+BC’D+A’C+AD A’B 1 1 1

5. PIs-1,3,4,5 : CD+A’BD+A’C+AD
AB 1 1
6. PIs-1,4,5,7: CD+A’C+AD+BD
AB’ 1 1
7. PIs-4,5,7: A’C+AD+BD
EPIS-4,5,7

RVK-LDCO-1.11 200
 Grouping
• It is a process of grouping the squares which contain 1s.
• The output expression can be simplified by properly combining
those squares in the K-map that contain 1s.
C changes across outer
f = A’B’C’D’+ A’BC’D’+ ABC’D+ AB’C’D boundary

+ABCD + AB’CD + A’B’CD’+ A’BCD’ CD

00 01 11 10
AB
f = A’B’C’D’+ A’BC’D’ + A’B’CD’+ A’BCD’ 00 1 1
+ ABC’D+ AB’C’D + ABCD + AB’CD B changes
01 1 1
f = A’C’D’(B’+ B) + A’CD’(B’+ B)
+ AC’D (B+ B’) + ACD(B+ B’) 11 1 1
B changes

f = A’ C’D’ + A’CD’ + AC’D + ACD 10 1 1

f = A’D’ (C’+ C) + AD (C’+C) C changes

f = A’D’ + AD -- Simplified form. RVK-LDCO-1.11 X 201

Examples: Grouping of Two Adjacent 1s
Q. Simplify the Boolean function F (a, b, c) = (3, 4, 6, 7)
Solution:
• There are 4 squares marked with 1s, one for each minterm of the
given function F (a, b, c) = (3, 4, 6, 7)
F = a’bc + ab’c’+ abc’+ abc
a changes but bc is
constant à bc

• So simplified form of a given

boolean function F(a,b,c) is:
ac’ is constant but b F = ac’ + bc
changes à ac’
RVK-LDCO-1.11 202
202
Examples: Grouping of Two Adjacent 1s
• Grouping (or
looping) of a
pair of adjacent
1s in a K-map
eliminates the
variable that
appears in
complemented
and
uncomplement
ed form

RVK-LDCO-1.11 203
203
Examples :Grouping of Four Adjacent 1s (Quads)

• Grouping of a
quad of adjacent
1s eliminates the
two variables that
appears in both
complemented
and
uncomplemented
form

RVK-LDCO-1.11 204
 Examples: Grouping of Eight 1s (Octets)

• Looping an octet
of adjacent 1s
eliminates the
three variables
that appears in
both
complemented
and
uncomplemented
form

RVK-LDCO-1.11 205
 Don’t-Care Conditions
x y z f(x,y,z)
• You don’t always need all 2n input combinations
0 0 0 0
in an n-variable function 0 0 1 1
– If you can guarantee that certain input combinations 0 1 0 X
never occur. For example, when dealing with Binary- 0 1 1 0
coded decimal (BCD), the inputs for 1010 - 1111 (10-15) 1 0 0 0
will never occur 1 0 1 1
– When a certain input(s) will occur, but we don’t care 1 1 0 X
1 1 1 1
what the output will be in response to them as we are
not going to use them in our circuit

• We mark don’t-care outputs in truth tables and K-maps with Xs

• Don’t-care conditions can be used to help simplify Boolean
expression further in K-maps
• They could be chosen to be either '1' or '0', depending on which
value will help the minimization
RVK-LDCO-1.11 206
 Don’t Care Condition Simplification
• Don't-care conditions should be changed to either 0 or 1 to
produce K-map looping that yields the simplest expression

RVK-LDCO-1.11 207
Example 1:Don’t Care Condition Simplification
• For comparison: CD
C

00 01 11 10
– WITHOUT Don’t-cares: AB
00
P = A'B'C'D’ + A'B'CD + A'BC'D 1 1
01
+ A'BCD' + AB'C'D 1 1
B
11
A
• Note: Cells with ‘0’ are not shown for 10 1

clarity D

– WITH Don’t-cares: CD
C

P = A'B'C'D' + B'CD + BC'D AB 00 01 11 10

00
+ BCD' + AD 1 1
01
1 1
B
11 X X X X
A
10 1 X X

D
RVK-LDCO-1.11 208
 Example 2:Don’t Care Condition Simplification
Q. Simplify the Boolean function represented by the following truth
table. Note don’t care conditions are marked as X’s in the truth table

Solution:
• Firstly, we can extract the minterms and write the
standard SOP form of the function:
F(W,X,Y,Z) = S m(1,3,7,11,15)

• The don’t care conditions are expressed as:

d(W,X,Y,Z) = S d(0,2,5)

• Thus the entire function may be expressed as:

F(W,X,Y,Z) = S m(1,3,7,11,15) + S d(0,2,5)
RVK-LDCO-1.11 209
 Example 2 (Cont.)
1. Place 1’s in the squares for minterms (1,3,7,11,15)
2. Place X’s in the squares for don’t cares (0,2,5)
3. Place 0’s in the remaining squares (4,6,8,9,10,12,13,14)
4. Group the adjacent 1’s (including any applicable X’s) into the
largest 2n groupings. One minimum solution uses the X in the
second row to yield the term W Z . The other grouping of 4 yields
the term YZ
WZ

YZ Thus, the solution is:

F = W Z + YZ

RVK-LDCO-1.11 210
K-Map Simplification of SOP
Expressions
 Complete Simplification Process
1. Construct the K-map and place 1s and 0s in the squares according to
the truth table.
2. Grouping the isolated 1s which are not adjacent to any other 1s
(single groups).
3. Grouping any pair which contains a 1 adjacent to only one other 1
(double groups).
4. Group any group of eight even if it contains one or more 1s that
have already been grouped.
5. Grouping any group of four that contains one or more 1s that have
not already been grouped, making sure to use the minimum number
of groups.
6. Group any pairs necessary to include any 1s that have not yet been
grouped, making sure to use the minimum number of groups.
7. Form the OR sum of all the terms generated by each group.
RVK-LDCO-1.11 212
 Example 1
Q. Determine the product terms for the Karnaugh map in Figure
below and write the resulting minimum SOP expression for X

Solution:
[Note: For convenience and simplicity cells in the K-map are numbered from 1 to 16
in row-major convention. These numbers do not represent minterms.]

• Step 1: Assume all minterms are filled in the K-map as shown above. 0s are placed
in the other squares
• Step 2: Square 4 is the only square containing a 1 that is not adjacent to any other
1. It is looped and is referred to as loop 4
RVK-LDCO-1.11 213
 Example 1 (Cont.)
• Step 3: Square 15 is adjacent only to square 11. This pair is looped and
referred to as loop 11, 15
• Step 4: There are no octets (group of 8)
• Step 5: Square 6, 7, 10, and 11 form a quad (group of 4). This quad is
looped (loop 6, 7, 10, 11). Note that square 11 is used again, even though
it was part of loop 11, 15
• Step 6: All 1s have already been looped
• Step 7: Each loop generates a term in the expression for X. Loop 4 is
simply ABC D . Loop 11, 15 is ACD (the variable B variable is eliminated).
Loop 6, 7, 10, 11 is BD (A and C are eliminated)

RVK-LDCO-1.11 214
 Example 2
Q. Determine the product terms for the Karnaugh map in Figure below
and write the resulting minimum SOP expression for X

Solution:
[Note: For convenience and simplicity cells in the K-map are numbered from 1 to 16
in row-major convention. These numbers do not represent minterms.]
• Step 1: Assume all minterms are filled in the K-map as shown above. 0s are placed
in the other squares
• Step 2: There are no isolated 1s
• Step 3: The 1 in square 3 is adjacent only to the 1 in square 7. Looping this pair (3,
7) produces the term ACD
RVK-LDCO-1.11 215
 Example 2 (Cont.)
• Step 4: There are no octets (group of 8)
• Step 5: There are two quads (group of 4). Square 5, 6, 7, and 8 from one
quad. Looping this quad produces the term AB . The second quad is made
up of squares 5, 6, 9, and 10. This quad is looped because it contains two
squares that have not been loop previously. Looping this quad produces BC
• Step 6: All 1s have already been looped
• Step 7: The terms generated by the three loops are ORed together to
obtain the expression for X

RVK-LDCO-1.11 216
 Example 3
Q. Determine the product terms for the Karnaugh map in Figure
below and write the resulting minimum SOP expression for X

Solution:

[Note: For convenience and simplicity cells in the K-map are numbered from 1 to 16
in row-major convention. These numbers do not represent minterms.]
• Step 1: Assume all minterms are filled in the K-map as shown above. 0s are
placed in the other squares
• Step 2: There are no isolated 1s
RVK-LDCO-1.11 217
 Example 3(Cont.)
• Step 3:The 1 in square 2 is adjacent only to the 1 in square 6. This
pair is looped to produce AC D . Similarly, square 9 is adjacent only
to square 10. Looping this pair produces ABC . Likewise, loop 7, 8
and loop 11, 15 produce the terms ABC and ACD , respectively
• Step 4: There are no octets (group of 8)
• Step 5: There is one quad (group of 4) formed by squares 6, 7, 10
and 11. This quad, however is not looped because all the 1s in the
quad have been included in other loops
• Step 6: All 1s have already been looped
• Step 7: The expression for X is shown in the figure

RVK-LDCO-1.11 218
 The Same K-Map with Two Equally Good
Solutions
• Consider the K map in Figure

• For this map, there are two possible groupings, which require only
four looped pairs. Figure (a) shows one solution and Figure (b)
shows the other. Both expressions are of the same complexity, and
so neither is better than the other.
RVK-LDCO-1.11 219
Conversion of SOP/POS into a
Standard(Canonical) SOP/POS
 Converting to Minterms Form
• The K-map of a function is easily drawn when the
function is given in standard sum-of-products, or
sum-of-minterms form
• What if the function is not in sum-of-minterms?
– Convert it to sum-of-products (SOP) form
– Expand the SOP expression into sum-of-minterms
expression, or fill in the K-map directly based on the
SOP expression

RVK-LDCO-1.11 221
 Example
Q. (a) Use a K-map to simplify y = ABC D + C D + ABC + D
(b) Implement the minimized function by using only-NAND gates

Solution:
(a) Logic Simplification using K-map:
• To simplify a given SOP using K-map, we need a standard SOP form.

• Step 1: Multiply out the first term to get y = ABC D + C D + ABC + D

• Step 2: For the ABC D term, simply put a 1 in the ABC D square of the K
map. For the CD term, place a 1 in all squares with CD in their labels, that
is, ABCD, ABCD, ABCD, ABCD. For the ABC term, place a 1 in all squares that
have an ABC in their labels, that is, ABC D, ABCD. For the D term, place a 1 in
all squares that have a D in their labels, that is all squares in the leftmost
and rightmost columns.

RVK-LDCO-1.11 222
 Example (cont..)
• Alternative way: Here, we have 4 product terms and 4 literals.
y = ABC D + C D + ABC + D

1st term: ABC D 3rd term: ABC 4th term: D

mi A B C D mi A B C D mi A B C D
m0 0 0 0 0 1 0 1 x x x x 0
m10 1 0 1 0 m0 0 0 0 0
2nd term: C D m11 1 0 1 1 m2 0 0 1 0
mi A B C D m4 0 1 0 0
x x 0 1 m6 0 1 1 0
m1 0 0 0 1 m8 1 0 0 0
m5 0 1 0 1 y = ∑m ( 0,1,2,,4,5,6,8, m10 1 0 1 0
m9 1 0 0 1 9,10,11,12,13,14) m12 1 1 0 0
m13 1 1 0 1 m14 1 1 1 0

RVK-LDCO-1.11 223
 Example (Cont.)
• The K map is now filled and can looped for simplification:

• For proper looping produces y = AB + C + D

RVK-LDCO-1.11 224
 Example (Cont.)
(b) Implementation of the minimized function by using only-NAND
gates:
y = AB + C + D

DeMorgan

• Thus, we have the circuit using NAND gates as shown below

RVK-LDCO-1.11 225
K-Map Simplification of POS
Expressions
 K-Map using Product-of-Sum (POS) Form
• Recall an expression in standard POS form would look like
• The output values placed in each cell are derived from the
"maxterm" of a Boolean function ( A + B + C )( A + B + C )( A + B + C )
• A maxterm is a sum term that contains all of the function’s
variables exactly once, either complemented or not
complemented
• Note: If variable input is 0, then it is
written as it is else the complement of
that variable is written
• Thus for the above example: the
binary values for each term are:

A+ B +C 000
A+ B +C 010
A+ B +C 110
RVK-LDCO-1.11 227
 Product of Sums
• Finding a minimum product of sums expression requires
no new theory. The following approach is the simplest:
1. Map the complement of the function (replace all 0’s by 1’s, all
1’s by 0’s and leave X’s (don’t care) unchanged)
• Any “don’t care” conditions may be assumed to be zero where
convenient
• If there is already a map for the function, instead of the replacement of
1’s and 0’s, we could simply look for rectangles of 0’s on the map
2. Find the minimum sum of products expression for the
complement of the function
3. Use DeMorgan’s theorem to complement that expression,
producing a product of sums expression

RVK-LDCO-1.11 228
 Example
Q. (a) Use K-Map to find a minimum product of sums expression for the
given function F(A,B,C,D) = Sm(0,1,2,3,5,7,8,9,10,11).
(b) Implement the minimized function by using only-NOR gates

Solutions: F(A,B,C,D) = Sm(0,1,2,3,5,7,8,9,10,11) =∏ M(4,6,12,13,14,15)

(a) We first draw the K-map, then group the 0s together and we get:

• This gives POS of F as:

RVK-LDCO-1.11 229
 Example (Cont.)
(b) As F = (A + B)(B + D)

= (A + B)(B + D)

= (A + B) + (B + D) DeMorgan

• Thus, we have the circuit using NOR gates as shown below

A
A A+ B

B
B F
B+D
D

RVK-LDCO-1.11 230
K-Map Simplification of
Checkerboard Pattern
 Checkerboard Pattern in K-Map
• When we rearrange the Exclusive-OR truth table to a K-Map as
shown below, we would observe K-Map displays a checkerboard
pattern (every other square) of 0s and 1s and we cannot form any
groups on the map.
• On a K-Map diagonally adjacent terms can be simplified by using
either XOR or XNOR functions as functional elements.

Truth table of K-Map for 2 variables K-Map for 3 variables

EX-OR gate
K-Map for 4 variables

RVK-LDCO-1.11 232
 Odd and Even Functions
• For more than 2 inputs, XOR is called an odd function
– It is equal to 1 if the input variables have an odd number of 1’s
• Similarly, for more than 2 inputs, XNOR is called an even function
– It is equal to 1 if the input variables have an even number of 1’s
• As shown in the K-map, A ⊕ B ⊕ C = 1, if and only if the number of
1’s in the input combination is odd.

• As Since XOR gates are only designed

with 2 inputs, the 3-input XOR
function is implemented by means of
two 2-input XOR gates, as shown in
figure

RVK-LDCO-1.11 233
Odd and Even Function Examples

RVK-LDCO-1.11 234
Thank You!

RVK-LDCO-Unit-1 235