Nptel Digital Gsaha

Digital Electronic Circuits
Goutam Saha
Indian Institute of Technology Kharagpur
Introduction
Lecture 01
Concepts Covered:
 Why ‘Digital’ and what is ‘Digital’?
 Manipulation of digital signal
 Switching and logic operation
 Diode as a switch
Why Digital?
• Popular terms of current times:
- Digital Clock, Digital Camera, Digital Money, Digital Media, …
• Prefix ‘Digital’ associates a term with digital technology.
• Digital technology is considered more efficient for reasons such as:

- Easy to store, copy, compress - Immunity: noise, interference
- Various transmission options - Error correction, encryption
- Flexibility in processing - Analysis of data
- Inexpensive building block
What is Digital?
• Digital signals represent only finite number of discreet values (2 valued: Binary).
- Signal is discreet by nature - Signal, analog by nature, converted to discreet
• Digital systems represent and manipulate digital signals.

Manipulation of Digital Signals
• Switching is key to manipulation of digital signals.
• Digital data storage involves switching.
Switching & Logic Operation
Realization of AND
Realization of OR
Realization of NOT
Switching Circuits
Realization of Tristate
Diode as a switch
• Realization of AND, OR logic
• Possibility of realizing NOT logic

References:
 Donald P. Leach, Albert P. Malvino, and Goutam Saha, Digital Principles &
Applications 8e, McGraw Hill
 M. Morris Mano, and Michael D. Ciletti, Digital Design 5e, Pearson
 Herbert Taub, Donald L Schilling, and Goutam Saha, Principles of Communication
Systems 4e, McGraw Hill
Conclusion:
• Digital technology provide better performance at a
lower cost. The key to it is inexpensive building blocks
i.e. digital electronic circuits.
• Digital systems represent and manipulate digital
signals. Digital signals are represented by finite
number of discreet values.
• Manipulation of digital signal involves switching.
Switching is associated with logic operations like AND,
OR, NOT.
• Diode as a switch can provide AND and OR logic.
Goutam Saha
Transistor as a switch
Lecture 02
Concepts Covered:
 Transistor as an inverter
 Input-output characteristics
 Noise margin, transition width, logic swing
 Fanout
Realization of NOT gate (inverter), Input-Output Characteristics
Vout For quantitative analysis:
VOH
5 • RB = 10 kΩ
4 • RC = 1 kΩ
• βF = 50
(in Volt)
3
• VBE(ON) = VBE(Sat) = 0.7V
Saturation
2
• VCE(Sat) = 0.2V
Cut-off
Active
1
VOL
1 2 3 4 5 Vin
VIL VIH (in Volt)
Transistor as a switch EOC
Cut-off region
• Base current IB = 0 till VBE < 0.7V i.e. Vin < 0.7V.
• Transistor is cut off and IC = 0 with Vout = 5V over entire range.
• When Vin is increased beyond 0.7V, base current begins to
flow and the transistor moves from cut off region to normal
active region.
• The coordinate, Vin = 0.7V, Vout = 5V mark first transition
point in the transfer function of this circuit. This is also
termed as breakpoint or edge of cutoff (EOC).
Active region
• Applying KVL along Vin, RB, VBE, Ground
IB = (Vin – VBE(on))/RB
• In active region, IC = βF IB (as long as VCE < VCE(sat))
• Applying KVL along Vcc, RC, VCE, Ground
Vout = VCC - IC RC = VCC - βF IB RC
• Combining,
Vout = VCC - βF RC (Vin – VBE(on))/RB
Saturation region
• As Vin (or IB) is increased a second transition point is
reached when Vout = VCE(sat). EOS
• The values of IC and IB for this condition (the subscript EOS

means edge of saturation):
IC(EOS) = (VCC – VCE(sat))/RC = (5-0.2)/1 = 4.8mA
and IB(EOS) = IC(EOS)/βF = 4.8/50 = 0.096mA
Then Vin(EOS) = VBE(on) + IB(EOS) RB = 0.7 + (0.096)(10) = 1.66V
• Thus Vin ≥ 1.66V the transistor saturates. (Saturating Logic)

Input-Output Mapping
Noise Margin, Transition width and Logic swing
NML = VIL – VOL = 0.7 – 0.2 = 0.5V

NMH = VOH – VIH = 5.0 – 1.66 = 3.34V
Transition width = VIH - VIL

NMH = 1.66 – 0.7 = 0.96V
L.S. T.W. Logic swing = VOH - VOL
NML = 5 – 0.2 = 4.8V
Fanout
Input to driver transistor: HIGH
• When Vin is HIGH, driver
transistor is saturated and
Vout will be LOW.
• With VCE(sat) = 0.2V all the
load gates will be in the OFF
state.
• No restriction on number of
load gates
Fanout
Input to driver transistor: LOW
• When Vin is LOW, driver transistor will be OFF and Vout will
be at HIGH level.
• A limit in the fanout is set when the voltage at Vout is
insufficient to saturate load gate transistors.
• Note that VIH = 1.66V
• For driver, IC(driver) = (VCC – Vout)/RC = (5 – 1.66)/1 = 3.34 mA
• For load, IB(load) = (Vout – VBE(sat))/RB
= (1.66 – 0.7)/10 = 0.096 mA
N = IC(driver)/IB(load) = 34.79 → 34
Fanout
Effect of noise margin
• For a 0.5V noise margin, Other factors:
Minimum HIGH level voltage at Vout Variation in βF, VBE(sat),
VOH = VIH + NMH = 1.66 + 0.5 = 2.16V VCE(sat), VCC, RC, RB.
• Similar calculation as before with Vout at 2.16V gives

IC(driver) = (VCC – Vout)/RC = (5 – 2.16)/1 = 2.84 mA
IB(load) = (Vout – VBE(sat))/RB = (2.16 – 0.7)/10 = 0.15 mA
N = IC(driver)/IB(load) = 19.4 → 19
• An increased NMH reduces fanout even further
References:
 Grinich, V.H., and H.G. Jackson, Introduction to Integrated Circuits, McGraw-Hill
 Donald P. Leach, Albert P. Malvino and Goutam Saha, Digital Principles &
 Herbert Taub, and Donald Schilling, Digital Integrated Electronics, McGraw Hill
Conclusion:
• A transistor can be used as a switch to realize an
inverter or NOT logic.
• The cut-off and saturation are two stable states of the
transistor when operated as a switch.
• The input-output characteristics define key
parameters of a logic circuit such as, noise margin,
transition width, logic swing.
• A logic gate connects to many similar gates to form a
large complex circuit. Fanout is an important
parameter in this context.
Goutam Saha
Performance Issues and

Introduction to TTL
Lecture 03
Concepts Covered:
 Propagation delay and power dissipation
 RTL NOR and NAND gate
 DTL NAND gate
 TTL NAND gate

Propagation Delay
• Due finite switching speed of transistors and circuit capacitances
tPHL: Delay in changing output from H to L

tPLH: Delay in changing output from L to H
input
Propagation delay, tPD = (tPHL + tPLH)/2
tr: Rise time 10% to 90% of max.

tf: Fall time 90% to 10% …
output
Power dissipation
• Static power dissipation Figure of Merit,
- when transistor is either ON or OFF F = PD x tPD
- depends on current drawn in each case The lower the F, the better.
- power dissipation, PD is average of these two
- significant in switching of Bipolar Junction Transistor
• Dynamic power dissipation
- when transistor switches
- depends on switching speed
- significant in switching of CMOS Transistor
RTL NOR Gate
RTL: Resistance Transistor Logic
• For 3 input NOR gate, another
input would come in parallel
with A and B.
• More no. of inputs increases
delay
• Fan-in: Max. number of
inputs a gate can handle
RTL NAND Gate
It will be shown that any

other logic gates can be
obtained using only
NAND gate or NOR gate.
From Archive (Motorola datasheet)
Two 3-input NOR gates
R1 = 450Ω , R2 = 640Ω
PD = 55 mW (input H), 15 mW (input L)
tPD = 12 ns
DTL NAND Gate
DTL: Diode Transistor Logic
• D1, D2, R1, VCC : AND logic at P.

• D3 and D4 are level shifters
(VP = 3 x 0.7V turns ON transistor.)
• R3 provides discharge path of
stored charge at BE junction that
reduces tPLH.
• Any of A or B low (0.2 V), VP = 0.9
V, insufficient to turn ON the
transistor.
TTL: Transistor Transistor Logic
NAND Gate
• Totem pole output
reduces output
resistance when at H.
• R3 cannot be made
zero.
• D1 to avoid
indeterminate
output.
Multi-emitter Phase
Transistor splitter
References:
 Motorla Datasheet accessed on Oct. 08, 2018 from
http://willowdaledesign.com/17_MRTL_700P_800P_text.pdf
Conclusion:
• Propagation delay, power dissipation and their
product, defined as figure of merit, are important to
characterize a logic gate.
• RTL NOR gate is formed of parallel connection of
transistors acting as switches akin to NOR logic
formed of electrical switches. Similarly, RTL NAND
gate is formed of series connection of transistors.
• DTL NAND gate uses diode AND logic, level shifter
diode and transistor inverter.
• TTL NAND gate uses transistor at the input stage, for
level shifting and phase splitting, and also totempole
output to improve switching speed.
IC 74147: Decimal-to-BCD
Priority Encoder Goutam Saha
Transistor Transistor Logic (TTL)

Lecture 04
Concepts Covered:
 TTL Transfer Characteristics and operating
parameters
 TTL Open Collector configuration
 TTL Tristate
 Schottky TTL
TTL: Transfer Characteristics
I: T4, T3 Cut-off. T1 Sat., T2 Active
IRc4 = IB2 negligible
V0 = 5 – 2x0.7 = 3.6V
If more load, V0 = 5 – 2x0.75 = 3.5V
A: T4 turns on at VBE4 = 0.65 V
Vi = 0.65 – VCE1(Sat) = 0.55 V
II: T4 active. T3 Cut-off. T1 Sat., T2 Active

IRC4 ≈ IC4 NOT negligible
AV4 = - (Rc4 / Re ) = -1.4
AV2 = 1 (emitter follower)
B: T3 turns on at Vi = 0.7 + 0.65 – 0.1
Vo = 3.5 – (1.4 x 0.65/1) = 2.6 V
TTL: Transfer Characteristics
III: T4, T3 Active. T1 Sat. T2 Active to Off
AV4 = - (Rc4 / Re || rd) = -2.8
AV3 = ΔV0 / ΔVB3 = - (βFRc3(eff.) / rd)
Rc3(eff.) = (rd(D) + rd(T2) + Rc4)/βF
AV3 = - (1.4 + 1 + 1) / 1 = - 3.4
ΔV0 = AV4 ΔVB4 + AV3 ΔVB3
AV = AV4 + AV3 = - 6.2 [as ΔVB4 = ΔVB3]
C: T3 saturates at Vi = 0.75 + 0.7 – 0.1 V
IV: T4, T3 Sat. T2 Cut-off. T1 inverse

T4, T3 saturate at Vi = 2 x 0.75 – 0.1 V
V0 = 0.1V
SN7404 Datasheet
Texas Instruments (Revised 2004)
Parameter Min. Typical Max. Unit
VIH 2 V
VIL 0.8 V
IOH -0.4 mA
IOL 16 mA
VOH 2.4 3.4 V Fanout = Lower [|IOH/IIH|, [|IOL/IIL|]=10
VOL 0.2 0.4 V NML = VIL – VOL = 0.8 – 0.4 = 0.4V
IIH 40 µA NMH = VOH – VIH = 2.4 – 2 = 0.4V
IIL -1.6 mA PD = 10mW
tPLH 12 22 ns
Note: Under specific test condition
tPHL 8 15 ns e.g. RL=400Ω, CL=15pF
TTL: Open Collector, Tri-state
TTL Gates: NAND, NOR
Input diodes
supress ringing
2-input NAND gate From TI SN7402 (2-input NOR) datasheet

Schottky TTL
Qty. Typ. Max. Unit
tPLH 3 4.5 ns
Cut-in ≈ 0.35V tPHL 3 5 ns
(range 0.2-0.5V)
Under test condition
RL=280Ω, CL=15pF
From TI SN74S00
Datasheet
References:
 Technical documents from http://www.ti.com accessed on Oct. 08, 2018
Conclusion:
• TTL Transfer Characteristics have 4 distinct zones
depending on operating conditions of 4 transistors.
• TTL NAND gate is obtained from multi-emitter input
while NOR gate is obtained from parallel connections
of as many numbers of input and phase splitter.
• TTL Open Collector requires external pull-up resistor
connected to power supply by which current can be
varied. This config. makes wired-AND is possible.
• TTL Tristate configuration doesn’t make any of the
transistors at Totempole output ON when disabled.
• Schottky TTL uses Schottky transistors which fall short
of saturation and increases switching speed.
Goutam Saha
CMOS Logic
Lecture 05
Concepts Covered:
 NMOS Logic gate
 CMOS Logic gate and its characteristics
 CMOS Tristate and Open-drain
 CMOS – TTL Interface

NMOS Gate Pinch-off Sat.: ID = k(VGS – VT)2
VDS ≥ VGS - VT Lin.: ID = k[2(VGS – VT)VDS - VDS2]
Linear
Saturation
Saturation region:
Note the difference
between TTL and MOS
NOR: T1A, T1B in parallel

Inverter with NMOS as resistance
NAND: T1A, T1B in series
CMOS Inverter
Output resistance = 1 KΩ
RT2 ≈ 10 RT1 RT2 ≈ RT1
(for both H and L)
Input resistance = 1012 Ω
Input capacitance = 5 pF
(shunt)
NMOS: Charging / discharging of CL CMOS Inverter

CMOS Transfer Characteristics
• Vi ≤ VT(n) : T1 OFF, T2 ON, Vo< VSS Vi ≤ 2V
• Vi ≥ VSS - VT(p) : T2 OFF, T1 ON, Vo = 0V Vi ≥ 8V
• T1 saturated: VDS1 ≥ VGS1 - VT(n)
i.e. VT(n) ≤ Vi ≤ Vo + VT(n) Vo≥ Vi - 2
• T2 saturated: VSD2 ≥ VSG2 - VT(p)
i.e. Vo - VT(p) ≤ Vi ≤ VSS - VT(p) Vo≤ Vi + 2
• Simultaneous saturation at unique Vi(sat.)
Vi(sat.) = 5V for kp = kn
CMOS Gate Parameters Large range of
VSS : 3 to 18 V and
T : -550C to 1250C
NML = NMH = 1.5V

tPHL = tPLH = 60 ns (25 ns at VSS = 10V)
Fanout ≈ 50 (Limited by tP)
PD (static) ≈ 10nW
PD (dynamic) (charging / disch. of CL)
= CLVSS2f
(1.25mW for
50pF, 5V, 1 MHz)
CMOS NAND and NOR Gates
Combinatorial Logic
NAND NOR
CMOS Tristate and Open-drain
Similar to
open-collector:
Provides
wired-AND
Open-drain with
protective diode
CMOS – TTL Interface
Both: 5V Supply
Parameter CMOS TTL Unit TTL driving CMOS
VIH 3.5 2 V • No issue with current levels.
VIL 1.5 0.8 V • Issue with VOH(TTL) < VIH(CMOS)
IOH -0.5 -0.4 mA • Pull-up resistance (2 - 6 kΩ) used
IOL 0.4 16 mA
CMOS driving TTL
VOH 4.99 2.4 V
• No issue with voltage levels.
VOL 0.01 0.4 V
• Issue with |IOL(CMOS)| < |IIL(TTL)|
IIH 10-6 40 µA
• CMOS buffer used
IIL -10-6 -1.6 mA
- dimension increased, ≈ 4mA
References:
 Herbert Taub, and Donald Schilling, Digital Integrated Electronics,
McGraw Hill
Conclusion:
• NMOS inverter uses NMOS load resistance as it takes
less space. CMOS inverter charges load capacitance
quicker through PMOS (ON) that improves speed.
• CMOS inverter transfer characteristics has 5 zones
depending on operating condition of two transistors.
• CMOS gate fanout is limited by propagation delay. Its
dynamic power dissipation at high freq. is comparable
to TTL. Else, CMOS takes less space and less power.
• CMOS gate can have Tristate and Open-drain config.
• CMOS and TTL gates are incompatible on few counts
for which appropriate interface is used.
Goutam Saha
Basic Gates and their representations

Lecture 06
Concepts Covered:
 Week 1 Recap.
 Basic Logic Gates
 Universality of NOR, NAND Gates
 AND-OR-Invert Gate
Week 1 Recap.
• Manipulation of digital signal is fundamental to Digital Technology.
• Switching and Logic operations are key at hardware level.
• Transistor based circuits can be used as inverter and can provide all
possible logic operations.
• TTL and CMOS based logic gates have wide applications as building blocks
of Digital Electronic Circuits.
• Practical issues associated with digital circuits e.g. propagation delay, noise
margin, fanout, power dissipation etc. need consideration.
Inverter (NOT Gate)
Y = not A
Delay in actual
circuit i.e. not
instantaneous.
AND Gate
Y = A AND B
Y = A.B.C
Y = A.B = A.B = A.(B.C)
= B.A = (A.B).C
(Commutative) (Associative)
OR Gate
Y = A OR B
Y=A+B+C
Y=A+B
= A + (B + C)
=B+A
= (A + B) + C
(Commutative) (Associative)
NOR Gate
De Morgan’s
1st Theorem:
𝒀𝒀 = 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪+. .
� . 𝑩𝑩
= 𝑨𝑨 �…
� . 𝑪𝑪
(Commutative)
NAND Gate
De Morgan’s
2nd Theorem:
𝒀𝒀 = 𝑨𝑨𝑨𝑨𝑨𝑨. .
� + 𝑩𝑩
= 𝑨𝑨 �+⋯
� + 𝑪𝑪
(Commutative)
Universality of NOR, NAND gate
Realization of AND, OR, NOT
AND-OR-Invert Gate SN7451: Dual 2-input, 2-wide AOI Gate
IC 7451
2-1 AOI Gate

(More transistors, if separately) Expanadable AOI Gate (e.g.7450), Expander(e.g.7460)
References:
Conclusion:
• Logic circuit operation is represented by Symbol,
Boolean Expression, Truth Table, Timing Diagram.
• AND, OR, NAND, NOR operations are commutative.
AND, OR operations are associative.
• NOR operation is equivalent to ANDing of
complemented inputs.
• NAND operation is equivalent to ORing of
complemented inputs.
• Any other logic gate or operation can be obtained
using only NAND or NOR gates.
• AND-OR-Invert gate takes less number of transistors
in comparison to implementing them separately.
Goutam Saha
Fundamentals of Boolean Algebra

Lecture 07
Concepts Covered:
 Huntington Postulates
 Basic Theorems and Duality
 Derivation of Theorems from Postulates
 Difference with ordinary Algebra

Possible Logic Operations
OR
NAND
NOR
NOT x NOT y
AND
𝟐𝟐𝒏𝒏
• 𝟐𝟐 possible functions with n variables
• Formalization of representation and manipulation: Boolean Algebra
Boolean Algebra: Huntington Postulates
No. Postulate Description 1854: Boolean Algebra,
George Boole
1 Closed with operators + and . Result of each is 1, 0 ϵ B 1904: Postulates, E. V.
2 Identity element: 0 with +, 1 with . x + 0 = x; x.1 = x Huntington
3 Commutative w.r.t. +, . x + y = y + x; x.y = y.x 1938: Switching Algebra
(2-valued), Claude. E.
4 . is distributive over +, x.(y + z) = x.y + x.z;
Shanon
+ is distributive over . x + (y.z) = (x + y).(x + z)
5 For x ϵ B, there is x’ ϵ B s.t. 0 + 0’ = 0 + 1 = 1, 1 + 1’ = 1;
x + x’ = 1 and x.x’ = 0 0.0’ = 0.1 = 0, 1.1’ = 1.0 = 0
6 At least 2 elements x, y ϵ B s.t. x ≠ y B = {0,1}, 0 ≠ 1
Associative Law: (x + y) + z = x + (y + z); (x.y).z = x.(y.z) From postulates

Postulates and Basic Theorems
Name (a) (b) Proof: Null (a)
Identity x+0=x x.1 = x x + 1 = (x + 1).1
= (x + 1).(x + x’)
Null x+1=1 x.0 = 0
= x + x’.1
Complementarity x + x’ = 1 x.x’ = 0 = x + x’
Idempotency x+x=x x.x = x =1
Involution (x’)’ = x
Commutative x+y=y+x x.y = y.x
Associative (x + y) + z = x + (y + z) (x.y).z = x.(y.z)
Distributive x.(y + z) = x.y + x.z x + (y.z) = (x + y).(x + z)
Duality and Boolean Expressions
Name (a) (b) Duality: Boolean Algebraic
expression remains valid if
Absorption x + x.y = x x.(x + y) = x
the operators and identity
Adsorption x + x’.y = x + y x.(x’ + y) = x.y elements are interchanged.
Uniting x.y + x.y’ = x (x + y).(x + y’) = x
Consensus x.y + x’.z + y.z = x.y + x’.z (x + y).(x’ + z).(y + z) = Proof: Null (b)
(x + y).(x’ + z) x + 1 = 1 (proven)
De Morgan’s (x1 + x2 + x3 + … xN)’ = (x1.x2.x3. … xN)’ =
By Duality, x.0 = 0
x1’.x2'.x3'. … xN’ x1’ + x2‘ + x3‘ + …+ xN’
Operator precedence: Parentheses, NOT, AND, OR

More Proof Proof: Involution
(x’)’= (x’)’ + 0
Proof: Idempotency (b) = (x’)’ + x.x’
Proof: Idempotency (a) x.x = x.x + 0 = [(x’)’ + x].[(x’)’ + x’]
x + x = (x + x).1 :Identity = x.x + x.x’ = [x + (x’)’].[x’ + (x’)’]
= (x + x).(x + x’) :Complem. = x.(x + x’) = [x + (x’)’].1
= x + x.x’ :Distribut. = x.1 = [x + (x’)’].[x + x’]
=x+0 :Complem. =x = x + (x’)’.x’
=x :Identity [Also, by duality of (a), = x + x’. (x’)’
x+x=x] =x+0
=x
More Proof
Proof: Consensus (a) Proof: De Morgan’s Th. (a) 2 var.: (x + y)’ = x’.y'
x.y + x’.z + y.z = x.y + x’.z + y.z.1 We know, (x + y) + (x + y)’ = 1

= x.y + x’.z + y.z.(x + x’) To show, (x + y) + x’.y' = 1
= x.y + x’.z + x.y.z + x’.y.z
(x + y) + x’.y' = [(x + y) + x’].[(x + y) + y']
= (x.y + x.y.z) + (x’.z + x’.y.z)
= [(y + x) + x’].[(x + y) + y']
= (x.y + x.y.z) + (x’.z + x’.y.z)
= [y + (x + x’)].[x + (y + y‘)]
= x.y.(1 + z) + x’.z.(1 + y)
= [y + 1].[x + 1]
= x.y.1 + x’.z.1
= 1.1
= x.y + x’.z
=1
More Characteristics
• Distributive Law, x + (y.z) = (x + y).(x + z), is not valid for ordinary algebra.
• Complement is not available in ordinary algebra. Difference
• Boolean algebra does not have subtraction, division. with ordinary
algebra
• Boolean algebra (2-valued) has finite set of elements (0 and 1).
Use of NAND (↑), NOR (↓) instead of AND (.), OR (+):

• (x↑y)↑z ≠ x↑(y↑z); (x↑y)’↑z = x↑(y↑z)’
Pseudoassociative
• (x↓y)↓z ≠ x↓(y↓z); (x↓y)’↑z = x↓(y↓z)’
• x↑(y↓z) ≠ (x↓y)↑(x↓z); x↑(y↓z) = (x’↓y)↑(x’↓z)
Pseudodistributive
• x↓(y↑z) ≠ (x↑y)↓(x↑z); x↓(y↑z) = (x’↑y)↓(x’↑z)
References:
Conclusion:
𝟐𝟐𝒏𝒏
• With n variables, there are 𝟐𝟐 possible functions.
• Six Huntington Postulates form the basic premise or
axioms of Boolean Algebra.
• The basic theorems of Boolean Algebra can be arrived
at from Huntington Postulates.
• Boolean Algebra has certain distinctive characteristics
that differentiate it from ordinary algebra.
• AND, OR operations are associative and they are
distributive over each other.
• NAND, NOR operations are not associative and they
are not distributive over each other. The relation here
is pseudoassociative and pseudodistributive.
Goutam Saha
Boolean Function to Truth Table and

Implementation Issues
Lecture 08
Concepts Covered:
 Conversion of Boolean Function to Truth Table
 Implementation of a Boolean Function
 Algebraic simplification
 Shanon’s Expansion Theorem

Boolean Function to Truth Table
F(x,y) = x + x’.y
x y z F(x,y,z) F(x,y,z) = (x + y).(x + z)
F(0,0) = 0 + 0’.0 = 0 + 1.0 = 0 + 0 = 0
F(0,1) = 0 + 0’.1 = 0 + 1.1 = 0 + 1 = 1 0 0 0 0 F(0,0,0) = (0 + 0).(0 + 0)
F(1,0) = 1 + 1’.0 = 1 + 0.0 = 1 + 0 = 1 = 0.0 = 0
0 0 1 0 F(0,0,1) = (0 + 0).(0 + 1)
F(1,1) = 1 + 1’.1 = 1 + 0.1 = 1 + 0 = 1
0 1 0 0 = 0.1 = 0
…
x y F(x,y) 0 1 1 1
…
0 0 0 1 0 0 1
0 1 1 1 0 1 1
1 0 1 1 1 0 1
1 1 1 1 1 1 1
Implementation of Boolean Function
F(x,y) = x + x’.y
F(x,y,z) = (x + y).(x + z)
Efficient Implementation Equivalence can be
verified from Truth Table.
Use of Boolean Algebra
From Adsorption Theorem: From Postulate (Distributive Law):
(x + y).(x + z) = x + y.z
F(x,y) = x + x’.y = x + y
Earlier: One NOT, One 2 i/p AND,

One 2 i/p OR Earlier: One 2 i/p AND, Two 2 i/p OR
Now: One 2 i/p OR Now: One 2 i/p AND, One 2 i/p OR
Algebraic Simplification
Simplify, Simplify, Y = (A + B)(A’(B’ + C’))’ + A’(B + C)
Y = F(A,B,C) = A(A’ + C)(A’B + C)(A’BC + C’)
Note that, output Y is always L here and

can be connected to LOW voltage directly.
Shanon’s Expansion Theorem Example:
F(x,y) = x + x’.y
F(x1, x2, x3, …, xN) = x1’.F(0, x2, x3, …, xN) + x1.F(1, x2, x3, …, xN) F(0,y) = 0 + 0’.y = 1.y = y
Proof: x1 can take only 2 values, 0 and 1 F(1,y) = 1 + 1’.y = 1
F(x,y) = x’.F(0,y)+ x.F(1,y)
For x1 = 0, LHS = F(0, x2, x3, …, xN) = 0’.F(0, x2, x3, …, xN) + 0.F(1, x2, x3, …, xN) = x’.y + x.1
= 1.F(0, x2, x3, …, xN) + 0 = x’.y + x
= F(0, x2, x3, …, xN) = RHS = x + x’.y
For x1 = 1, LHS = F(1, x2, x3, …, xN) = 1’.F(0, x2, x3, …, xN) + 1.F(1, x2, x3, …, xN)
= 0.F(0, x2, x3, …, xN) + F(1, x2, x3, …, xN)
= 0 + F(1, x2, x3, …, xN)
= F(1, x2, x3, …, xN) = RHS
Dual Form:
F(x1, x2, x3, …, xN) = [x1’ + F(1, x2, x3, …, xN)].[x1 + F(0, x2, x3, …, xN)]
Example on Simplification
Simplify,
Choice of A as expansion variable as it is associated with more number of terms

More on Shanon’s Expansion Theorem
F(x1, x2, x3, …, xN) = x1’.F(0, x2, x3, …, xN) + x1.F(1, x2, x3, …, xN)
F(x1, x2, x3, …, xN) = x1’.[x2’.F(0, 0, x3, …, xN) + x2.F(0, 1, x3, …, xN)] Nesting
+ x1.[x2’.F(1, 0, x3, …, xN) + x2.F(1, 1, x3, …, xN)]
F(x,y) = x’.F(0,y)+ x.F(1,y) = x’.[y’.F(0,0)+ y.F(0,1)]+ x.[y’.F(1,0)+ y.F(1,1)] For 2 variables
= x’.y’.F(0,0)+ x’.y.F(0,1)+ x.y’.F(1,0)+ x.y.F(1,1)
x y F(x,y)
Example: 0 0 0
F(x,y) = x + x’.y F(0,0) = 0 + 0’.0 = 0; F(0,1) = 0 + 0’.1 = 1; 0 1 1
F(1,0) = 1 + 1’.0 = 1; F(1,1) = 1 + 1’.1 = 1; 1 0 1
1 1 1
F(x,y) = x’.y’.0 + x’.y.1+ x.y’.1+ x.y.1 = x’.y + x.y’ + x.y In Truth Table,
= x’.y + x.(y + y’) = x’.y + x.1 = x + x’.y o/p is 1 in 3 rows
References:
Conclusion:
• By obtaining function output through substitution of
Boolean variables with possible binary combinations,
corresponding Truth Table can be arrived at.
• Boolean function can be realized by using logic gates
that corresponds a logic operation.
• Algebraic manipulation can provide simplified
Boolean expression for efficient implementation.
• Shanon’s Expansion Theorem and its nested version
is useful in algebraic manipulation of a Boolean
function.
Goutam Saha
Truth Table to Boolean Function and

Implementation Issues
Lecture 09
Concepts Covered:
 Canonical representation using minterms
 Canonical representation using Maxterms
 2-Level, 3-Level Implementation
 Positive and Negative Logic

Truth Table to Boolean Function: Minterm
F(x,y) = x + x’.y • Product term containing all variables of a
function (primed, unprimed): fundamental
x y F(x,y) product or standard product or minterm.
0 0 0 x’.y’ • Minterms of F(x,y): x’.y’, x’.y, x.y’, x.y (also
0 1 1 x’.y designated as m0, m1, m2, m3, respectively)
1 0 1 x.y’ • The minterm designation mi corresponds to
1 1 1 x.y decimal eqv. of x,y combination of a row.
[Decimal Eqv. = B3.23 + B2.22 + B1.21 + B0.20]
F(x,y) = x’.y’.F(0,0)+ x’.y.F(0,1) • Boolean function: Taking OR of
+ x.y’.F(1,0)+ x.y.F(1,1) minterms associated with 1
= x’.y + x.y’ + x.y in function output.
Minterm: More Example Sum of Product (SOP):
Canonical Form
F(x,y,z) = (x + y).(x + z)
F(x,y,z) = x’yz + xy’z’ + xy’z
x y z minterm Notation x y z F(x,y,z) + xyz’ + xyz
0 0 0 x’y’z’ m0 0 0 0 0 F(x,y,z) = m3 + m4 + m5
0 0 1 x’y’z m1 0 0 1 0 + m6 + m7
0 1 0 x’yz’ m2 0 1 0 0 F(x,y,z) = ∑ m(3,4,5,6,7)
0 1 1 x’yz m3 0 1 1 1
1 0 0 xy’z’ m4 1 0 0 1
1 0 1 xy’z m5 1 0 1 1
1 1 0 xyz’ m6 1 1 0 1
1 1 1 xyz m7 1 1 1 1
Truth Table to Boolean Function: Maxterm
• Sum term containing all variables of a function
x y F(x,y) (primed, unprimed): fundamental sum or
0 0 0 x+y standard sum or Maxterm.
0 1 1 x + y’ • Maxterms of F(x,y): x+y, x+y’, x’+y, x’+y’ (also
1 0 1 x’ + y designated as M0, M1, M2, M3, respectively)
1 1 1 x’ + y’ • The minterm designation Mi corresponds to
decimal eqv. of x,y combination of a row.
F(x,y) = [x’ + y’ + F(1,1)].[x’ + y + F(1,0)] • Boolean function: Taking AND of
.[x + y’ + F(0,1)].[x + y + F(0,0)] Maxterms associated with 0
= 1.1.1.(x + y) = x + y in function output.
F(x1, x2, x3, …, xN) = [x1’ + F(1, x2, x3, …, xN)].[x1 + F(0, x2, x3, …, xN)]
Maxterm: More Example Product of Sum(POS):
Canonical Form
F(x,y,z) = (x + y).(x + z)
F(x,y,z) = (x+y+z).(x+y+z’)
x y z Maxterm Notation x y z F(x,y,z) .(x+y’+z)
0 0 0 x+y+z M0 0 0 0 0 F(x,y,z) = M0.M1.M2
0 0 1 x+y+z’ M1 0 0 1 0 F(x,y,z) = ∏ M(0,1,2)
0 1 0 x+y’+z M2 0 1 0 0
0 1 1 x+y’+z’ M3 0 1 1 1
1 0 0 x’+y+z M4 1 0 0 1
1 0 1 x’+y+z’ M5 1 0 1 1
1 1 0 x’+y’+z M6 1 1 0 1
1 1 1 x’+y’+z’ M7 1 1 1 1
More on Canonical Forms
We have seen, (i) F(x,y) = x + x’.y = ∑ m(1,2,3) = ∏ M(0)
and (ii) F(x,y,z) = (x + y).(x + z) = ∑ m(3,4,5,6,7) = ∏ M(0,1,2) Conversion between
From example(ii) Truth Table (T.T.): Canonical Forms
F’(x,y,z) = ∑ m(0,1,2) = m0 + m1 + m2
F(x,y,z) = (F’(x,y,z))’ = (m0 + m1 + m2)’ = m0’.m1’.m2’ (De Morgan’s Th.)
We already noted, F(x,y,z) = ∏ M(0,1,2) = M0.M1.M2
Extending to any T.T., mi’ = Mi
F(x,y) = x + x’.y = x.(y + y’) + x’.y = x’.y + x.y’ + x.y Getting minterms
F(x,y,z) = (x + y).(x + z) = (x + y + z.z’).(x + z + y.y’) and Maxterms
= (x + y + z).(x + y + z’).(x + z + y).(x + z + y’) algebraically
= (x + y + z).(x + y + z’).(x + y’ + z)
Two Level Implementation SOP: 3-level implementation
SOP POS
Y = ABC + D(E + F)
Y = F(A,B,C) = ∑ m(3,5,6,7) Y = F(A,B,C) = ∏ M(0,3,6)

NAND - NAND, NOR - NOR Implementation
A.B + C.D + E.F = ((A.B + C.D + E.F )’)’ (A + B).(C + D).(E + F) = (((A + B).(C + D).(E + F))’)’
= ((A.B)’.(C.D)’.(E.F)’)’ = ((A + B)’+(C + D)’+(E + F)’)’
AND - OR NAND - NAND OR - AND NOR - NOR
Positive and Negative Logic Positive Negative
Logic Logic
A B Y
OR AND
A Electronic
0 0 0
Y Positive 0 1 1 AND OR
Circuit OR
B Logic
H=1 1 0 1 NAND NOR
L=0 1 1 1 NOR NAND
A B Y
Low Low Low A B Y
Low High High 1 1 1
High Low High Negative 1 0 0 AND
Logic
High High High 0 1 0
H=0
L=1 0 0 0
In terms of voltage levels
References:
Conclusion:
• Taking OR of minterms Canonical Sum of Product (SOP)
form of Boolean equation can be obtained.
• Taking AND of Maxterms Canonical Product of Sum (POS)
form of Boolean equation can be obtained.
• Maxterms and minterms can be obtained from Truth
Table. These can be obtained from a Boolean expression,
if not explicit, by algebraic manipulation.
• Conversion between Canonical SOP and POS considers
complement of a minterm giving corresponding Maxterm
(vice versa).
• 2-level SOP realization considers AND-OR or NAND-NAND
while 2-level POS realization considers OR-AND or NOR-
NOR realization.
• Same hardware provides negative logic based realization
for alternate interpretation of High and Low volatages.
Goutam Saha
Karnaugh Map and Digital

Circuit Realization
Lecture 10
Concepts Covered:
 Karnaugh Map (K-Map) representation
 Simplification using Karnaugh Map
 Use of Don’t Care in Karnaugh Map simplification
 Dual Circuit and Self-duality

Two-Variable Karnaugh Map
Y = F(A,B) = ∑ m(2,3) Y = F(A,B) = ∑ m(1,2,3)
Y=A Y=A+B
SOP: Simplification
Three Variable Karnaugh Map B.C’
• Largest logically adjacent
group of size 2i
A
• Minimum no. of groups to
cover all 1s
• Each group gives one product Y = A + B.C’
term
• Variables remaining constant
form product term Y = F(A,B,C)
= ∑ m(2,4,5,6,7)
(1:unprimed, 0:primed)
F(A,B,C)
• All product terms are
minterm
summed. numbers
Four-Variable Karnaugh Map Y = F(A,B,C,D)
= ∑ m(0,1,2,6,8,10,13,14)
A’B’C’ = B’D’ + CD’ + A’B’C’ + ABC’D
CD’
B’D’ ABC’D
F(A,B,C,D)
minterm numbers
Don’t Care in Karnaugh Map
Not considering X Considering X
Design: Y is H when
BCD (Binary Coded
Decimal) input is odd.
A
B Digital
C Circuit Y
D Y=D
Y = A’D + B’C’D
Y = F(A,B,C,D)
• If not considered, X = 0.
= ∑ m(1,3,5,7,9) +
d(10,11,12,13,14,15) • If considered, X = 1.
• Consideration wherever helps.
Karnaugh Map: POS • To cover all 0s
• Variables remaining
(A + B) Y = F(A,B,C,D) constant form sum term
= ∏ M(0,2,4,6,8).D(10,
(1:primed, 0:unprimed)
11,12,13,14,15)
• Product of all sum
terms generate output
(A + C’) • X is considered 0
wherever helps
Y = (A + B).(A + C’)
Y = F(A,B,C)
Distributive D
= ∑ m(2,4,5,6,7)
= ∏ M(0,1,3) SOP Y=D
Y = A + B.C’ Simplification
Dual Circuit • NAND → NOR,
NOR → NAND,
Complement all
input and output
• AND → OR,
OR → AND,
Complement all
input and output
Conditions:
Self-Dual Function • Neutral: No. of
A’.B minterms is same as
Consider, F(A,B) = A.B’ + A’.B A.B’ no. of Maxterms
Its dual, FD(A,B) = (A+B’).(A’+B) • Function not to
(on simplification) = A’.B’ + A.B contain any mutually
exclusive minterm
F(A,B) ≠ FD(A,B)
mutually
A.B.C A’.B’.C’
Consider, F(A,B,C) = A.B + B.C + C.A exclusive
Then, FD(A,B,C) = (A+B).(B+C).(C+A) A’.B.C

(on simplification) = A.B + B.C + C.A
A.B’.C
F(A,B) = FD(A,B) : Self-dual
A.B.C’
A.B.C
References:
Conclusion:
• Logical adjacency is key to Karnaugh Map based
representation and simplification.
• In Sum of Product (SOP) simplification, all 1s need to
be covered with minimum number of largest 2i sized
logically adjacent groups.
• In Product of Sum (POS) simplification, all 0s need to
be covered with minimum number of largest 2i sized
logically adjacent groups.
• Function outputs for don’t care input combinations
can be treated as 1 or 0 to get minimized expression.
• Duality at circuit level can quickly convert a AND-OR /
NAND-NAND realization to OR-AND / NOR-NOR and
vice versa.
Goutam Saha
Karnaugh Map to Entered

Variable Map
Lecture 11
Concepts Covered:
 Week 2 Recap.
 Five-variable Karnaugh Map
 Entered Variable Map for SOP simplification
 Entered Variable Map for POS simplification

Week 2 Recap.
• Logic circuit operation is represented by Symbol, Boolean Expression, Truth
Table, Timing Diagram. NAND and NOR are considered universal logic gate.
• Huntington Postulates and Basic Theorems of Boolean Algebra help in
analysis and simplification of digital logic circuits. Boolean function can be
realized by using logic gates that corresponds a logic operation.
• Canonical SOP representation uses minterms (realization by AND-OR or
NAND-NAND) and Canonical POS representation uses Maxterms
(realization by OR-AND or NOR-NOR).
• Concept of Negative Logic and Dual Circuit has its own use.
• Karnaugh Map based simplification is useful for SOP and POS
realization.
Five-Variable Karnaugh Map
Reflection Map
A B C D E minterm Notation
0 0 0 0 0 A’B’C’D’E’ m0
0 0 0 0 1 A’B’C’D’E m1
... … … … …
1 1 1 1 0 ABCDE’ m30
1 1 1 1 1 ABCDE m31
Five-Variable Karnaugh Map
Example
F(A,B,C,D,E) = ∑ m(2,6,9,11,13,15,18,19,22,23,25,27,29,31)
B’.D.E’
F = B.E + A.B’.D + B’.D.E’

Or
F = B.E + A.D.E + B’.D.E’
B.E
A.D.E
A.B’.D
Entered Variable (EV)
A B C Y B C Y
A B C Y
0 0 0 0 0 0 0
0 0 0 0
Y=0 A B Y 0 0 1 0 0 1 0
0 0 1 0
0 0 0 Y=0 0 1 0 1 1 0 1
0 1 0 1
Y=C’
0 1 C’ 0 1 1 0 1 1 A
0 1 1 0
1 0 0 1 0 0 0
1 0 0 0
Y=0
1 1 1 Y=A 1 0 1 0
1 0 1 0
1 1 0 1
1 1 0 1
Y=1 1 1 1 1
1 1 1 1
F(A,B,C) = ∑ m(2,6,7)
EV Map: SOP Simplification
B.(C’)
C + C’ =1
B.C’.(1) A.(C)
1 + C’ = 1
1+A=1 F(A,B,C) = B.C’ + A.C
A.B.(1) B.(C’)
B.(A)
A.B.(1)
F(A,B,C) = ∑ m(2,6,7)
B.C’.(1)
F(A,B,C) = B.C’ + A.B
EV Map: POS Simplification
0.A = 0
0.C’ = 0
B + (0)
A + C’ + (0)
A + (C’)
C’ + (A)
B + (0)
B +(0) F(A,B,C) = B.(A + C’)
Also, C.C’ = 0 can be considered by which C could be in

one sum term and C’ in another sum term to cover a 0.
Simplification: Five-Variable A B C D E Y
1 1 0 0 0 0
E
1 1 0 0 1 1
A B C D E Y A B C D E Y A B C D E Y
1 1 0 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 E 1 1 0 1 1
0 E 0 1
0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 0
0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 E 1 1 1 0 0 0
E’ E 1 1 1 1 0 1 1
0 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1
1 1 1 1 0 0
0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 E 1 1 1 1 1
0 E 0 1
0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0
0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1
E’ E 1
0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1
F(A,B,C,D,E) = ∑ m(2,6,9,11,13,15,18,19,22,23,25,27,29,31)
Simplification: Five-Variable
A.D.E and B’.D.E’ together cover
1s covered by A.B’.D where is
considered as 1 = E + E’
B’.D.(E’)
F(A,B,C,D,E) = B.E + A.B’.D + B’.D.E’
Or
F(A,B,C,D,E) = B.E + A.D.E + B’.D.E’
B.(E)
A.D.(E)
A.B’.D.(1)
References:
Conclusion:
• Simplification of 5-variable function using Karnaugh
Map requires 3D visualization.
• For the map entered variable, variation of output
with respect to the entered variable is considered for
cases when other variables remain constant.
• In SOP realization, using Entered Variable Map
(EVM), each 1 and entered variable (complemented
or uncomplemented) need to be covered.
• In POS realization, using EVM, each 0 and entered
variable (comple. or uncomple.) need to be covered.
• For EVM based SOP, 1 can also be considered as 1+x,
1+x’ or x+x’ while for POS, 0 can also be considered
as 0.x, 0.x’ or x.x’.
Goutam Saha
Quine - McClusky (QM)

Algorithm
Lecture 12
Concepts Covered:
 QM Algorithm – Finding Prime Implicants (P.I.)
 QM Algorithm – Finding Essential P. I.
 Use of Don’t Care in QM Method

QM Algorithm Grouping according
to no. of 1s input
• Finding Prime Implicants variable combi.
(P.I.) through an iterative have in T.T. for Y = 1
process.
• P.I is a product term that Numbering of
cannot be combined with minterms to ensure all
any other product term are included as its
(least no. of literals) order changes
• Finding Essential P.I. to
cover all minterms.
• Selecting minimal set.
Y = ∑ m(0,1,2,3, 10,11,12,
13,14,15)
QM Algorithm • Grouping of terms from
adjacent blocks of Stage 1
which differ in only one
position of input variable
combinations.
• Writing ‘–’ (eqv. to don’t
care) in those positions.
• Ticking terms of Stage 1
which could make it to
Stage 2.
QM Algorithm • Similar grouping of
Stage 2 terms in Stage 3.
• Ticking terms of Stage 2
which could make it to
Stage 3.
• This continues as long as
grouping possible for
next stages.
• In each stage no. of
blocks reduce.
QM Algorithm
• For this example, no further
grouping and thus, no Stage 4.
• Every term in Stage 3 remains
unticked. There were no unticked
term in Stage 2 and Stage 1.
• Each unticked term of any stage is
to contribute to generation of P.I.
• For this example, 4 P.I.s which are
mutually exclusive for ABCD
combinations 00--, -01-, 1-1-, 11--.
QM Algorithm
P.I. minterms
A’.B’ 0,1,2,3
B’.C 2,3,10,11
A.C 10,11,14, 15
A.B 12,13,14,15
P.I. Table
(All stages together)
P.I. minterms
QM Algorithm A’.B’ 0,1,2,3 A’.B’
B’.C 2,3,10,11
A.C 10,11,14, 15
A.B
Essential P.I. Table A.B 12,13,14,15
P.I. 0 1 2 3 10 11 12 13 14 15
A’.B’ √ √ √ √ Either A.C
or B’.C
B’.C √ √ √ √
A.C √ √ √ √
A.B √ √ √ √
Essential P.I. : A’.B’, A.B and any one of B’.C or A.C

Minimal set: Y = A’.B’ + A.B + B’.C or Y = A’.B’ + A.B + A.C
P.I. minterms
QM Algorithm with Don’t Care A’.B’ (0),(1),2,3
B’.C 2,3,10,11
• Include don’t care in finding P.I.
A.C 10,11,14, 15
• Exclude don’t care in finding Essential P.I. A.B 12,13,14,15
Essential P.I. Table Example:

P.I. 2 3 10 11 12 13 14 15 Y = ∑ m(2,3,10,11,12,13,
A’.B’ √ √
14,15) + d(0,1)
B’.C √ √ √ √ P.I. as before
A.C √ √ √ √
A.B √ √ √ √
Essential P.I. : B’.C and A.B Y = A.B + B’.C

References:
Conclusion:
• QM algorithm based simplification first identifies
Prime Implicants (P.I.).
• P.I is a product term that cannot be combined with
any other product term (least no. of literals)
• Essential P.I. are the P.I. which together cover all the
1s of a Truth Table.
• A minimal set with Essential P.I. is arrived at for the
function output.
• Don’t Care conditions are included in finding P.I. and
excluded in finding Essential P.I.
• QM algorithm is useful for computer program based
simplification of Boolean Expression containing large
number of variables.
Goutam Saha
Cost Criteria and Minimization

of Multiple Output Functions
Lecture 13
Concepts Covered:
 Cost Criteria
 Multiple Output Minimization
 Use of Don’t Care in Multiple Output

Minimization
Simplest SOP and POS: An Example
Y = A + B.C’ Y = (A + B).(A + C’)
Y = F(A,B,C) Here, realization

= ∑ m(2,4,5,6,7)
of POS is costlier.
Cost Criteria
Y = A + B.C’
• Literal Cost: The number of times a literal appears in
complemented or uncomplemented form (L).
• Gate Input Cost: The number of inputs to the gates in Y = (A + B) .(A + C’)
the implementation. It may not count NOT gates (G) or
it may include NOT gate count (GN).
If the number of terms excluding single variable term is
T, and the number of distinct inversions is N, then
G=L+T Implementation L T N G GN
GN = L + T + N Y = A + B.C’ 3 1 1 4 5
Y = (A + B) .(A + C’) 4 2 1 6 7
Cost Criteria: Examples Y = A.B + C.(D + E)
Implementation L T N G GN
Y = A.B + B.C + C.A 6 3 0 9 9 3 level
Y = (A+B).(B+C).(C+A) 6 3 0 9 9
Y = A.B + C.D + C.E
Y = A.B.C + A’.B’.C’ 6 2 3 8 11
Y = (A’+B).(B’+C).(C’+A) 6 3 3 9 12 2 level
Y = A.B + B’.C.D + A’.B’.D + B.C’.D 11 4 3 15 18
Y = (A+C’).(A+D).(B’+C’+D).(B+C+D’) 10 4 3 14 17
Considered: 2-Level implementation, no restriction in fan-in or Total Cost (TC)
kind of logic gates to be used (as in K-Map, QM simplification) = No. of gate i/p
+ No. of gates
Implementation using only 2-input NAND gate: An Example
Cost: 5 Units
Y = A.B + C.D.E = ((A.B)’.(C.D.E)’)’ = ((A.B)’.((C.D)’)’.E)’)’
(10 Gate inputs)
Common P.I.
Multiple Output Minimization
F1 = B’.C + A.B
Individual
Individual
implementation
G = 6 x 2 = 12
TC = 12 + 3 x 2 = 18
Using common P.I.

