EEE 303

Digital Electronics
Introduction to Logic Circuits
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Basic Workflow

Network

❖Variables - Input and Output

❖Variables are in binary (0 or 1)

 Switch

❖Switch- Simplest binary element

❖Switch is open if x = 0 and closed if x = 1
 A Simple Function

Off
Off

❖Output- Condition of light (Denoted by L)

❖If the light is on, we will say that L = 1. If the light is off, we will say that L = 0.
 A Simple Function

On
On

𝑳 𝒙 =𝑿
❖Output- Condition of light (Denoted by L)

❖If the light is on, we will say that L = 1. If the light is off, we will say that L = 0.
 AND

❖Output is 1 only if both the inputs are 1

❖Symbols used- ‘.’, ‘&’

 OR

❖Output is 0 only if both the inputs are 0

❖Symbols used- ‘+’, ‘|’

 NOT

Off On
 NOT

On Off

❖Also known as inversion/complement

❖𝐿 𝑥 = 𝑥ҧ = 𝑥! = 𝑥 ′ = ~𝑥
 NOT

On Off

❖A resistance is used to avoid the short condition

Try Yourself

𝐿 𝑥 = (𝑥1 +𝑥2 ). 𝑥3
 Input and Output
❑ If I wake up at 3pm and its raining, I will cook. Otherwise I will play ludo.

➢ Wake up at 3pm = 1, Wake up at 4pm = 0.

➢ Raining = 1, Not raining = 0.
➢ Cook = 1, Play Ludo =0.

❖ So output is 1 only if both the inputs are 1. I will use an AND logic.

➢ Set i/p and o/p that makes sense.

 Logic Gate & Network

❖ Logic gate – A circuit element using which logic operation can be implemented
electronically with transistors

❖ Can have more than one inputs, generally one output

❖ In a circuit diagram or schematic, they are represented with symbols

❖ A network of gates is often called a logic network or simply a logic circuit

Logic Gate Symbols

AND Gate Symbols

Not Gate Symbols

OR Gate Symbols
Logic Network Example
 EEE 303
Digital Electronics
Analysis and Synthesis
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Analysis
❖ Analysis - To determine the function performed by an existing network

Given

Network
 Synthesis
❖ Synthesis - To design a new network that implements a desired functional behaviour

Find

Network
Analysis Technique
 Truth Table
Input Node Output

❖ LSB (𝑥2 ) changes (oscillates between 0 and 1) the most while MSB (𝑥1 ) changes
the least
❖ Total number of inputs = 2𝑛 where n= number of input bits
❖ Show the intermediate nodes
 Timing Diagram

❖ LSB (𝑥2 ) changes the most (time period small) while MSB (𝑥1 ) changes the least
(time period large)
❖ Use 2X time period for every next bit from LSB
❖ Show the intermediate nodes
 XOR Gate

Circuit Symbol
𝐿 = 𝑥𝑦ത + 𝑥𝑦
ҧ
Truth Table
Basic Gate Implementation
❖ If both inputs are same output is 0, if the inputs are different output is 1
❖ Symbol - ⊕ , ^

❖ 𝑥 ⊕ 0 = 𝑥 and 𝑥 ⊕ 0 = 𝑥ҧ → xor with 0 retains the input while xor with 1

complements the inptut
 XNOR Gate
Try yourself first!!!

𝐿 =𝑥⊕𝑦
Circuit Symbol
Truth Table
❖ If both inputs are same output is 1, if the inputs are different output is 0

❖ 𝑥 ⊕ 0 = 𝑥ҧ 𝑎𝑛𝑑 𝑥 ⊕ 1 = 𝑥 → xnor with 1 retains the input while xnor with 0

complements the inptut
 Synthesis
❖ Task- Addition of two one-digit binary numbers

Steps:

➢ Find out all the cases

➢ Form a truth table (make sure you have given all the inputs)

➢ Find out the required logic gates

 Synthesis
Remember the
definition – It
helps

❖ 𝑠1 = 𝐴𝑁𝐷 →Output is 1 only when both the inputs are 1

❖ 𝑠2 = 𝑋𝑂𝑅 → Output is 0 when both inputs are same, output is 1 when inputs differ
 More on XOR
Modulo 2 addition
❖ For many input XOR gate consider it as a modulo 2 addition

1. Sum all the inputs as using normal algebra

2. Divide by 2. The resultant modulus (remainder) is the output

