Combinational Logic Design

Combinational Logic Design
Prepared By: Bishal Khadka

Basic logic gates
• Building blocks of all the modern digital electronics system such as computer,
electronics devices etc.
• At least one or more input and single output
• Input and output values are only in logic state either True(T/1) or False (F/0)
• Total number of possible combination depends upon the number of input bit or
variables
Mathematically: N = 2n
• It have no memory
• Output depends only on the current values of inputs
• Logical relationship between inputs of the gate and output of the gate in tabular
format is called truth table

NOT Gate
• NOT gate accepts one input signal (0 or 1) and returns the opposite
signal as output

AND Gate
• If both i/p are 1, the output is 1; otherwise, the output is 0

OR Gate
• If both i/p are 0, the output is 0; otherwise, the output is 1

XOR Gate
• If both i/p are the same, the output is 0; otherwise, the output is 1

NAND Gate
• If both i/p are 1, the output is 0; otherwise ,the output is 1

• AND + NOT = NAND

NOR Gate
• If both i/p are 0, the output is 1; otherwise ,the output is 0

• OR + NOT = NOR
• Universal Logic Gate: Logic gate that can be used to construct all other
logic gates
Design Truth Table and Logic Circuit
• Examples??
i. Y = ABꞌ+Aꞌ
ii. Y = ABCꞌ+AꞌC+Bꞌ
iii. Y = (Aꞌ+C)(ACꞌ+D)+ABꞌ(Cꞌ+Dꞌ)
iv. XNOR Gate

Timing diagram of basic gates
• Whose timing diagram is this? AND Gate, OR Gate or NOT Gate
QN: Design timing diagram of all basic gates, other gates and universal gates.

Boolean Algebra
• Logic calculus of truth table
• Used to analyze and simplify the digital logic circuits
• It uses only the binary number i.e. ‘0’ and ‘1’
• It is an powerful tool in computer system design
• It is used to obtaining few number of gates while designing
circuits
• It uses some postulates and theorem to simplify expression

Some postulates and theorems

Contd…
• Verify Distributive law and absorption law using truth table
• Prove all the above theorems
• Duality Principle:
• Change binary operator ‘+’ to ‘.’ and vice versa
• Inverse all the identity element i.e. ‘0’ and ‘1’

De-Morgan’s Theorem
• Can be stated in two statements as follows:
i. The complement of sum of two or more variables is equal to the product of the complements of
individual variables
i.e. if ‘X’ and ‘Y’ are two variables then,
(X + Y) ꞌ = X ꞌ . Yꞌ
ii. The complement of product of two or more variables is equal to the sum of complements of individual
variables
i.e. if ‘X’ and ‘Y’ are two variables then,
(X . Y) ꞌ = X ꞌ + Yꞌ
• State De-Morgan’s first and second theorem. Verify using truth table. Also illustrate by gate equivalences.

Some related question??
1) Define universal gate. Why NAND and NOR Gate is called
Universal Gate.
a. Construct all basic gates using only NAND Gate
b. Construct all basic gates using only NOR Gate.
2) Realize Ex-OR gate using only NAND gates.

3) Realize Ex-NOR gate using only NAND gates.
4) Construct NOR gate using AND & NOT gate.
5) Construct NAND gate using NOR gate and NOR gate using NAND
gate

Boolean Algebra Simplification Rules:
Boolean Law Statement
Idempotent Laws AA = A A+A = A .
Associative Laws (AB)C = A(BC) (A+B)+C = A+(B+C) .
Commutative Laws AB = BA A+B = B+A .
Distributive Laws A(B+C) = AB+AC A+BC = (A+B)(A+C) .
Identity Laws A.0 = 0 A+0 = A
A.1 = A A+1 = 1 .
Complement Laws 1’ = 0 0’ = 1
AA’ = 0 A+A’ = 1 .
Involution Law (A’)’ = A
DeMorgan's Law (AB)’ = A’+B’ Prepared By:(A+B)’ = A’. B’
Bishal Khadka
Boolean Alzebra Simplification
#1. Simplify: C + ( BC )’ :
Expression Rule(s) Used