G = 6 + 4 = 10
TC = 10 + 3 +2 = 15
F2 = B’.C + A’.B Combined

Multiple Output Minimization Common term need
to be generated
F1 = ∑ m(0,1,3)
= A’.B’ + A’.C
Individual
implementation
F1 = A’.B’ + A’.B.C
G = 6 + 8 = 14
TC = 14 + 3 + 3 = 20 F2 = A’.B.C + A.B.C’
Combined
F2 = ∑ m(3,6) G = 7 + 5 = 12
= A’.B.C + A.B.C’ TC = 12 + 3 + 2 = 17
Multiple Output Minimization Common term part of
individual bigger group
F1 = A’.B’ + A’.B.C
F1 = ∑ m(0,1,3)
F2 = A’.B.C + A.B.C
= A’.B’ + A’.C
G = 7 + 5 = 12
Individual TC = 12 + 3 + 2
implementation = 17
G=6+2=8
TC = 8 + 3 + 1 = 12
F2 = ∑ m(3,7)
= B.C Individual: Less cost
Multiple Output Minimization Common term part of
bigger group in which other
members already covered
Individual
G = 10 + 10 = 20
TC = 20 + 4 + 4 = 28
Combined
G = 11 + 8 = 19
Individual Combined TC = 19 + 4 + 3 = 26
Minimization Minimization
F1 = B.C’ + B.D + A’.B’.C F1 = B.C’ + B.C.D + A’.B’.C

F2 = B.D’ + B.C + A.B’.D F2 = B.D’ + B.C.D + A.B’.D
Multiple Output Minimization Use of Don’t Care
F1 = B.C’.D’ + B.C.D + A’.B’.C

F2 = B.C’.D’ + B.C.D + A.B’.D
G = 12 + 6 = 18
F1 = B.D + A’.B’.C TC = 18 + 4 + 2 = 24
F2 = B.C + A.B’.D
Individual
G = 7 + 7 = 14 G = 20, TC = 28
TC = 14 + 3 + 3 = 20
References:
Conclusion:
• Comparison of different logic circuit implementation
is done through cost criteria.
• Literal Cost considers number of times variables
appear in an expression, complemented or
uncomplemented.
• Gate Input Cost considers total number of inputs to
different logic gates.
• A total cost is defined which consider Gate Input Cost
and number of logic gates used.
• Consideration of shared terms in multiple functions
can lead to an overall minimized circuit with less cost.
• Don’t Care conditions are useful in deciding shared
terms that can be generated for minimized circuit.
Goutam Saha
Static 1 Hazard
Lecture 14
Concepts Covered:
 Propagation Delay and Glitch
 Static 1 Hazard
 Detection of Static 1 Hazard
 Covering of Static 1 Hazard

Minimization and Propagation Delay
A’.C
Truth Table is
realized by
Y = A’.C + A.B
A.B
B.C
B.C : Redundant P.I. Its inclusion increases cost ‘unnecessarily’.

Effect of propagation delay in logic gates is not considered.
Propagation Delay in Logic Gate
Prop. Delay: TTL ≈ 10 ns

Logic operations realized by logic gates CMOS ≈ 50 ns
have finite propagation delay. (depends on load; also,
supply voltage for CMOS)
Glitches and Hazards in Logic Circuit
• Glitches are undesired positive or negative going pulse in
a digital logic circuit.
• Glitch occurs due to finite propagation delay of logic
gates and occurs for specific combinations of input
(not for other combinations)
• Glitch is transient in nature and has short duration (≈ ns).
• A logic circuit has Hazard if there is a potential for glitch.

• A circuit with hazard may generate glitch depending on
input combination.
Example of Glitch
Consider, B = 1, C = 1 B = 1, C = 1, A : 1 → 0
Then, Y = A’.1 + 1.A Glitch occurs: Due to
= A’ + A propagation delay of
=1 NOT gate, both AND
i.e. Y = 1, always Gates have 0 in one of
for B = 1, C = 1 the inputs for a short
as per Boolean Algebra duration.
Y = A’.C + A.B
Glitch: B = 1, C = 1, A : 1 → 0
No Glitch: B = 1, C = 1, A : 0 → 1
Static 1 Hazard
A’ + A = 1
Glitch
In Static 1 Hazard, output should
remain static at 1 according to
Boolean Logic but glitch occurs
under certain conditions.
Detecting Static 1 Hazard
• Two logically adjacent cells with output 1 in K-Map not
covered by a common product term.
• Boolean expression produces (A + A’) for certain condition.
Y = B.C + A.C’.D’
ABD = 110, Y = C + C’
Glitch: Static 1 Hazard
Y = B’.C + A.B Y = B’.C + B.C’ ABCD : 1110 → 1100
AC = 11, Y = B + B’ No Hazard for one
Glitch, ABC : 111 → 101 variable changing
Covering Static 1 Hazard
Y = A’.C + A.B + B.C Y = B.C + A.C’.D’ + A.B.D’
Hazard-free by covering Hazard-free circuit

with common product term
(redundant in SOP minimization)
References:
Conclusion:
• Logic Circuit Minimization on its own does not
consider the effect of propagation delay.
• Glitches are undesired, short duration pulse that may
occur in a transition due to finite propagation delay
for certain input combination.
• A circuit with a potential for glitch is considered to
have hazard.
• In Static 1 Hazard, output should remain at Static 1
but glitch may occur.
• Static 1 Hazard can be detected by examining the K-
Map or Boolean expression.
• Circuit can be made hazard-free by covering the
hazard(s) by additional term(s), otherwise redundant.
Goutam Saha
Static 0 Hazard and

Dynamic Hazard
Lecture 15
Concepts Covered:
 Static 0 Hazard
 Detection and Cover of Static 0 Hazard
 Dynamic Hazard
Static 0 Hazard
A.A’ = 0
Y = (A + C).(A’ + B)
B = 0, C = 0
Glitch
A:0→1
In Static 0 Hazard, output Glitch occurs
should remain static at 0
according to Boolean Logic
but glitch occurs under
certain input condition.
Detecting Static 0 Hazard
• Two logically adjacent cells with output 0 in K-Map not
covered by a common sum term.
• Boolean expression (A.A’) for certain condition.
Y = (A + C).(C + D’).(B + C’)

Glitch: Static 0 Hazard
ABCD : 0001→ 0011
1001→ 1011
Y = (A + B’).(B + C) Y = (B + C).(B’ + C’) 0000→ 0010
Glitch, ABC : 000 → 010 No Hazard for one
Static 0 Hazard variable changing
Static 0 Hazard and its Cover
Y = (A + C).(C + D’).(B + C’)

Y = (A + C).(A’ + B).(B + C) .(B + D’).(A + B)
Hazard-free circuit
(B + C) = 0 for B = 0, C = 0
This OR gate output when fed
Hazard-free by covering logically
to AND gate, suppresses glitch. adjacent 0s with common sum term
Hazard in NAND-NAND, NOR-NOR Circuit
1 0 Static 1 and Static 0
0 1
1 0 Hazards can be
1 0 avoided by adding
0
delay (controlled) in
1
0 the transition path.
1 1 0
Y = A’.C + A.B
Y = (A + C).(A’ + B)
B = 1, C = 1 Cover: (B.C)’ as Cover: (B + C)’
B = 0, C = 0
A:1→0 3rd input to as 3rd input to
A:0→1
Glitch occurs output NAND output NOR
Glitch occurs
Dynamic Hazard
• Potential for multiple transitions before settling to 0 1 0 1
final value while Boolean logic asks for only one
transition.
1 0 1 0
• One input variable is to have three or more paths to
the output.
• No. of levels three or more.
• For specific combination of input variables, Boolean
expression reduces to (A + A’).A or A + A’.A
Dynamic Hazard: Example
Y = (A.C + B.C’).(CD)’
To prevent, cover implicit Static 1.

Y = (A.C + B.C’ + A.B).(CD)’
Convert to 2-level circuit
and cover Hazard, if any.
References:
Conclusion:
• In Static 0 Hazard, output should remain static at 0
but glitch occurs for certain input combination.
• Static 0 hazard can be detected by examining the K-
Map or Boolean expression.
• Static 0 hazard can be avoided by including additional
sum terms.
• Static 0 and Static 1 Hazards can be removed by
adding appropriate delay.
• In Dynamic Hazard, potential for multiple transitions
exist while the logic relation asks for one.
• Dynamic Hazard requires 3 or more level circuit.
• Dynamic hazard has implicit Static 1, Static 0 hazard
which if covered, can avoid its occurrence.
Goutam Saha
Multiplexer: Part I
Lecture 16
Concepts Covered:
 Week 3 Recap.
 Multiplexer Basics
 Higher Order Multiplexer from Lower Order
 Multiplexer and Shanon’s Expansion Theorem

Week 3 Recap.
• Simplification of 5-variable function using Karnaugh Map requires 3D visualization. It is difficult to
simplify using K-Map if no. of variables is more than 4.
• In Entered Variable Map based minimization, when a variable enters K-Map, the size of the K-Map
reduces by a factor of 2.
• QM algorithm is useful for computer program based simplification of Boolean Expression containing
large number of variables.
• Comparison of different logic circuit implementation is done through cost criteria.
• Consideration of shared terms in multiple functions can lead to an overall
minimized circuit with less cost.
• Glitches may occur in a circuit due to finite propagation delay for certain input
combination. A circuit with a potential for glitch is considered to have hazard.
• Circuit can be made hazard-free by covering the hazard(s) by otherwise
redundant additional term(s).
If-Then-Else Y = A’.C + A.B If A (i.e. A = 1)
Then, Y = B
A B C Y
Else, Y = C
0 0 0 0
0 0 1 1 A Y
0 1 0 0
0 C
0 1 1 1
1 0 0 0
1 B
1 0 1 0
1 1 0 1
1 1 1 1
Multiplexer
A multiplexer steers one of
S0 Y
the many inputs to an output
Y = A’.C + A.B 0 D0 based on control input(s).
1 D1
Consider,
A = Control (Select)
input, S0 D0 0 D0
B = Data input, D1 2-to-1
Y
MUX Y
C = Data input, D0
D1 1 D1
S0
Y = S0’.D0 + S0.D1
S0
4-to-1 Multiplexer
D0 00
S1 S0 Y Y = S1’S0’D0 + S1’S0D1 + S1S0’D2 + S1S0D3 D1 01 4-to-1
0 0 D0 D2 10 MUX
Y
0 1 D1
D3 11
1 0 D2
1 1 D3 S1 S0
D0
D1
Y
D2
D3
S1S0
4-to-1 MUX from 2-to-1 MUX
D0 0
2-to-1
MUX
Y = S1’S0’D0 + S1’S0D1 + S1S0’D2 + S1S0D3 D1 1 0
F0
= S1’.(S0’D0 + S0D1) + S1.(S0’D2 + S0D3) 2-to-1
Y
S0 MUX
= S1’.F0 + S1.F1 F1 1
D2 0
2-to-1 S1
MUX
D3 1
S0
Higher order MUX from lower order
D0 00 F0 00
D0 000
D1 01 4-to-1 01 4-to-1
D1 001 Y
D2 10 MUX 10 MUX
D2 010 F0 0
D3 11 F1 11
D3 011 8-to-1 2-to-1
Y MUX Y
S1 S0
D4 100 MUX F1 S2
1
D4 00
D5 101
D5 01 4-to-1 S2
D6 110
D6 10 MUX
D7 111
D7 11
S2 S1 S 0
S1 S0
Higher order MUX from lower order
32-to-1 MUX from

16-to-1 MUX
and 2-to-1 MUX
8-to-1 MUX using

only 2-to-1 MUX
Shanon’s Expansion Theorem and MUX
Shanon’s Expansion Theorem: (inherent If-Then-Else) F(0, x2, x3, …, xN) 0
2-to-1
F(x1, x2, x3, …, xN) = x1’.F(0, x2, x3, …, xN) MUX
Y
+ x1.F(1, x2, x3, …, xN) F(1, x2, x3, …, xN) 1
Y = S1’S0’D0 + S1’S0D1 + S1S0’D2 + S1S0D3 x1

= S1’.[0’.S0’D0 + 0’.S0D1 + 0.S0’D2 + 0.S0D3] + S1.[1’.S0’D0 + 1’.S0D1 + 1.S0’D2 + 1.S0D3]
= S1’.(S0’D0 + S0D1) + S1.(S0’D2 + S0D3)
F(x1, x2, x3, …, xN) = x1’.[x2’.F(0, 0, x3, …, xN) + x2.F(0, 1, x3, …, xN)]
+ x1.[x2’.F(1, 0, x3, …, xN) + x2.F(1, 1, x3, …, xN)]
Shanon’s Expansion Theorem and MUX
F(A,B,C) = A’B’C’.D0 + A’B’C.D1 + A’BC’.D2 + A’BC.D3

+ AB’C’.D4 + AB’C.D5 + ABC’.D6 + ABC.D7
A B C F(A,B,C)
0 0 0 1 D0 = 1
0 0 1 0 D1 = 0
0 1 0 0 D2 = 0
0 1 1 1 D3 = 1
… … … …
References:
Conclusion:
• A multiplexer steers one of the many inputs to an
output based on control input(s).
• n control inputs can select up to 2n data inputs and
steer it towards output.
• Higher order multiplexer can be obtained from lower
order by cascading.
• Lower order multiplexer can be obtained from higher
order by appropriate connection of select inputs.
• Shanon’s expansion theorem and its inherent if-then-
else structure is useful in getting insights of
multiplexer operation.
Goutam Saha
Multiplexer: Part II
Lecture 17
Concepts Covered:
 Multiplexer with Strobe Input
 Multiplexer as Universal Logic Circuit
 Nibble Multiplexer