Example:
𝐹𝑖𝑣𝑒 𝑖𝑛𝑝𝑢𝑡 𝑥𝑜𝑟: 𝟏 ⊕ 𝟎 ⊕ 𝟏 ⊕ 𝟏 ⊕ 𝟏 =? ? ?

1. 1+ 0 + 1 + 1 + 1 = 4
2. 4 ÷ 2 → Remainder is 0. So the output is 0.
❖ In another way, we can say that if the number of 1 is even the o/p is 0 and if the
number of 1 is odd o/p is 1
 EEE 303
Digital Electronics
2.3 Boolean Algebra
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Boolean Algebra
❖ Found application in engineering after almost 100 years
❖ Introduced by George Boole In 1849

Axioms
❖ Based on a set of rules derived from a small number of basic assumptions- Axioms
❖ Think of Euclidean Geometry
 Axioms and Theorems
Axioms Single Variable Theorems
Theorems
Theorems
Proof via Truth Table
 Principle of Duality
❖ Replace 0s with 1s and vice versa
❖ Replace ∙ with + and vice versa

𝑥. 𝑦 + 𝑦. 𝑧 + 𝑥.ҧ 𝑧 = 𝑥. 𝑦 + 𝑥.ҧ 𝑧

𝑥. 𝑦 + 𝑧 = 𝑥. 𝑦 + 𝑥. 𝑧
𝑥 + 𝑦. 𝑧 = (𝑥 + 𝑦). (𝑥 + 𝑧)
 Precedence of Operations
NAO - Not > And >Or

❖ Always put a parenthesis if you are confused

Problem 1
Problem 2
Problem 3
 EEE 303
Digital Electronics
2.4 Synthesis Using Minterm and Maxterm

Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Minterm
❖ For a function of n variables, a product term in which each of the n variables appears
once is called a minterm.
❖ The variables may appear in a minterm either in uncomplemented or complemented
form.
❖ Denoted by small letter ‘m’ with the corresponding number as subscript
Process:
1. Determine the binary
2. Uncomplemented if 1, complemented if 0
3. Product of all the variables
 Minterm

❖ Minterm is 1 for the corresponding number and zero for

all the other numbers
 Maxterm
❖ For a function of n variables, a product term in which each of the n variables appears
once is called a minterm.
❖ The variables may appear in a maxterm either in uncomplemented or complemented
form.
❖ Denoted by capital letter ‘M’ with the corresponding number as subscript
Process:
1. Determine the binary
2. Uncomplemented if 0, complemented if 1 (Be very careful!!!)
3. Summation of all the variables
 Maxterm

❖ Maxterm is 0 for the corresponding number and one for

all the other numbers
 Sum of Products (SOP)
❖ A function f can be represented by an expression that is a sum of minterms, where
each minterm is ANDed with the value of f for the corresponding valuation of input
variables.
❖ A logic expression consisting of product
(AND) terms that are summed (ORed) is said
to be in the sum-of products (SOP) form.

❖If each product term is a minterm, then the expression is called a canonical sum-of-
products for the function f .
Sum of Products (SOP)

Why???
Sum of Products (SOP)
❖Write the terms
❖Use Boolean Algebra

Most used equations:

𝒙+𝒙=𝒙
ഥ=𝟏
𝒙+𝒙
𝒙. 𝟏 = 𝒙
𝒙. 𝒚 + 𝒙. 𝒛 = 𝒙. (𝒚 + 𝒛)
Product of Sums (POS)

Why???
Switch
❖Write the terms
❖Use Boolean Algebra

Most used equations:

𝒙. 𝒙 = 𝒙
ഥ=𝟎
𝒙. 𝒙
𝒙+𝟎=𝒙
𝒙 + 𝒚 . 𝒙 + 𝒛 = 𝒙 + (𝒚. 𝒛)
Three Way Switch
Multiplexer Circuit
SOP in Minterms
 EEE 303
Digital Electronics
3.2 K Map Part 1
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Main Idea
❖ A systematic way of producing a minimum-cost logic expression

If a bit changes, it does not matter. If it stays the same, it matters

 Two Variable

❖1s for SOP, 0s for POS

❖Terms- minterm format for SOP, maxterm format for POS
 Three Variable - 1
Grey Coding

❖Select the largest chain (lateral or vertical) or rectangle with size 2𝑛 where n=0,1,2,3,…
❖Include all 1’s for SOP and all 0’s for POS
❖Chains may partially overlap (but full overlap is redundant)
 Three Variable - 2

❖ Grey coding is cyclic

Four Variable - 1
 Four Variable - 2