• C + ( BC )’ Original Expression
• C + (B’ + C’) DeMorgan's Law.
• (C + C’ ) + B Commutative, Associative Laws.
• 1 + B Complement Law.
• 1 Identity Law.

Boolean Alzebra Simplification
#2. Simplify: (A + B)(A + C) :
• (A + B)(A + C) Original Expression
• A.A + A.C + A.B + B.C Distributive law
• A + A.C + A.B + B.C Idempotent Law
• A + A.B + B.C Absorption Law {A + A.C = A}
• A + B.C Absorption Law {A + A.B = A}
 Hence, A+BC is the reduced expression.

Boolean Simplification
#3. Simplify: ( AB )’ (A’ + B)(B’ + B) :

• ( AB )’ (A’ + B)(B’ + B) Original Expression
• ( AB )’ (A’ + B ). 1 Complement law
• ( AB )’ (A’ + B ) Identity law.
• (A ’+ B’)(A’ + B) De-Morgan's Law
• A’ + B’B Distributive law.
• This step uses the fact that or distributes over and.
• It can look a bit strange since addition does not distribute over multiplication.
• X +YZ = (X+Y)(X+Z)
• A + 0 Complement
• A Identity.

Boolean Simplification
#4. Simplify (A + C)(AD + AD’) + AC + C :

 (A + C)(AD + AD’) + AC + C Original Expression
 (A + C) A(D + D’) + AC + C Distributive.
 (A + C)A.1 + AC + C Complement
 (A + C)A + AC + C Identity.
 A((A + C) + C) + C Commutative, Distributive.
 A(A + C) + C Associative, Idempotent.
 AA + AC + C Distributive.
 A + (A + 1)C Idempotent, Identity, Distributive.
A + C Identity (twice).
#5. Simplify: A’(A + B) + (B + AA)(A + B’)
?
Simplification: A’(A + B) + (B + AA)(A + B’)
 A’(A + B) + (B + AA)(A + B’) Original Expression
 A’(A + B) + (B + A )(A + B’) Idempotent (AA to A)
 A’A + A’B + (B + A)A + (B + A)B’ Distributive, used twice.
 A’B + (B + A)A + (B + A)B’ Complement (A’A=0) then Identity (0 +X =X).
 A’B + BA + AA + BB’ + AB’ Distributive, two places.
 A’B + BA + A + AB’ Idempotent (AA=A),Complement and Identity (BB’=0)
 A’B + AB + A1 + AB’ Commutative, Identity; {setting up for the next step}.
 A’B + A(B + 1 + B) Distributive.
 A’B + A Identity,
 A + A’B Commutative.
 (A + A’)(A + B) Distributive.
 A + B Complement, Identity.

Assignment: Simplification of Boolean expression
1. What is Boolean Simplification ? Why Boolean Simplification is required ?
2. Simplify the following Boolean expression

a. F=A+AꞌB
b. F=A(A ꞌ+B)
c. F=XY+X ꞌZ+YZ
d. F=(A ꞌ+B ꞌ) ꞌ + (A+B) ꞌ + (A+B ꞌ) ꞌ
e. F=(A+(BC) ꞌ) ꞌ
f. F= AB(B’C + AC) Ans: ABC
g. F= (A + B + C)(A +B + C)(A + B + C) Ans:A + (B C)

Canonical form
• Literal: Any variables which is primed or unprimed
• Term: It is an expression formed by literals
EX: F=X+YꞌZ, where X, Yꞌ & Z are literals and X & YꞌZ are terms of f
• Canonical form: Boolean function that is expressed as a sum of minterm or as a product of

maxterm.
EX: F=XYꞌZ+XꞌYZꞌ → Sum of minterm
F=(Xꞌ+Y+Zꞌ)(X+Yꞌ+Z) → Product of maxterm
• Minterm: ‘n’ variables forming AND term with each variables being primed or unprimed , provides
2n possible combinations (Note: variables being primed if the corresponding bit of binary no. is ‘0’
& unprimed if bit is ‘1’)
• Maxterm: ‘n’ variables forming OR term with each variables being primed or unprimed , provides
2n possible combinations (Note: variables being primed if the corresponding bit of binary no. is ‘1’
& unprimed if bit is ‘0’)
Contd…