STROBE B A Y
IC 74153 (G)
H X X L
L L L C0
L L H C1
L H L C2
L H H C3
IC 74153
Y = E’.[(B’.A’).C0 + (B’.A).C1 +
(B.A’).C2 + (B.A).C3]
Multiplexer with inverted output
Di = Ei
……….………………………….
Control inputs
Y = (E’.A’B’C’D’.D0 + E’.A’B’C’D.D1 + …
…. + E’.ABCD’.D14 + E’.ABCD.D15)’
IC 74153 Y = F(A,B,C)
= ∑ m (0,2,3,6,7)
IC 74151
Y = E’.[(B’.A’).C0 + (B’.A).C1 + 1 000 8-to-1 MUX
(B.A’).C2 + (B.A).C3] with STROBE (EN’),
0 001 both non-inverted
B A Y 0 00 1 and inverted output
010
F(0,0) L L 0 1 01 4-to-1 1 011 8-to-1
F(0,1) L H 1 Y Y
1 10 MUX 0 100 MUX
F(1,0) H L 1
0 11 0 101
F(1,1) H H 0
1 110
Y = B’.A + B.A’ B A
1 111
Y = (B’.A’).0 + (B’.A).1 + ½ IC 74153, E = 0
(B.A’).1 + (B.A).0 A B C
Multiplexer as Universal Logic Circuit
Y = (E’.A’B’C’D’.D0 + E’.A’B’C’D.D1 + …
…. + E’.ABCD’.D14 + E’.ABCD.D15)’
E = 0,
Y’ = A’B’C’D’.D0 + A’B’C’D.D1 + …
…. + ABCD’.D14 + ABCD.D15
Y = F(A,B,C,D)
= ∑ m (0,2,3,4,5,8,9,
10,11,12,13,15)
Y’ = ∑ m(1,6,7, 14)
Entered Variable and Multiplexer
C’ 00
1 01 4-to-1
1 000 A B C Y Y
0 10 MUX
0 001 0 0 0 1
Y=C’ A B Y 1 11
1 010 0 0 1 0
1 011 8-to-1 0 1 0 1 0 0 C’
Y Y=1 A B
0 100 MUX 0 1 1 1 0 1 1
½ IC 74153, E = 0
0 101 1 0 0 0 1 0 0
Y=0
1 110 1 0 1 0 1 1 1
1 111 1 1 0 1
Y=1 Y = F(A,B,C)
1 1 1 1 = ∑ m (0,2,3,6,7)
A B C
8-to-1 MUX and 4-variable function
IC 74151
Y = F(A,B,C,D) EN = 0
= ∑ m (0,2,3,4,5,8,9,
10,11,12,13,15)
}
}
Nibble Multiplexer
IC 74157
Nibble Multiplexer with Tristated Output
OE’ SELECT Y
H X High Z
L L A
L H B
IC 74257
References:
Applications 8e, McGraw Hill\
Conclusion:
• Output is held at H or L value if Strobe or Enable control
input of multiplexer chip is not activated. Usual
multiplexer operation when it is enabled.
• Multiplexer can be used as universal logic circuit that
combines all minterms generated of select inputs.
• Multiplexer with active low output requires
appropriate consideration of minterm combination.
• Concept of entered variable is useful in realizing logic
function with lower order multiplexer.
• Multiplexer with tristated output has additional control
input which if not enabled keep output at high
impedance.
• Nibble multiplexer selects one of the two sets of nibble
(4-bits) based on select input.
Goutam Saha
Demultiplexer / Decoder
Lecture 18
Concepts Covered:
 Demultiplexer Basics
 Higher Order Demultiplexer from Lower Order
 Decoder Basics
 Use of Demultiplexer as Decoder
 Decoder and Multiple Output Function

Demultiplexer
Y0 = S0’.D
D0 Y0
Y D
D1 Y1
S0 (MUX) Y1 = S0.D
S0 (DEMUX)
0 Y0 S0 Y0 Y1 A demultiplexer steers
D
1-to-2
0 D 0 the input to one of the
DEMUX
1 Y1
many outputs based on
1 0 D control input(s).
S0
1-t0-4 Demultiplexer
S1 S0 Y0 Y1 Y2 Y3
00 Y0 Y0 = S1’S0’.D
0 0 D 0 0 0
1-to-4 01 Y1 Y1 = S1’S0.D
D 0 1 0 D 0 0
DEMUX 10 Y2 Y2 = S1S0’.D
1 0 0 0 D 0
11 Y3 Y3 = S1S0.D
1 1 0 0 0 D
S1 S0
IC 74155
1Y0 = (B’A’.G1’.1C)’
B A G1 C1 1Y0 1Y1 1Y2 1Y3 1Y1 = (B’A.G1’.1C)’
X X H X H H H H …………..
X X X L H H H H 2Y0 = (B’A’.G2’.2C’)’
L L L H L H H H 2Y1 = (B’A.G2’.2C’)’
L H L H H L H H …………..
H L L H H H L H
H H L H H H H L
B A G2 C2 2Y0 2Y1 2Y2 2Y3

L L L L L H H H
…………..
IC 74155: Dual 1-to-4 DEMUX

1-to-16 Demultiplexer IC 74154: 1-to-16 DEMUX
Y0 = (A’B’C’D’.DATA’.STROBE’)’
Y1 = (A’B’C’D.DATA’.STROBE’)’
………………
Y31 = (ABCD.DATA’.STROBE’)’
If STROBE = 0 and A = 0,
select inputs BCD steers
DATA to one of Y0 … Y7
outputs: 1-to-8 DEMUX.
Higher order DEMUX from lower order
Y0 00 F0
00
0 Y0 01
1-to-4 01 Y1 D 1-to-4
1-to-2 DEMUX 10 DEMUX 10
Y2
DEMUX 11 F1
1 Y1 0 11 Y3
0 F0
1-to-2
1-to-2 D
D DEMUX S1 S0
DEMUX S0 F1 S2
1 Y4
1 00
0 Y2 01 Y5
S2 1-to-4
S1 1-to-2 DEMUX 10 Y6
DEMUX
1 Y3 1-to-8 DEMUX from 11 Y7
1-to-4 DEMUX from 1-to-4 DEMUX
1-to-2 DEMUX and 1-to-2 DEMUX
S0 S1 S0
Higher order DEMUX using Strobe
Y0 = (B’C’D’E’.DATA’.A’)’
Y1 = (B’C’D’E.DATA’.A’)’
………………
Y16 = (B’C’D’E’.DATA’.A)’
………………
Y31 = (BCDE.DATA’.A)’
IC 74155: 1-to-8
from dual 1-to-4
Select = 1C = 2C’
Data = 1G = 2G
Decoder
A decoder decodes input bit pattern by appropriate logic and activates
the output when specific combination is present.
00 Y0
To decode AB = 01 A
(active HIGH) 00 Y0 Y0 = S1’S0’.D 2-to-4 01 Y1
Decoder 10 Y2
D 1-to-4 01 Y1 Y1 = S1’S0.D B
DEMUX 10 11 Y3
Y2 Y2 = S1S0’.D
11 Y3 Y3 = S1S0.D
To decode AB = 11 HIGH
S1 S0
IC 74154 as Decoder
Chip expansion /
IC 74154 as Higher order from
4-to-16 Decoder lower order:
Similar to DEMUX
Output
Y0-15 Y16-31
Active LOW
Decoder for Multiple Output
• Decoder generates all

the minterms.
• OR gate sums up
minterms defining a
function.
References:
Conclusion:
• A demultiplexer steers the data input to one of the
many outputs based on control input(s).
• With n control inputs, the data input can be steered to
up to 2n outputs.
• Strobe or Enable input of a demultiplexer chip need to
be active for usual operation.
• Higher order demultiplexer can be obtained from lower
order and vice versa by appropriate connection.
• A decoder decodes input bit pattern and activates the
output when specific combination is present.
• Demultiplexer circuit can be made to act as decoder e.g.
1-to-4 Demultiplexer can act as 2-to-4 Decoder.
• Decoder generates all minterms. Decoder-OR
combination can generate multiple outputs.
Goutam Saha
Decoder with BCD Input

and Encoder
Lecture 19
Concepts Covered:
 BCD to Decimal Decoder / Driver
 BCD to 7-segment Decoder / Driver
 Encoder Basics
 Priority Encoder
BCD-to-Decimal Decoder
Input IC 7445: BCD-to-Decimal Decoder / Driver
Active HIGH
Open collector output
SN7445 can sink up to 80 mA
(SN7404, standard inverter sinks 16 mA max.)
DCBA: LLLL, 0: L, 1-9: H

DCBA: LLLH, 0: H, 1: L, 2-9: H
DCBA: LLHL, 0-1: H, 2: L, 3-9: H
…
DCBA: HLLH, 0-8: H, 9: L
-----
DCBA: HLHL, 0-9: H,
…
Output
Active LOW DCBA: HHHH, 0-9: H
Decoder / Driver driving LED
If LED drop = 1.6 V

Resistance = 330 Ω
VCE(Sat.) = 0.1 V
LED current
= (5 – 1.6 – 0.1) / 330
= 10 mA
BCD-to-7 Segment Decoder / Driver
Common
Anode type
Output
Active LOW
a = F(A,B,C,D) = ∑ m(0,2,3,5,6,7,9)
b = F(A,B,C,D) = ∑ m(0,1,2,3,4,7,8,9)
…
IC 7446 has other control inputs for

additional functionality e.g. blanking of
leading zero, lamp test etc.
Encoder A decimal-to-BCD
encoder
An encoder converts an active input Only one of the 0 to 9
signal to a coded output signal. input is to connect
0: DCBA = 0000
1: DCBA = 0001
2: DCBA = 0010
…
1 & 2: DCBA = 0011
1 & 3: DCBA = 0011
n ≤ 2m
Concept of Priority Encoder
D1D0
D3D2 00 01 11 10
D1D0 00 X 0 1 1
D3 D2 D1 D0 C1 C0 D3D2 00 01 11 10
01 0 0 0 0
1 X X X 1 1 00 X 0 0 0 D2 D2’.D1
11 1 1 1 1
0 1 X X 1 0 01 1 1 1 1
10 1 1 1 1
0 0 1 X 0 1 11 1 1 1 1
10 1 1 1 1 D3
0 0 0 1 0 0 C0
D3
C1
C1 = D3 + D2
Also, from Karnaugh Map
C0 = D3 + D2’.D1
(D1 if not D2, due to priority)
Priority Encoder: Decimal-to-BCD
IC 74147: Decimal-to-BCD
Priority Encoder
Higher number has higher priority.
Input and Output: Active Low
9: L, DCBA: LHHL
9: H, 8: L, DCBA: LHHH
9-8: H, 7: L, DCBA: HLLL
…
9-2: H, 1: L, DCBA: HHHL
9-1:H, DCBA: HHHH
D = (8’ + 9’)’
C = [(8’ + 9’)’.(7’+6’+5’+4’)]’
Priority Encoder: 8-to-3 IC 74148: 8-to-3 Priority Encoder
EI = H, A2-0: HHH, GS: H, EO: H

EI = L, 0 – 7: H, A2-0: HHH, GS: H, EO: L
EI = L, 7: L, A2-0: LLL, GS: L, EO: H
EI = L, 7: H, 6:L, A2-0: LLH, GS: L, EO: H
EI = L, 7 - 6: H, 5:L, A2-0: LHL, GS: L, EO: H
…
EI = L, 7 - 1: H, 0:L, A2-0: HHH, GS: L, EO: H
The higher the number, the

higher is the priority.
Input and Output:
Active Low
Higher Order from Lower Order
EI = H, A2-0: HHH, GS: H, EO: H

EI = L, 0 – 7: H, A2-0: HHH, GS: H, EO: L
EI = L, 7: L, A2-0: LLL, GS: L, EO: H
…
GS: Group Signal Output,
indicates presence of active input
EI and EO: Useful for cascading
IC 7408
Quad, 2-input
AND gate
References:
Conclusion:
• Decoder / Driver is capable of providing higher
current through open collector output e.g. BCD-to-
Decimal and BCD-to-7 Segment Decoder / Driver.
• An encoder converts an active input signal to a
coded output signal.
• Priority encoder is useful when more than one input
is active. The output is according to priority assigned
to input.
• Certain priority encoders can be cascaded to encode
larger number of inputs.
Goutam Saha
Parity Generator and

Checker
Lecture 20
Concepts Covered:
 Exclusive-OR Gate
 Even and Odd Parity
 Parity Generation
 Parity Checking
Exclusive-OR Gate
A B Y
0 0 0
0 1 1 AꚚ0 = A
1 0 1 AꚚ1 = A’
1 1 0
Y = A’.B + A.B’ = AꚚB

Multi-input Exclusive-OR If A = 1, Y = (BꚚCꚚD)’
• If no. of 1s in input
A B C D Y A B C D Y combination is odd,
0 0 0 0 0 1 0 0 0 1 then the output is 1,
else, output is 0.
0 0 0 1 1 1 0 0 1 0
• This happens for any
0 0 1 0 1 1 0 1 0 0 number of inputs
0 0 1 1 0 1 0 1 1 1 e.g. 2,3,4,5,6,7, …
0 1 0 0 1 1 1 0 0 0
0 1 0 1 0 1 1 0 1 1
0 1 1 0 0 1 1 1 0 1
0 1 1 1 1 1 1 1 1 0
Y = AꚚBꚚCꚚD If A = 0, Y = BꚚCꚚD AꚚ0 = A

AꚚ1 = A’
Even Parity and Odd Parity
• Even Parity: In the input bits, there is even number of 1s. TI’s DS90C031,DS90C032 line
Example: For, 4-bit input: 1001, 1100, 1111 transmitter, receiver under test
8-bit input: 11000101, 01111011 condition gives bit error rate
16-bit input: 1011001110110011 (BER) less than 1 per 1012 bits.
• Odd Parity: In the input bits, there is odd number of 1s.

Example: For, 4-bit input: 0001, 1101, 1110
8-bit input: 11000001, 01011011
16-bit input: 1011001010110011
• Prior information about parity (even or odd) in the message

can help in detecting 1-bit error.
Parity Generation • The aim here is to add a parity
bit with the message so that
message and parity bit together
make it of a predefined parity
(even or odd).
• The message is random i.e. can
be of even or odd parity.
Example: Instead of
8 bits (message), 9
bits (message +
parity bit) sent.
Parity Checking
Odd parity checking by
For 9-bit data received with pre-defined Ex-OR, Odd parity
parity (even or odd). generation by Ex-NOR
(i.e. EX-OR then NOT)
Similarly, for Even Parity.
Example of 16-bit odd

parity checking
IC 74180
9-bit (8 data bits, 1 parity bit)
parity generator / checker.
• For 9-bit parity checking even /

odd input can be used as 9th bit.
• It can also be used for cascading to
work on larger number of bits.
Example with IC 74180
Use of IC 74180 to
generate odd parity
Higher Order from Lower Order
X15 … X8 X7 … X0 Lower order from
8 8
Higher Order: Connect
Even in Even in unused inputs to GND.
+5V
74180 Odd in 74180 Odd in
GND
Even Odd Even Odd

Out Out Out Out
16-bit parity checking by cascading two 74180

References:
Conclusion:
• The output of a 2-input Ex-OR gate is 1 when only
one of the input is 1. For more than 2-input Ex-OR
gate, output is 1 if there are odd no. of 1s at input.
• Even parity refers to presence of even no. of 1s in bit
patterns and odd parity refers to odd no. of 1s.
• Parity bit is generated to make the bit combination
that includes the parity bit one of even or odd parity.
• Parity generation and checking involve multi-input
Ex-OR gate circuit.
• Higher order parity generator / checker circuit can be
obtained by cascading lower order circuits.
• Parity check is useful in detection of error when a
group of bits is transmitted.
Goutam Saha
Number System
Lecture 21
Concepts Covered:
 Week 4 Recap.
 Number System
 Binary to Decimal and Decimal to Binary
 Octal and Hexadecimal Representation
 Fixed-point and Floating-point Representation

Week 4 Recap.
• A multiplexer steers one of the many inputs to an output based on control input(s). n control inputs
can select up to 2n data inputs.
• Higher order multiplexer can be obtained from lower order by cascading. Lower order multiplexer
can be obtained from higher order by appropriate connection of select inputs.
• Multiplexer can be used as universal logic circuit that combines all minterms generated of select
inputs. Concept of entered variable is useful in realizing logic function with lower order multiplexer.
• A demultiplexer steers the data input to one of the many outputs based on control input(s). Higher
order demultiplexer from lower order or the reverse can be obtained by appropriate connection.
• A decoder decodes input bit pattern and activates the output when a specific
combination is present. Demultiplexer and decoder circuit are basically same.
• Decoder generates all minterms. Decoder-OR combination gives multiple outputs.
• An encoder converts an active input signal to a coded output signal. In priority
encoder, the output is according to priority assigned to active inputs.
• Parity generation and checking involve multi-input Ex-OR gate circuit.
Working of an odometer
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
0 0 0 0 2 0 0 0 0 2 0 0 0 1 0
0 0 0 0 3 0 0 0 0 3 0 0 0 1 1
0 0 0 0 4 0 0 0 0 4 0 0 1 0 0
Decimal system
0 0 0 0 5 0 0 0 0 5 0 0 1 0 1
(we are used to) Binary
0 0 0 0 6 0 0 0 0 6 0 0 1 1 0 system
Octal
0 0 0 0 7 0 0 1 1 1
system 0 0 0 0 7
0 0 0 0 8 0 0 0 1 0 0 1 0 0 0
0 0 0 0 9 0 0 0 1 1 0 1 0 0 1
0 0 0 1 0 0 0 0 1 2 0 1 0 1 0
Concept of place value
1 x 101 + 0 x 100 Base or radix – r

di = {0,1, …, r - 1)
Octal
0 0 0 1 0 1 x 81 + 0 x 80
dn … d1d0.d-1d-2 … d-m
1 x 21 + 0 x 20 = dn x rn + … + d1 x r1 + d0 x r0
+ d-1 x r-1 + d-2 x r-2 + … + d-m x r-m
1010 in binary: 1 x 23 + 0 x 22 + 1 x 21 + 0 x 20
12 in octal: 1 x 81 + 2 x 80
Binary to Decimal Conversion
Binary Decimal
23 22 21 20 2-1 2-2 2-3 2-4
Binary Number Decimal Value 11 3
b3 b2 b1 b0
. b-1 b-2 b-3 b-4
1 20 = 1 111 7
8 4 2 1 1⁄
2
1⁄
4
1⁄ 1⁄
8 16
10 21 = 2 1111 15
binary 1111 1111 255
100 22 = 4
point
1000 23 = 8
10000 24 = 16
(1010.101)2
= (1 x 23 + 0 x 22 + 1 x 21 + 0 x 20 10000 0000 28 = 256
+ 1 x 2-1 + 0 x 2-2 + 1 x 2-3)10 100 0000 0000 210 = 1024 (1 K)
= (8 + 2 + 0.5 + 0.125)10 1000 0000 0000 211 = 2048 (2 K)
= (10.625)10 10000 0000 0000 0000 0000 220 = 1024 K (1 M)
Decimal to Binary Conversion
Number Multiplied Carry Fraction
Conversion of (10)10 by
Number Divide by Quotient Remainder 0.625 2 1 (MSB) 0.25
10 2 5 0 (LSB) 0.25 2 0 0.5

0.5 2 1 (LSB) 0
5 2 2 1
2 2 1 0
Conversion of (0.625)10
1 2 0 1 (MSB)
Integer Fraction
(10)10 = (1010)2 (0.625)10 = (0.101)2

More Example
(23.6)10 = (10111.10011)2
(fractional part truncated at 5 bits)
• Convert (23.6)10 to binary
No. X Carry Fraction
No. ÷ Quot. Remainder 0.6 2 1 0.2
23 2 11 1 0.2 2 0 0.4
11 2 5 1 0.4 2 0 0.8
5 2 2 1 0.8 2 1 0.6
2 2 1 0 0.6 2 1 0.2
1 2 0 1 0.2 … … …
Conversion of 23 Conversion of 0.6

Integer part Fractional part
Octal and Hexadecimal Representation
Similar to binary
Octal / Hex to Decimal:
Octal: Base – 8 Hexadecimal: Base – 16
Using base 8 / 16
Valid digits: 0,1,2,3,4,5,6,7 Valid digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Decimal to Octal / Hex:
82 81 80 8-1 8-2 162 161 160 16-1 16-2 Int.: Division by 8 / 16
Frac.: Multi. by 8 / 16
o2 o1 o0
. o-1 o-2 h2 h1 h0
. h-1 h-2
Hexadecimal point
Octal point
Octal: 35.6 Binary: 011101.110 Hex: 3D.6 Binary: 00111101.0110

= 11101.11 = 111101.011
Binary: 1101110.1011 Octal: 156.54 Binary: 1101110.101101 Hex: 6E.B4

= 001101110.101100 = 01101110.10110100
Fixed-point Representation
• In practice, fixed number of bits are available to represent a binary number.
• In fixed-point representation, (i) width and (ii) position of binary point are defined.
• Similar to integer representation which is a special case where no bit assigned after binary point.
Consider 8 bits stored in memory is: 10011110.
When represented as fixed(8,3), it is
10011.110 = (1 x 24 + 1 x 21 + 1 x 20 + 1 x 2-1 + 1 x 2-2)10 = (19.75)10 Note that, one left shift of
binary point is division by 2
and one right shift is
1001.1110 = (1 x 23 + 1 x 20 + 1 x 2-1 + 1 x 2-2 + 1 x 2-3)10 = (9.875)10
multiplication by 2.
100111.10 = (1 x 25 + 1 x 22 + 1 x 21 + 1 x 20 + 1 x 2-1)10 = (39.5)10
Due to similarity, integer arithmetic circuit can be used directly here.

Floating Point Representation
For fixed(8,4), precision is 2-4 = 0.0625; range is 0000.0000 to 1111.1111 i.e. 0 to 15.9375
For fixed(8,3), precision is 2-3 = 0.125; range is 00000.000 to 11111.111 i.e. 0 to 31.875
If a and b are the bits before and
fixed(8,4) has better precision over fixed(8,3) but lower range. after binary point, respectively
then the range is 2a – 2-b.
In floating-point representation, the binary point is not fixed.
Gap between consecutive numbers is high for larger numbers, small for smaller numbers.
M: Mantissa
E: Exponent E M Number = M x 2E
Normalized representation: 1101.01 = (1.10101) x 23 01110101

References:
Conclusion:
• A number system with base or radix – r has digits 0 to
(r – 1). The place value or weight is multiplied with the
digit to find its contribution.
• To convert decimal to binary, integer is successively
divided by 2 and remainders accumulated; fraction is
successively multiplied by 2 and carry accumulated.
• For octal / hexadecimal system, it is similar to binary
but 8 / 16 replaces 2.
• Octal / Hexadecimal - binary is relationship considers
grouping of 3 / 4 binary digits.
• Fixed-point representation has fixed precision. Fixed-
point arithmetic is similar to integer arithmetic.
• Floating-point representation has variable precision.
Gap between numbers is higher for larger numbers.
Goutam Saha
Negative Number and 2’s

Complement Arithmetic
Lecture 22
Concepts Covered:
 Sign-Magnitude Representation
 1’s Complement Number
 2’s Complement Number
 Binary Addition and Subtraction
 2’s Complement Arithmetic

Sign-Magnitude Number
0000 0001 : +1
1000 0001 : -1
Sign Magnitude
Bit bits 0001 0110 : +22
(MSB) 1001 0110 : -22
0111 1111 : +127
1111 1111 : -127
Range: -127 to +127 i.e. with 8 bits 255 numbers can be represented.
(-127 to -1, 0, +1 to +127)
0 is represented twice: 0000 0000 and 1000 0000
1’s Complement Number
0000 0001 : +1
1111 1110 : -1
Sign Magnitude
Bit bits 0001 0110 : +22
(MSB) 1110 1001 : -22
0111 1111 : +127
Negative number representation is obtained by taking 1000 0000 : -127
1’s complement or inversion of positive counterpart.
Range: -127 to +127 i.e. with 8 bits 255 numbers can be represented.
(-127 to -1, 0, +1 to +127)
0 is represented twice: 0000 0000 and 1111 1111
2’s Complement Number 1111 1110
+ 1
0000 0001 : +1 --------------
1111 1111 : -1 1111 1111 (2’s C)
0001 0110 : +22 1110 1001

Sign Magnitude
Bit bits
1110 1010 : -22 + 1
--------------
(MSB) 0111 1110 : +126 1110 1010 (2’s C)
1000 0010 : -126
Negative number representation is obtained by 0111 1111 : +127
adding 1 to 1’s complement of positive counterpart. 1000 0001 : -127
1000 0000 : -128
Range: -128 to +127 i.e. with 8 bits 256 numbers can
be represented. (-128 to -1, 0, +1 to +127)
0 is represented once: 0000 0000
2’s Complement of 2’s Complement
0000 0001 : +1 0000 0000

1111 1111 : -1 + 1
2’s C 2’s C
-------------- X -X - ( - X) = X
0000 0001
0001 0110 : +22

1110 1010 : -22
0001 0101
+ 1
--------------
0001 0110
Binary Addition and Subtraction
(1): Borrow
0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 10 0 – 0 = 0, 1 – 0 = 1, 1 – 1 = 0, 0 – 1 = (1)0 – 1 = (1)1
1 Borrow • Done here as done for standard
0 001 0101 (21)10 1 decimal subtraction; borrowed is 2
0 001 0101 (21)10 (binary) instead of 10 (decimal)
+ 0 010 0001 (33)10
- 0 000 0010 ( 2)10 from next higher position.
----------------- ------
---------------- ------
0 011 0110 (54)10 • Sign is changed if smaller
Sign 0 001 0011 (19)10
number is subtracted from
bit
larger number as in decimal
Carry
Borrow e.g. 5 – 8 = - (8 – 5) = -3
111
11 11 i.e. 0 0101 – 0 1000
0 001 0111 (23)10
0 110 0101 (101)10 = 1 0011
+ 0 110 0101 (101)10
- 0 001 0111 ( 23)10
----------------- -------
---------------- ---------
0 111 1100 (124)10
0 100 1110 (78)10
2’s Complement Arithmetic Carry
1
(83)10 : 0101 0011
• Addition follows standard process. (83)10 + (16)10 + (16)10 : + 0001 0000
• Subtraction by taking 2’s complement of subtrahend (i.e. ------------------------------
(99)10 : 0110 0011
making it negative) and adding it with minuend Minuend
- Subtrahend
-----------------
(83)10 – (16)10 = (83)10 + (-16)10
Difference
Subtrahend (16)10 = (0001 0000)2

0101 0011 If carry is generated,
1’s C + 1111 0000 discard it and answer
0001 0000 1110 1111
-----------------
(16)10
1111 0000 is positive.
1 0100 0011
(-16)10
Carry (0100 0011)2 = (67)10
2’s Complement Arithmetic
Minuend
• Subtraction of larger number from smaller number Subtrahend
---------------
If no carry and the sign bit Difference
(16)10 – (83)10 = (16)10 + (-83)10 is 1, the answer
is negative and in 2’s
Subtrahend (83)10 = (0101 0011)2
Complement form.
1’s C
0101 0011 1010 1100 0001 0000 1’s C
(83)10 1011 1101 0100 0010
1010 1101 + 1010 1101
(-83)10 ----------------- 0100 0011
Note: 1011 1101
1010 1101
1’s C
0101 0010 (0100 0011)2 = (67)10
2’s C
0101 0011 (1011 1101)2 = (- 67)10
Minuend
• Subtraction from a negative number Subtrahend
If carry then discard it, if the ---------------
(- 83)10 – (16)10 = (-83)10 + (-16)10 sign bit is 1 then the answer Difference
is negative and in 2’s
Complement form.
(-83)10 = 1010 1101 1010 1101
+ 1111 0000
(-16)10 = 1111 0000 ----------------- 1’s C
1001 1101 0110 0010
11001 1101
0110 0011
(0110 0011)2 = (99)10

2’s C
(1110 1101)2 = (- 99)10
Minuend
• Subtraction of a negative number For subtraction,
Subtrahend
(i) Take 2’s C of the subtrahend ---------------
(83)10 – (-16)10 = (83)10 + (16)10 (ii) Add it with Minuend Difference
(iii) Discard carry, if any
(iv) If sign bit is 0, answer positive
(83)10 = 0101 0011 and can be directly read.
(v) If sign bit is 1, answer is
(-16)10 = 1111 0000 0101 0011
+ 0001 0000 negative and in 2’s C form
2’s C ----------------- (Take 2’s C to find the magnitude
0110 0011 in binary coding i.e. number with
(16)10 = 0001 0000 position weights ..8421).
(99)10
References:
Conclusion:
• Sign-Magnitude representation has a separate sign bit.
Using 8-bits, range of number: -127 to +127
• In 1’s C representation, -ve no. is obtained by 1’s C or
inversion of positive counterpart; range: -127 to +127.
• In 2’s C representation, -ve no. is obtained by adding 1
to 1’s C number; range: -128 to +127.
• In binary addition, carry may be generated. In binary
subtraction, borrow may be there.
• In 2’s C arithmetic, subtraction is done by considering
addition of –ve number.
• For 2’s C arithmetic, rules can be framed to get the
result for all possible cases of addition / subtraction.
Goutam Saha
Arithmetic Building Blocks - I

Lecture 23
Concepts Covered:
 Half Adder
 Full Adder
 Ripple Carry Adder
 Adder – Subtractor Circuit

Half Adder
Input Output A C
A B C S H. A.
0 0 0 0 B S
0 1 0 1
1 0 0 1
1 1 1 0
Augend A C = A.B
Addend B
----------- S = A’.B + A.B’ = A B
C Carry Sum S
Full Adder
A Cout
Input Output
F. A.
Cin A B Cout S
B S
0 0 0 0 0
0 0 1 0 1
Cin
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0 Cout = A.B + A.Cin + B.Cin
1 1 1 1 1 S = A B Cin
Full Adder using Half Adder
F.A.
Full Adder:
Cout = A.B + Cin.(A + B)
= A.B + Cin(A’.B + A.B’ + A.B)
= A.B + Cin.A.B + Cin(A.B’ + A’.B) H.A.1
H.A.2
= A.B.(1 + Cin) + Cin(A.B’ + A’.B)
= A.B + Cin.(A B)
S = A B Cin
H.A.: C = A.B
S=A B
Ripple Carry Adder Intermediate
Carry
C2 C1 C0
A3 B3 A2 B2 A1 B1 A0 B0 A3 A2 A1 A0
B3 B2 B1 B0
-----------------
C-1 C3 S3 S2 S1 S0
F. A. F. A. F. A. F. A.
Final Carry
and Sum
C3 S3 C2 S2 C1 S1 C0 S0
Carry 111
(15)10 + (1)10 1111 4-bit Ripple Carry Addition First stage
= (1111)2 + (0001)2 + 0001 can be H.A.
--------- C-1 = 0 (GND)
1 0000
Subtraction using Adder Circuit (15)10 – (1)10
= (1111)2 – (0001)2
A3 A2 A1 A0 B3 B2 B1 B0 2’s C Arithmetic 2’s C

1111
2’s C of B = - B 1110
+ 1
---------
1’s C of B 1 1110
2’s C of B Discard
(1110)2 = (14)10
4-bit F. A. 1 (+5 V)
C-1
Adder circuit performs