❖Cost= #gates+ #total inputs to all the gates
❖Input variables are available in both true and complemented forms at zero cost
Four Variable - 3
Four Variable - 4
Five Variable
 Things to Take
❖K-map provides the minimized SOP or POS version (not the most minimized form)
❖If a bit changes, it does not matter. If it stays the same, it matters
❖Include all 1’s for SOP and all 0’s for POS. Minterm format for SOP, maxterm
format for POS
❖Select the largest chain (lateral or vertical) or rectangle with size 2𝑛 where
n=0,1,2,3,… (even if some part of the largest is already selected)
❖Chains may partially overlap (but full overlap is redundant)
❖Grey coding is cyclic. So, the ends are connected

Practice! Practice!! Practice!!!

 EEE 303
Digital Electronics
3.3 K Map Part 2
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Literal and Implicant
Literal - Each appearance of a variable, either uncomplemented or complemented

Implicant- A product term that indicates the input valuation(s) for which a given
function is equal to 1
 Prime Implicant
Prime implicant -if it cannot be combined into another implicant that has fewer literals
 Cover
Cover - A collection of implicants that account for all valuations for which a given function
is equal to 1
❖ Obviously, a set of all minterms for which f = 1 is a cover
❖ It is also apparent that a set of all prime implicants is a cover.
 Cost
❖Cost= #gates+ #total inputs to all the gates
❖Input variables are available in both true and complemented forms at zero cost
❖If an inversion is needed inside a circuit, the corresponding NOT gate and its i/p are included
 Essential Prime Implicant
Essential Prime Implicant - If a prime implicant includes a minterm for which f = 1 that is
not included in any other prime implicant, then it must be included in the cover and is called
an essential prime implicant.
 Minimization Procedure
The process of finding a minimum-cost circuit involves the following steps:
❖Generate all prime implicants for the given function f .
❖Find the set of essential prime implicants.
❖If the set of essential prime implicants covers all valuations for which f = 1, then
this set is the desired cover of f . Otherwise, determine the nonessential prime
implicants that should be added to form a complete minimum-cost cover.
The choice of nonessential prime implicants to be included in the cover is governed
by the cost considerations. This choice is often not obvious.
Example - 1
Example - 2
Example - 3
 EEE 303
Digital Electronics
3.4 K Map Part 3
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Incompletely Specified Function
Suppose, that x1 and x2 control two interlocked switches such that both switches cannot
be closed at the same time. Thus the only three possible states of the switches are that
both switches are open or that one switch is open and the other switch is closed. Namely,
the input valuations (x1, x2) = 00, 01, and 10 are possible, but 11 is guaranteed not to
occur. Then we say that (x1, x2) = 11 is a don’t-care condition, meaning that a circuit
with x1 and x2 as inputs can be designed by ignoring this condition.

A function that has don’t-care condition(s) is said to be incompletely specified.

 SOP

❖Choose the value of d such that it helps to reduce the cost of the function (not the
largest chain of d)
POS
Example – 1 (Individual SOP)
Example – 1 (Combined SOP)
Example – 1 (Individual POS)
Example – 1 (Combined POS)
Example – 2 (Individual SOP)
Example – 2 (Combined SOP)
Example – 2 (Individual POS)
Example – 2 (Combined POS)
 EEE 303
Digital Electronics
3.5 Universal Gates
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Universal Logic Gates

❖NAND and NOR are universal logic gates

❖NAND and NOR functions are obtained by complementing the output generated by
AND and OR operations, respectively (in practical circuits, the opposite happens!!!)
❖Implemented with simpler electronic circuits
Gates Using NAND
Gates Using NOR
Conversion
Circuits using NAND
Circuits using NOR
 EEE 303
Digital Electronics
4.1 Arithmetic Circuits
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Half Adder
Full Adder
Full Adder from Half Adder
Ripple Carry Adder
Multiplication
Multiplication
Subtraction
Adder/Subtractor
Overflow
 EEE 303
Digital Electronics
4.3 Binary Coded Decimal
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
BCD
Addition
Schematic
Compact Circuit
 EEE 303
Digital Electronics
5.1 Multiplexers
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Combinational Circuits

❖Output is dependent on the combination of inputs

 Multiplexer

❖Multiplexer circuit has a number of data inputs, one or more select inputs, and one
output.
❖It passes the signal value on one of the data inputs to the output.
❖The data input is selected by the values of the select inputs.