Examples: • To represents F in sum of minterm,
• add all the minterm where F is 1
F = XꞌYꞌZ+XꞌYZꞌ+XꞌYZ+XYZ
= m1+m2+m3+m7
• Truth table = ∑(1,2,3,7)
XYZ F
000 0 • For maxterm:
001 1 F = (X+Y+Z)ꞏ(Xꞌ+Y+Z)ꞏ(Xꞌ+Y+Zꞌ)ꞏ(Xꞌ+Yꞌ+Z)
010 1
= M0ꞏM4ꞏ M5ꞏ M6
011 1
= ∏(0,4,5,6)
100 0
101 0
QN: Draw truth table of F=X+YꞌZ and find out minterm and
110 0
maxterm.
111 1

Standard form
• Sum of product (SOP) and product of sum (POS) are standard form
• SOP: An expression formed by ORing of already ANDed term
EX: XY+XꞌZ
• POS: An expression formed by ADNing of already ORed term
EX: (X+Yꞌ)(Yꞌ+Z)
• Solved Example:

Simplification of logic function using
Karnaugh Map(K-Map)
• Method of simplification of Boolean algebraic expression by diagrammatic method without using
Boolean algebra theorems and postulates
• Diagram made up of squares with squares representing one minterm of a function
• Rules:
1) Grouping most contains 2n cells i.e. 1,2,4,8,…..(Note: Each group should be large as
possible)
2) Group may be horizontal or vertical but not diagonal (Note: group may be overlapped)
3) Opposite grouping and corner grouping is allowed (i.e. group may warp around the table)
4) Highest Groups are Recommended however Fewest number of groups are also allowed
(Note: K-Map used in 2,3,4,5,6 variables)
(Meaning of warp around the table: leftmost cell in a row may grouped with the rightmost cell and
the top cell in a column may be grouped with the bottom cell)

2-Variables K-Map
• Rules:
YX 1) Combination of 4 squares gives the function value
0 1 equal to 1. (i.e. F=1)
2) Combination of 2 adjacent squares gives the results
XꞌYꞌ XꞌY in single literal
0 m0 m1 3) Uncombined square gives the result in two literals
00 01 EX:
XYꞌ XY i. F(X,Y)=∑(0,1,2,3)
1 m2 m3 ii. F(X,Y)=∑(1,2,3)
10 11 iii. F(X,Y)=∑(0,1,2)
iv. F(X,Y)=∑(0,3)
v. F(X,Y)=∑(1,2)

• Solutions:
1) Combination of 4 squares gives the function value
2-Variables K-Map equal to 1. (i.e. F=1)
i. F(X,Y)=∑(0,1,2,3) =1
YX 2) Combination of 2 adjacent squares gives the results

0 1 in single literal
i. F(X,Y)=∑(1,2,3) =A+B
m0 m1 ii. F(X,Y)=∑(0,1,2) =A’ +B’
0
3) Uncombined square gives the result in two literals
m2 m3
iii. F(X,Y)=∑(0,3) =AB + A’B’
1 iv. F(X,Y)=∑(1,2) = A’B + AB’

3-Variables K-Map Rules:
• Combination of 8 adjacent squares
gives the function value equal to 1
23 =8 Minterms • Combination of 4 adjacent squares
gives the results in single literal
YZ
00 01 11 10 • Combination of 2 adjacent squares
X
gives the result in two literals
0 m0 m1 m3 m2
• Uncombined squares gives the
results in 3 literals
1
m4 m5 m7 m6 • EX:
i. F(X,Y,Z)=∑(2,3,4,5) v. F(X,Y,Z)=∑(0,2,4,6)
ii. F(X,Y,Z)=∑(3,4,6,7) vi. F(X,Y,Z)=∑(0,1,2,4,6)
vii. F(X,Y,Z)=∑(1,2,4,6)
iii. F(X,Y,Z)=∑(3,5,6,7)
iv. F(X,Y,Z)=∑(1,2,3,7)