C3 S3 S2 S1 S0 A + (- B) = A – B
Adder – Subtract0r Circuit
If SUB = 0, then C-1 = 0 If SUB = 1, then C-1 = 1

Ex-OR gate output = Bi 0 = Bi Ex-OR gate output = Bi 1 = Bi’
F.A. output = A + B F.A. output = A + (-B) = A - B
Example
0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0
90
+ 50
0 ------
140
0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0
0
1 1 1 0 0 1 0
0 1 0 0 0 1 1 0 0
0101 1010 + 0011 0010 = 1000 1100

Example
0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0
90
- 50
1 ------
40
0 1 1 1 0 0 1 0 1 1 0 1 1 0 0 1
1
1 0 1 1 1 1 1
1 0 0 1 0 1 0 0 0
0101 1010 - 0011 0010 = 0101 1010 + 1100 1101 + 1 = 1 0010 1000
References:
Conclusion:
• Half-adder adds two binary digits to generate sum
and carry. Full adder also considers carry input from
previous place and thus has 3 inputs and 2 outputs.
• A full adder unit can be obtained by two half-adders
and one additional OR gate.
• In ripple carry addition, carry output of one full adder
is connected as carry input of next full adder.
• Subtraction can be done by full-adder circuit by 2’s C
method. Here, 2’s C is achieved by bank of NOT gates
and making the carry input 1.
• Full adder and a bank of Ex-OR gates for the
subtrahend / addend input can give a circuit that can
perform both addition and subtraction.
Goutam Saha
Arithmetic Building Blocks - II

Lecture 24
Concepts Covered:
 Propagation Delay in Ripple Carry Adder
 Carry Look Ahead Adder
 Cascading Fast Adders
 Group Carry Generation and Propagation

Delay in Ripple Carry Adder Propagation delay is cumulative.
For n-bit addition, 2nτ delay.
t=0
t = 8τ t = 6τ t = 4τ t = 2τ
C3 available after 8τ delay.
Each basic gate delay = τ
(AND, OR) For S3, A3 B3 result after 2τ.
This is Ex-Ored with C2.
Ci = Ai.Bi + Ai.Ci-1 + Bi.Ci-1 Each Ex-OR gate delay = 2τ C2 available after 6τ.
Si = Ai Bi Ci-1 S3 available after 8τ.
Carry: Serial to Parallel
C0 = G0 + P0C-1 … (1)
Ci = AiBi + AiCi-1 + BiCi-1 C1 = G1 + P1C0 … (2)
Ci = AiBi + Ci-1(Ai + Bi)
Substituting C0 from Eq.(1) in Eq.(2),
Ci = Gi + PiCi-1
C1 = G1 + P1(G0 + P0C-1)
Where, Gi = AiBi : Generation term C1 = G1 + P1G0 + P1P0C-1 … (3)
and Pi = Ai + Bi : Propagation term
2 parallel AND delay: τ
1 OR delay :τ
Gi = 1 : Carry is generated For Gi and Pi, delay : τ
Pi = 1 : Input carry is propagated -------------
Total delay : 3τ
Carry Look Ahead Adder
Si = Ai Bi Ci-1
C2 = G2 + P2C1 … (4) Si = Gi Pi Ci-1
Substituting C1 from Eq.(3) in Eq.(4), (avoids loading of inputs)
C2 = G2 + P2(G1 + P1G0 + P1P0C-1 ) All Gi Pi in 3τ
C2 = G2 + P2G1 + P2P1G0 + P2P1P0C-1 … (5) All Ci-1 in 3τ
C2 is generated after 3τ delay, too. All Si in 3τ + 2τ = 5τ
Delay is not
C3 = G3 + P3C2 … (6)
cumulative.
From Eq.(5) and Eq.(6)
C3 = G3 + P3G2 + P3P2G1 + P3P2P1G0
+ P3P2P1P0C-1 … (7) C1 = G1 + P1G0 + P1P0C-1 C0 = G0 + P0C-1
C3 is generated after 3τ delay, too.
IC 7483A
Different manufacturers
use different notations.
Addition / Subtraction in Cascade
• Carry ripples from
one IC to other.
• Carry look ahead
within IC.
Group Carry Generation and Propagation
C3 = G3 + P2G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C-1
G3-0 = G3 + P2G2 + P3P2G1 + P3P2P1G0 : Group Carry Generation term
P3-0 = P3P2P1P0 : Group Carry Propagation term
C3 = G3-0 + P3-0C-1 G(i+3)-i : in 3τ and P(i+3)-i : in 2τ
C7 = G7-4 + P7-4C3 Carry look ahead: in 5τ
C7 = G7-4 + P7-4(G3-0 + P3-0C-1 ) = G7-4 + P7-4G3-0 + P7-4P3-0C-1

Similarly,
C11 = G11-8 + P11-8G7-4 + P11-8P7-4G3-0 + P11-8P7-4P3-0C-1
C15 = G15-12 + P15-12G11-8 + P15-12P11-8G7-4 + P15-12P11-8P7-4G3-0
+ P15-12P11-8P7-4P3-0C-1
Look Ahead Carry Generator Input
G0 P0 G1 P1 G2 P2 G3 P3 Cn
74182
G P Cn+x Cn+y Cn+z
Output
G0’.P0’ G0’.Cn’ Cn+x = (G0’.P0’ + G0’.Cn’)’
= (G0’.P0’)’.(G0’.Cn’)’
= (G0+P0).(G0+Cn)
= G0+G0Cn+G0P0+P0Cn
= G0(1+Cn+P0)+P0Cn
= G0+P0Cn
References:
 www.alldatasheet.com accessed on 15-11-2018
 Texas Instrument’s Digital Logic Pocket Data Book (2007)
Conclusion:
• Propagation delay is cumulative in ripple carry adder.
If basic gate delay is τ, then n-bit addition is done in
2nτ time since the placement of valid data.
• Carry look ahead adder does a serial to parallel
conversion for obtaining carry by which addition is
completed in 5τ time within the block.
• Cascading parallel adders where carry output of one
block is fed as carry input of next block makes the
carry ripple between blocks with cumulative delay.
• Additional group carry generation and propagation
terms are useful in more than one block of carry look
ahead adders are required.
Goutam Saha
Overflow Detection and

BCD Arithmetic
Lecture 25
Concepts Covered:
 Overflow Detection for Adder
 Binary Coded Decimal (BCD) Representation
 BCD Addition
 BCD Subtraction using 10’s Complement
 9’s Complement and 1’s Complement Subtraction

Overflow Detection for Adder
A3A2A1A0 Overflow Flag: O
+ve with +ve :
B3B2B1B0 O = A3’B3’S3 + A3B3S3’
------------ 0010 (2) 0010 (2) 0111 (7)
[C3] S3S2S1S0 0011 (3) 0111 (7) 1110 (-2) = C3 C2
------ ------ ------
0000 : 0 1000 : -8 0101 (5) 1001 (-7) 1 0101 (5)
0001 : 1 1001 : -7 Overflow
0010 : 2 1010 : -6
0011 : 3 1011 : -5 -ve with -ve :
0100 : 4 1100 : -4 1110 (-2) 1110 (-2) 0010 (2)
0101 : 5 1101 : -3 1101 (-3) 1001 (-7) 1001 (-7)
0110 : 6 1110 : -2 ------ ------ ------
0111 : 7 1111 : -1 1 1011 (-5) 1 0111 (7) 1011 (-5)
Range: -8 to +7 Overflow
Binary Coded Decimal (BCD)
0: 0000 Decimal BCD BCD: 0110100100000010

1: 0001
10 0001 0000
2: 0010 53 6 9 0 2
3: 0011 11 0001 0001
Decimal: 6902
4: 0100 99 1001 1001
0101 0011
5: 0101 100 0001 0000 0000
6: 0110
101 0001 0000 0001
7: 0111
8: 1000 487 0100 1000 0111
9: 1001 … …
Addition of BCD
• Result is valid BCD when 4-bit sum is less than or equal to 9. Binary addition
0101 0011 A3A2A1A0
0010 0110 B3B2B1B0
------ ------ ------------
0111 1001 C3 S3S2S1S0
7 9
• Result is not valid when 4-bit sum is more than 9. Addition of 6 gives valid BCD.
0100 1011 1001 (000)1 0001
0111 0110 1000 0110
------ ------ ------ ------
1011 (000)1 0001 (000)1 0001 (000)1 0111
Not valid BCD 1 1 1 1 1 7
Logic for Addition of 6
Decimal C3 S3 S2 S1 S0 Y BCD Addition result is between 0 and 18.
result (Add 6)
0-9 -- -- -- -- -- 0 Y = 1 when Addition of 6 is needed
10 0 1 0 1 0 1 Y = 1 when addition result is between 10 and 18.
11 0 1 0 1 1 1 i.e. C3S3S2S1S0 : 01010 to 10010
12 0 1 1 0 0 1
Y = 0 when C3S3S2S1S0 : 00000 to 01001
13 0 1 1 0 1 1 Y = X (don’t care) when C3S3S2S1S0 > 10010
14 0 1 1 1 0 1
15 0 1 1 1 1 1 This Truth Table on simplification gives
16 1 0 0 0 0 1
17 1 0 0 0 1 1
Y = C 3 + S 3S 2 + S 3S 1
18 1 0 0 1 0 1
BCD Adder Unit BCD Input 1 BCD Input 2
A3 A2 A1 A0 B3 B2 B1 B0
49 0100 1001 Carry from
7483 C-1
+ 58 0101 1000 previous
------ C3 S3 S2 S1 S0
1 0001
0110
...
------ ------
1010 0111
0 . 0
0110 A3 A2 A1 A0 B3 B2 B1 B0
------- ------ C-1 0
BCD Adder Unit 7483
(000)1 0000 0111 from 4-bit Adder C3 S3 S2 S1 S0
1 0 7 Next BCD
BCD Digit 1
Digit / Carry
BCD Subtraction 1 Subtrahend BCD Input: V3-0
4 . . X
Subtraction using 10’s C: Decimal
(Similar to 2’s C subtraction in binary)
X V3-0 .
10’s C 0 0 X =1 if 10’s C
W3-0 else, 0
Smaller from larger: 7 – 4 A3 A2 A1 A0 B3 B2 B1 B0
10’s C of 4 = 10 – 4 = 6 4 4 C-1
Minuend 7483
7 + 6 = 13 A3-0 B3-0
C3 S3 S2 S1 S0
Carry present: Result +ve BCD Adder Cin 0
Ignore
Ignore carry Cout S3-0
Difference = 3 (+ve) BCD 10’s C: W3-0
4 10’s C Generator Unit
Larger from smaller: 4 – 7 .
10’s C of 7 = 10 – 7 = 3
X V3-0
4+3=7 BCD
10’s C
Carry absent: Result -ve W3-0 Subtractor
Difference = 10’s C of 7 (-ve) 4 Unit
= 10 – 7 = 3 (-ve) 0: +ve
Sign Difference in BCD
1: -ve
9’s Complement and 1’s Complement
Decimal Subtraction using 9’s C: Binary Subtraction using 1’s C:
Smaller from larger: 7 – 4 Smaller from larger: 0111 – 0100
9’s C of 4 = 9 – 4 = 5 1’s C of 0100 = 1011
7 + 5 = 12 0111 + 1011 = 10010
Carry present: Result +ve Carry present: Result +ve
Add carry to get result Add carry to get result
Difference = 2 + 1 = 3 (+ve) Difference = 0010 + 1 = 0011 (+ve)
Larger from smaller: 4 – 7 Larger from smaller: 0100 – 0111

9’s C of 7 = 9 – 7 = 2 1’s C of 0111 = 1000
4+2=6 0100 + 1000 = 1100
Carry absent: Result -ve Carry absent: Result -ve
Difference = 9’s C of 6 (-ve) Difference = 1’s C of 1100 (-ve)
= 9 – 6 = 3 (-ve) = 0011 (-ve)
References:
Conclusion:
• Overflow in an adder occurs when the result goes out of
range e.g. in 4-bit adder if outside {-8, 7}.
• Addition of +ve and -ve number cannot give overflow.
Addition +ve with +ve, -ve with –ve can.
• In BCD addition, if the result is more than 1001 then
further addition of 0110 gives correct representation.
• A BCD adder unit has two 4-bit binary adder units and a
logic circuit to add 0110 when required.
• BCD subtraction by 10’s Complement (10’s C) requires a
10’s C generator circuit which uses a 4-bit binary adder
and a bank of Ex-OR gates.
• One BCD subtractor unit (using 10’s C) requires one BCD
adder unit and two 10’s C generator units.
• 9’s C Subtraction in decimal and 1’s C subtraction show as
much similarity as is shown by 10’s C and 2’s counterparts.
EL
Goutam Saha
PT
Magnitude Comparator
N Lecture 26
Concepts Covered:
 Week 5 Recap.
EL
 Magnitude Comparison by Subtraction
 Magnitude Comparator Logic Circuit
PT
 Serial Connection of Magnitude Comparator
N  Parallel Connection of Magnitude Comparator

Week 5 Recap.
• A number system with base or radix – r has digits 0 to (r – 1). The place value or weight is multiplied
with the digit to find its contribution.
• To convert decimal to binary, integer is successively divided by 2 and remainders accumulated;
fraction is successively multiplied by 2 and carry accumulated.
EL
• Fixed-point representation has fixed precision. Fixed-point arithmetic is similar to integer arithmetic.
• Sign-Magnitude representation has a separate sign bit. Using 8-bits, range of number: -127 to +127.
• In 2’s C arithmetic, subtraction is done by considering addition of –ve number.
PT
• In ripple carry addition, carry output of one full adder is connected as carry input
of next full adder. Propagation delay is cumulative in ripple carry adder.
• Carry look ahead adder does a serial to parallel conversion for obtaining carry by
•
•
N
which the carry generation delay is not cumulative between stages.
Overflow in an adder occurs when the result goes out of range.
In BCD addition, if the result is more than 1001 then further addition of 0110
gives correct representation.
Magnitude Comparison by Subtraction
• Magnitude comparison finds if (i) one number is
S3-0
same as the other number (identity / equality) or X3-0 X> Y
(ii) greater / smaller than the other number. 4-bit 2’s C
EL
Combinatorial X= Y
Subtractor
• An adder circuit performing 2’s C subtraction (from 4-bit
Logic
X< Y
Y3-0
(X – Y) can be used for this. Adder)
Cout
PT
- If X = Y and X > Y then Cout = 1.
If Cout = 0, then X < Y.
- if Cout is 1 and any of Si = 1 then X > Y, else X = Y.
(X < Y) = Cout’ N
(X = Y) = Cout.S3’.S2’.S1’.S0’ (X > Y) = Cout.(S3+S2+S1+S0)
1-bit Magnitude Comparison
X.Y’
• Magnitude comparison can be done without
generating addition / subtraction result. X’+Y’
EL
Input Output
X’.Y
X Y X>Y X=Y X<Y (X > Y): G = X.Y’ (If NAND gate is not used,
PT
(X = Y): E = X’.Y’ + X.Y two NOT gates will be
0 0 0 1 0
(X < Y): L = X’.Y required to get X’ and Y’)
0 1 0 0 1
1
1
0
1
1
0
0
1 N0
0
X’.Y’ + X.Y = (X’ + Y).(X + Y’)
= (X.Y’)’.(X’.Y)’
= [(X.Y’) + (X’.Y)]’
2-bit Magnitude Comparison Xi.Yi’
Numbers to be compared: X : X1X0 and Y : Y1Y0

Xi’.Yi
Define: X> Y :
EL
G0 = X0.Y0’ • If X1 > Y1 (X > Y) = G1 + E1G0 Other than two 1-bit
E0 = X0’.Y0’ + X0.Y0 • If X1 = Y1 and X0 > Y0 comparators, a logic
L0 = X0’.Y0 circuit to generate
PT
X= Y : final outputs.
G1 = X1.Y1’ • If X1 = Y1 and X0 = Y0 (X = Y) = E1.E0
E1 = X1’.Y1’ + X1.Y1
L1 = X1’.Y1 X< Y :
N
• If X1 < Y1
• If X1 = Y1 and X0 < Y0
(X < Y) = L1 + E1L0
n-bit Magnitude Comparison
Numbers to be compared: X : Xn-1Xn-2 … X1X0 and Y : Yn-1Yn-2 … Y1Y0
(X > Y) = Gn-1 + En-1Gn-2 + En-1En-2Gn-3 + … + En-1En-2 … E1G0
EL
(X = Y) = En-1En-2 … E1E0
(X < Y) = Ln-1 + En-1Ln-2 + En-1En-2Ln-3 + … + En-1En-2 … E1L0
PT
With cascading inputs coming from another block with lower significant bits:
(X > Y)out = Gn-1 + En-1Gn-2 + … + En-1En-2 … E1G0 + En-1En-2 … E0.(X > Y)in
N
(X = Y)out = En-1En-2 … E1E0.(X = Y)in
(X < Y)out = Ln-1 + En-1Ln-2 + … + En-1En-2 … E1L0 + En-1En-2 … E0.(X < Y)in
4-bit Comparator IC
EL
PT
N AND output = 1
AND output = 1
if A3=0, B3=1
if A3=B3 and A2=0, B2=1

IC 7485 Function Table
EL
PT
N
Cascaded Comparison
8-bit comparison
Here, generation of comparator

output of one stage delays the
EL
output generation of next stage
to which it is fed.
PT
24-bit comparison
X23-20 Y23-20
……………. X3-0 Y3-0
3
4 4 4
3
4 4
3
N 4 4
3
4 4
3
4
3
4 4
3
Comp. in
Comp. out
Multi-level Comparison
EL
Treated equal in next level
PT
24-bit comparison using
6 IC 7485 : Parallel
(less delay than serial)
N
References:
EL
PT
N
Conclusion:
• Magnitude comparison of two numbers can be done by
subtracting one number from the other and developing
suitable logic circuit to generate X>Y, X=Y, X<Y outputs.
• A direct approach for magnitude comparison of two
numbers can avoid subtraction. In this, place value of
EL
the bits being compared is useful.
• IC 7485 is a 4-bit comparator which has inputs that can
be connected to outputs of another IC comparing lower
PT
significant bits of two numbers.
• Delay of every stage adds up when larger number of
bits are compared with IC 7485 is connected in serial.
N
• There can be parallel, multi-level arrangement of IC
7485 which can give lower delay.
N
PT
EL
EL
Goutam Saha
PT
Arithmetic Logic Unit (ALU)

N Lecture 27
Concepts Covered:
 Arithmetic Logic Unit (ALU) Fundamentals
EL
 Working of IC 74181 ALU
 Connecting IC 74181 ALU to IC 74182 Look
PT
Ahead Carry Generator
N
Arithmetic Logic Unit
Arithmetic Logic Unit (ALU) is a versatile unit that can perform
arithmetic or logic operation on operands as per control input.
EL
If S = 0, Y0 = S’.(A.B)’ + S.(A’.B + A.B’)
Y0 = (A.B)’
A Y0 … simplification ...
Y1 = (A + B)’
PT
= S’.A’ + A’.B + A.B’
If S = 1,
B Y1 Y0 = A’.B + A.B’
S
N
(sum bit of H.A.)
Y1 = A.B
(carry bit of H.A.)
Y1 = S’.(A + B)’ + S.A.B
= S’.A’.B’ + S.A.B
Arithmetic Logic Unit
Function Table
S1 S0 Cin Output
EL
A0 0 0 X Y = (A.B)’
A1 Y0 0 1 X Y = (A + B)’
B0 Y1 1 0 0 Y=A Y0
PT
B1 1 0 1 Y = A PLUS 1 for Cin = 0
Cin Cout 1 1 0 Y = A PLUS B
1 1 1 Y = A PLUS B PLUS 1
S1 S0
N
Logic operation: Bitwise
Arithmetic operation: 2-bit number
IC 74181 M: Mode L: Arithmetic operation
H: Logic operation
Arithmetic operation:
Addition
Subtraction
Function
EL
Shift operand A by one position
outputs:
Magnitude comparison
(F3…F0)
….
Logic operation:
PT
NOT, AND, NAND, OR, NOR
Ex-OR, Ex-NOR
….
N Other outputs:
Group carry Generation
and Propagation,
Ripple carry, Equality
Function Table
• (A = B) output is open
Note:
collector providing
74181 uses 1’s C
wired-AND option (to
subtraction.
compare > 4 bits)
• A PLUS A = 2 x A which
EL
makes one left shift of A.
Cn Cn+4 Result Magnitude
PT
Comparison
L L A≤B
Data: Active Low
L H A>B
Mode, M: L
H L A<B
N H H A≥B
S3S2S1S0 : LHHL
(Subtraction)
Function Table
EL
PT
13 5 9 1 14 6 10 2 15 7 11 3 16 8 12 4
S3 S2 S1
S0: Function No.
L LL L 1 All possible logic functions of 2
L
L
L
L
H
L
…….
L
H
2
3 N variables are generated. Note
that A and B are of 4-bits and
bit-wise logic operation is done.
H H H H 16
Logic Circuit
1 0 0 0 0
1 0
0 0
0
S3 S2 S1 S0: 0000
EL
1 0 0 0 0
0 M: 1, B: 0000, Cn: 0
0 1
1 A0: 1 F0: 0
A0: 0 F0: 1
PT
1 F0 = A0’
0
0
1
N
ALU with LAC Generator
…….
EL
…….
PT
…….
64-bit ALU, Carry Look
N
IC x81: Arithmetic Logic Unit (ALU)
IC 182: Look Ahead Carry (LAC) Generator
Ahead in three levels
Level 1: 16 ALU (each 4-bit)
Level 2: 4 LAC Generator
Level 3: 1 LAC Generator
References:
Texas Instrument’s Digital Logic Pocket Data Book (2007)
EL
PT
N
Conclusion:
• Arithmetic Logic Unit (ALU) is a versatile unit that can
perform arithmetic or logic operation on operands
according to control inputs.
• IC 74181 is a 4-bit ALU with a mode select input (M). If M
is H, the ALU performs bitwise logic operation and if M is
EL
L, the ALU performs arithmetic operation.
• Logic operation performed by IC 74181 ALU not only
includes commonly used NOT, AND, NAND, OR, NOR, Ex-
PT
OR, Ex-NOR but also, all possible functions of 2-variables.
• Arithmetic operation performed by IC 74181 includes
Addition, Subtraction, Magnitude Comparison.
N
• IC 74181 has additional outputs like ripple carry, group
carry generation and propagation term, equality.
• IC 74181 can be connected to IC 74182 to generate look
ahead carry for more than 4-bit arithmetic e.g. 64-bit.
N
PT
EL
EL
Goutam Saha
PT
Unweighted Code
N Lecture 28
Concepts Covered:
 Need of Unweighted Code
EL
 Gray Code
 Excess-3 (XS-3) Code
PT
 Addition and Subtraction using XS-3 Code
N  ASCII Code
Issue with Binary Code
B3 B2 B1 B0
0 0 0 0
2 digits 0 0 0 1
change B2B1B0 : 001
EL
0 0 1 0 Possibility of decoding a wrong
(If B1 change is
0 0 1 1 000 010 direction of movement
3 digits slower than B0)
change 0 1 0 0
PT
0 1 0 1
.
0 1 1 0 dn … d1d0.d-1d-2 … d-m = dn x rn + … + d1 x r1 + d0 x r0
0 1 1 1 + d-1 x r-1 + d-2 x r-2 + … + d-m x r-m
.
.
1 0 0 0
1 0 0 1
N
1010 in 8421 code = 1 x 8 + 0 x 4 + 1 x 2 + 0 x 1
8421 : Weights associated with position
1 0 1 0 Note: 1010 in 2421 code = 1 x 2 + 0 x 4 + 1 x 2 + 0 x 1
Gray Code
B3 B2 B1 B0 G3 G2 G1 G0 • Gray Code is an unweighted
0 0 0 0 0 0 0 0 code with unit distance i.e.
only one position changes
0 0 0 1 0 0 0 1
between two successive
EL
0 0 1 0 0 0 1 1 positions.
0 0 1 1 0 0 1 0 • It is also called reflected code
0 1 0 0 0 1 1 0 as by reflecting (n – 1)-bit
PT
gray code, n-bit gray code
0 1 0 1 0 1 1 1
can be obtained.
0 1 1 0 0 1 0 1
0 1 1 1
1 0 0 0
1 0 0 1
0 1 0 0
1 1 0 0
1 1 0 1
N
1 0 1 0 1 1 1 1
Code Conversion
B3 B2 B1 B0 G3 G2 G1 G0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
EL
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 0
PT
Gn = Bn Bn = Gn
0 1 0 1 0 1 1 1
Gi = Bi+1 Bi for i < n Bi = Bi+1 Gi for i < n
0 1 1 0 0 1 0 1
0 1 1 1
1 0 0 0
1 0 0 1
0 1 0 0
1 1 0 0
1 1 0 1
N
1 0 1 0 1 1 1 1
Excess-3 Code Code Conversion:
Approach 1:
Binary Code Decimal + 0011 = Excess-3 Code (XS-3) • BCD to XS-3: Represent each
XS-3 bit, Xi = F(B3,B2,B1,B0)
BCD XS-3 • XS-3 to BCD: Bi = F(X3,X2,X1,X0)
0: 0000 0011 Decimal XS-3 (Consider ‘don’t care’ for
EL
1: 0001 0100 10 0100 0011 unused input combinations.)
2: 0010 0101 53 Approach 2:
11 0100 0100
3: 0011 0110 • BCD to XS-3: Add 0011
PT
99 1100 1100 • XS-3 to BCD: Subtract 0011
4: 0100 0111 1000 0110
100 0100 0011 0011 (Consider 4-bit
5: 0101 1000 Adder-Subtractor)
6: 0110 1001 101 0100 0011 0100
(6.9)10
7:
8:
9:
0111
1000
1001
1010
1011
1100
N
= (0110.1001)BCD
= (1001.1100)XS-3
487
…
0111 1011 1010
…
Addition of XS-3 Code
1
• Subtract 0011 from addition result if no carry is produced. 0101 1000 (25)10
(5)10 1000 (XS-3) + 1000 1010 + (57)10
1101 (XS-6)
+ (2)10 + 0101 (XS-3) ---------------- ---------
- 0011
EL
No carry 1110 0010 (82)10
--------- ------ ------ up to - 0011 +0011
(7)10 1101 (XS-6) 1010 (XS-3) (1111)XS-6 ----------------
= (1001)2
PT
1011 0101 (XS-3)
= (9)10
• Add 0011 to addition result if carry is produced. 8 2 (Dec.)
= (1100)XS-3
(5)10 1000 0010
+ (7)10
---------
(12)10
+ 1010
------
1 0010
N + 0011
------
(0)1(00) 0101 (XS-3)
1 2 (Decimal)
XS-3 Adder Unit XS-3 Input 1 XS-3 Input 2
XS-3 Adder Unit A3 A2 A1 A0 B3 B2 B1 B0

1 from 4-bit Adder Carry from
0101 1000 (25)10 . C3
7483 C-1
S3 S2 S1 S0
previous
+ 1000 1010 + (57)10
EL
---------------- --------- .
1110 0010 (82)10
- 0011 +0011 .
PT
1
----------------
A3 A2 A1 A0 B3 B2 B1 B0
1011 0101 (XS-3)
8 2 (Dec.) C-1 0
7483
N C3
Ignore
S3 S2 S1 S0
XS-3 Digit 1
XS-3 Digit 2 / Carry
XS-3 Subtrahend
XS-3 Subtractor Unit XS-3 Minuend
SUB
Subtraction using 9’s C: XS-3 Subtractor A3 A2 A1 A0 B3 B2 B1 B0

Inverting bits of XS-3 code 9’s C Unit
Carry from
In XS-3 directly obtained. . C3
7483
S3 S2 S1 S0
C-1
previous
EL
(2)10 : (0101)XS-3
9’s C of 2: 9 – 2: 7
(7)10 : (1010)XS-3
.
. . .
PT
• Add 9’s C of subtrahend with 1
minuend A3 A2 A1 A0 B3 B2 B1 B0
• If carry, result +ve, add carry,
C-1
also add 0011 for XS-3 7483
• If no carry, result –ve, subtract
3 for XS-3, invert its bits N C3
Ignore
S3 S2 S1 S0
Carry XS-3 Result

ASCII Code
ASCII: American Standard Code for Information Interchange; standardized for computer hardware
7 bits: 128 Codes
Includes control codes for EBCDIC (Extended Binary
peripherals and printable Coded Decimal Interchange
EL
Code) was introduced for
characters
IBM devices.
A: 1000001 a: 1100001
B: 1000010 b: 1100010
PT
C: 1000011 c: 1100011
0: 0110000 =: 0111101
1: 0110001 : : 0111110
N 2: 0110010 . : 0101110
0000000: Null Character
0000001: Start of Heading
0001101: Carriage Return
References:
 https://www.ascii-code.com/ accessed on 15-12-2018
EL
PT
N
Conclusion:
• Change of more than 1 digit for two consecutive numbers
in binary code may give problem in certain applications if
one digit change is slower than other.
• In Gray Code, consecutive bits change by only one
position. Binary to Gray as well as Gray to Binary code
EL
conversion use EX-OR gates.
• Excess-3 (XS-3) code is 0011 added to binary coded
decimal. The allowable values are 0011 to 1100.
PT
• XS-3 addition and subtraction uses simpler circuit than
BCD addition and subtraction. It involves addition and / or
subtraction of 0011 in both the cases.
N
• ASCII (American Standard Code for Information
Interchange) is a 7-bit code which includes control codes
for peripherals as well as printable characters.
N
PT
EL
EL
Goutam Saha
PT
Error Detection and

N Correction Code
Lecture 29
Concepts Covered:
 Hamming Distance and Parity Code
EL
 Hamming Code Generation
 1-bit Error Correction using Hamming Code
PT
 2-bit Error Detection using Hamming Code
N
Hamming Distance and Parity Code
• The number of bit positions by which code words differ is called Hamming distance.
• It can be found by counting number of 1s in bit-wise Ex-OR of two code words.
Parity bit
EL
Data 1: 10100011 Code word 1: 010100011 Parity Code:
Even parity coded
Data 2: 11011001 Code word 2: 111011001 Data with a parity bit
Bit-wise Ex-Or output: 101111010 : Hamming distance, d = 6
PT
Data 1: 00000000 Can detect 1 bit error.
Code word 1: 000000000
Data 2: 00000001 Cannot correct any.
Code word 2: 100000001
Bit-wise Ex-Or output: 100000001 : Hamming distance, d = 2
N
• To detect b bit errors, minimum hamming distance, dmin = b + 1.
• To correct b bit errors, minimum hamming distance, dmin = 2b + 1.
Hamming Code
• Useful for correcting 1-bit error. It uses more than 1 parity bits.
• Parity bits in the code word are positioned at 2i-th positions.
Rest of the positions are filled by data bits.
EL
20 21 22 23
P1 P2 D3 P4 D5 D6 D7 P8 D9 D10 D11 D12 D13 D14 D15
PT
• If m parity bits (m ≥ 2) are used Parity bits Max. data Max. total
to code n data bits then, bits length
2m > m + n N 2
3
4
1
4
11
3
7
15
Hamming Code Generation
P1 = D3 D5 D7 : All with 1 in 1’s place of position
P1 P2 D3 P4 D5 D6 D7 P2 = D3 D6 D7 : All with 1 in 2’s place of position
Binary coded position 0001 0010 0011 0100 0101 0110 0111 P4 = D5 D6 D7 : All with 1 in 4’s place of position
EL
(7,4) Code: Rate = 4/7
Extending: dmin = 3
P1 P2 Can detect all 2 bit error.
PT
D3 P4 D5 D6 D7 P8 D9 D10 D11 D12
Can correct all 1 bit error.
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
P1 = D3 D5 D7 D9 D11 …
N
P2 = D3 D6 D7 D10 D11
P4 = D5 D6 D7 D12
P8 = D9 D10 D11 D12 : All with 1 in 8’s place of position
…
…
Example
Data: 10110101
P1 P2 1 P4 0 1 1 P8 0 1 0 1
EL
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
PT
P1 = D3 D5 D7 D9 D11 = 1 0 1 0 0=0
P2 = D3 D6 D7 D10 D11 = 1 1 1 1 0 = 0
P4 = D5 D6 D7 D12 = 0 1 1 1 =1
N
P8 = D9 D10 D11 D12 = 0 1 0 1
Coded Data: 001101100101

