Prepared By: Prof. C. S.
Mogare
Lecturer
MET BKC IOT Polytechnic, Nashik
9595159287
Prepared By: Prof. C. S. Mogare (9595159287)
Minterm & Maxterm:
Prepared By: Prof. C. S. Mogare (9595159287)
Minterm & Maxterm:
Output
1
0
1
0
1
1
1
1
The function is The function is
1 for these rows 0 for these rows
f(x1, x2, x3) = Σ m (0, 2, 4, 5, 6, 7) f(x1, x2, x3) = Π M (1, 3)
How to Write Equation from Truth table
in Minterm or Maxterm form:
A B Output (Y) MinTerm/
Maxterm
0 0 0 M0
0 1 1 m1
1 0 1 m2
1 1 0 M3
Minterm Representation : F(A,B)=Σ m(1,2)
Maxterm Representation : F(A,B)=Π M(0,3)
Prepared By: Prof. C. S. Mogare (9595159287)
Sum of Product (SOP):
In SOP different product terms of inputs are being summed together.
Sum and product derived from the symbolic representations of the OR and AND
functions.
OR (+) , AND ( . ) , addition and multiplication.
Types Of SOP form
1. Standard SOP: Product terms with less input variables.
2. Canonical SOP: Each product term must contain all input variables(Minterm).
Prepared By: Prof. C. S. Mogare (9595159287)
Sum of Product (SOP):
Prepared By: Prof. C. S. Mogare (9595159287)
Product of Sum (POS):
All these sum terms are ANDed (multiplied) together to get the product-of-
sum form.
Sum terms are defined by using OR operation and the product term is
defined by using AND operation.
Types Of POS form
1. Standard POS: Sum terms with less input variables.
2. Canonical POS: Each Sum term must contain all input variables (Maxterm).
Prepared By: Prof. C. S. Mogare (9595159287)
Product of Sum (POS):
Prepared By: Prof. C. S. Mogare (9595159287)
Conversion standard SOP to canonical SOP:
Step 1: Find Missing variable.
Step 2: Multiply each product term with (missing variable + Its Complement)
Step 3: Use distributive Law A.B.(C + C ) = A.B.C + A.B.C
Step 4: Simplify.
Prepared By: Prof. C. S. Mogare (9595159287)
Conversion standard POS to canonical POS:
Step 1: Find Missing variable.
Step 2: Add each Sum term with (missing variable * Its Complement)
Step 3: Law A + B + C . C = ( A + B + C ) . ( A + B + C )
Step 4: Simplify.
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Structure:
2m=n
m= No. of Input variables
n= No. of box in K-Map
Prepared By: Prof. C. S. Mogare (9595159287)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Structure:
Prepared By: Prof. C. S. Mogare (9595159287)
K Map filling technique:
Prepared By: Prof. C. S. Mogare (9595159287)
K Map adjacent cells:
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Grouping Techniques:
Pair : Group of two adjacent 1 or 0 is called “Pair”.
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Grouping Techniques:
Quad : Group of four adjacent 1 or 0 is called “Quad”.
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Grouping Techniques:
Octet: Group of eight adjacent 1 or 0 is called “Octet”.
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Rules: (for SOP)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Rules: (for SOP)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Rules: (for SOP)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Examples: for SOP
Simplify.
1) F(A,B,C) = ∑m(0,1,3,4,6) 2) F(A,B,C,D) = ∑m(0,1,2,4)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Examples: for SOP
Minimize using K map & realise using basic gates.
F(A,B,C,D) = ∑m(0,1,3,4,5,6,7,13,15)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Examples: for SOP
Minimize using K map & realise using NAND gates.
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Examples: for SOP
Minimize using K map & realise using basic gates.
F(A,B,C,D) = ∑m(1,5,6,7,11,12,13,15)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Examples: for POS
Minimize using K map.
F(A,B,C) = M(2,3,4,5,6,7)
Prepared By: Prof. C. S. Mogare (9595159287)
K Map Simplification Examples: for POS
Minimize using K map & realise using NOR gats.
F(A,B,C,D) = M(0,4,5,7,10,11,14,15)
Prepared By: Prof. C. S. Mogare (9595159287)
Combinational Circuits:
Its out put is depends on only present input.
Examples: Half adder, Full adder, Half Subtractor, Full Subtractor,
MUX, DEMUX.
Steps to build any digital circuit.
1. Block Diagram
2. Truth Table
3. Boolean Expression
4. Circuit Diagram
Prepared By: Prof. C. S. Mogare (9595159287)
Half Adder:
Half Adder is a combinational logic circuit.
It is used for the purpose of adding two single bit numbers.
It contains 2 inputs and 2 outputs (sum and carry).
Prepared By: Prof. C. S. Mogare (9595159287)
FullAdder :
It is used for adding two single bit numbers with a carry.
Thus, full adder has the ability to perform the addition of three bits.
Full adder contains 3 inputs and 2 outputs (sum and carry)
*Truth Table *Block Diagram *Boolean Expression
Inputs Outputs
S
A B Cin Cout
Sum
0 0 0 0 0
0 0 1 1 0 *Circuit Diagram
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Prepared By: Prof. C. S. Mogare (9595159287)
FullAdder using Half Adder :
It is used for adding two single bit numbers with a carry.
Thus, full adder has the ability to perform the addition of three bits.
Full adder contains 3 inputs and 2 outputs (sum and carry)
*Truth Table *Circuit Diagram
Inputs Outputs
S
A B Cin Cout
Sum
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
*Boolean Expression
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Prepared By: Prof. C. S. Mogare (9595159287)
Half Subtractor:
Half Subtractor is a combinational logic circuit.
It is used for the purpose of subtracting two single bit numbers.
It contains 2 inputs and 2 outputs (difference and borrow).
*Block Diagram: *Boolean Expression:
*Truth Table:
Inputs Outputs
D b *Circuit Diagram:
A B
(Difference) (Borrow)
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
Prepared By: Prof. C. S. Mogare (9595159287)
Full Subtractor:
Full Subtractor is a combinational logic circuit.
It is used for the purpose of subtracting three single bit numbers.
It contains 3 inputs and 2 outputs (difference and borrow).
*Truth Table *Block Diagram *Boolean Expression
Inputs Outputs
D
A B Bin Bout
Diff
0 0 0 0 0
0 0 1 1 1 *Circuit Diagram
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
Prepared By: Prof. C. S. Mogare (9595159287)
Full Subtractor using Half Substractor:
Full Subtractor is a combinational logic circuit.
It is used for the purpose of subtracting three single bit numbers.
It contains 3 inputs and 2 outputs (difference and borrow).
*Truth Table *Circuit Diagram
Inputs Outputs
D
A B Bin Bout
Diff
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
*Boolean Expression
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
Prepared By: Prof. C. S. Mogare (9595159287)
Need of Multiplexer:
In electronic system digital data available from more than one
sources and to route digital data over single line.
In telephone networks, multiple audio signals are integrated on a
single line of transmission with the help of a multiplexer.
The efficiency of the communication system can be increased by
allowing the transmission of data, such as audio and video data
from different channels through single lines or cables.
in computer memory to maintain a huge amount of memory in
the computers, and also to reduce the number of copper lines
required to connect the memory to other parts of the computer.
Multiplexer is used to transmit the data signals from the computer
system of a spacecraft or a satellite to the ground system by using
a GSM satellite.
Prepared By: Prof. C. S. Mogare (9595159287)
Multiplexer (Many to One):
It is a combinational circuit which have many data inputs and
single output depending on control or select inputs.
Multiplexers are also known as “Data n selector”.
Types MUX: 2:1 MUX , 4:1 MUX , 8:1 MUX , 16:1 MUX.
Prepared By: Prof. C. S. Mogare (9595159287)
4:1 Multiplexer:
4x1 Multiplexer has four data inputs I3, I2, I1 & I0, two selection
lines S1 & S0 and one output Y.
*Block Diagram: *Boolean Expression:
Out
I
put
n *Circuit Diagram:
p
u
t
Select
Lines
*Truth Table:
Prepared By: Prof. C. S. Mogare (9595159287)
MUX Tree: (4:1 Using 2:1)
Prepared By: Prof. C. S. Mogare (9595159287)
MUX Tree: (8:1 Using 4:1)
Enable S2
Prepared By: Prof. C. S. Mogare (9595159287)
MUX Examples:
Realize logical Function using Multiplexer.
Connect Minterms Connect Maxterms
to Logic 1 to Logic O
Prepared By: Prof. C. S. Mogare (9595159287)
De-Multiplexer:
It is a combinational circuit which have one data input and many
outputs depending on control or select inputs.
For N output lines, log n (base2) selection lines, or we can say that
for 2n output lines, n selection lines are required.
Types DEMUX: 1:2 DEMUX, 1:4 DEMUX, 1:8 DEMUX, 1:16 DEMUX.
2n =m
n= Select Lines
E m= Output
Prepared By: Prof. C. S. Mogare (9595159287)
1:4 DEMUX:
The single input ‘I’ will be connected to one of the four outputs,
Y3 to Y0 based on the values of selection lines S1 & S0.
*Block Diagram: *Boolean Expression:
Y0= IE S1 S0 Y1= IE S1 S0
Y2= IE S1 S0 Y3= IE S1 S0
*Circuit Diagram:
E
Select Line Output
*Truth S1 S0 Y
Table:
0 0 Y0 =I
0 1 Y1 =I
1 0 Y2 =I
1 1 Y3 =I
Prepared By: Prof. C. S. Mogare (9595159287)
DEMUX Tree: (1:8 Using 1:4)
Prepared By: Prof. C. S. Mogare (9595159287)
DEMUX Examples:
Implement full Adder using DEMUX.
Sum= ∑m(1,2,4,7) Carry= ∑m(3,5,6,7)
Inputs Outputs
S
A B Cin Cout
Sum
0 0 0 0 0
0 0 1 0 1
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
1 1 1 1 1
Prepared By: Prof. C. S. Mogare (9595159287)
Assignment:
1. Q.1 b) Define terms “Minterm” and “Maxterm” with proper example
Q.2 b) Convert the given minterm into standard POS form
2. Y(A,B,CD) = (ABC) + (BC D) + (A B)
3. Q.2 d) Prove A (A + C) (A B + C) (ABC + C ) = 0
Q.3 d) Simplify Y = F (A, B, C, D) = Σm (1, 2, 8, 9, 10, 12, 13) + d (4, 5) using K-MAP and write
4. expression. W-18
Q.4 b) Minimize the expression and draw logic circuit using basic gates.
5.
F(A,B,CD) = πM {0, 2, 4, 6, 7, 10, 11, 14, 15)
6. Q.4 e) Draw 16:1 multiplexer using 4:1 multiplexers “ONLY” with proper labels.
Q.6 b) Design full adder using K-MAP and draw logic circuit using basic gates and write truth
7. table.
8. Q.1 c) State the Boolean laws with expression.
S-19
9. Q.3 b) Design half adder using K-map and realize it using basic gate.
10. Q.1 b) State the principle of multiplexer and mention its two types.
Q.4 b) Minimize the four variable logic function using K-map and realize it.
11. f (A,B,C,D) = Σm (0, 1, 2, 3, 5, 7, 8, 9, 11, 14) W-19
Q.2 b) Simplify the given equation into canonical SOP form
12. Y = AB + AC + BC and represent the same equation in canonical POS form.
13. Implement Half adder & Full Subtractor using Demux.
14. Draw 1:16 Demultiplexer using 1:4 Demultiplexers.
Thank You