3-Variables K-Map Rules:
• EX:
i. F(X,Y,Z)=∑(2,3,4,5) : A'B + AB'
ii. F(X,Y,Z)=∑(3,4,6,7) : BC + AC'
YZ iii. F(X,Y,Z)=∑(3,5,6,7) : AB+BC+AC
00 01 11 10
X
m0 m1 m3 m2 iv. F(X,Y,Z)=∑(1,2,3,7) : A'B+BC+A'C
0
m4 m5 m7 m6 v. F(X,Y,Z)=∑(0,2,4,6) : C'
1 vi. F(X,Y,Z)=∑(0,1,2,4,6) : C' + A'B'
vii. F(X,Y,Z)=∑(1,2,4,6) : BC’+AC’+A'B'C

4-Variables K-Map
• 24 =16 Minterms • Rules:
1. Combination of 16 adjacent squares gives the function
YZ value equal to 1
00 01 11 10 2. Combination of 8 adjacent squares gives the single literal
WX 3. Combination of 4 adjacent squares gives the two literals
00
m0 m1 m3 m2 4. Combination of 2 adjacent squares gives the three literals
5. Uncombined squares gives the results in four literals
01 m4 m5 m7 m6 EX:
i. F(W,X,Y,Z)=∑(0,1,2,4,5,6,8,9,12,13,14)
ii. F(W,X,Y,Z)=∑(4,6,7,15)
11 m12 m13 m15 m14 iii. F(W,X,Y,Z)=∑(2,3,12,13,14,15)
iv. F(W,X,Y,Z)=∑(0,1,2,4,5,6,8,9,12,13,14)
m8 m9 m11 m10 v. F(W,X,Y,Z)=∑(3,7,11,13,14)
10 vi. F(W,X,Y,Z)=∑(0,1,2,4,5,6,8,9,12,13,14)
vii. F(W,X,Y,Z)=∑(1,4,5,6,12,14,15)
viii. F(W,X,Y,Z)=∑(0,2,4,5,6,7,8,10,13,15)
Don’t Care Condition
• Those conditions for which we can assume the value either ‘1’ or ‘0’ in
the K-Map
• Can be represented by cross sign ‘X’ in the K-Map
• Actually it is those input combination which can never occurs
• It helps to simplify Boolean algebra
Note: After grouping all ‘1’ or ‘0’ in the K-Map, we can simply ignore
cell containing ‘X’

Questions??
• Simplify the following functions:
i. F(W,X,Y,Z)=∑(1,3,7,11,15) and D(W,X,Y,Z)=∑(0,2,5)
(Where D is Don’t care conditions)
ii. F(W,X,Y,Z)=∑(0,1,2,3,7,8,10) and D(W,X,Y,Z)=∑(5,11,15)
iii. F(A,B,C,D)=∑(3,4,13,15) and D(A,B,C,D)=∑(1,2,5,6,8,10,12)
• Simplify the following Boolean function in SOP and POS form using K-Map
i. F(W,X,Y,Z)=∑(3,4,13,15) and D(W,X,Y,Z)=∑(1,2,5,6,8,10,12,14)
ii. F(W,X,Y,Z)=∑(0,6,8,13,14) and D(W,X,Y,Z)=∑(2,4,10)
iii. F(A,B,C,D)=∏(0,1,3,7,8,12) and D(A,B,C,D)= ∏(5,10,13,14)
iii. F(A,B,C,D)=∏(0,2,4,6,8) and D(A,B,C,D)= ∏(1,12,9,15)
iv. F(A,B,C,D)=∏(0,2,4,6,8,10,12,14) and D(A,B,C,D)= ∏(1,3,9,11)
And design logic diagram

Combinational Logic Circuit??
• Block Diagram:
• It consists of logic gates

• Consists of ‘n’ number of inputs and ‘m’ numbers of outputs
• At any time output of combinational logic circuits depends only upon current
inputs only (i.e. outputs at any time is determined by present combinations of
inputs without depending on previous input and output)
• Perform specific operation fully specified by set of logical Boolean functions

Design Procedure
1) Question is given to you i.e. Problem is stated
2) Find out number of inputs ‘n’ and number of outputs ‘m’
3) Assign input and output variables name
4) Draw the truth table
5) Simplify the output function using K-Map
6) Draw the logic diagram