=0
One bit Error Correction
C1 = D3 D5 D7 D9 D11 P1 • If C8C4C2C1 = 0000 : No error
C2 = D3 D6 D7 D10 D11 P2 • Else, it gives position of the error bit
C 4 = D5 D 6 D 7 D12 P4 e.g. C8C4C2C1 = 0111 means 7th bit is
EL
erroneously received
C8 = D9 D10 D11 D12 P8 • Invert the erroneous bit to correct.
Example:
PT
Coded Data: 001101100101 C1 = 1 0 1 0 1 0 = 1 1011: 11th bit 1 is erroneous
Data with : 001101100111 It is to be made 0 to correct
C2 = 1 1 1 1 1 0=1
1-bit error
In 11th pos. N C4 = 0
C8 = 0
1
1
1
1
1
1
1
0
=0
=1
Note: If C8C4C2C1 = 1000 then 8th position bit i.e. P8 is erroneous.

Two bit Error Detection
C1 = D3 D5 D7 D9 D11 P1 C1 = D3 D5 D7 D9 D11 P1 Two bits flip
C2 = D3 D6 D7 D10 D11 P2 C2 = D3 D6 D7 D10 D11 P2
C 4 = D5 D 6 D 7 D12 P4 C 4 = D5 D 6 D 7 D12 P4
EL
C8 = D9 D10 D11 D12 P8 C8 = D9 D10 D11 D12 P8
C8C4C2C1 = 0010 C8C4C2C1 = 0110
PT
C1 = D3 D5 D7 D9 D11 P1 C1 = D3 D5 D7 D9 D11 P1 Three bits flip
C2 = D3 D6 D7 D10 D11 P2 C2 = D3 D6 D7 D10 D11 P2
C 4 = D5 D 6 D 7 D12 P4
C8 = D9 D10 D11 D12 P8
N
C 4 = D5 D 6 D 7 D12 P4
C8 = D9 D10 D11 D12 P8
C8C4C2C1 = 0001 C8C4C2C1 = 0000
References:
EL
PT
N
Conclusion:
• The number of bit positions by which code words differ is
called Hamming distance. It can be found by counting
number of 1s in bit-wise Ex-OR of two code words.
• To detect b bit errors, minimum hamming distance,
dmin = b + 1. To correct b bit errors, minimum hamming
EL
distance, dmin = 2b + 1.
• In Even or Odd parity code, dmin = 1. It can detect 1-bit
error but cannot correct any.
PT
• In Hamming code, Parity bits in the codeword are
positioned at 2i-th positions. Rest of the positions are
filled by data bits.
N
• Hamming code generation and checking involves sum or
Ex-OR operation of specific bits.
• In Hamming code, dmin = 3. It can detect 2-bit error and
correct 1-bit error.
N
PT
EL
EL
Goutam Saha
PT
Multiplication and Division

N Lecture 30
Concepts Covered:
 Binary Multiplication
EL
 A Combinatorial Circuit for Binary Multiplication
 Binary Division
PT
 A Combinatorial Circuit for Binary Division
N
Binary Multiplication
Multiplicand
Factors Multiplier
0x0=0 1101 -----------------
0x1=0 10 Product
(13)10
1x0=0 ---------- 1101
0000 (2)10
1x1=1
EL
------ 1011
1101 (13)10
x y m (26)10 Carry 1111----------
---------------- 1101 (11)10
11010
0 0 0 1101 ------
PT
0000 (143)10
0 1 0 1101
1101
1 0 0 11 (13)10 -------------------
10001111
(3)10
1 1
m = x.y
1
N
Carry 11 ----------
1101
1101
----------------
100111
------
(39)10
4-bit x 2-bit Multiplication
x3 y0 x2 y0 x1 y0 x0 y0
x3 x2 x1 x0
EL
y1 y0 x3 y1 x2 y1 x1 y1 x0 y1
-------------------
x3y0 x2y0 x1y0 x0y0 0
x3y1 x2y1 x1y1 x0y1
PT
F.A. F.A. F.A. H.A.
------------------------------------------------------
m5 m4 m3 m2 m1 m0
m5 m4 m3 m2 m1 m0
N
4-bit x 4-bit Multiplication x3x2x1x0 : 1101
Example:
x3 y0 x2 y0 x1 y0 x0 y0 y3y2y1y0 : 1011
x3 y1 x2 y1 x1 y1 x0 y1
01 11 10 01 1 1st row adder
0
EL
10 00 00 10 1 2nd row adder
F.A. F.A. F.A. H.A.
x3 y2 x2 y2 x1 y2 x0 y2 01 11 00 01 1 3rd row adder
PT
1 0 0 0 1
F.A. F.A. F.A. H.A.
x3 y3 x2 y3 x1 y3 x0 y3 Result: 10001111
F.A. F.A. F.A.

N H.A.
m7 m6 m5 m4 m3 m2 m1 m0
Binary Division 1001
(0)11 1101 1110101

1101
11 1011 D = (1110101)2 = (117)10
00 0011 d = (1101)2 = (13)10
Dividend Quotient 0000 q = (1001)2 = (9)10
EL
101
r=0
11 0110
Divider
0000
Divisor Remainder 101
PT
11 1101
1101
10
D=dxq+r
N
Dividend = Divisor x Quotient + Remainder D = (1011)2 = (11)10
d = (11)2 = (3)10
q = (11)2 = (3)10
r = (10)2 = (2)10
Unit Cell for Divider Array
x y bin x y d bout
. 0 0 0 0 0
0 0 1 1 1
EL
S Y
bout (x – y) Full bin 0 1 0 1 0 Unit
0 D0
Subtractor 0 1 1 0 0 Cell
1 D1
PT
1 0 0 1 1
0 1 1 0 1 0 1 Y = S’.D0 + S.D1
. S
2-to-1 1 1 0 0 0 2-to-1
Multiplexer
Unit Cell
N 1
Full
1 1 1
d = x y bin
1
Multiplexer
Subtractor bout = x’.y + x’.bin + y.bin

A Divider Circuit Example:
11 11 10 01 D: 1110101
D6 d3 D5 d2 D4 d1 D3 d0 1 0 0 0 0 1 d: 1101
00 01 01 10 11
.
q3
0 0 1 1 0 1 1 0 q: 1001
r: 0000
00 01 11 10 01
d3 d2 d1 D2 d0
0 0 1 1 1 0 0 1
EL
00 11 11 00 11
q.
0
2 1 0 0 0 0 0 0
d3 d2 d1 D1 d0
PT
0 bout
q1 . 0
d3 d2 d1 D0 d0
0
Units with 0 as an input

to the subtractor can
use half-subtractor.
q0 . N 0
r3 r2 r1 r0
References:
 Lloris Ruiz A., Castillo Morales E., Parrilla Roure L., García Ríos A. Number
EL
Systems. In: Algebraic Circuits. Intelligent Systems Reference Library, vol 66. Springer,
Berlin, Heidelberg
PT
N
Conclusion:
• Product from binary multiplication of two 1-bit number is
obtained from logical AND operation of the numbers.
• Binary multiplication of more than 1-bit numbers can be
obtained by getting partial products of and adding them
after appropriate shift.
EL
• A combinatorial circuit based multiplier circuit using cell
array performs the shift within the arrangement.
• Binary division of numbers give two binary outputs:
PT
quotient and remainder. It involves subtraction of divisor
after appropriate shift.
• A combinatorial circuit based divider circuit using cell
N array performs the shift within the arrangement.

• The shift operation can be done by sequential logic circuit.
There are other approaches to perform binary
multiplication and division.
N
PT
EL
EL
Goutam Saha
PT
N
SR Latch and Introduction
to Clocked Flip-Flop
Lecture 31
Concepts Covered:
 Week 6 Recap.
 Bistable Circuit
 SR Latch
EL
PT
 Debounce Switch
 Gated Latch
N  Clocked SR Flip-Flop
Week 6 Recap.
• Magnitude comparison of two numbers, X and Y is done to find X>Y, X=Y, X<Y. It can be obtained by
understanding the value associated with more significant bits or by interpreting the subtraction result.
• IC 7485 is a 4-bit comparator with cascade option. Serial and multi-level arrangement is possible with
IC 7485 to compare two numbers with larger number of bits.
• Arithmetic Logic Unit (ALU) is a versatile unit that can perform arithmetic or logic operation on
EL
operands according to control or function-select inputs.
• IC 74181 is a 4-bit ALU with a mode select input (M) and 4 selection inputs. Besides function outputs,
PT
it has other outputs to get ALU operation done for larger number of bits.
• Unweighted codes are useful in specific cases where binary code falls short. In
Gray Code, consecutive numbers differ in one bit position. Excess-3 code is useful
N
in developing addition / subtraction circuit.
• Minimum Hamming distance between code words gives how many errors in bits
can be detected and corrected. Hamming code can detect 2 errors and correct 1.
• For multiplication and division, unit cell based array structured combinatorial
circuit can be made.
Bistable Circuit
• A bistable circuit has two stable states. Feedback
Inconvenient
• Its value changes only by external trigger. to apply input
• It can store one bit of information / trigger
EL
PT
N
SR Latch S R V2 V3
1 1 0 0
S R Qlast Q If SR = 00 follows SR = 11, then
0 0 0 0 there is a race between two
gates and depending on who
0 0 1 1 responds faster, V2V3 settles at
EL
0 1 0 0 one of 01 or 10.
0 1 1 0
PT
1 0 0 1
1 0 1 1 Latches to prior state
N
1 1 0 N.A.
1 1 1 N.A.
N.A.: Not allowed

SR Latch
EL
PT
S R Q+
0 0 Q-
N
0 1 0 Realizing SR Latch using only NAND gate
1 0 1
1 1 N.A.
IC 74279
EL
1 2 Truth Table of 1 and 4
PT
3 4
N Truth Table of 2 and 3

Debounce Switch
Ideal
EL
PT
N
Actual
Gated Latch
EL
PT
N
Gated Latch
EL
PT
N
Clocked SR Flip-Flop
Usually, Latch with
clock / enable input is
referred as Flip-Flop.
EL
PT
N
Level-triggered
SR Flip-Flop
When C is at HIGH level, state can
change according to SR input.
References:
EL
PT
N
Conclusion:
• A bistable circuit has two stable states. Its value
changes only by external trigger. It can store one bit of
information.
• In SR latch, previous state is latched to if 00 is
presented at the input. At its input 11 is not allowed to
avoid race which leads to indeterminate state.
EL
• SR latch can arrest the bounce of an ordinary switch.
• In gated SR latch, there is an additional Enable input.
PT
The output can react to the input only when Enable is
active i.e. HIGH if it is active high.
N
• When a clock is presented at the Enable input of SR
latch, the circuit can change in one phase of the clock.
• In synchronous sequential circuit, one state change can
occur in every clock cycle, synchronized with the clock.
N
PT
EL
EL
Goutam Saha
PT
N
Edge-Triggered Flip-Flop
Lecture 32
Concepts Covered:
 Triggering Flip-Flop with Narrow Pulse Width Clock
 Edge-triggered SR Flip-Flop
EL
 D Flip-Flop
PT
 JK Flip-Flop
N
 Master – Slave Flip-Flop
 Edge-triggering with Input Lockout

Triggering with Narrow Pulse
• Synchronous digital system requires one state
change per clock cycle, synchronized with clock.
• More than one state change can occur in level-
triggered flip-flop if there is feedback / input
EL
changes when clock remains enabled.
PT
N
A very narrow pulse width positive trigger
(effectively edge-triggered)
Edge Triggered SR Flip-Flop
-ve edge triggered
EL
SR Flip-Flop
PT
N
+ve edge triggered SR Flip-Flop
D Flip-Flop
EL
PT
D Flip-Flop with asynchronous preset and clear
N
JK Flip-Flop
Dual -ve edge triggered
EL
JK Flip-Flop with active
low PRESET and CLEAR
PT
N
Master-Slave Flip-Flop
IC 7476
JK Master-Slave
with asynch.
preset and clear
EL
PT
N
Master Flip-Flop: According to type of
Individually level-triggered, changes in
Flip-Flop i.e. JK, SR, D. different phases of clock, effectively
Slave Flip-Flop: Always SR Flip-Flop. edge-triggered.
Edge-Triggering by Input Lockout
EL
PT
N
Edge-Triggering by Input Lockout
EL
PT
N
IC 7474 IC 7475 is a Quad D latch with two
enables (one each for 2 latch).
IC 7476A: Dual -ve edge

triggered JK Flip-Flop with active
low PRESET and CLEAR
EL
PT
N
IC 7474: Dual +ve edge-triggered D Flip-Flop with asynch. active low preset and clear.
References:
 Motorola Integrated Circuit Datasheet
EL
PT
N
Conclusion:
• In a level-triggered flip-flop, there can be more than
one or unintended state change in one clock cycle.
• If clock is passed through a pulse forming circuit that
generates very narrow pulse width, effectively an edge-
triggered circuit can be obtained.
• Master-Slave arrangement uses two level-triggered flip-
EL
flops which work in two different phases of the clock.
• Edge-triggering using input lockout does not require
PT
separate pulse forming circuit/ Master-Slave
arrangement.
N
• D and JK flip-flops with their own Truth-Tables are
useful in sequential logic circuit.
• Asynchronous preset / clear inputs is useful in setting /
resetting a flip-flop without clock trigger.
N
PT
EL
EL
Goutam Saha
PT
N
Representations of Flip-Flops
Lecture 33
Concepts Covered:
 Truth Table and Characteristic Equation
 Excitation Table
EL
 State Transition Diagram
PT
N
Characteristic Equation: SR S
0
R
0
Qn+1
Qn
0 1 0
S R Qn Qn+1 1 0 1
0 0 0 0 1 1 N.A.
0 0 1 1
EL
0 1 0 0
PT
0 1 1 0
1 0 0 1
N
1 0 1 1
1 1 0 N.A.
1 1 1 N.A.
Characteristic Equation: JK J K Qn+1
0 0 Qn
0 1 0
J K Qn Qn+1 1 0 1
0 0 0 0 1 1 Qn’
0 0 1 1
EL
0 1 0 0
PT
0 1 1 0
1 0 0 1
N
1 0 1 1
1 1 0 1
1 1 1 0
Characteristic Equation: D and T
D Qn Qn+1
0 0 0
0 1 0
EL
1 0 1
1 1 1
PT
T Qn Qn+1
0 0 0
N
0 1 1
1 0 1
1 1 0
Excitation Table: SR
• It presents what input should be present to cause a
specific transition of the Flip-Flop when clock triggers.
• It can be obtained from Flip-Flop Truth Table.
EL
Consider SR Flip-Flop with Qn = 0
S R Qn+1 If SR = 00, Qn+1 = 0
Excitation Table of SR Flip-Flop
PT
0 0 Qn If SR = 01, Qn+1 = 0
i.e. if SR = 0X, Qn+1 = 0
0 1 0
N
Therefor for SR FF,
1 0 1 If Qn → Qn+1 = 0 → 0
1 1 N.A. then its input SR before clock trigger
SR = 00 or 01 i.e. 0X
Excitation Table: JK, D and T
EL
PT
J K Qn+1
N
0 0 Qn D Qn+1 T Qn+1
0 1 0 0 0 0 Qn
1 0 1 1 1 1 Qn’
1 1 Qn’
State Transition Diagram
It can be directly
EL
obtained from
SR Flip-Flop JK Flip-Flop excitation table.
PT
D Flip-Flop N T Flip-Flop
References:
EL
PT
N
Conclusion:
• The next state or output of a flip-flop can be obtained
from its Truth Table (also called Characteristic Table).
• Characteristic Equation of a flip-flop is a minimized
representation of the next state by considering present
input and present state.
• Excitation Table shows in tabular from what as input is
EL
required to move the flip-flop from one particular state
to other.
PT
• A don’t care in Excitation Table indicates that the
specific transition will take place irrespective of the
N
variable under consideration being 0 or 1.
• The change in state of a flip-flop for a specific input can
be represented by state transition diagram.
N
PT
EL
EL
Goutam Saha
PT
N
Analysis of Sequential Logic Circuit
Lecture 34
Concepts Covered:
 Analysis Using State Table
 Analysis Using Timing Diagram
EL
 Analysis Using Characteristic Equation
PT
 Presentation of Analysis Result
N
An Example Note that,
- for the basic logic gate part of the
circuit, output will be considered as
• To analyse the circuit and find how states change with the immediately available when input is
input clock and how output is generated. presented and
- for the flip-flop / memory element part
of the circuit, its output change as per
EL
Truth Table / Characteristic Eqn. waits
till the clock trigger.
- Basic gate delay is negligible compared
PT
to clock time period. Effect of those
delay will be considered later.
N
Defining Flip-Flop Inputs and Output
For Flip-Flop A, For Output,
SA = An’ X = An.Bn
RA = An
EL
PT
For Flip-Flop B,
SB = An.Bn’
N
RB = An.Bn
S R Qn+1
State Analysis Table 0 0 Qn
0 1 0
Current State Current Flip-Flop Input Next State Output
1 0 1
CLK Bn An SB RB SA RA Bn+1 An+1 X 1 1 N.A.
0 0 0 0 0 1 0 0 1 0
SA = An’
EL
1 0 1 1 0 0 1 1 0 0 X = An.Bn
RA = An
2 1 0 0 0 1 0 1 1 0
PT
3 1 1 0 1 0 1 0 0 1 SB = An.Bn’
4 0 0 0 0 1 0 0 1 0 RB = An.Bn
N
5 0 1 …
• Clock 0: The initial state is assumed to be 0 for each flip-flop.
• Clock n: Next state of clock (n – 1) is the present state at clock n and the circuit evolves.
• State transition as per Flip-Flop Truth Table for the input present.
Analysis Result
The circuit generates an output = 1
BA / X 01 / 0 at every 4th clock trigger when it
reaches the state BA = 11 and
repeats the state transition
EL
00 → 01 → 10 → 11 → 00 → …
PT
00 / 0 10 / 0
BA : Current State
X : Current Output
11 / 1 N
Using Timing Diagram
• Starting with initial 00 state,
progress with time where Flip-Flop
can change state only at –ve edge
of the clock.
• Timing diagram can show the effect
EL
of delay in various elements and
any deviation in performance due
PT
to propagation delay.
N
Using Characteristic Equation
CLK Bn An Bn+1 An+1 X
SR Flip-Flop Characteristic Eqn.: Qn+1 = S + R’.Qn 0 0 0 0 1 0
1 0 1 1 0 0
SA = An’ SB = An.Bn’
2 1 0 1 1 0
EL
RA = An RB = An.Bn
3 1 1 0 0 1
An+1 = SA + RA’.An Bn+1 = SB + RB’.Bn
4 0 0 0 1 0
PT
Substituting, 5 0 1 …
Substituting,
Bn+1 = An.Bn’ + (An.Bn)’.Bn
N
An+1 = An’ + An’.An
= An’ = An.Bn’ + (An’ + Bn)’.Bn X = An.Bn
= An.Bn’ + An’.Bn + Bn’.Bn
= An.Bn’ + An’.Bn
= An Bn
Another Example
T Flip-
Flop
Qn X D Qn+1 Y
State toggles when input is
0 0 0 0 0 1, else maintains previous
0 1 1 1 1 state. Output is 1 when
EL
1 0 1 1 0 input received at State 0 is 1,
else output is 0.
1 1 0 0 0
PT
D = X Qn
Y = X.Qn’
N
References:
EL
PT
N
Conclusion:
• The analysis of a sequential logic circuit begins with a
specified / assumed initial state.
• The combinatorial logic part of the circuit is used to find
relation of final output and inputs at flip-flop terminals in
terms of current state and external input.
• The State Analysis Table lists all the inputs of the flip-slop
EL
at a given state and finds out next state using flip-flop
Truth Table and also notes the final output.
PT
• Analysis result is presented through a state transition
diagram and / or a text description.
N
• Timing diagram based analysis can evaluate the progress
of the state and can show effect of propagation delay, if
comparable.
• Flip-flop characteristic equation based study can help find
next state and output through algebraic manipulation.
N
PT
EL
EL
Goutam Saha
PT
N
Conversion of Flip-Flops and
Flip-Flop Timing Parameters
Lecture 35
Concepts Covered:
 Conversion of D Flip-Flop
 Conversion to D Flip-Flop
EL
 Flip-Flop Conversion: A Synthesis Problem
PT
 Flip-Flop Timing Parameters
N
D to other Flip-Flops
EL
Qn+1 = D
PT
N
Qn+1 = T.Qn’ + T’.Qn Qn+1 = S + R’.Qn
Qn+1 = J.Qn’ + K’.Qn
D = T.Qn’ + T’.Qn D = S + R’.Qn

D = J.Qn’ + K’.Qn
SR, JK Flip-Flops to D Flip-Flop
Qn+1 = S + R’.Qn Qn+1 = J.Qn’ + K’.Qn Qn+1 = T.Qn’ + T’.Qn
Consider, Consider,
?
EL
S=D J=D
R = D’ K = D’
PT
Then, Then,
N
Qn+1 = D + (D’)’.Qn Qn+1 = D.Qn’ + (D’)’.Qn
= D + D.Qn = D.Qn’ + D.Qn
= D.(1 + Qn) = D.(.Qn’ + Qn)
= D.1 = D = D.1 = D
D Flip-Flop from T Flip-Flop
D 0 1
D Qn Qn+1 T Qn
0 0 0 0 0 0 1
EL
0 1 0 1
1 1 0
1 0 1 1
PT
1 1 1 0
T = D.Qn’ + D’.Qn
N
Truth Table Qn+1 = T.Qn’ + T’.Qn
= (D.Qn’ + D’.Qn).Qn’ + (D.Qn’ + D’.Qn)’.Qn
Excitation Table = D.Qn’ + (D’.Qn’ + D.Qn).Qn
= D.Qn’ + D.Qn = D
Conversion: SR and JK
• JK Flip-Flop can directly replace SR Flip-Flop as the Truth Table differs only
for 11 input which is avoided in a circuit that uses SR Flip-Flop.
EL
PT
N
To obtain JK Flip-Flop
from SR Flip-Flop
Conversion: SR and JK
EL
PT
N
Flip-Flop Timing Parameters
Setup time: Minimum amount of time data must
be present before clock trigger arrives.
Hold time: Minimum amount of time data must be
held after clock trigger.
EL
Propagation delay: Time taken for the output to
change after clock trigger in response to the input.
PT
Parameter 74LS74A 74HC74
(VCC=5V) (VCC=4.5V)
N
tsetup (Data)^ 20 25 ^:minimum
time in ns
#:maximum time in ns
thold ^ 5 ≈0
tp (CLK to Q)# 25/40* 44 *:L
to H / H to L
fmax$ 33 50 $:typical in MHz
References:
EL
PT
N
Conclusion:
• Conversion of D Flip-Flop to any other Flip-Flop is
straight forward if we consider the characteristic
equations.
• Conversion of SR and JK Flip-Flop to D Flip-Flop can be
done by comparison of their characteristic.
• The conversion of T Flip-Flop to D Flip-Flop can be
EL
posed as a synthesis problem. In this, D Flip-Flop Truth
Table and T Flip-Flop Excitation Table are required.
PT
• Conversion of SR Flip-Flop to JK Flip-Flop or any one
type to other, can also be done through synthesis of
N
sequential logic circuit.
• Setup time, Hold time, Propagation delay are important
timing parameters of Flip-Flop that are key to its
reliable operation.
N
PT
EL
EL
Goutam Saha
PT
N
Register and Shift Register:
PIPO to SISO
Lecture 36
Concepts Covered:
 Week 7 Recap.
 Register
 Shift Register
EL
 Writing and Reading
PT
N
Week 7 Recap.
• A bistable circuit has two stable states. It can store one bit of information.
• When a clock is presented at the Enable input of SR latch, the circuit can change in one phase of the
clock. In synchronous sequential circuit, one state change can occur in every clock cycle, synchronized
with the clock.
• In a level-triggered flip-flop, there can be more than one or unintended state change in one clock
EL
cycle. Edge-triggered flip-flop ensures only one state change per clock cycle.
• Asynchronous preset / clear inputs is useful in setting / resetting a flip-flop without clock trigger.
PT
• The next state or output of a flip-flop can be obtained from its Truth Table. Characteristic Equation of
a flip-flop is a minimized Boolean representation of the next state.
N
• Excitation Table shows in tabular from what as input is required to move the flip-
flop from one particular state to other. Pictorially, it can be shown using state
transition diagram.
• Truth Table and Characteristic equations are useful for analysis of sequential logic
circuit while excitation table / state transition diagram come of use in synthesis.
Register
• A register is a group of flip-flops that can be used to store a
binary number.
• There must be one flip-flop for each bit in the binary number.
(To store an 8-bit binary number there must be 8 flip-flops.)
EL
Key Operations
PT
• Storing data (writing) in the register
• Retrieving data (reading) from the register. (PIPO)
N
Considerations
• Availability of input – output pins
• Time to write / read data
• Non-destructive / Destructive reading
Shift Register
EL
PT
(SISO)
(SIPO) (PISO)
N
PIPO and SIPO : PISO and SISO :
Non-destructive Destructive External feedback for
reading non-destructive reading
reading
PIPO (IC 74174)
EL
IC 74174
PT
N
Note: IC 74175 contains 4 D Flip-Flops but both Q and Q’ outputs in 16 pin package.
SISO (IC 7491)
EL
PT
Trade-off with time
N
Serial in: Writing
0 0 1 0
EL
PT
0 - - - -
0 0 - - -
N
1 0 0 - -
0 1 0 0 -
- 0 1 0 0
Q R S T
Serial out: Reading
Destructive
Reading:
3 clock cycles
EL
Serial
PT
- 1 0 1 0
data
- - 1 0 1 out
N
- - - 1 0
- - - - 1
Q R S T 0 1 0 1 -
Serial out: Reading
Non-destructive
Reading:
4 clock cycles
EL
Data is rewritten while
PT
0 1 0 1 0 reading through
1 0 1 0 1 external feedback.
N
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
Q R S T
References:
EL
PT
N
Conclusion:
• A register is a group of flip-flops that can be used to
store binary data. One bit of information storage
requires use of one flip-flop.
• Parallel-input parallel-output (PIPO) option for data
storage requires largest number of input output ports
while serial-in, serial-out (SISO) requires the least.
EL
• The trade-off associated with serial mode is larger
number of clock cycles required to complete write or
PT
read operation.
• Serial out read operation on its own is destructive that
N
is data once read is lost.
• Additional circuitry in the form of serial out fed back as
serial in can write the data back in the shift register and
data once read is not destroyed.
N
PT
EL
EL
Goutam Saha
PT
N
Shift Register: SIPO, PISO
and Universal Shift Register
Lecture 37
Concepts Covered:
 Serial In Parallel Out (SIPO)
 Parallel In Serial Out (PISO)
EL
 Universal Shift Register
PT
N
Serial In Parallel Out
EL
PT
Also, serial
N
out from QH
Serial In and Asynchronous Reset
EL
1 1 0 1
1 1 0 1
PT
1 1 0 1 QXn: Level of QX before
1 1 0 1 last clock trigger
N
1 1 0 1
1 1 0
1 1
1
Parallel In Serial Out
IC 74166
EL
It also has serial in
PT
Pin 15 = 1: Shift
N
= 0: Load
SH = Shift.QG + Shift’.H … SB = Shift.QA + Shift’.B SA = Shift.Serialin + Shift’.A

Universal Shift Register
• A universal shift register can perform all four operations:
PIPO, SISO, SIPO, PISO IC 74194
• The shift is bidirectional.
- Left shift: QA ← QB ← QC ← QD ← Data in
- Right shift: Data in → QA → QB → QC → QD
EL
PT
N
IC 74194 is a 4-bit
universal shift register
IC 74194 S1 S0 Operation
0 0 No change
0 1 Right shift
1 0 Left shift
1 1 Parallel load
SA = S1’.S0’.QA + S1’.S0.SRSER
EL
+ S1.S0’.QB + S1.S0.A
…
PT
SD = S1’.S0’.QD + S1’.S0.QC
+ S1.S0’.SLSER + S1.S0.D
N
IC 7495A
EL
No built-in left shift!
PT
M = 1: Parallel load
M = 0: Right shift
Parallel load/
Left shift N
IC 7495A
Left shift through

parallel load when
Mode Control = 1
EL
PT
Serial data out
N
References:
EL
PT
N
Conclusion:
• In Serial In Parallel Out (SIPO) register, writing takes
more than one clock cycles but reading takes one.
• In Parallel In Serial Out (PISO) register, reading takes
more than one clock cycles but writing takes one.
• Universal shift register can perform PIPO, SISO, SIPO,
PISO operations. The shift operation here is
EL
bidirectional i.e. both left to right and right to left.
• An appropriate control logic decides which operation is
PT
to be performed when multiple options are available. A
Mode input or Select inputs decide the operation.
N
• If a specific operation is not built-in, external
connection may be used to obtain that e.g. left shift in
IC 7495 can be obtained by external wiring that makes
use of parallel loading.
N
PT
EL
EL
Goutam Saha
PT
N
Application of Shift Register
Lecture 38
Concepts Covered:
 Serial Data Transmission
 Introducing Time Delay
EL
 Sequence Generator and Detector
PT
 Ring Counter
N
 Johnson Counter
Serial Data Transmission Appropriate protocol
between transmitter
and receiver on start
of data and its stop.
EL
PT
N
• One wire instead of eight wires
• Reduction in number of wires in transmission
line reduces cost
• Trade-off is with time taken for transmission
Introducing Time Delay IC 7491
EL
QH Delay = 8 x T
PT
T = Time period of clock
Output after n-bit is
N
delayed by nT time.
• Charging time = 0.693(RA + RB)C
• Discharging time = 0.693RBC
• Time period, T = 0.693(RA + 2RB)C If T = 1 µs, then delay here is 8 µs.
Sequence Generator
• Sequence generator is useful in generating a pattern repetitively. With serial data out fed
back directly as serial
data in, n-bit shift register
can generate up to n-bit
long pattern.
EL
PT
N
Sequence Detector • Sequence detector
identifies a specific pattern
from incoming bit string.
• Sequence to be detected
can be hard-wired to VCC
and GND in the circuit.
• The register gives a
EL
convenient option to
change the pattern to be
PT
detected.
N
Y = 0 changes to
Y = 1 when next
serial data enters.
Ring Counter IC 74164
EL
PT
Serial data out = 1 once in every
N
n clock cycle for a n-bit shift
register connected as shown.
Johnson Counter
EL
PT
• Also called Switched-Tail or
N
Twisted-Tail Counter.
• With n-bit register a count of
2n can be obtained.
• Different initialization possible.
• 2-input gate to decode.
References:
EL
PT
N
Conclusion:
• Parallel to serial conversion at transmitter end and serial
to parallel conversion at receiver end help in reducing
number of transmission channels.
• Serial data can be appropriately delayed by selecting clock
time period and size of the shift register used.
• With serial data out fed back directly as serial data in,
EL
n-bit shift register can generate up to n-bit long pattern,
repetitively.
PT
• Shift register as sequence detector identifies a specific
pattern from incoming bit string.
N
• n-bit shift register in ring counter configuration can act as
a modulo-n counter and in Johnson counter configuration
as modulo-2n counter.
• Decoding required in Johnson counter can be done by
using 2-input logic gate.
N
PT
EL
EL
Goutam Saha
PT
N
Linear Feedback Shift Register
Lecture 39
Concepts Covered:
 Feedback Polynomial
 Pseudorandom Sequence