n-to-1 multiplexer
2-to-1 Multiplexer
4-to-1 Multiplexer
4-to-1 Mux using 2-to-1 Mux
16-to-1 Mux using 4-to-1 Mux
Crossbar Switch
 Demultiplexer
❖Opposite function of a multiplexer - placing the value of a single data input onto
multiple data outputs
❖In this case the En input serves as the data input for the demultiplexer, and the y0
to y3 outputs are the data outputs. The valuation of w1 w0 determines which of
the outputs is set to the value of En.
Communication Line
 EEE 303
Digital Electronics
5.2 Synthesis Using Multiplexers
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Simple Way
❖ Choose all the inputs of the given function as the select pins of the mux
❖ Choose the outputs of the given function as the inputs of the mux- simple as that
Basic Gates Using Simple Way
XOR

x y f x y f
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
 Smart Way

❖ Choose some of the inputs (usually starting from the MSB) of the
given function as the select pins of the mux
❖ Derive the expression of the functions for those select pins – also
not that difficult
Basic Gates Using Smart Way
XOR

x y f x y f
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
3-Input Majority Function using 2-to-1 Mux
3-Input Majority Function using 4-to-1 Mux
3-Input XOR using 2-to-1 Mux
3-Input XOR using 4-to-1 Mux
Shannon's Expansion Theorem - 1
Shannon's Expansion Theorem - 2
Shannon's Expansion Theorem - 3
Shannon's Expansion Theorem - 4
Using only 2-to-1 Mux - 1
Using only 2-to-1 Mux - 2
Using Few Gates
 EEE 303
Digital Electronics
5.4 Decoders
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Decoder
❖ Decoder circuits are used to decode encoded information.
❖A binary decoder is a logic circuit with n inputs and 2𝑛 outputs.
❖An n-bit binary code in which exactly one of the bits is set to 1 at a time is
referred to as one-hot encoded
❖The outputs of a binary decoder are one-hot encoded.
2-to-4 Decoder
3-to-8 Decoder using 2-to-4 Decoder
4-to-16 Decoder using 4-to-2 Decoder
Mux from Decoder
Synthesis using Decoder - SOP
Synthesis using Decoder - POS
Memory Block
 EEE 303
Digital Electronics
5.5 Encoders
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Encoder
❖An encoder performs the opposite function of a decoder. It encodes given
information into a more compact form
❖A binary encoder encodes information from 2𝑛 inputs into an n-bit code
❖Inputs are one hot encoded for binary encoder
❖Are used to reduce the number of bits/wires in a digital system
4-to-2 Binary Encoder
8-to-3 Binary Encoder
 Priority Encoder - 1

❖In a priority encoder each input has a priority level associated with it
❖The encoder outputs indicate the active input that has the highest priority
❖When an input with a high priority is asserted, the other inputs with lower
priority are ignored.
Priority Encoder - 2
Priority Encoder - 3
Precedence- 2> 0 > 1> 3
 EEE 303
Digital Electronics
5.6 More on Combinational Circuits
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Arithmetic Comparator
Arithmetic Comparator Circuit
Code Converter
 EEE 303
Digital Electronics
6.1 SR Latch
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Need for a Memory
Simple Memory Element
Basic Latch with NOR Gates
Basic Latch with NOR Gates
Gated SR Latch
Gated SR Latch
Gated SR Latch with NAND Gate
Comparison
Debounce
 EEE 303
Digital Electronics
6.2 D Latch and Flip-Flop
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Gated D Latch
Gated D Latch
Master-Slave D Flip-Flop
Negative-Edge Triggered D Flip-Flop
Positive-Edge Triggered D Flip-Flop
Positive-Edge Triggered D Flip-Flop
Positive-Edge Triggered D Flip-Flop
Comparison
Master-Slave D Flip-Flop with Clear and Preset
Positive-Edge Triggered D Flip-Flop with Clear and Preset
Positive-Edge Triggered D Flip-Flop with Clear and Preset
Synchronous Reset
Propagation Delay
 EEE 303
Digital Electronics
6.3 Other Flip-Flops
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
T Flip-Flop
T Flip-Flop
JK Flip-Flop
 EEE 303
Digital Electronics
6.4 Conversion among Flip-Flops
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
D to T
D to JK
T to D
T to JK
JK to D
JK to T
SR to T
 EEE 303
Digital Electronics
7.1 Registers
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Registers

❖Registers are primarily used for the temporary storage of data present at the output
of a digital circuit before they are fed to another digital circuit.
❖When a set of n flip-flops is used to store n bits of information, such as an n-bit
number, we refer to these flip-flops as a register.
Shift Registers
Serial in Shift Register
Parallel in Shift Register
Bidirectional Shift Register
 EEE 303