Examples of CLC
• Adder
1) Half Adder(HA)
• Performs addition of binary numbers
• Two bit adder circuits
• Used in ALU(Arithmetic Logic Unit)
• Number of inputs(n)= 2 (X and Y suppose)
• Number of output(m)=2 (Sum ‘S’ and Carry ‘C’)
• Draw truth table??
• Find out expression for S and C using K-Map??
• Draw logic diagram??
Contd…
2) Full Adder(FA)
• Three bit adder
• It add two bit number as well as carry bit
• Number of input(n)=3 (X, Y and Z where ‘Z’ is carry-in)
• Number of output(m)=2 (Sum ‘S’ and Carry ‘C’)
• Draw truth table??
• Find out expression for S and C using K-Map??
• Draw logic diagram??
• Can we construct FA using HA and OR gate? If yes, Draw logic diagram
and verify your answer.

FA
• Truth table
XYZ S C
000 0 0
001 1 0 ❖ For Sum(S)
S(X,Y,Z)=∑(1,2,4,7)
010 1 0
011 0 1 ❖ For Carry(C)
100 1 0 C(X,Y,Z)=∑(3,5,6,7)
101 0 1
Find out Boolean expression and draw logic diagram??
110 0 1
111 1 1

Can we construct FA using HA and OR gate? If yes, Draw
logic diagram and verify your answer.
• Block Diagram
• Logic Diagram

Decoder and Encoder
• Decoder
• CLC that converts binary information from ‘n’ inputs lines to maximum of 2 n lines.
• Where, ‘n’ inputs lines and ‘m’ outputs lines where m≤ 2n
• Size: n* 2n (or, n to 2n Decoder)
• For n=2, size of decoder is 2*4
• EX: BCD-to-7-Segment Decoder
• Block diagram:

Contd…
• 2*4 Decoder Block Diagram • Truth table
E AB D0 D1 D2 D3
0 XX 0 0 0 0
1 00 1 0 0 0
1 01 0 1 0 0
1 10 0 0 1 0
E 1 11 0 0 0 1

Logic Diagram of 2*4 Decoder
QN: Design 3*8 Decoder with Enable input.

3*8 Decoder from 2*4 Decoder??

Questions??
1) Implement F(X,Y,Z)=∑(2,5,6,7) using Decoder and OR gate.
2) Implement full adder circuit using Decoder.

Encoder
• Just opposite of Decoder • Truth table
• Size of encoder = 2n * n Inputs Output
• Block Diagram D0 D1 D2 D3 A B
1 0 0 0 0 0
0 1 0 0 0 1
A 0 0 1 0 1 0
0 0 0 1 1 1
B
Boolean Expression: A= D2 + D3 And
B= D1+ D3

Multiplexer and De-multiplexer
• Multiplexer(Many to one)
• Also known as data selectors
• It is a CLC consists of 2n inputs and a single output
• Where ‘n’ is number of selection lines which is less than input lines used to select one of the
input lines at a time
• Size of MUX: Input*Output = 2n *1
• EX: For n=2, 4*1 MUX, similarly
for n = 3, Size of Mux=??
• Block diagram: 4*1 MUX

Contd…
• Truth table • Logic diagram
Boolean Expression:
QN: Design a Multiplexer that has three selection lines.

Implementation
• To implement any Boolean function using a mux, we have to convert the functions
into the sum of the minterms forms
• If there is ‘n’ variables, (n-1) be the selected inputs(control lines) and 2n-1 be the
inputs lines
• Works when Enable (E) = 1
• Size of MUX = 2select * 1
• QN:
1) Implement F(X,Y,Z)=∑(1,3,5,6) using MUX
2) Implement F(W,X,Y,Z)=∑(0,1,3,4,8,9,15) using MUX
3) Implement FA circuits using two 4*1 MUX
4) Implementation of 8*1 MUX using 4*1 MUX’s with enable input and without enable input

De-multiplexer
• Inverse of MUX • Block diagram of 1*4 DEMUX
• Consists of 1 input and 2n outputs lines i.e.
one to many
• Size of DEMUX: 1* 2n where ‘n’ is selected
inputs lines
• Selected lines determines which output lines
have the same value as the data input and
other data outputs will have the value ‘0’
• Each combination of selected lines select only
one output at a time
• EX: 1*4 DEMUX, 1*8 DEMUX