EL
 Primitive Polynomials
PT
 Internal Feedback
N
 Cycle Redundancy Check (CRC)
Feedback Shift Register Linear feedback example:
y = x1 + x2 + x7
Length 8
If shift register (SR) contains,
y
10011011 → y = 1 + 0 + 1 = 0
With clock trigger, SR value
x1 x2 x3 x4 x5 x6 x7 x8 01001101 → y = 0 + 1 + 0 = 1
…
EL
Feedback function Nonlinear feedback
PT
example: y = x1x2 + x7
N
Linear feedback: y = C1x1 + C2x2 + C3x3 + C4x4 + C5x5 + C6x6 + C7x7 + C8x8
Ci = 0 or 1 when 1, the output bit is tapped

+ : Sum operation obtained by Ex-OR
Feedback Polynomial
Example:
Length 8
x0 f(x) = x8 + x7 + x4 + x2 + x + 1
f(x) = x8 + x7 + x2 + x + 1
x1 x2 x3 x4 x5 x6 x7 x8 f(x) = x8 + x7 + 1
EL
Tap from bit 7 and 8
Ex-Ored and fed as
Feedback function
PT
serial input to bit 1
N
f(x) = 1 + C1x1 + C2x2 + C3x3 + C4x4 + C5x5 + C6x6 + C7x7 + C8x8
For n-bit shift register, degree of the polynomial is n.

Pseudorandom f(x) = x4 + x3 + 1
Sequence Cycle length = 15
Pseudorandom sequence:
000100110101111..
If QRST = 0000, it remains
locked i.e. no change in state
EL
Also possible with Ex-NOR
PT
feedback where 1111
excluded.
N
Non-Maximal Length
EL
PT
f(x) = x3 + x2 + 1
N
Cycle length = 7
Primitive Polynomials Degree Polynomial#
2, 3, 4, 6, 7 xn + x + 1
• Polynomials that produce maximal length (2n – 1) 5 x 5 + x2 + 1
sequence are called primitive polynomials. 8 x 8 + x6 + x5 + x + 1
• Necessary (but, not sufficient condition) to be 9 x 9 + x4 + 1
primitive polynomial 10 x10 + x3 + 1
EL
- No. of taps even #Polynomial that requires
- Tap numbers are co-prime minimum number of Ex-OR
PT
• If tap sequence of n-bit LFSR generating primitive gates for given degree.
polynomial is n, m, l, k, …, 0 then the tap sequence
N
n - n, n - m, n - l, n - k, …, n - 0 i.e. x5-5 + x5-2 + x5-0
i.e. x5 + x3 + 1
0, n - m, n - l, n - k, …, n will also give primitive is also primitive
polynomial. polynomial
Internal Feedback
Ext. feedback
Primitive polynomial for

external feedback also
gives maximal length for
EL
internal feedback and
f(x) = x4 + x3 + 1 generates pseudorandom
sequence (different).
PT
Cycle length = 15
N
Pseudorandom sequence with int. feedback:
101011001000111..
Pseudorandom sequence with ext. feedback:

000100110101111.. (earlier)
External Input Clock Sin Q1 Q2 Q3 Clock Sin Q1 Q2 Q3
0 1 0 0 0 D1 = Sin Q3
0 1 0 0 0 1 1 1 0 0 D2 = Q1 Q3
Example: Cycle Redundancy Check (CRC) 1 1 1 0 0 2 0 1 1 0
3 0 0 1 1
D3 = Q2
2 0 1 1 0
4 1 1 1 1 Qn+1 = Dn
3 0 0 1 1 5 0 0 0 1
1 2 3 4 1 1 1 1 6 1 1 1 0
EL
7 0 1 1 1
5 0 0 0 1
8 1 1 0 1
6 1 1 1 0
PT
9 0 0 0 0
g(x) = x3 +x+1 7 0 1 1 1 10 end 0 0 0
N
Transmitter 8 0 1 0 1 Receiver
Receiver
Message: 1100101(000) 9 0 1 0 0
Remainder: 010 Remainder: 000
No error 10 - 0 1 0
Coded
message: 1100101010 CRC is specially useful Q1Q2Q3: initialized with 000
for detecting burst error
3 check bits Transmitter
Application
• Fast Counter: Simpler feedback for which higher clock rate is possible.
• Test pattern generator: Pseudorandom pattern is efficient in high fault-
coverage of Application-Specific Integrated Circuit (ASIC).
• Scrambling: LFSR output is Ex-Ored with data to widen the bandwidth.
EL
• Cryptography: Pseudorandom numbers are generated from an LFSR with a
PT
seed value which serves as cryptographic key and provides efficient
encryption / decryption.
N
• Error Control Code: Used in Cycle Redundancy Check (CRC) for data
transmission and storage. It is popular as it is easy to implement.
(CRC-16: g(x) = x16 + x15 + x2 + 1 can detect up to 16 burst error)
References:
EL
PT
N
Conclusion:
• Linear Feedback Shift Register (LFSR) uses feedback of
chosen bits through Ex-OR (sum) operation and the
same can be expressed as a polynomial.
• Primitive polynomials generate maximal length
pseudorandom sequence for both external and internal
feedback of LFSR.
EL
• Necessary condition to generate primitive polynomials
is (a)number of taps would be even and (b)tap indices
PT
would be relatively prime.
• Cycle Redundancy Check (CRC) code, a error control
N
code, uses a generator polynomial and appends check
bits to message bits to form code words.
• LFSR in different form has many other applications as in
cryptography, test pattern generation, scrambling etc.
N
PT
EL
EL
Goutam Saha
PT
N
Serial Addition, Multiplication
and Division
Lecture 40
Concepts Covered:
 Serial Addition
 Serial Multiplication
EL
 Serial Division
PT
N
Serial Addition • Initially, register A and B store the
addend and augend.
• Least significant bits are first out
serially when addition starts.
• Initially, D flip-flop is reset. It stores
the carry generated from i-th bit
addition and feed that as input to
Register A
EL
(i+1)-th bit addition.
• Sum bit is serially entered in A.
• If required, next number to be
PT
Register B added with former two can be
serially entered in B.
N
Serial Addition Clock 0:
A: 00001010
Q: 0
B: 00001011
A: 10000101 Q: 0
Clock 1:
B: x0000101
A: 01000010 Q: 1
Clock 2:
EL
B: xx000010
…
…
PT
x: 0 or 1 depending on next
N
no., if any, to be added
8 clock cycles to complete 8 bit addition

Serial Multiplication x3x2x1x0 : 1101
y3y2y1y0 : 1011
1101 (13)10
X x3 x2 x1 x0 1011 (11)10
0
. . . y3 y2 y1 y0 Y -------------------
10001111
------
(143)10
… 4
EL
A7-1 7-bit adder B7-1 • X: Latch
PT
• Y: Shifts at –ve edge of clock
• M: Loads at +ve edge of clock
m7 m6 m5 m4 m3 m2 m1 m0 (Initial value 00000000)
N
•
• In storage of adder result, one left shift
… M
• Addition with m6..m0 returns as m7..m1
Example
x3x2x1x0 : 1101
y3y2y1y0 : 1011
x3x2x1x0 : 1101 1101
y3 : 1 y2 : 0
…
EL
AND o/p: 1101 0000 1101 1101
M output: 00000000 00001101 00011010 01000001
PT
M at adder i/p (in blue): 00000000 00011010 00110100 10000010
Other adder i/p (in blue): 00001101 00000000 00001101 00001101
N
--------------------- ------------- ------------- ------------- -------------
Addition result (in blue): 00001101 00011010 01000001 10001111
M at clock trigger: 00001101 00011010 01000001 10001111

Clock 1 2 3 4
Review: Combinatorial Divider Circuit
EL
PT
N
Serial Division
D6 … D0: 7-bit dividend
d3 d2 d1 d0 d3 … d0: 4-bit divisor
D7 … D4: 4-bit register
D3 … D0: 4-bit shift register
0 d3 … d0: 4-bit register
EL
0
5 4 3 2 1
PT
D7 D6 D5 D4 D3 D2 D1 D0
N
After 4 clock triggers:
1 and 5 can use D7 … D4: 4-bit remainder

Half-subtractor D3 … D0: 4-bit quotient
References:
 Lloris Ruiz A., Castillo Morales E., Parrilla Roure L., García Ríos A. Number Systems.
In: Algebraic Circuits. Intelligent Systems Reference Library, vol 66. Springer, Berlin,
EL
Heidelberg
PT
N
Conclusion:
• Serial addition uses an adder unit successively where
consecutive bits are presented from shift register. The
carry can be handled by a D flip-flop.
• In a serial multiplier realization, one of the factors is
shifted through a shift register and one bank of AND
gates and the adder block is used successively. In
EL
storage of adder result, one left shit is made.
• In a serial divider realization, one bank of unit cell
PT
comprising of subtractor and multiplexer can be used
successively.
N
• These unit cells in the divider circuit receive the
dividend bits through a register and a shift register and
places the remainder in quotient in them, respectively.
N
PT
EL
EL
Goutam Saha
PT
N
Asynchronous Counter
Lecture 41
Concepts Covered:
 Week 8 Recap.
 Counter Basics
 Asynchronous Up Counter
EL
 Asynchronous Down Counter
PT
N
 Asynchronous Up – Down Counter
Week 8 Recap.
• A register is a group of flip-flops that can be used to store binary data. One bit of information storage
requires use of one flip-flop. The four configurations used for this are: PIPO, SIPO, PISO, SISO.
Universal shift register can operate in all the modes that include bidirectional shift.
• Serial in / out mode of operation requires less number of input / output pins but at the cost of more
time required for data write / read.
EL
• Data reading through serial out is as such destructive but, non-destructive reading is possible with
data fed back as input.
PT
• Shift register can be used for parallel-to-serial and serial-to-parallel conversion that can reduce the
number of transmission channels required. It has its use in introducing delay, as sequence
N
generator, sequence detector and also as ring counter and Johnson counter.
• Linear Feedback Shift Register (LFSR) uses feedback of chosen bits through Ex-OR
(sum) operation and the same can be expressed as a polynomial. It has various
use as pseudorandom number generator and also, in error control code.
• Shift register can be used for efficient realization of adder, multiplier, divider.
Counter Basics
• A counter keeps a record of the number of times a particular event has occurred by advancing its state.
• In counter, a unique state of the digital circuit is associated with a particular count.
• With every trigger, the state advancement can be
- in any random order
EL
- a sequential increase (up counter)
- a sequential decrease from a pre-defined value (down counter)
PT
• All the flip-flops defining the state of the count get the trigger:
- simultaneously in synchronous counter
- at different point of time in asynchronous counter
N
• A modulo-n or mod-n counter has n different states. It returns to initial value
after n triggers. For m flip-flops used in counter design, 2m ≥ n.
• Usually, clock is given as input trigger. Mod-n counter is also called
divided-by-n counter.
Asynchronous Up Counter Also, called
Ripple Counter
CLK↓ C B A Count
- 0 0 0 0
• fA = fClock / 2
a 0 0 1 1
• fB = fClock / 4
EL
b 0 1 0 2
• fC = fClock / 8
c 0 1 1 3
PT
d 1 0 0 4
e 1 0 1 5
N
f 1 1 0 6
0 1 0 1 0 1 0 1 0 1 g 1 1 1 7
0 0 1 1 0 0 1 1 0 0 h 0 0 0 0
0 0 0 0 1 1 1 1 0 0
Cumulative Delay
TClock
For n flip-flops, the delay is nτ
EL
0 1 0 1 0
where τ is propagation delay
of each flip-flop.
PT
0 0 1 1 0
• No miss till nτ < Tclock
N
• Glitch
0 0 0 0 1
000 010 000

Asynchronous Down Counter
CLK↓ C B A Count Here, if output as
C’B’A’, then up counter
- 0 0 0 0
a 1 1 1 7 Similarly, previous up
b 1 1 0 6 counter circuit gives
EL
down count at its
c 1 0 1 5
inverted outputs.
1 0 0 4
PT
d
e 0 1 1 3
N
f 0 1 0 2
g 0 0 1 1
0 1 0 1 0 1 0 1 0 1
0 1 1 0 0 1 1 0 0 1
h 0 0 0 0
0 1 1 1 1 0 0 0 0 1
Asynchronous Up – Down Counter
EL
PT
N
Mode, M = 0: Up counter
M = 1: Down counter
IC 7493 4-bit Asynchronous
Binary Up Counter
Can be used as mod 2, 4, 8

and mod 16 counter
EL
Mod 8: CKA unused, CKB triggered
External connection (QA to CKB)
PT
when used as mod 16 and
CKA triggered.
N
References:
EL
PT
N
Conclusion:
• A counter keeps a record of the number of times a
particular event has occurred by advancing its state
which is unique for each count.
• Modulo-n counter has n different states. It is also called
divided-by-n counter. For m flip-flops used in counter
design, 2m ≥ n.
EL
• In asynchronous counter, clocking of consecutive flip-
flops are through rippling and in different point of time.
PT
• In up counter the counting states sequentially go up
and in down counter it sequentially come down.
N
Inverted outputs give counter of opposite kind.
• In asynch. counter, propagation delay is cumulative.
• In up – down counter, with suitable choice of external
control input, the circuit can act as up or down counter.
N
PT
EL
EL
Goutam Saha
PT
N
Decoding Logic and
Synchronous Counter
Lecture 42
Concepts Covered:
 Decoding Logic
 Glitch and Strobed Decoding Gate
 Synchronous Up Counter
EL
 Synchronous Down Counter
PT
N
 Synchronous Up – Down Counter
Decoding Counter State
Decoding 111 Once in every 8 clock
cycles, Y = 1 for 1 clock
cycle whenever the state
of the counter, CBA = 111
EL
PT
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
N
1 1
1 1
1 1
Decoding Logic
0 1 2 3 4 5 6 7 8 9 10
0 1 0 1 0 1 0 1 0 1 0
Decoding 7
0 0 1 1 0 0 1 1 0 0 1 A decoding gate connected
0 0 0 0 1 1 1 1 0 0 0 to the outputs of a counter
EL
1 1 is activated only when the
1 counter content is equal to
1
PT
a given state.
1 1
Mod-16 Counter:
N
4-input logic gate
for decoding
Glitch and Strobed Decoding Gate tp = FF Propagation delay
Note that the basic gate
delay for the decoding logic
which is smaller than FF, is
not shown in diagram .
111→000
1 111→(110)→(100)→000
EL
TClock usually much
PT
larger than tp
1
N
1 Strobed gate
Glitch between a and b
Glitch removed
Synchronous Up Counter
EL
PT
N
Timing Diagram
Decoding 6
tp = FF Propagation delay
0
EL
• No cumulative delay
PT
• No glitch
1
N
1
Synchronous Down Counter
C B A Count
0 0 0 0
1 1 1 7
1 1 0 6
EL
1 0 1 5
PT
1 0 0 4
0 1 1 3
N
0 1 0 2
0 0 1 1
0 0 0 0
1 1 1 7
Synchronous Up-Down Counter
Count states: DCBA
Up Counter: Clock to ‘Count up’
while ‘Count down’ held at 0.
Down Counter: Clock to ‘Count
down’ while ‘Count up’ held at 0.
EL
PT
M is mode of counter
N
M = 0: Up
M = 1: Down
References:
EL
PT
N
Conclusion:
• A decoding gate connected to the outputs of a counter is
activated only when the counter content is equal to a
given state.
• For optimal use of number of flip-flops in counter design,
n-bit counter requires n-input logic gate for decoding.
• Decoding gate strobed by clock can remove propagation
EL
delay related glitch in asynchronous counter.
• In synchronous counter, every flip-flop is triggered
PT
simultaneously which avoids accumulation of delay and
possible glitch.
N
• Unlike asynchronous Up or Down counter, additional logic
gates are required in synchronous counter circuit to have
appropriate inputs to a flip-flop.
• Design of synchronous up-down counter is analogous to
its asynchronous counterpart.
N
PT
EL
EL
Goutam Saha
PT
N
Cascading: Mod 2, 3, 5 for
Mod 6, 10, 1000 Counter
Lecture 43
Concepts Covered:
 Mod 3 Counter
 Mod 6 Counter by Cascading
 Mod 5 Counter
EL
PT
N
Mod 3 Counter
0 1 0 0
EL
0 0 1 0
PT
Clock B A JB = A KB = 1 JA = B’ KA = 1 Count
N
0 0 0 0 1 1 1 0
1 0 1 1 1 1 1 1
2 1 0 0 1 0 1 2
3 0 0 … … 0
Mod 6 Counter by Cascading
EL
0 1 0 1 0 1 0 1 0 1
PT
0 0 1 1 0 0 0 0 1 1
N
0 0 0 0 1 1 0 0 0 0
0 1 2 3 4 5 0 1 2 3
0 1 0 0 1 0 0 1 0
0 0 1 0 0 1 0 0 1
0 0 0 1 1 1 0 0 0
0 1 2 4 5 6 0 1 2
Mod 5 Counter
EL
PT
N
JA = C’, KA = 1 11 11 11 11 01 11
Flip-Flop JK inputs
JB = 1, KB = 1 11 11 11 shown for each
JC = AB, KC = 1 01 01 01 11 01 01 before clocking
EL
BCD 0 1 2 3 4 5 6 7 8 9 0
PT
0 1 2 3 4 8 9
N
10 11 12 0 1 Bi-quinary (5-2)
IC 7490A
BCD: QA to CLK B
Bi-quinary: QD to CLK A
EL
PT
N
CLR PRE
Earlier: Divided by 6 by cascading ÷ 3 and ÷ 2,
Divided by 10 by cascading ÷5 and ÷2
EL
PT
N
Counts from 0 to 999
References:
EL
PT
N
Conclusion:
• Mod-3 and 5 Counters require 2 and 3 flip-flops, respectively.
The last flip-flop output has a +ve / - ve edge in every 3 or 5
clock cycles in respective cases.
• Mod-3 counter with counting states 0-1-2-0 when cascaded with
a Mod-2 counter at its output gives a Mod-6 counter with
counting states 0-1-2-4-5-6-0.
• If the Mod-3 counter is connected at the output of Mod-2
EL
counter, the resulting Mod-6 counter has counting states 0-1-2-
3-4-5-0.
PT
• Mod-5 counter with counting states 0-1-2-3-4-0 when cascaded
with a Mod-2 counter at its output gives a Mod-10 counter with
N
counting states 0-1-2-3-4-8-9-10-11-12-0 (Bi-quinary).
• If the Mod-5 counter is connected at the output of Mod-2
counter, the resulting Mod-10 counter has counting states 0-1-2-
3-4-5-6-7-8-9-0 (BCD).
• Three Mod-10 counter in cascade gives Mod-1000 counter.
N
PT
EL
EL
Goutam Saha
PT
N
Counter Design with
Asynchronous Reset and Preset
Lecture 44
Concepts Covered:
 Asynchronous Reset to change Modulo Number
 IC 7490A and Asynchronous Reset / Preset
 Parallel Data Input in IC 74193 Up – Down
EL
Counter and Change in Modulo Number
PT
 A Digital Clock
N
Use of Asynchronous Reset
Clocking for BCD Counter Clock QDQCQBQA Count
0 0000 0
CLK
1 0001 1
2 0010 2
EL
3 0011 3 Mod 6
4 0100 4
PT
5 0101 5 Glitch: For the
duration of internal
6 (0110) (6)
N
AND gate propagation
0000 0
delay << TClock
7 0001 1
+5 V Mod 9: If QD and QA to R0(1) and R0(2)
Mod 8: If QD to both R0(1) and R0(2)
Mod 7: Since QCQBQA = 111 to reset, 3-input gate (external)
Use of Asynchronous Fixed Preset
Clock QDQCQBQA Count
Clocking for BCD Counter
0 1001 9
CLK 1 0000 0
2 0001 1
EL
3 0010 2 Mod 7
4 0011 3
PT
5 0100 4 For the duration
of internal AND
6 0101 5
N
gate propagation
7 (0110) (6) delay << TClock
1001 9
+5 V 8 0000 0
9 0001 1
IC 74193 Synchronous 4-bit Up – Down Counter with
Parallel Data-in (variable Asynchronous Preset)
EL
PT
N
Timing Diagram
EL
PT
N
Asynchronous Preset in
Up and Down Count
If instead, Preset data
DCBA data input for Preset: 1001

input, DCBA = 0110
then, Up Count: Mod 9
EL
Down Count: Mod 7
PT
Up count: Mod 6 N
Down count: Mod 10
A Digital Clock Synchronization
• Depressing ‘Set hours’ push
button, hour count advances by
one in each second.
• Depressing ‘Set minutes’ push
button, minute count advances by
one in each second.
• Depressing ‘Set seconds’ push
EL
button, second count is stopped.
PT
Decoder and display driver
N
7 segment display
References:
EL
PT
N
Conclusion:
• Using asynchronous reset, counting state 0 can be
enforced early and in a clock cycle in which a specific
count is reached.
• This helps in getting a modulo number of one’s choice
but a glitch occurs because the state causing reset
appears for a short duration.
EL
• The internal 2-input AND gates are useful in Counter ICs
to effect asynchronous reset to obtain different modulo
PT
numbers.
• IC 7490A provides a fixed asynchronous preset of 1001
N
along with asynchronous reset to set modulo numbers.
• IC 74193 provides variable preset in the form of parallel
data-in which offers greater flexibility in this context.
• A circuit for digital clock can be made using counters.
N
PT
EL
EL
Goutam Saha
PT
N
Counter Design as Synthesis Problem
and Few Other Uses of Counter
Lecture 45
Concepts Covered:
 State Transition Diagram to State Table
 Design Equations and Logic Circuit
 Avoidance of Lock-Out
EL
 Use of Counter in Sequence Generation and
PT
in Time-Multiplexing
N
to State Table
Considered: JK Flip-Flop is used and the counter
is initialized with one of the valid six states.
EL
PT
N
Design Equations from K-Map
…
EL
JA = KA = 1
PT
N
Logic Circuit
JB = Cn’.An No glitch as was in Mod 6
JC = Bn.An
KB = An counter realization using
JA = KA = 1 KC = An asynchronous reset: CBA
000→001→010→011→100
1 0 0 1 →101→(110)000
EL
0 Here:
PT
0 1 1 000→001→010→011
1 0
→100→101→000
N
Role of Invalid States
Possibility of lock-in
EL
PT
N
No lock-in but,
not by design
Consideration of
Unused States
To come from invalid state(s)

to valid state(s) and to
EL
continue with the counting.
PT
N
Example:
Design Equations from K-Map
EL
PT
N
Logic Circuit
Without considering invalid states
EL
PT
N
Considering both the invalid states going to valid 000 at next clock trigger
Irregular Sequence
using D Flip-Flop
EL
PT
N
Few Other Applications D0 000 D0 in 0th, 8th, 16th … clock cycle
D1 in 1st, 9th, 17th … clock cycle
D1 001 …
C B A Y BA D2 010
0 0 0 0 00 01 11 10
D3 011 8-to-1 Parallel to Serial:
0 Y
0 0 1 1 0 1 0 0 D4 100 MUX Time Multiplexing
C
1 1 1 1 0
EL
0 1 0 0 D5 101
0 1 1 0 D6 110
PT
1 0 0 1 Y = B’.A + C.B’ + C.A C.L. D7 111
1 0 1 1 S2 S1 S0
N
1 1 0 0 Mod 8
C. L. Mod 8
1 1 1 1 CLK Counter Y
Counter
0 0 0 0
Sequence Generator CLK
References:
EL
PT
N
Conclusion:
• Sequential logic circuit design concept can be applied to
synchronous counter design for different modulo
numbers.
• Such design can avoid glitch which could be there in
asynchronous reset / preset based counter design.
• Lockout occurs when a counter remains trapped in
EL
unused state(s), if any, and cannot move to valid state(s)
on its own.
PT
• Avoidance of lockout can be included in design steps.
• It is possible to design counter with irregular sequence
N
of states and any of the JK, SR, D, T flip-flops by using
excitation table, state table, K-Map.
• Counters can also be used in parallel to serial conversion
through time multiplexing, sequence generation etc.
N
PT
EL
EL
Goutam Saha
PT
N
Synthesis of Sequential Logic Circuit:
Moore Model and Mealy Model
Lecture 46
Concepts Covered:
 Week 9 Recap.
 Basics of Moore Model and Mealy Model
 Synthesis of Sequential Logic Circuit using
EL
Moore Model and Mealy Model
PT
 Conversion between Moore Model and
N
Mealy Model
Week 9 Recap.
• A counter keeps a record of the number of times a particular event has occurred by advancing its state
which is unique for each count. Modulo-n counter has n different states. It is also called divided-by-n
counter. For m flip-flops used in counter design, 2m ≥ n.
• In asynchronous counter, clocking of consecutive flip-flops are through rippling and in different point
of time. Here, the propagation delay is cumulative.
EL
• A decoding gate connected to the outputs of a counter is activated only when the counter content is
equal to a given state.
PT
• In synchronous counter, every flip-flop is triggered simultaneously which avoids
accumulation of delay and possible glitch.
N
• Mod-m counter cascaded with Mod-n counter gives Mod-m x n counter. Counting
sequence changes with order of cascade. Mod 2 then 5: BCD; reverse: Bi-quinary.
• Using asynchronous reset, counting state 0 can be enforced early and in a clock
cycle in which a specific count is reached. But, a glitch may occur in decoding.
• Sequential logic circuit design concept can be applied to synchronous counter
design for different modulo numbers without any glitch.
Moore Model
EL
00/0
PT
0 0
1 1
N
11/1 01/0
1 1
• Input effects internal state and not output directly.
0 10/0 0
• Output is generated solely from flip-flops / registers.
• Output is synchronized with clock.
Mealy Model
EL
PT
• Input effects internal state and output directly.
N
• Output is generated from flip-flops / registers and input.
• Output is not synchronized with clock, may change if
the input changes during a clock period.
• Input transients / glitches may affect the output
Synthesis with Moore Model
State definition:
Problem Statement:
a: No bit is correctly decoded
A sequence detector for ‘110’ from a (initial state)
binary data stream is to be designed. b: 1 bit is correctly decoded
EL
c: 2 bits are correctly decoded
d: 3 bits are correctly decoded
PT
Digital State transition diagram
X Y
Circuit
Example:
N
CLK 0 1 2 3 4 5 6 7 8 9 10
Y is 1 if in the binary data stream, X
Input 0 1 0 1 1 1 0 1 1 0 0
a sequence 110 is detected else, Y
is 0. State a a b a b c c d b c d
Output 0 0 0 0 0 0 0 1 0 0 1
Synthesis with Mealy Model Problem Statement:
A sequence detector for
State definition: ‘110’ from a binary data
a: No bit is correctly decoded stream is to be designed.
(initial state)
b: 1 bit is correctly decoded
EL
c: 2 bits are correctly decoded
PT
Example:
N
CLK 0 1 2 3 4 5 6 7 8 9 10
Input 0 1 0 1 1 1 0 1 1 0 0
State a a b a b c c a b c a
State transition diagram
Output 0 0 0 0 0 0 1 0 0 1 0
Mealy – Moore Conversion
EL
PT
N
Synthesis Example
a2
EL
a1
PT
N
References:
EL
PT
N
Conclusion:
• In Moore Model, input effects internal state and not
output directly; output is generated directly from
internal states and is synchronized with clock.
• In Mealy Model, input effects both internal state and
output directly; output changes whenever input
changes and is not synchronized with clock.
EL
• Moore Model based sequential logic circuit usually
takes more states than Mealy Model.
PT
• Mealy Model responds faster to change in input.
N
• Moore Model is safer to use in the sense the input
transients or glitches are not passed to output.
• A Mealy Machine can be converted to Moore
Machine and vice versa by suitable conversion rule.
N
PT
EL
EL
Goutam Saha
PT
N
Moore Model and Mealy Model:
Realization of Digital Logic Circuit
Lecture 47
Concepts Covered:
 State Assignment
 State Table
 Design Equations
EL
PT
 Circuit Realization & Comparison of Complexity
N
Moore Model: State Assignment Problem Statement:
State assignment: ‘110’ from a binary data
For N states, number of flip-flops stream is to be designed.
required = log 2 𝑁𝑁 i.e. ceiling(log 2 𝑁𝑁)
EL
Flip-Flop Alternate assignment
PT
(one FF value changes!!)
State B A State B A
N
a 0 0 a 0 0
b 0 1 b 0 1
State transition diagram c 1 0 c 1 1
d 1 1 d 1 0
Moore Model: State Table
EL
PT
N
State table
Moore Model: Design Equations
EL
PT
Design Equations
N
Moore Model: Circuit Realization
EL
PT
N
Mealy Model: State
Assignment & State Table State B A
a 0 0
Continuing with the same design problem: A sequence
detector for ‘110’ from a binary data stream is to be designed. b 0 1
Required, log 2 3 = 1.585 = 2 Flip-Flops c 1 0
EL
PT
N
Mealy Model: Design Equations
Don’t care
Input
EL
included
PT
N
Mealy Model: Circuit Realization
Less complex
compared to
Moore Model
based circuit.
EL
PT
N
Mealy to Moore:
Another Example Also, by splitting b
1
0
0/0 1/0
a/0 b/0
Problem Statement: a b 0
0
A sequence detector for e/1 0 1
0/0
EL
‘1101’ from a binary 0/0 1/0 1
data stream is to be 1
1/1
PT
designed in which d/0 c/0
overlap is allowed i.e. d c
N
final bit(s) of a sequence 1/0 0
can be start bit(s) of next 0/0
sequence.
a: No bit detected b: 1 bit detected
c: 2 bits detected d: 3 bits detected e: 4 bits detected
References:
EL
PT
N
Conclusion:
• To realize logic circuit for Moore Machine or Mealy
Machine, the number of flip-flops required is log 2 𝑁𝑁
where N is the number of states in the model.
• Assignment of states to specific combinations of flip-
flop values are done next. One combination may give a
simpler circuit than the other.
EL
• Next, State Table is prepared using excitation table of
flip-flop used for circuit realization and design
PT
equations are obtained through simplification.
• Mealy Model provides more don’t care states for
N
equations involving flip-flop inputs while output
equation includes input.
• Mealy Model is usually found to have less hardware
complexity but directly passes input changes to output.
N
PT
EL
EL
Goutam Saha
PT
N
Algorithmic State Machine (ASM) Chart
and Synthesis of Sequential Logic Circuit
Lecture 48
Concepts Covered:
 Basic Components of ASM Chart
 ASM Chart and Mealy Model
EL
 ASM Chart and Moore Model