Digital Electronics
7.2 Counters
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Counters
❖ The term asynchronous refers to events that do not have a fixed time relationship
with each other and, generally, do not occur at the same time.
❖An asynchronous counter is one in which the flip-flops (FF) within the counter do
not change states at exactly the same time because they do not have a common
clock pulse.
❖The term synchronous refers to events that have a fixed time relationship with
each other.
❖A synchronous counter is one in which all the flip-flops in the counter are clocked
at the same time by a common clock pulse.
Asynchronous Up Counter
Asynchronous Down Counter
Synchronous Up Counter
Synchronous Up Counter
Synchronous Up Counter with Clear and Enable
Synchronous Up Counter with D Flip-Flop
Synchronous Up Counter with D Flip-Flop
Synchronous Up Counter with Parallel Load Capability
Up-Down Counter
 EEE 303
Digital Electronics
7.3 More on Counters
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Counter with Parallel Load
Modulo-6 Counter with Synchronous Reset
Modulo-6 Counter with Asynchronous Reset
Two-Digit BCD Counter
Ring Counter
Ring Counter with Decoder
Johnson Counter
A Digital Clock
 EEE 303
Digital Electronics
8.1 Moore Type Sequential Circuit
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Sequential Circuit
 Moore Type Problem
❖The output z is equal to 1 if during two immediately preceding clock cycles the
input w was equal to 1. Otherwise, the value of z is equal to 0.
Forming State Diagram
Forming State Table
Forming State Assigned Table
Synthesis using K-map
Circuit
Timing Diagram
 Summary of Steps

State
State State Timing
Assigned Synthesis Circuit
Diagram Table Diagram
Table
Minimized Version (Optional)
One Hot Encoding (Optional)
 EEE 303
Digital Electronics
8.2 Mealy Type Sequential Circuit
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Mealy Type
❖ the output z should be equal to 1 in the same clock cycle when the second
occurrence of w = 1 is detected.

Mealy

Moore
Forming State Diagram
Forming State Table
Forming State Assigned Table
Synthesis using K-map
Circuit
Timing Diagram
Mealy to Moore (Optional)
 EEE 303
Digital Electronics
8.3 More on Sequence Detector
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Sequence Detector (1)
❖The output z is equal to 1 when the previous two values of w were 00 or 11.
Otherwise, the value of z is equal to 0.
State Diagram
Solution
 Sequence Detector (2)
❖The output z is equal to 1 when the two values of w were 00 or 11 in the current
cycle. Otherwise, the value of z is equal to 0.
Solution
 3 Consecutive 1’s
❖The output z is equal to 1 if during three immediately preceding clock cycles the
input w was equal to 1. Otherwise, the value of z is equal to 0.
Solution
 Parity Generator
❖The output z is equal to 1 when the number of 1’s in all previous cycles is odd and
z is equal to 0 when the number of 1’s in all previous cycles is even.
Solution
 EEE 303
Digital Electronics
8.4 Serial Adder
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Serial Adder
Mealy Type State Diagram
Solution
Circuit
Moore Type State Diagram
Solution
Circuit
 EEE 303
Digital Electronics
9.1 Basics of Asynchronous
Sequential Circuits
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
Asynchronous Sequential Circuit
 Steps

State Flow Excitation

Synthesis Circuit
Diagram Table Table
Basic SR Latch
State Diagram
Flow Table
Excitation Table
Synthesis
Circuit
Gated D Latch
State Diagram
Flow Table
Excitation Table
Synthesis
Circuit
 EEE 303
Digital Electronics
9.2 Applications of Asynchronous
Sequential Circuits
Rajat Chakraborty
Lecturer
Dept. of EEE, BUET
 Parity Generator

Suppose that we want to design a circuit that has an input w and an output z, such
that when pulses are applied to w, the output z is equal to 0 if the number of
previously applied pulses is even and z is equal to 1 if the number of pulses is odd.
Hence the circuit acts as a serial parity generator.
State Diagram
Solution
Potato Crackers Vending Machine
❖ Potato Crackers price – 10 tk.
❖ Only available coins – 5 tk. and 10 tk.
❖ Provides the chips when a total of 10 tk. is reached. Then returns to the
initial state
❖ Does not return change if 10 tk. is exceeded
❖ Cannot enter two coins simultaneously
❖ There is a gap between entering coins
State Diagram
Solution
Circuit