Contd…
• Truth table • Logic Diagram
Selection Outputs
inputs
S1 S0 Y0 Y1 Y2 Y3
0 0 I 0 0 0
0 1 0 I 0 0
1 0 0 0 I 0
1 1 0 0 0 I
Y1 , Y2 , Y3 = ??

Contd…
• Implementation
• To implement any Boolean function using a de-mux, we have to convert the functions into the
sum of the minterms forms
• If there is ‘n’ variables, ‘n’ be the selected inputs(control lines) and 2n be the output lines
• Works when Enable (E) = 1
• Size of DE-MUX = 2select * 1
• QN:
1) Design 1*8 de-multiplexer with essential truth table, Boolean expression and logic diagram
2) Design 1*8 DMUX with two 1*4 DEMUX’s
3) Implement F(A,B,C)=∑(0,1,2,3,5) using De-Multiplexer

N-bit Binary Parallel Adder(PA)
• Single FA perform the addition of two one bit numbers and an carry input
• Similarly, Parallel adder perform the addition of two n-bit numbers and carry input
• Connecting ‘n’ number of Full Adder (FA) in parallel
• The connection is also called as cascading i.e. output of one block is input of next block
• Simple block diagram of PA:

Contd…
• Tow binary numbers Bn-1…….B3B2B1B0 and An-1…….A3A2A1A0 to be added
which are applied to the corresponding input of the FA
• There is no end carry at the least significant position so we can use either HA or
made Cin of FA to ‘0’ at that position
• The parallel adder produce there sum as Cn-1Sn-1…….S3S2S1S0
B = Bn-1…….B3B2B1B0
A = An-1…….A3A2A1A0
Total sum = Cn-1Sn-1…….S3S2S1S0

4-bit binary parallel adder
• Add two 4-bit number with carry-in
• Block diagram:

Parity Generator
• CLC that accept (n-1) bit and generate an additional bit that is to be
transmitted with the bit stream
• The additional bit is called parity bit depends on parity generator i.e.
even parity or odd parity generator
• For even parity, parity bit is ‘0’ if there are even numbers of 1’s in the
beat stream and vice versa
• For odd parity, parity bit is ‘0’ if there are odd numbers of 1’s in the
beat stream and vice versa

Even Parity Generator
• 3-bit even parity generator
• That means 3-bit message is transmitted with an even parity bit
• Truth table
From Truth table:

P(A,B,C)=∑(1,2,4,7)

Contd…
• Find Boolean expression using truth table??
• Boolean expression for even parity bit generator (P) is P=(A⊕B⊕C)
• Draw logic using MUX??
• CW: Design odd parity generator??
• Truth table:
From Truth table:
P(A,B,C)=∑(0,3,5,6)
Boolean Expression For P:
P=(A⊕B⊕C)ꞌ

Parity Checker
• Consider that three bit input message along with even parity bit is generated at the
transmitted end
• These transmitted 4-bit message is applied to the even parity checker circuit
which checks the even number of 1’s on the transmitted data
• And found out the possibility of error on the transmitted data
• If any error occurs, the received message consists of odd number of 1’s and out
put of parity error checker Cp is 1
• Summary,
if Cp = 1, Error occurs and if Cp = 0 there is no any error occur

Contd…
• Function table
From Function table:

Cp (A,B,C,P)=∑(1,2,4,7,8,11,13,14)
Design Parity checker using MUX??

Odd parity Checker
• Design odd parity checker using multiplexer??

Basic concept of Programmable Logic
• ROM(Read Only Memory)
• ROM is a device that contains both decoder and the OR gate within the single IC chip
• Connections between the outputs of the decoder and the inputs of the OR gates can be
specified by programming the ROM
• ROM is essentially a storage device in which fixed set of binary information is stored
• Binary information is specified by the user and then embedded in the single unit to form the
required interconnection pattern
• Block diagram of ROM:

Contd…
• It consists of ‘n’ input lines and ‘m’ outputs lines
• Each combination of ‘n’ gives the address and each combination of ‘m’ gives the word
• The number of bits per word is equal to the number of output lines ‘m’
• Address is essentially a binary number that represents one of the minterms of n input variables
• Number of distinct addresses possible with n input variables is 2n
• Consider a 32*4 ROM i.e. consists of 32 words of 4 bit each (Required: 5*32 Decoder)
• There are 5 input lines or variables with these variables we can specify 32 addresses or
minterms
• If the input address is 00000 word number 0 is selcted and if input address is 11111 word
number 31 is selected and are applied to the output lines
• In summary: Inputs = 5, Words = 32, Bit/Words = 4, Outputs =4, Total bit stored =32*4 = 128
• EX: 2048 bit ROM i.e. 512*4 bit ROM

Contd…
• Logic construction of a 32*4 ROM • Block Diagram:

Implementation?
• Implement F1(A,B)=∑(1,2,3) and F2(A,B)=∑(0,2) using ROM
• ANS:
Number of input variables (n)= 2 (A and B)

Size of Decoder = n*2n = 2*4
Number of OR gates = Number of outputs (m) = 2
(F1 and F2 )
Size of ROM =2n * m = 4*2

Contd…
• Implement FA using ROM
• Implement the following combinational logic function using ROM
A B F1 F2
0 0 1 0
0 1 0 1
1 0 1 1
1 1 1 0

Contd…
• Types of ROM
• PROM: Programmable Read-Only Memory
• PROM is manufactured with blank memory and programmed after manufacturing
• Data store on it can’t be modified so it is called one-time programmable device
• Uses: Different applications such as cell phones, medical devices and other electronics
devices
• EPROM: Erasable Programmable Read-Only Memory
• Overcomes the disadvantages (one-time programmable) of PROM, but it is difficult
• Used ultraviolet light for a length of time, due to this shortwave radiation makes the
EPROM to the factory state
• Uses: Before invention of EEPROM use in Microcontrollers, Intel 8048 Version

Programmable Logic Device(PLD)
• Programmable Array Logic(PAL) and Programmable Logic Array(PLA) are the categories of PLD
• Main Difference:
• PAL is designed with the programmable array of AND gates and the fixed OR gates
• In PAL provides limited number of functions
• PLA is designed with the programmable array of AND gates and programmable array of OR gates
• Provides larger number of functions than PAL
• Block Diagram:
Fig: PAL Fig: PLA

Examples

Implementation
• Implement F1(A,B,C)=∑(3,5,6,7) and F2(A,B,C)=∑(0,2,4,7) using
PLA
• Rules:
1) Calculate Boolean expression for F1 , F1ꞌ , F2 and F2ꞌ
2) Analyze the number of AND gate used in various combination of outputs
3) Select minimum number of AND gate required
4) Write PLA program table for combination of selected output
5) Draw PLA Diagram with the help of PLA Program table

Step_1

Step_2

Step_3

Step_4

Combinational Logic Design

Uploaded by

Copyright:

Available Formats

Combinational Logic Design

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

Combinational Logic Design

Uploaded by

Copyright:

Available Formats

Combinational Logic Design

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

• If both i/p are 1, the output is 1; otherwise, the output is 0

Prepared By: Bishal Khadka

• If both i/p are 0, the output is 0; otherwise, the output is 1

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

• If both i/p are 1, the output is 0; otherwise ,the output is 1

Prepared By: Bishal Khadka

• If both i/p are 0, the output is 1; otherwise ,the output is 0

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

2) Realize Ex-OR gate using only NAND gates.

Prepared By: Bishal Khadka

Expression Rule(s) Used

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Expression Rule(s) Used

Prepared By: Bishal Khadka

Expression Rule(s) Used

Prepared By: Bishal Khadka

2. Simplify the following Boolean expression

Prepared By: Bishal Khadka

• Canonical form: Boolean function that is expressed as a sum of minterm or as a product of

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

YX 2) Combination of 2 adjacent squares gives the results

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

• It consists of logic gates

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

QN: Design 3*8 Decoder with Enable input.

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

QN: Design a Multiplexer that has three selection lines.

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka

Prepared By: Bishal Khadka