PT
N
Algorithmic State Machine (ASM) Chart
01
• State Transition Diagram though compact is unsuitable for 00
00 01
describing large state machines. a/0
b/1
• Algorithmic State Machine (ASM) chart is a flow diagram like 11 10 10
representation to design sequential digital electronic circuits. 11
EL
Basic Components: n input: 2n branch at each state
PT
State name
N
Output, if any, derived Output derived from Variable value?
only from state state and input
0 1
State Box Conditional Output Box Decision Box
ASM Chart: Mealy Model - Part 1
State Definition:
Problem Statement: a: Initial state i.e. money
Design circuit for a vending machine that takes only accumulated is zero.
Rs. 5 and Rs. 10 coin as inputs to deliver a product b: Rs. 5 accumulated.
that is priced Rs. 15. Coin sensing is as follows. c: Rs. 10 accumulated.
EL
I J Activity
PT
0 X No coin deposited
1 0 Rs. 5 deposited
N
1 1 Rs. 10 deposited
Other than the output, X for product , there is At every clock trigger, I is sensed.
another output, Y to return Rs. 5 if Rs. 20 is If I = 0, state is maintained. Both
received by the machine anyhow. output are 0.
Part 2 State Definition:
a: Initial state i.e. money
accumulated is zero.
b: Rs. 5 accumulated.
At state a, If I = 1, a coin c: Rs. 10 accumulated.
has been deposited.
EL
Then decision is taken on
PT
J = 0 / J = 1 whether the At state a, if IJ = 11,
circuit goes to state b / then, output XY = 00.
N
state c, at next clock
trigger.
At state b, If I = 1, a coin b: Rs. 5 accumulated.
has been deposited. c: Rs. 10 accumulated.
EL
Then decision is taken on
J = 0 / J = 1 whether the
PT
circuit goes to state c with
XY = 00 / delivers product
N
with XY = 10 and goes to
state a, at next clock
trigger.
At state c, If I = 1, a coin accumulated is zero.
has been deposited. b: Rs. 5 accumulated.
c: Rs. 10 accumulated.
Then decision is taken on J
EL
= 0 / J = 1 whether only
product is delivered with
PT
XY = 10 to go to state a /
product delivery and Rs. 5
N
return happen with XY = 11
and circuit goes to state a,
at next clock trigger.
Full ASM Chart
EL
Full ASM Chart for the
vending machine example.
PT
N
X
ASM Chart: Input: X Y
Moore Model Output: Y
Problem Statement:
EL
‘110’ from a binary data
PT
stream is to be designed.
ASM Chart N
References:
EL
PT
N
Conclusion:
• State Transition Diagram though compact is unsuitable
for describing large state machines.
• Algorithmic State Machine (ASM) chart is a flow diagram
like representation to design sequential digital electronic
circuits.
• Three basic components of ASM Chart are State Box,
EL
Conditional Output Box, Decision Box.
• Unlike others, Decision Box has two outputs. Based on
PT
the input value (0/1), one of the output path is followed.
• Entry into a state is synchronized with clock trigger.
N
• In Moore Model, conditional output box is not
necessary. There the output is shown in state box.
• In Mealy Model, output is available through conditional
output box.
N
PT
EL
EL
Goutam Saha
PT
N
Circuit Realization from ASM Chart
and State Minimization
Lecture 49
Concepts Covered:
 Circuit Realization from ASM Chart

based Design
EL
 Decoder-OR for Combinatorial Circuit
PT
 State Minimization: Row Elimination
Method
N
State Assignment accumulated is zero.
Problem Statement: c: Rs. 10 accumulated.
Design circuit for a vending machine that takes Two flip-flops: BA
only Rs. 5 and Rs. 10 coin as inputs to deliver a
product that is priced Rs. 15. Coin sensing is as State B A
follows.
EL
a 0 0
I J Activity b 0 1
PT
0 X No coin deposited c 1 0
1 0 Rs. 5 deposited
N
1 1 Rs. 10 deposited
Other than the output, X for product , there is

another output, Y to return Rs. 5 if Rs. 20 is
reached anyhow.
State Table a: Initial state i.e. money
c: Rs. 10 accumulated.
State B A
a 0 0
EL
b 0 1
c 1 0
PT
N
Design Equations
EL
PT
N
Design Equations
EL
PT
N
Circuit Diagram
EL
PT
N
Use of Decoder-OR 0000
0001
0010
Bn 0011
0100
An 0101
0110
I 0111
1000
1001
J … …
EL
1111
PT
…
N
DB
𝐷𝐷𝐵𝐵 = 𝐹𝐹 𝐵𝐵𝑛𝑛 , 𝐴𝐴𝑛𝑛 , 𝐼𝐼, 𝐽𝐽 = ∑𝑚𝑚(3,6,8,9) 𝐷𝐷𝐴𝐴 = ∑𝑚𝑚(2,4,5) 𝑋𝑋 = ∑𝑚𝑚(7,10,11) Y = ∑𝑚𝑚(11)

State Minimization
EL
PT
N
Two states are considered equivalent
if they move to same or equivalent
state for every input combination
and also generate same output.
Row Elimination Method
EL
PT
N
One row eliminated
Row Elimination Method
EL
Two rows eliminated
PT
Tautology: b and c are
equivalent if c and b
N
are equivalent
Three rows eliminated

References:
EL
PT
N
Conclusion:
• Circuit realization using ASM Chart is similar to State
Transition Diagram.
• It follows the steps like State Assignment, State Table
formation, Design Equations through simplification and
translating design equations to circuit.
• For large complex circuit using D flip-flops, state table can
EL
be mapped to Decoder-OR based realization for
combinatorial part of the circuit.
PT
• State reduction technique is useful in removing redundant
state(s), if any, to give minimized circuit.
N
• Two states are considered equivalent if they move to
same or equivalent state for every input combination and
also generate same output.
• In row elimination method, redundancy is removed by
sequentially eliminating row(s) after testing equivalence.
N
PT
EL
EL
Goutam Saha
PT
N
State Minimization by Implication Table
and Partitioning Method
Lecture 50
Concepts Covered:
 State Minimization using Implication

Table Method
EL
 State Minimization using Partitioning
Method
PT
 Difference between Mealy Model and
N
Moore Model based State Minimization
Implication Table Method: Part 1
Example:
EL
PT
N
• Lower diagonal of a matrix where row and column
represent states.
• At the cross-point the conditions for equivalence
between two states crossing each other, are tested.
Part 2
EL
• First, states are identified
PT
which cannot be equivalent,
as their outputs do not
N
match.
• Next, necessary conditions
for equivalence is written at
the cross points.
Part 3
• Relationships obtained in
previous steps are used for
further marking of cross-
points.
• This is repeated till no further
marking is possible.
√
EL
PT
• Finally, pairwise equivalence is
checked starting from rightmost
N
√ column and a Partition Table is
obtained.
Partitioning Method
Partition P1 : For each input, the Partition Partition
output is identical for blocks (Output/Next State) Blocks
formed due to partition. P0 a b c d e f
Partition P2 : If for each input, next Output for X = 0 0 0 0 0 0 0
EL
states lie in single block of P1. Output for X = 1 0 0 0 1 0 1
P1 a b c e d f
Partition P3 : If for each input, next
PT
Next state for X = 0 a c e c b b
states lie in single block of P2. P: (a)(bce)(df)
Next state for X = 1 b d f d a a
N
… P2 a b c e d f
until, Pk = Pk – 1 i.e. for each input, Next state for X = 0 a c e c b b
next states lie in single block of Next state for X = 1 b d f d a a
previous partition. P3 = P2 a b c e d f
Example with
Moore Model Partition
(Output/Next State)
Partition
Blocks
P0 a b c d e f
Output 1 1 0 1 0 0
P1 a b d c e f P: (ad)(b)(ce)(f)
EL
Next state for X = 0 b a b f f c
Next state for X = 1 e f c c e a
PT
P2 a b d c e f
Next state for X = 0 b a b f f c
Next state for X = 1 e f c c e a
N
P3 a d b c e f
Next state for X = 0 b b a f f c
Next state for X = 1 e c f c e a
P4 = P3 a d b c e f
References:
EL
PT
N
Conclusion:
• In the cross-point of an Implication Table, the equivalence
between two intersecting states are tested.
• In it, states are identified first which cannot be equivalent,
as their outputs do not match. Also, necessary condition
of equivalence is identified.
• Relationships obtained in previous steps are used
EL
iteratively. From this, final partition table is obtained that
provide the minimized states.
PT
• In Partitioning Method, the first partition considers that
the output is identical for blocks formed due to partition.
N
• Subsequent partition considers if for each input, next
states lie in single block of previous partition. This
continues till no further partition is possible.
• In state minimization, Moore and Mealy Model differ in 1st
step where output is considered.
N
PT
EL
EL
Goutam Saha
PT
N
Digital to Analog Conversion - I
Lecture 51
Concepts Covered:
 Week 10 Recap.
 Need of Conversion between Analog and Digital
EL
 Weighted Resistor based DAC
PT
 Binary Ladder based DAC
N
Week 10 Recap.
• Synchronous sequential logic circuit design can be done using Moore Model and Mealy Model.
• In Moore Model, input effects internal state and not output directly; output is generated directly from
internal states and is synchronized with clock.
• In Mealy Model, input effects both internal state and output directly; output changes whenever input
changes and is not synchronized with clock.
EL
• Mealy Model responds faster to change in input. In Moore Model, input transients or glitches are not
passed to output. Using conversion rules one model can be changed to other.
PT
• Mealy Model usually has less states, more don’t care positions in simplification
and accordingly, has less hardware complexity.
N
• Algorithmic State Machine (ASM) chart is a flow diagram like representation to
design sequential digital electronic circuits. It is preferred for large state machines.
• State reduction technique is useful in removing redundant state(s), if any, to give
minimized circuit. Two states are considered equivalent if they move to same or
equivalent state for every input combination and also generate same output.
Need of Conversion between Analog and Digital
Analog to Digital to
Digital
Digital Signal Analog
Converter Processing Converter
EL
ADC DAC
PT
N
• Most real world data are available in analog form.
• Aim is to use digital manipulation of data to one’s advantage.
• Need to have interfaces for analog-to-digital and digital-to-analog.
Weighted Resistor From KCL, Neglecting current
through very high
22 21 20 𝑉𝑉0 − 𝑉𝑉𝐴𝐴 𝑉𝑉1 − 𝑉𝑉𝐴𝐴 𝑉𝑉2 − 𝑉𝑉𝐴𝐴 resistance RL
+ + =0
𝑅𝑅0 𝑅𝑅1 𝑅𝑅2
EL
PT
N
1
𝑉𝑉𝐴𝐴 = (𝑉𝑉 + 2𝑉𝑉1 + 4𝑉𝑉2 )
7 0
Output Combinations
𝟏𝟏
𝑽𝑽𝑨𝑨 = (𝑽𝑽 + 𝟐𝟐𝑽𝑽𝟏𝟏 + 4𝑽𝑽𝟐𝟐 )
𝟕𝟕 𝟎𝟎
EL
1
𝑉𝑉𝐴𝐴 = (7 + 0 + 0) = 1 V
7
PT
0: 0 V
LSB weight = 1/7
1: +7 V
N 1
𝑉𝑉𝐴𝐴 = (7 + 0 + 4x7) = 5 V
7
Weighted Resistor and n-bit DAC
Extending for n-bit (n = 0,1,2 … , n – 1)
1
𝑉𝑉𝐴𝐴 = (𝑉𝑉 + 2𝑉𝑉1 + 4𝑉𝑉2 + 8𝑉𝑉3 +2𝑛𝑛−1 𝑉𝑉𝑛𝑛−1 )
2𝑛𝑛 −1 0
EL
1
LSB weight =
2𝑛𝑛 −1
PT
Limitations:
N
1 • Precision resistor required
𝑉𝑉𝐴𝐴 = (𝑉𝑉 + 2𝑉𝑉1 + 4𝑉𝑉2 + 8𝑉𝑉3 ) • MSB resistor is to handle much
15 0
more current than LSB resistor
LSB weight = 1/15 (For 8-bit: 128 times more)
Binary Ladder
𝑉𝑉0
Extending to next cut, 𝑉𝑉𝐴𝐴 =
16
EL
LSB weight = 1/16
PT
Consider, only V0 is non-zero. Using
Thevenin’s Theorem for the cut shown,
N
2𝑅𝑅 𝑉𝑉0
𝑉𝑉𝑇𝑇𝑇 = 𝑉𝑉0 =
2𝑅𝑅+2𝑅𝑅 2 Extending further,
𝑅𝑅𝑇𝑇𝑇 = 2𝑅𝑅||2𝑅𝑅 = 𝑅𝑅
Weighted Sum
EL
𝑉𝑉1
𝑉𝑉𝐴𝐴 =
8
PT
Extending and from principle of superposition,
N
𝑉𝑉0 𝑉𝑉1 𝑉𝑉2 𝑉𝑉3
𝑉𝑉𝐴𝐴 = + + +
16 8 4 2
1
𝑉𝑉𝐴𝐴 = (𝑉𝑉 + 2𝑉𝑉1 + 4𝑉𝑉2 + 8𝑉𝑉3 )
16 0
Binary Ladder and DAC • Output impedance always R, regardless
of the number of bits.
• Terminating ladder with 2R impedance,
Consider, 5-bit ladder looking into any branch from any node,
0: 0 V impedance is 2R.
1: 10 V
• Each digital source sees input
10
LSB: = 0.3125 𝑉𝑉 impedance as 3R. (equal loading)
EL
25
Full scale voltage: With 2R termination, full scale o/p
PT
10(1 + 2 + 4 + 8 + 16) voltage = 9.6875 (2R/(R+2R))
= 6.4583V
25
Current drawn from each
N
= 9.6875 𝑉𝑉 digital source for R = 1KΩ
is 10V/3KΩ = 3.33 mA
References:
EL
PT
N
Conclusion:
• For digital manipulation of analog signal, analog to
digital conversion (ADC) is needed.
• To get back the processed digital signal in analog form,
digital to analog conversion (DAC) is needed.
𝟏𝟏
• Weighted resistor based n-bit DAC has LSB weight 𝒏𝒏 .
𝟐𝟐 −𝟏𝟏
KCL is useful to analyse such circuit.
EL
• DAC requires precision resistors. In it, MSB resistor
PT
handles 2n-1 times more current than LSB resistor.
𝟏𝟏
• Binary ladder based n-bit DAC has LSB weight 𝒏𝒏 .
N
𝟐𝟐
Thevenin’s Theorem is useful to analyse such circuit.
• Binary ladder based DAC has constant output
impedance irrespective of number of bits. It can have
equal loading for each input.
N
PT
EL
EL
Goutam Saha
PT
N
Digital to Analog Conversion - II
Lecture 52
Concepts Covered:
 Use of Buffer Amplifier
 Additional Circuitry of a DAC
 Decoding Multiple Signals
EL
 Performance Issues
PT
N
 DAC 0808
Non-Inverting Buffer Amplifier Output impedance
of binary ladder is R.
• It is required to ensure that the output of ladder, VA does not vary with
change in load at its output else, misinterpretation of digital input. 𝑉𝑉𝐴𝐴 × 𝑅𝑅𝐿𝐿
• A buffer is an intermediate circuit that isolates or separates one circuit 𝑉𝑉𝐿𝐿 =
𝑅𝑅 + 𝑅𝑅𝐿𝐿
from another.
EL
OA: Operational Amplifier
PT
•
•
Unity gain non-inverting op-amp N
Very high input impedance (no loading)
Inverting Buffer Amplifier
EL
PT
N
MSB produces current: V / 2R (virtual ground)
Next bit produces: V / 4R These currents go to output.
….
Other Blocks • Register stores digital information.
(Can be extended to n-bits) • Level amplifiers ensures that signals
presented to ladder network are of same
level and constant for Low and High.
• Gating at the input of register to store the
digital data properly in the register.
EL
• There is transient during data
transfer to register due to different
PT
rise and fall time.
• A settling time is required between
data shift and data read. It is main
N
factor behind maximum rate of
conversion.
To buffer
Decoding Multiple Signals
Sample and Hold Circuit
EL
S/H circuit is not required if one
PT
DAC for each channel as data will
remain stored in register ensuring
constant output.
N
• Analog output needs to be held between sampling periods.
• Capacitor holds the analog voltage till next sampling period.
• Op-amp has high impedance for which capacitor discharges slowly.
• Sampling rate depends on capacitor and frequency content of analog signal.
(Nyquist rate).
Performance Issues
Accuracy: It is a measure of how close is the actual
Slew rate: The maximum rate at which
value to theoretical value. It depends on the
analog output value of the DAC can
precision resistors and reference voltage supply.
change. It depends on the working of
output amplifier (op-amp).
Resolution: It is the smallest increment in the
EL
voltage that can be recognized. It depends on the
PT
number of bits in the input digital signal.
N
Consider, 4-bit ladder, reference 16 V Consider, 11-bit ladder, reference 10 V
Resolution = 16/24 = 1 V Resolution = 10/211 ≈ 5 mV
Accuracy 0.1 % = 16 mV Accuracy 1 % = 100 mV
More bits or less precise components Needed Less bits or more precise components
Performance Issues
Issue with 2nd
MSB: Problem
could be with AND
Gate / Amplifier
EL
PT
N
Monotonicity test: It checks if analog output voltage increases regularly
with increase in digital input.
Steady state accuracy test: Known digital no. to register; measurement of
analog output with accurate meter; comparison with theoretical value.
DAC 0808 •
•
VCC = 5 V
VEE = -15 V
8-bit Digital to Analog Converter
• Settling time = 150 ns
• Slew rate = 8 mA/µs
• Relative accuracy = ± 0.19%
• Output voltage range at Pin 4
= -0.6 V to +0.5 V
EL
• Output current range at Pin 4
= 0 to Iref
PT
• Iref = Vref / Rref
N Absolute accuracy depends on relative

accuracy and full scale current drift.
DAC 0808
EL
PT
N
References:
 http://www.ti.com/lit/ds/symlink/dac0808.pdf
EL
PT
N
Conclusion:
• Buffer circuit is used at the output of the ladder not to
load the network and ensure integrity of output voltage.
• Op-Amp in inverting and non-inverting mode can be
used as buffer circuit.
• Additional circuitry of a DAC involves register, level
amplifier, gating to shift digital input to register.
EL
• Settling time required between data shift and data
read primarily decides maximum rate of conversion.
PT
• Sample and Hold circuit is useful when conversion is
N
done for multiple channels using one DAC.
• Accuracy and resolution are important performance
metric of a DAC. Slew rate gives maximum rate of
change of analog output.
N
PT
EL
EL
Goutam Saha
PT
N
Analog to Digital Conversion - I
Lecture 53
Concepts Covered:
 Simultaneous Conversion and Flash Converter
 Counter based Conversion
EL
 Continuous Conversion
PT
N
Input Voltage C3 C2 C1 21 20
Simultaneous Conversion 0 to + V/4 0 0 0 0 0
+ V/4 to + V/2 0 0 1 0 1
+ V/2 to + 3V/4 0 1 1 1 0
+ 3V/4 to + V 1 1 1 1 1
• 21 is 1 if C2 is 1.
EL
• 20 is 1 if C3 is 1 or
C2 is 0 and C1 is 1.
PT
C3
21
N
C2 Encoder
20
C1
2 1 = C2
20 = C3 + C2’.C1
Flash Converter For 3-bit ADC, 7 comparators needed
(n-bit ADC requires 2n – 1 comparators)
2 2 = C4
21 = C6 + C4’.C2
20 = C7 + C6’.C5 + C4’.C3 + C2’.C1
EL
Encoding can also be achieved by
directly using priority encoder IC 9318.
PT
Reference voltages from precision
voltage divider network.
N
Simple, fast and thus, also called
flash converter. Limitation is in
number of required comparators
for large n.
Counter Method • Simpler than simultaneous
conversion for high resolution ADC.
• Counter always begins from zero.
• One comparator is required.
• More time is required for
conversion.
• Maximum conversion time is 2n
EL
clock period.
PT
Consider, 10-bit ADC and 1 MHz clock.
Max. conversion time = 210 x 1µs
N
= 1.024 ms
Average conversion time
Analog o/p
= 1.025 / 2 = 0.512 ms
of DAC
Gate and Control
EL
PT
OS: One shot (IC 555 in monostable mode
N
with appropriate choice of R and C)
The OS delay is to ensure that the counter

is reset in the beginning following which
control flip-flop allows clocking of counter.
Speed up by Continuous Conversion
Basic counter
based method
EL
PT
N
• If new START signal immediately after one • Speed up by not starting
conversion. from zero but from
• Different conversion time depending on previous value.
amplitude of signal. • Needs both up counter
• Transient time needs to be smaller than and down counter.
conversion time for proper reconstruction.
Continuous Conversion
One of Count up or
Count down is High
EL
At every clocking, OS resets
PT
Up/Down SR flip-flop. This makes
a fresh decision if Count up or
N
Count down and counter
advances by one unit i.e.
increments or decrements.
Continuous Conversion • The converter may oscillate when ladder
output is within 1 LSB of the analog signal.
• To avoid it, arrangement is made such that
up output will not be high unless ladder
voltage is more than ½LSB below the
analog signal.
Similarly, for down output these can be
EL
•
done by adjusting comparator (hysteresis).
Fast conversion when locked but that
PT
•
does not help if multiplexed input.
N
Converter digital output tries to track the analog input for
which it is also called A/D Converter – tracking type.
Count Limiting Gates
No Up count when all 1

reached (to stay at 111..1)
EL
PT
N
No Down count when all 0
reached (to stay at 000..0)
References:
 http://www.ti.com/lit/ds/symlink/dac0808.pdf
EL
PT
N
Conclusion:
• The simultaneous method of Analog to Digital Conversion
requires a bank of comparators and an encoder to convert
comparator outputs to digital equivalent.
• Flash converter uses simultaneous conversion. It is fast but
requires 2n – 1 no. of comparators for n-bit ADC.
• Counter based conversion requires only one comparator but
EL
it takes more time for conversion.
• Continuous-tracking type converter requires both up and
PT
down counter. It is faster when it gets locked.
• In continuous conversion, arrangement is made to avoid
N
oscillation. In this, up output of comparator will not be high
unless ladder voltage is more than ½LSB below the analog
signal. Similarly, for down output.
• Count limiting gates are used when analog input exceeds
highest value both in +ve and –ve directions.
N
PT
EL
EL
Goutam Saha
PT
N
Analog to Digital Conversion - II
Lecture 54
Concepts Covered:
 Successive Approximation based ADC
 Single Ramp ADC
EL
 Dual Trace ADC
PT
N
 Delta – Sigma ADC
Successive Approximation Continuous A/D
• Successively divides voltage Converter is not
ranges in half. advantageous if
input is multiplexed.
• n-bit register is first reset.
For that, successive
• Then, MSB is set to 1. approximation is
• DAC output is compared with
EL
suggested.
input by a comparator.
• From comparison, MSB Flip-
PT
Flop remains set or reset.
• Second MSB is set to 1.
N
• The process is repeated.
Example:
10×𝑉𝑉𝑟𝑟𝑟𝑟𝑟𝑟 11×𝑉𝑉𝑟𝑟𝑟𝑟𝑟𝑟
≤ 𝑉𝑉𝐴𝐴 ≤
16 16
Building Blocks When conversion time
is short, need to
consider other delays :
settling time of ladder
• n-bit ADC requires (DAC), comparator
n bifurcations i.e. delay, switching time of
n iterations. multiplexer etc.
EL
• Each iteration
PT
requires 1 clock
cycle.
N
10-bit converter with 1 MHz
clock completes conversion in
10 / 1 MHz = 10 µs
Use of Ramp Signal DAC used at the input of
comparator in ADC design is
driven by binary counter /
register and generates
staircase waveform.
EL
PT
N
Constant slope is a key requirement.
Single Ramp ADC
EL
PT
N
If ramp is 1 mV/µs, clock is 1
MHz, Vx = 345 mV, then 345
clock pulses to RESET with
latched display showing 345.
Strobe passes content of decade
counters to four latches. Variation in R,C affect.
Dual Trace ADC
Fixed
• Vr and t1 are constant.

• t2 value varies as per Vx.
EL
• Variation in R, C values
cancel out.
PT
Fixed N - ve ref. voltage
Dual Trace ADC • When the counter reaches the fixed count
at time t1, the CONTROL unit generates a
pulse to clear the decade counters to all 0s
and switch the integrator input to the
negative reference voltage Vr.
• The counter at the end of the conversion
EL
cycle stores t2 (clock is disabled).
PT
Consider, 1 MHz clock, Vr = - 1 V, t1 = 1000 µs,
RC time constant = 1.0 ms, Vx = 1.25 V.
N
In time t1, Vc = -1.25V
During t2, slope = 1 V/ms
t2 = (1.25/1) ms = 1250 µs
requires 1250 clocking.
Counter shows 1.250
CK A C D E B
A Comparison
Delta-Sigma ADC 0
1
5/8
5/8
0
5/8
0
5/8
0
1
0
+1
Delta-Sigma: 8-32 bits, <1MS/S
Sample Dual Trace: 12-20 bits, <100 S/S
Converter 2 5/8 -3/8 2/8 1 +1
Integrator Clock (fs) Suc. Approx.: 8-18 bits, < 10MS/S
Clock (kfs) 3 5/8 -3/8 -1/8 0 -1 Flash: 4-12 bits, <10 GS/S
A Serial
C D 4 5/8 13/8 12/8 1 +1
+ + E out Flash: expensive, high power
5 5/8 -3/8 9/8 1 +1
Analog - Dual Trace: noise immune
- 6 5/8 -3/8 6/8 1 +1
Input B (use in digital voltmeter)
EL
Latched Digital Filter 7 5/8 -3/8 3/8 1 +1 Succ. Approx.: Low cost
Comparator and Decimator 8 5/8 -3/8 0/8 0 -1
+ Vref Note: Technology is changing
PT
9 5/8 13/8 13/8 1 +1 fast and accordingly, limits.
10 5/8 -3/8 10/8 1 +1
Vref = ±1V
N
11 5/8 -3/8 7/8 1 +1
1-bit Input = 5/8 V
12 5/8 -3/8 4/8 1 +1
DAC - Vref +1: 13
13 5/8 -3/8 1/8 1 +1
-1: 3
• Input needs to be oversampled (≈100 times) Average 14 5/8 -3/8 -2/8 0 -1
• Works well for slow changing signal = (13 – 10)/16 15 5/8 13/8 11/8 1 +1
• High resolution possible but low speed =5/8 16 5/8 -3/8 8/8 1 +1
References:
 https://www.digikey.com/en/articles/techzone/2018/apr/match-the-right-adc-to-
the-application
EL
PT
N
Conclusion:
• Successive approximation type ADC overcomes the
limit of continuous type ADC when converting multiple
inputs. It successively divides voltage range in half.
• n-bit successive approximation type ADC requires n
clock cycles for conversion.
• Slope of single ramp ADC is highly affected by variation
EL
in R and C.
• The integrator of dual trace ADC averages out noise and
PT
shows better noise immunity. However, it is slower.
• Delta- Sigma ADC needs to oversample the input and
N
works well for slow changing signals. It provides higher
resolution but at slower speed compared to successive
approximation and flash ADC.
• Flash ADC is fastest but takes more power, costs more.
N
PT
EL
EL
Goutam Saha
PT
N
Certain Performance Issues of
ADC and DAC
Lecture 55
Concepts Covered:
 Offset Error
 Gain Error
 Differential and Integral Nonlinearity Error
EL
PT
 ADC 0804 and its Use
N
Performance Issues
• A/D converter is a closed-loop system
involving both analog and digital systems.
• Digital error comes from resolution of the system.
EL
• Inherent error due to digital step is called quantization error.
• If the comparator is centred, the quantization error is ± ½ LSB.
PT
• Increasing number of bits, quantization error can be reduced.
• Main source of analog error is comparator which is centred around
N
variations in dc switching point.
• Variations in switching are primarily due to offset, gain, and linearity of the
amplifier used in the comparator (depends on i/p voltage and temperature).
• Other sources are: Resistor, Reference Voltage, Noise.
Offset Error For an ADC, the offset point is the mid-step
value when the digital output is zero.
For DAC, it is the step value Offset error is also

when the digital input is zero. called zero scale error.
Offset error is usually

compensated during
EL
calibration.
PT
N
Gain Error For an ADC, the gain point is the midstep
value when the digital output is full scale.
The gain error is the difference
For a DAC, gain point is the step value
between the nominal and
when the digital input is full scale.
actual gain points on the
transfer function after offset
error correction.
EL
Gain error can be adjusted
during calibration.
PT
N
Differential Nonlinearity (DNL) The counter-type and continuous-
type converters usually have better
differential linearity compared to
• Differential nonlinearity (DNL) error, sometimes seen as simply
successive approximation-type.
differential linearity error, is the difference between an actual step width
(for an ADC) or step height (for a DAC) and the ideal value of 1 LSB. ½ LSB DNL Limit
Loss of 1 bit
resolution
DNLk = (Widthk – 1 LSB)/ 1 LSB DNLk = [(Ok – Ok-1) – 1 LSB]/1 LSB]
EL
PT
ADC
N DAC
k-th code
Integral Nonlinearity (INL) The absolute accuracy or
total error of an ADC is the
maximum value of the
• Integral nonlinearity (INL) error, sometimes seen as simply linearity error, is
difference between an
the deviation of the values on the actual transfer function from a straight line. analog value and the ideal
• INL is the summation of DNL from the bottom up to a particular step. mid-step value. It includes
INLk = V(ideal)k – V(actual)k offset, gain, and integral
linearity errors and also the
EL
quantization error.
PT
ADC
N DAC
ADC 0804 • 8 bit, successive approximation type.
• Analog input range, 0 to + 5V.
• Single power supply, usually 5 V.
• Pin 9 is input ref. voltage, if left open it
is internally set at VCC/2.
• Output TTL and CMOS compatible.
EL
1
• Frequency of internal clock ≈
1.1×𝑅𝑅𝑅𝑅
f = 1/(1.1 x 10 kΩ x 150 pF) = 607 kZ
PT
• Conversion time ≈ 100 µs
• Total error (maximum) = ± 1 LSB
N
8 bit, eqv. to = 5/28 = 19.53 mV
• Output tri-stated.
00000000: 00H = 0 V
Free-running mode 11111111: FFH = 5 V
Span Adjustment
Vref = 2.5 V allows full scale
for input 0 to 5V
By making Vref = 1 V full scale

utilized for input 0 to 2 V.
EL
PT
Resistive divider:
N LSB is equivalent to
2 V / 28 = 7.8 mV
Zero Shift and Bipolar Input Vi : - 5 V to 5 V
Vi+ : 0 V to 5 V
Vi = - 5 V: 00H
Vi = + 5 V: FFH
EL
PT
N
Span: 5 V
• Digitizing analog signal in
the range 1.5 V to 4 V.
• Span is 2.5 V. Vref = 1.25 V LSB is eqv. to 10 V / 28
• LSB eqv. = 2.5/28 = 9.77 mV = 39.01 mV
References:
 http://www.ti.com/lit/an/slaa013/slaa013.pdf
 http://www.ti.com/lit/ds/symlink/adc0804-n.pdf
EL
PT
N
Conclusion:
• In ADC, the source of error comes from both digital and
analog part. Digital part error is related to quantization.
• For an ADC, offset error is found by giving zero to analog
input and increasing it till first transition occurs. For DAC,
it is the output when digital code is zero.
• The gain error is the difference between the nominal and
EL
actual gain points.
• Differential nonlinearity (DNL) error is the difference
PT
between an actual step width (for an ADC) or step height
(for a DAC) and the ideal value of 1 LSB.
N
• Integral nonlinearity (INL) error is the deviation of the
values on the actual transfer function from a straight line.
• ADC 0804 is an 8-bit successive approx. ADC providing
useful options such as span adjustment, zero shift etc.
N
PT
EL
EL
Goutam Saha
PT
N
Introduction to Memory
Lecture 56
Concepts Covered:
 Week 11 Recap.
 Types of Memory
EL
 Input – Output: Separate and Common
PT
 Linear and Matrix Addressing
N
 Memory Read and Write Cycles
Week 11 Recap.
• For digital manipulation of analog signal, analog to digital conversion (ADC) is needed. To get back the
processed digital signal in analog form, digital to analog conversion (DAC) is needed.
𝟏𝟏
• Binary ladder based n-bit DAC has LSB weight 𝒏𝒏 . It has constant output impedance irrespective of
𝟐𝟐
number of bits. It can have equal loading for each input. It is preferred to weighted resistor based DAC.
• Additional circuitry of a DAC involves buffer amplifier, register, level amplifier, gating to shift digital
EL
input to register, sample and hold for multiple inputs etc.
• Flash ADC uses simultaneous conversion. It is fast but requires 2n – 1 no. of comparators for n-bit ADC.
PT
• Counter based conversion requires only one comparator. Time taken by it to
complete a conversion can be reduced by continuous-tracking.
N
• Successive approximation type ADC overcomes the limit of continuous type ADC
when converting multiple inputs. It takes n cycles for n bit conversion.
• Dual trace ADC that uses integrator shows better noise immunity. However, it is
slower. Delta- Sigma ADC, good for slow-changing signals, oversamples input.
• Accuracy, resolution, digital and analog errors are key performance issues.
Types of Memory
• Circuits and/or systems designed specifically for data storage are referred to as memory.
• Memory may be flip-flop, register, semiconductor memory chips (also magnetic, optical).
• RAM (Random Access Memory) is volatile, meant for multiple read and write (Read/Write Memory).
• ROM (Read Only Memory) is non-volatile, meant for multiple reading, also random access.
Random access: Independent of the physical
EL
position of the memory within memory block.
Bit organized: 1-bit stored in
PT
one address
Word organized: Group of bits
N
stored in one address
There are further

subdivisions of each
If m address lines, memory type.
memory size 2m x n
Separate I/O Tri-state
Buffer –
Amplifier
EL
𝑊𝑊𝑊𝑊 = 𝐶𝐶𝐶𝐶𝐶. 𝑊𝑊
= 𝐶𝐶𝐶𝐶𝐶. 𝑅𝑅�
PT
CS R WR RD 𝑅𝑅𝑅𝑅 = 𝐶𝐶𝐶𝐶𝐶. 𝑅𝑅
0 0 1 0 �
= 𝐶𝐶𝐶𝐶𝐶. 𝑊𝑊
N
0 1 0 1
1 0 0 0
1 1 0 0
Memory IC Organization No. of pins Type
Common I/O 2114 1K x 4 18 Common
2115 1K x 1 16 Separate
2147 4K x 1 18 Separate
6168 (CMOS) 4K x 4 20 Common
All these Static RAM (doesn’t require refresh)
� as control logic i/p.
have 𝐶𝐶𝐶𝐶 and 𝑅𝑅/𝑊𝑊
EL
CMOS IC 6116 ( 2K x 8, 24 pins, Common)
PT
and 6264 (8K x 8, 28 pins, Common) have
𝐶𝐶𝐶𝐶, 𝑊𝑊𝑊𝑊, 𝑂𝑂𝑂𝑂 as control inputs where,
N
𝑾𝑾𝑾𝑾 = 𝑪𝑪𝑪𝑪𝑪. 𝑾𝑾𝑾𝑾𝑾
𝑹𝑹𝑹𝑹 = 𝑪𝑪𝑪𝑪𝑪. 𝑶𝑶𝑶𝑶𝑶. 𝑾𝑾𝑾𝑾
Common I/O lines save

number of external pins.
Linear Addressing
EL
IC 7489, 16 x 4, 64 bit
PT
RAM follows this
(word addressing)
N
Matrix Addressing
EL
8 lines
16 lines (preferred)
PT
• Square array requires fewest lines to
address a cell / group of cells (word-
N
organized) in particular location.
• Note that no. of address bits coming
to address decoder(s) of memory IC
remains same.
• Row address and col. address may
be time-multiplexed (saves pins).
Memory Read Cycle
Read cycle time (tread-cycle): Time to be allowed
between two consecutive valid addresses for
memory read (≈100 ns).
Access time (taccess): Time to be allowed between
EL
placement of stable address and availability of
stable data.
PT
Hold time (thold): Amount of time output data is
to remain valid after the address is changed.
N
tcs-access and tcs-hold are similar
quantities but w.r.t. CS signal.
Memory Write Cycle
Write cycle time (twrite-cycle): Time to be allowed between two
consecutive valid addresses fore memory write (≈100 ns).
Setup time (tsetup): Minimum time between
placement of valid address and write enable.
EL
Data write time overlap (toverlap): Minimum time
input to remain stable before write disables.
PT
Data hold time (tdata-hold): Minimum time data
to remain valid after write disables.
N
Similarly, taddress-hold.
Write enable time (twrite-enable):
Minimum time required for write
to remain enabled.
References:
 D. Raychaudhuri, Digital Circuits, Part II, Eureka Publisher
 https://www.digchip.com/datasheets/parts/datasheet/477/SN7489-pdf.php
EL
PT
N
Conclusion:
• Semiconductor memory chips are primarily of two types:
Random Access Memory (RAM) which is also called Read-
Write Memory and Read Only Memory (ROM).
• Both RAM and ROM are random access i.e. access time is
independent of physical location of the memory cell(s).
• Input and Output data lines to memory can be separate or
EL
common. It is time-multiplexed in common which leads to
savings in number of pins.
PT
• Memory addressing can be linear or matrix based. The
number of input lines required to locate cell(s) is minimum
N
for square matrix.
• In memory read and write cycle the sequence of
appearance of control inputs, address and data are
important and there are minimum allowable times for
various segments.
N
PT
EL
EL
Goutam Saha
PT
N
Static Random Access
Memory (SRAM)
Lecture 57
Concepts Covered:
 SRAM Memory Cell using BJT
 Reading and Writing of BJT Memory Cell
EL
 CMOS based SRAM Memory Cell
PT
 MOS based SRAM Memory Cell
N
SRAM using BJT Memory Cell: A multi-emitter
transistor pair operating in
bistable mode.
SRAM (Static RAM: BJT, MOS) in
contrast to DRAM (Dynamic RAM:
MOS) does not require refreshing. Representation of a BJT
based bit-organized SRAM
Control Logic: It decides when the chip is with array of cells (M x N)
EL
selected whether Din is to be written in cells using 2-dimensional
the cell or the cell is to be read out matrix based addressing.
PT
through Dout.
_
Write Amplifier: It contains circuitry to Dout Dout
N
send current to memory cell as per Din to
effect switching when required.
Read Amplifier: It contains circuitry to
sense the current from a cell and delivers
appropriate output Dout.
Din
BJT Memory Cell
Many such cells in parallel connect to Data lines with common Read
/ Write circuit. Individual cell is addressed by row select (X) and
column select (Y) lines.
Logic LOW is ≤ 0.3V and logic HIGH is ≥ 3.0V.
A bias voltage of 0.5V is applied to emitters ED0 and ED1.
EL
X = L and / or Y = L: if Q0 is ON then Q1 will be off (vice versa).
PT
No current through ED1 as Q1 is OFF.
No current through ED0 as EC0 / ER0 is at
0.5V – 0.3V = 0.2V lower potential.
N
Both X and Y are H: ED0 and ED1 come into
consideration (cell is read or written into)
i.e. the cell gets addressed.
Reading from the Cell
Memory cell is addressed by
making X = Y = H.
Consider, Q0 is ON and Q1 is OFF is

storage of 1 in the cell.
EL
____
Current flows from ED0 via Data
PT
through
___ base Q2 making Q2 ON.
Dout is L.
N
No current flows from ED1 via
Data through base Q3 and thus, Q3
is OFF. Dout is H.
Similarly, for ___
Q0 OFF and Q1 ON,
Dout is L and Dout is H.
Writing into the Cell Initially,
• If 𝐶𝐶𝐶𝐶 = H, the cell is neither read, Q0 is ON,
nor written into. (additional Q1 is OFF.
circuitry e.g. tristate)
�
• If 𝐶𝐶𝐶𝐶 = L, 𝑅𝑅/𝑊𝑊=H and X=Y=H, the
cell is read. VB4 = VB5 = H; Q4 and
Q5 are ON; VC4 = VC5 = L; D1 and D2
EL
do not conduct.
PT
• If 𝑪𝑪𝑪𝑪 = L, 𝑹𝑹/𝑾𝑾=L and X=Y=H, the cell is written into.
N
Case 1: Din = L, VB5 = H, Q5 is ON, D2 does not conduct.
VB4 = L, Q4 is OFF, D1 conducts forcing ED0 go H compared to
ED1, Q0 non-conducting i.e. OFF, VC0 go H, Q1 becomes ON.
Case 2: Din = H, VB5 = L, Q5 is OFF D2 conducts.
VB4 = H, Q4 is ON, D1 does not conduct. Q0 is ON, Q1 is OFF.
SRAM using CMOS • Basic memory cell is cross-coupled CMOS inverters.
• If Q2 is ON, VA = L, Q4 is OFF and VB = H (vice versa)
• Q1 to Q6: Basic cell and access to bitlines: 6T configuration
• Q5, Q6, Q7, Q8, Q9 are pass transistors.
• Q10, Q11 form CMOS inverter: output buffer.
• X=L, Y=L: Q5, Q6, Q7, Q8 are OFF, cell not addressed.
(Additional circuitry for CS)
A B
EL
Read: _
X=H,
___ Y=H, R/W=L: Q9 is OFF, Data = VA = L,
PT
Data = H, Dout = L (Similarly for VA = H)
There can be differential sensing of bitlines.
N
Write: _
X=H, Y=H, R/W=H: Q9 is ON.
Consider, Din = H.
Forced input makes VA = H
which in turn makes VB = L.
MOS SRAM
Matrix Addressing:
64 rows, 64 columns;
6 row address bits,
6 column address bits.
EL
PT
N
6T (Six transistor) configuration of
MOS memory cell with Q3 and Q4
connected as load (replaced with
resistors in 4T configuration) Organization of a MOS SRAM:
4096 x 1 bit MOS SRAM
References:
EL
PT
N
Conclusion:
• Static RAM or SRAM can be made with BJT, MOSFET and
in contrast to DRAM (Dynamic RAM: MOS), it does not
require refreshing.
• Basic BJT memory cell is made up of cross-coupled npn
transistor-inverters. If the cell is not addressed, the cross-
coupling holds one transistor ON, the other OFF.
EL
• During memory read, one of the sense-amplifier is ON
and the other is OFF that generate corresponding output.
PT
• During memory write, a condition is created to make
cross-coupled transistors ON/OFF in a specific way.
N
• SRAM using CMOS uses cross-coupled inverters for basic
memory cell. These 4 transistors and 2 pass transistors
giving access to bitlines form 6T configuration.
• MOS transistors with resistive load can give memory cell.
N
PT
EL
EL
Goutam Saha
PT
N
Dynamic RAM(DRAM) and
Memory Expansion
Lecture 58
Concepts Covered:
 DRAM Basics and Multiplexed Addressing
 4T DRAM Memory Cell and its Read and Write
EL
 3T and 1T DRAM Memory Cell
PT
 Address and Data Range Expansion
N
DRAM Basics and
Multiplexed Addressing
• MOSFET has nearly infinite input impedance and 16 Kbit
very low leakage current from gate. DRAM
• Charge can be stored on the MOSFET gate
capacitance for a short time.
EL
• The capacitance can act as a memory cell
providing a simple circuit that gives higher
PT
packing density at less cost.
The cell needs to be charged periodically (ms
N
• For larger sized memory, more address
order) even when no memory read or write. lines required as input. Addressing can
This is called refreshing of cells, characteristic of be multiplexed to save pins.
Dynamic Random Access Memory (DRAM). Row addr. and col. addr. use same
• DRAM timing cycles are more complicated than pins but latched into respective
SRAM timing cycles. registers through strobing.
Refreshing:
DRAM Memory Recharge of capacitor
Cell (4T) needed before the charge
loss is significant.
• Make X = H, R = H.
• Parasitic capacitors C1 and C2
• VDD recharges C1
store 1-bit information.
through Q4 and Q6.
EL
• Consider, Q1 ON is storage of 1. • C2 cannot be
Then C1 is charged to VDD and C2 charged as bypass
PT
is discharged i.e. Q2 is OFF. through Q1(ON).
• If not accessed, C1 voltage keeps Here, all cells
N
Q1 ON and low C2 voltage keeps of a row are
Q2 OFF. refreshed
• However, C1 charge leaks and together.
stored data may get lost.
Read:
Write and Read _
R/W = L: Q17 OFF (no ground
path through it or Q9, Q10)
X = H: Q3, Q4 ON ____
Cell is addressed VGQ13 = Data = C2 = L (say, Q1 ON)
Y = H: Q7, Q8 ON
Dout = VGQ13’ = H (inverter,
Write:
_
amplifier)
R/W = H: _ Q17 ON VGQ14 = Data = C1 = H
___
EL
Din = L, Din = H: Q9 OFF, Q10 ON Dout = VGQ14’ = L
VDQ9 = H (VDD through load Q11)
PT
VDQ10 = L
____
Data = H
N
Data = L
C2 becomes H, Q2 ON
C1 goes L (previous charge if any,
discharges through Q2(ON).)
DRAM Memory Cell: 3T and 1T • 1T configuration: C1 stores
1 bit. Q1 connects it to data
bit line or column line.
• X = H, Y = H, C1 is sensed in
read operation and
amplified for Dout.
• X = H, Y = H, C1 is charged /
discharged as per Din in
EL
write operation through
write amplifier.
PT
N
• 3T configuration: C (parasitic) stores 1 bit.
___
• C fully charged: H, Q2 ON; Dout = L when R = H. Reading is destructive due to larger
___ parasitic C2, restoration after each
• C fully discharged: L, Q2 OFF, Dout = H when R = H. read, pre-charging of data bit line to H,
• Din fully charges or discharges C when W = H. difference due to C1 storage is sensed.
Address Range Expansion • IC 2114 is a 1024 x 4 bits Memory chip.
• In this arrangement, A10A11 address
lines are decoded and the decoder
output goes to chip select inputs.
1024 x 4
A11A10A9 … A0: 0000 0000 0000 (000H)
4096 x 4 0011 1111 1111 (3FFH)
EL
A11A10A9 … A0: 0100 0000 0000 (400H)
0111 1111 1111 (7FFH)
PT
.
.
N
.
Data Range Expansion • IC 74201 is a 256 x 1 bit Memory chip.
• 8 address inputs A0 – A7 are used to
locate 256 memory cells.
• 4 such IC 74201 connected as shown
(common address lines) expands the
memory to 256 x 4.
EL
• In this arrangement, in each location, 4
bit words can be written or read from.
PT
N
256 x 1
256 x 4
Both Address and Data
Range Expansion
Thirty two IC 74201 Memory chip (each
256 x 1) is arranged in a matrix
formation (4 x 8) by which the resulting
EL
memory bank has 10 bit address lines
providing 1024 memory locations with
PT
8 bit data storage in each location.
N
256 x 1
1024 x 8
References:
EL
PT
N
Conclusion:
• DRAM (Dynamic RAM) is made from MOSFET where binary
information is stored in the form of charge at the gate
capacitance. It requires refreshing to replenish lost charge.
• Larger sized memory requires more address lines for which
row-column address multiplexing saves pins.
• 4T DRAM Memory Cell operation resembles MOSFET based 6T
SRAM Cell but without 2 load transistors. Charge stored in
EL
parasitic capacitances at cross-coupled transistor gates help in
PT
storing the information.
• There are 3T and 1T based DRAM Memory Cells. In 1T
N
Memory Cell, reading is destructive due to higher parasitic line
capacitance and it requires restoration.
• Address range of Memory can be increased by using additional
decoder and Chip Select input of a memory block. Data range
can be increased by putting memory blocks in parallel.
N
PT
EL
EL
Goutam Saha
PT
N
Read Only Memory (ROM)
Lecture 59
Concepts Covered:
 Decoder – OR Circuit and ROM
 ROM using Diode and Transistor Switch
EL
 Squarer Circuit using ROM
PT
 Programmable ROM (PROM)
N
 EPROM, EEPROM
Decoder-OR Circuit
and ROM
A2-0 D2-0
A Read Only Memory (ROM )
is memory device where A B C F1 F2 F3
EL
binary information is stored 0 0 0 1 1 0
in certain interconnection 0 0 1 0 0 1
PT
pattern that is non-volatile.
0 1 0 0 0 1
0 1 1 0 0 1
N
1 0 0 1 0 0 Decoder – OR circuit that is
equivalent to 8 x 3 ROM
2m x n 1 0 1 0 1 0
ROM
m address n data 1 1 0 1 0 0 ROM is essentially a
inputs outputs
1 1 1 0 0 1 combinatorial circuit.
Diode Switch From the list of data to be
stored, IC manufacturer
and ROM produces a mask (photographic
template) of the circuit which is
A2-0 D3-0 used in the production of ROM.
A B C Y3 Y2 Y1 Y0 𝑌𝑌3 = ∑𝑚𝑚(1,2,3,5,7)
EL
0 0 0 0 1 1 1 𝑌𝑌2 = ∑𝑚𝑚(0,3,4,7)
0 0 1 1 0 0 0 𝑌𝑌1 = ∑𝑚𝑚(0,2,4,6,7)
PT
0 1 0 1 0 1 1 𝑌𝑌0 = ∑𝑚𝑚(0,2,5,6)
0 1 1 1 1 0 0
N
1 0 0 0 1 1 0
1 0 1 1 0 0 1
1 1 0 0 0 1 1
1 1 1 1 1 1 0
A Squarer Circuit using ROM D0
D1
Consider a squarer circuit with 3-bit input in this example.
Input Output
A0 . D2
D3
A1 8x4
A2 A1 A0 Dec. D5 D4 D3 D2 D1 D0 Dec. ROM D4
A2
0 0 0 0 0 0 0 0 0 0 0 D 0 = A0
EL
D5
0 0 1 1 0 0 0 0 0 1 1 D1 = 0
PT
0 1 0 2 0 0 0 1 0 0 4
D2 = ∑ m(2,6)
0 1 1 3 0 0 1 0 0 1 9
N
D3 = ∑ m(3,5)
1 0 0 4 0 1 0 0 0 0 16
D4 = ∑ m(4,5,7)
1 0 1 5 0 1 1 0 0 1 25
D5 = ∑ m(6,7)
1 1 0 6 1 0 0 1 0 0 36
1 1 1 7 1 1 0 0 0 1 49 Less than 8 x 6 ROM does.
Squaring BCD 0000 0000 : 00
0000 0001 : 01
Other than Diode,
BCD Input (0 – 9) 0000 0100 : 04 BJT and MOSFET
0000 1001 : 09 can also be used
as switch.
0001 0110 : 16
BCD Squarer
EL
0010 0101 : 25
0011 0110 : 36
PT
IC IC 0100 1001 : 49
N
7447 7447 .
64
.
81 .
4-line BCD to 10-line
Decimal Decoder
To IC 7447 To IC 7447
Programmable
ROM (PROM) To store 1001 (Y3-0) in the
address location ABC = 000,
fuses at the cross points of
• PROM allows the user, instead of the Y2 and Y1 in the 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ row
manufacturer, to store the data. need to be burnt. Similarly
for other cross points
• An instrument called a PROM
EL
according to what is
programmer stores the words by
stored in each address.
“burning in.”
PT
• Originally, all diodes with a fusible
link remain connected at the cross
N
points.
• The PROM programmer sends
destructively high currents through
diodes that are to be removed.
EPROM, EEPROM
• The erasable PROM (EPROM) uses MOSFETs.
• Data is stored with an EPROM programmer.
• All stored data can be erased by shining ultraviolet light
through a quartz window that releases all stored charges.
• There is one time programmable EPROM without window.
EL
Electrical charge is forced on floating gate. When electron
is present, threshold voltage is higher than normal which
is usually considered as logic ‘0’; else, logic ‘1’.
Electrically Erasable PROM (EEPROM) is similar to EPROM
PT
where data is erased from target cells by removing the Reading: 5V to gates
charge for which a pulse of opposite polarity is sent. of both Q1 and Q2.
N
Q2 OFF if charge in
EEPROM is very slow. floating gate.
Flash Memory is further advancement of EEPROM. It is

much faster as data writing is in block (say, 512 bytes)
instead of 1 byte at a time.
EPROM: IC 2716 • For reading, valid address, 𝐶𝐶𝐶𝐶 and 𝑂𝑂𝑂𝑂 are
successively placed or made L to get valid output.
• Access time up to 450 ns.
• Erasing by exposing to light with wavelength
shorter than 4000 𝐴𝐴.̇ (2537 𝐴𝐴̇ recommended.)
• Opaque label to prevent slow erasing by
EL
sun / room light.
• During programming, Vpp is at 25 V,
PT
𝑂𝑂𝑂𝑂 is at H, data to programmed is
applied to output pins in parallel.
N
Data and Address level is TTL.
2K x 8 • When Address and Data are stable
a 50 ms TTL pulse to 𝐶𝐶𝐶𝐶.
• A verification is done after
programming.
References:
 https://www.futurlec.com/Memory/2716_Datasheet.shtml
EL
 https://web.eecs.umich.edu/~prabal/teaching/eecs373-f10/readings/rom-eprom-
eeprom-technology.pdf
PT
N
Conclusion:
• A Read Only Memory (ROM ) is memory device where
binary information is stored in certain interconnection
pattern that is non-volatile.
• ROM is essentially a combinatorial device which follows
Decoder-OR paradigm. The decoder generates all the
minterms. In the OR plane, Diode or Transistor switches are
EL
used at the cross points appropriately.
• While ROM is factory made, the Programmable ROM
PT
(PROM) provides opportunity to the developer to program
a pattern.
N
• Erasable PROM uses floating gate concept where charge is
stored to increase the threshold voltage of the transistor
for a specific switching operation.
• In EPROM, erasing is done by UV exposure. In Electrically
Erasable ROM (EEPROM), electrical pulse is used.
N
PT
EL
EL
Goutam Saha
PT
N
PAL, PLA, CPLD, FPGA
Lecture 60
Concepts Covered:
 Programmable Array Logic (PAL)
 Programmable Logic Array (PLA)
EL
 Realization of Multiple Outputs by PAL and PLA
PT
 Complex Programmable Logic Device (CPLD)
N
 Field Programmable Gate Array (FPGA)
PROM to PAL, PLA
PROM
• In PROM (Programmable Read
Only Memory), AND array is
fixed and OR array is
programmable.
EL
• In PAL (Programmable Array PAL
PT
Logic), OR array is fixed, AND
array is programmable.
N
• In PLA (Programmable Logic
Array), both AND and OR PLA
array are programmable.
PAL PAL IC 16L8 has 10 dedicated
inputs; 8 tristated outputs out of
which 6 can be fed back (I/O).
• A representative Programmable
Array Logic (PAL) circuit is shown.
• Each input is complemented as
well as uncomplemented.
Output comes from three wide
EL
•
AND-OR array sections.
PT
• One of the output is fed back and
Part of layout
is available to AND gate as input
N
(complemented and uncomplemented).
• Each AND gate along the horizontal
line has 10 programmable input
connections that connect to
vertical lines.
PAL IC 16R6 has 8 dedicated inputs;
PAL : Example 2 tristated combinatorial I/O and 6
tristated registered outputs.
W = ∑ m(2,12,13)
X = ∑ m(7,8,9,10,11,12,13,14,15)
Part of
Y = ∑ m(0,2,3,4,5,6,7,8,10,11,15) layout
Z = ∑ m(1,2,8,12,13)
EL
Individually, minimizing
PT
𝑊𝑊 = 𝐴𝐴𝐴𝐴 𝐶𝐶̅ + 𝐴𝐴̅𝐵𝐵𝐶𝐶
� 𝐷𝐷�
𝑋𝑋 = 𝐴𝐴 + 𝐵𝐵𝐵𝐵𝐵𝐵
N
̅ + 𝐶𝐶𝐶𝐶 + 𝐵𝐵� 𝐷𝐷
𝑌𝑌 = 𝐴𝐴𝐵𝐵 �
𝑍𝑍 = 𝐴𝐴𝐴𝐴 𝐶𝐶̅ + 𝐴𝐴̅𝐵𝐵𝐶𝐶
� 𝐷𝐷� + 𝐴𝐴𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴̅𝐵𝐵� 𝐶𝐶𝐷𝐷
̅
4 inputs
𝑍𝑍 = 𝑊𝑊 + 𝐴𝐴𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴̅𝐵𝐵� 𝐶𝐶𝐷𝐷
̅
PLA : Functional Diagram
Programmable Logic Array
PLS100 has
- 16 inputs,
- 48 AND gates,
- 8 OR gates,
- 8 Ex-OR gates
EL
(complements OR output if
1 is at the other input)
PT
- Final output is tristated by
chip enable.
N
- Also referred as
16 x 48 x 8 PLA
PLA : Example A
BC 00 01 11 10
_
0 0 0 1 0 F2
F1 = ∑ m(2,4,5,7)
1 0 1 1 0
F2 = ∑ m(0,1,2,4,6)
AC : Common product
BC 00 01 11 10
A
Joint minimization:
0 0 0 0 1
EL
F1
1 ̅ 𝐶𝐶̅
𝐹𝐹1 = 𝐴𝐴𝐵𝐵� + 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐵𝐵
1 1 1 0
PT
𝐹𝐹2 = 𝐴𝐴𝐴𝐴 + 𝐵𝐵𝐵𝐵
BC 00 01 11 10
A 𝐹𝐹2 = 𝐴𝐴𝐴𝐴 + 𝐵𝐵𝐵𝐵
N
0 1 1 0 1 F2
1 1 0 0 1
Six product terms. No common term.

Problem if there are less AND gates.
CPLD
• Programmable Logic Device or PLD
(also called, simple PLD or SPLD) can
handle 10 – 20 logic equations.
• For more complex circuits Complex
PLD or CPLD can be used in which
PLDs are interconnected.
EL
• Two level of programming is used. Macro cell of a PLD
One for PLD and another for – Each PLD usually has 8 to 10 cells.
PT
switches in Interconnection Block. – 16R8, 22V10 are PAL based PLD.
• Transistors are used as switches.
N
• Input, Output are routed through
I/O Block which provides buffering.
• Commercial CPLDs have up to 50
PLD blocks. (Xilinx XC 95288 , 16 Typical block diagram
blocks, 18 macrocells in each block.) representation of a CPLD
FPGA
• Field Programmable Gate Array (FPGA)
consists configurable logic blocks (CLB).
• Each CLB can generate logic functions of
many inputs (9 for Xilinx XC 4000).
• Logic blocks uses programmable look up
EL
table or LUT. The LUT can generate any Any of the possible 24
logic combination for the variables functions of 2 variables
can be obtained by this
PT
involved.
MUX based LUT.
• The interconnection switches in
N
interconnection blocks are either SRAM or
antifuse type.
• Antifuse is non-volatile, not
reprogrammable, offers low resistance.
• SRAM based FPGA comes with EPROM
which loads during power on. Typical structure of FPGA
References:
 M. Morris Mano and Michael D. Ciletti, Digital Design 5e, Pearson
 https://www.digchip.com/datasheets/parts/datasheet/364/PLS100-pdf.php
EL
 https://www.xilinx.com/support/documentation/data_sheets/DS063.pdf
PT
N
Conclusion:
• In contrast to PROM, PAL (Programmable Array Logic), has fixed OR
array and programmable AND array.
• In PLA (Programmable Logic Array), both AND and OR array are
programmable.
• Realization of multiple outputs by PAL requires individual
minimization. It takes into consideration the possibility of using
feedback from an already realized output.
EL
• Realization of multiple outputs by PLA considers joint minimization
and reuse of product terms.
PT
• Macro cell of a Programmable Logic Device (PLD) consists of
combinatorial logic elements and flip-flop. It can realize simple
N
Boolean equation. Each PLD usually has 8 to 10 macro cells.
• Complex PLD (CPLD) consists of interconnected PLDs. Switches at
interconnection is programmable.
• Field Programmable Gate Array (FPGA) consists of configurable
logic blocks (CLB). CLB uses look up table (LUT) to generate output.
N
PT
EL

Nptel Digital Gsaha

Uploaded by

Copyright:

Available Formats

Nptel Digital Gsaha

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Nptel Digital Gsaha

Uploaded by

Copyright:

Available Formats

Digital Electronic Circuits

 Why ‘Digital’ and what is ‘Digital’?

 Manipulation of digital signal

 Switching and logic operation

• Prefix ‘Digital’ associates a term with digital technology.

• Digital technology is considered more efficient for reasons such as:

• Digital systems represent and manipulate digital signals.

• Possibility of realizing NOT logic

 Noise margin, transition width, logic swing

• The values of IC and IB for this condition (the subscript EOS

• Thus Vin ≥ 1.66V the transistor saturates. (Saturating Logic)

NML = VIL – VOL = 0.7 – 0.2 = 0.5V

Transition width = VIH - VIL

• Similar calculation as before with Vout at 2.16V gives

Performance Issues and

 Propagation delay and power dissipation

 RTL NOR and NAND gate

 DTL NAND gate

 TTL NAND gate

tPHL: Delay in changing output from H to L

Propagation delay, tPD = (tPHL + tPLH)/2

tr: Rise time 10% to 90% of max.

It will be shown that any

• D1, D2, R1, VCC : AND logic at P.

Transistor Transistor Logic (TTL)

 TTL Open Collector configuration

II: T4 active. T3 Cut-off. T1 Sat., T2 Active

IV: T4, T3 Sat. T2 Cut-off. T1 inverse

2-input NAND gate From TI SN7402 (2-input NOR) datasheet

 CMOS Tristate and Open-drain

 CMOS – TTL Interface

NOR: T1A, T1B in parallel

NMOS: Charging / discharging of CL CMOS Inverter

NML = NMH = 1.5V

Fanout ≈ 50 (Limited by tP)

Basic Gates and their representations

 Basic Logic Gates

 Universality of NOR, NAND Gates

2-1 AOI Gate

Fundamentals of Boolean Algebra

 Basic Theorems and Duality

 Derivation of Theorems from Postulates

 Difference with ordinary Algebra

Associative Law: (x + y) + z = x + (y + z); (x.y).z = x.(y.z) From postulates

Operator precedence: Parentheses, NOT, AND, OR

x.y + x’.z + y.z = x.y + x’.z + y.z.1 We know, (x + y) + (x + y)’ = 1

Use of NAND (↑), NOR (↓) instead of AND (.), OR (+):

Boolean Function to Truth Table and

 Conversion of Boolean Function to Truth Table

 Implementation of a Boolean Function

 Shanon’s Expansion Theorem

Earlier: One NOT, One 2 i/p AND,

Note that, output Y is always L here and

Choice of A as expansion variable as it is associated with more number of terms

Truth Table to Boolean Function and

 Canonical representation using minterms

 Canonical representation using Maxterms

 2-Level, 3-Level Implementation

 Positive and Negative Logic

Y = F(A,B,C) = ∑ m(3,5,6,7) Y = F(A,B,C) = ∏ M(0,3,6)