Digital Electronics (K-Wiki - Combinational Circuits)

Digital Electronics (Combinational Circuits)
Combinational Logic Circuits
Objectives
Upon completion of this chapter you will be able to:
 Simplify Boolean Expressions using K-Map
 Design basic Combinational Logic Circuits
 Implement Boolean expressions using basic Combinational Circuits as building
blocks.
 Analyze Combinational Circuits for any timing hazards.
Introduction
In last chapter we simplified Boolean expressions and designed logic circuits as a
combination of logic gates. Those circuits are called as Combinational Logic Circuits as the
output of those circuits depends on the combination of logic levels of Inputs. These circuits
do not have any memory characteristic. In this chapter we will discuss more about such
circuits and present a simple method for logic simplification which is K-Map (Karnaugh Map).
K-Map
 It is used when output can be 0, 1 and x (don’t care)

 K – Map is graphical representation.
 Each Square in a K-Map represents one Minterm or Maxterm.
 In K – Map gray code representation is used
 Gray code representation
Each successive term is changed by only one bit
© Kreatryx. All Rights Reserved. 1 www.kreatryx.com

For Two variables
For Three variables
For Four variables

Procedure to simplify Boolean Expression using K-Map
i) Octets (group of 8 adjacent squares)

ii) Quads (group of 4 adjacent squares)
iii) Pairs (group of 2 adjacent squares) Priority decreases
iv) Single term
v) Remove redundant (a term whose all minterms are part of other groups)
Solved Examples
Minimize:-
  m0,2,3
Problem: f A,B 
Solution:
f  A,B  A  B (+ is put due to SOP form)
  m0,1,2,3
Problem: f A,B 
Solution: f(A, B)=1
In k – map if all are one means the function is 1.
Problem: f  A,B    m 1,3   d 2

Solution: f(A, B) = B (no need of any gate)
Problem: f  A,B    0,3   d 2,1

Solution: f(A, B) = 1
In SOP form if all are 1’s means o/p is 1.

Problem: f  A,B,C    m 1,3,5,7 


Solution: f A,B,C  C
Problem: f  A,B,C    m 0,1,3,6 

Solution: f  A,B,C   AB  AC  ABC
Problem: f  A,B,C    m 1,3,6,7 

Solution: If we take BC then it is redundant
term and it must be removed.
f  A,B,C   AC  AB
Problem: f  A,B,C    m 0,1,5,6,7 

f  A,B,C   AB  BC  AB 

Solution:  two solution
 AB  AB  AC
K–map provide minimize expression but not necessary unique i.e. two solution also possible.
Problem: f  A,B,C    m 0,1,2,5,7    d 3,6 

Solution: f  A,B,C   A  C


Problem: f A,B,C   m0,1,6,7  d3, 4,5
Solution: f  A,B,C   B  AB

Problem: f A,B,C,D   m0,1,3,5,7,8,9,11,13,15
Solution:
f  A,B,C,D  D  BC
Problem: f  A,B,C,D    m 0.2,8,10,14    d 5,15 

Solution:
f  A,B,C,D   BD  ACD
  M 0,2,3
Problem: f A,B 
 
Solution: f A,B  B A

  M 2,3  d1
Problem: f A,B 
 
Solution: f A,B  AB

Problem: f A,B,C   M 0,1,3,5,7
Solution: f  A,B,C   C  A  B 

Problem: f A,B,C   M 0,2, 4,6

Solution: f A,B,C  C 
Problem: For the k – map minimize POS expression is
Solution:

f  A,B,C   B  C  B  C 
 The two function are same if the position of 1’s and 0’s are same in k – map and if the 1’s
place 0 are placed and at 0’s place 1’s are placed then the function is complement to each
other.
Implicant, Prime Implicant and Essential Prime Implicant
Implicant: It is the set of all adjacent min terms
Eg. Pair, quad, octants

Prime Implicant: It is an implicant which is not a subset of another implicant.
Essential PI (EPI): It is a prime implicant which contains at least one min terms which is not
covered by other prime implicant.
In the figure shown below various Implicants can be formed by grouping the minterms in
different order and their classification is as mentioned below:
1) PI,Non EPI
2) PI, EPI
3) PI, EPI
4) PI, EPI
5) PI, EPI
Classification of Digital Circuits

Digital Circuits
Combinational Circuit Sequential Circuit

Present output is only depend on Present output depends on
present input present input

previous output
No feedback Feedback
No memory Memory
Example: Half Adder, Full Adder, Multiplexer, Example: Flip Flop, Register, Counter
Decoder
Procedure to Design Combinational Circuits

 Identify input and output
 Construct truth table
 Write logical expression in SOP or POS form
 Minimize logical expression, if possible.
 Implement logic circuits using Logic Gates

Half Adder (HA)

Half Adder performs basic Arithmetic Operation of addition of two bits.
Truth Table
A B SUM CARRY
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Logical expression
SUM = AB  AB  A  B and CARRY = AB
Implementation
Important Points
 Logical expression for SUM = A  B , CARRY = AB

 Min. no. of NAND Gate : 5
 Min no. of NOR Gate : 5
 No. of MUX : 3
 No. of DECODER: 1 2 x 4 Decoder and 1 OR Gate.

Half Adder implementation using NAND gate
=> Number of gates required =

5
Half Adder implementation using NOR Gate
=> Number of gates required=5
Half Subtractor
Half Subtractor performs the basic arithmetic operation of subtraction of two bits.
Truth Table
A B Diff Borrow
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
Logical expression
Difference = AB  AB and Borrow B = AB

Implementation
Half Adder and Half Subtractor
 If control = 0, then A  0  A , Y = AB and circuit is HA.

 If control = 1, then A  1  A , Y  AB and circuit is HS.
Important Points
 Number of NAND gate required = 5

 Number of NOR gate required = 5
 Number of MUX required= 3 (2 x 1 MUX)
 Number of Decoder required = 1(2 x 4) Decoder and 1 OR gate.
Half Subtractor using NAND gate
Number of NAND gate required = 5

Half Subtractor using NOR gate
Number of NOR gate required = 5
Full Adder
A Full Adder is a combinational circuit that forms the arithmetic sum of three bits.
Truth Table
A B C SUM CARRY
0 0 0 0 0
0 0 1 1 0
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
Logical expression
SUM = ABC  ABC  ABC  ABC  A  B  C   m 1,2, 4,7 
CARRY = ABC  ABC  ABC  ABC = AB + BC + AC=  m  3,5,6,7 
In full adder if each logic gate has proportion delay of tpd, then to provide sum or carry
output, it requires to 2tpd delay.

   
Now, CARRY = ABC  ABC  ABC  ABC  AB C  C  C AB  AB  AB  C  A  B 
Implementation
Using Half Adders
Important Points
 Logical expression for SUM = A  B  C, CARRY  AB  BC  AC

 Number of Half Adder and OR gate required = 2HA, 1 – OR
 Minimum Number of NAND gate required = 9
 Minimum Number of NOR gate required = 9
 Number of MUX required = 3 (4 x 1) MUX
 Number of DECODER required = (3 x 8) Decoder and 2 OR gate.

Implementation of Full adder using NAND gate
Implementation of Full adder using NOR gate

Since, A  B  C  ABC , the circuit is same only NAND is replaced by NOR.
Types of Adders
 There are three types of adders

1. Serial adder (we design as sequential circuit)
2. Parallel adder.
3. Carry Look Ahead adder.
 In serial adder only one full adder (FA) is used to add group of bits.
 It is slowest adder.
Parallel Adder
4 bit adder
 3Full Adder and 1 Half Adder required or 4 Full Adder is required.

 Parallel adder is used to add group of bits.
 To add two N bit number it requires (N – 1) full adder and half adder or N Full adder or
(2N – 1) Half adder and (N – 1) OR gates required.

Implementation of Parallel adder
A A A A 
3 2 1 0
1 1 0 1 
 S S S S C
1 0 1 1  3 2 1 0 4
Carry
B B B B  Sum
3 2 1 0
 Parallel adder is also called Ripple Carry Adder.

 There is Propagation delay from Input Carry to Output Carry, Hence it is also known as
Ripple carry adder.
 In parallel adder each Full Adder will provide 2 logic gate delay. In n bit parallel adder
provide total delay of Tdelay  2ntpd
Carry Look Ahead Adder
 Disadvantage of parallel adder is carry propagation delay present.

 As number of bits increase, speed of operation is reduced.
 To avoid this Carry Look Ahead Adder is used.
P = Propagation, G = Generation term.

i i

P  A B , G  A B , S  P C , C  PC  G
i i i i i i i i i i 1 i i i
Four Bit Carry Look Ahead adder

Input A A AA , B B B B
3 2 1 0 3 2 1 0
Then P  A B , P  A B , P  A B , P  A B
0 0 0 1 1 1 2 2 2 3 3 3
G A B S  P C , G  A B S  P C
0 0 0 0 0 0 1 1 1 1 1 1
G A B S  P C , G A B S  P C
2 2 2 2 2 2 3 3 3 3 3 3
C  PC  G Carry Look Ahead generator expression.

i 1 i i i
C P C G
1 0 0 0
1 1 0 0 0 1 
C  P C  G  P P C  G  G  P P C P G  G
2 1 1 1 0 0 1 0 1
C  P C  G  P P P C P P G P G  G
3 2 2 2 210 0 21 0 2 1 2
C P C  G P P P P C P P P G P P G P G  G
4 3 3 3 3210 0 321 0 32 1 3 2 3
n n  1  4 5
Total number of AND gate inside = 1 + 2 + 3 + 4 =   10
2 2
Number of OR Gate = n
Total propagation delay = 2t
pd
This is faster than parallel adder.
Full Subtractor
It performs the arithmetic subtraction of three bits.

Truth table
A B C Diff  A  B  C  BORROW
0 0 0 0 0
0 0 1 1 1
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
Logic expression
Difference  A  B  C = m 1,2, 4,7 
Borrow  AB  AC  BC   m 1,2,3,7 
Implementation
Full subtractor can be implemented with 2 – Half Subtractor and 1 OR gate.
Important Points
 Number of NAND gate required = 9
 Number of NOR gate required = 9
 Logical expression for Difference = A  B  C
 Logical expression for Borrow = AB  AC  BC or AB  C  A B
 Number of MUX required = 3 (4 x 1) MUX
 Number of Decoder required = 1 (3 x 8) Decoder and 2 OR gate.

Comparator
A comparator is a combinational circuit which compares two bits and produces three outputs
based on the relative values of the bits.
Truth Table
A B X Y Z
0 0 0 1 0
0 1 0 0 1
1 0 1 0 0
1 1 0 1 0
x y z
 AB  AB  AB
Logic Expression
X  AB , Y  AB  AB  AB , Z  AB
Implementation
Note: For equality condition AB holds
If A A A A are equal to B B B B
3 2 1 0 3 21 0
 3 3  A2B2 A1B1  A0B0 

Then the equality condition is A B

Then the circuit is
Multiplexer
 Multiple inputs and one output

 Depending on control or select input, one of the inputs is transferred to the output line.
 It is also called as Data selector or many to one circuit or universal logic circuit or parallel
to serial circuit.
m  2n or n=log2m
Where m = no. of data inputs
n = no. of select inputs (control inputs)

2:1 MUX
It has two inputs and 1 select line.
Symbol of MUX
Truth table
S Y
0 I
o
1 I
1
Logical expression
Y  SI  SI
o 1
Implementation

4 : 1 MUX
It has 4 inputs and 2 select lines.
Truth Table
S S Y
1 0
0 0 I
o
0 1 I
1
1 0 I
2
1 1 I
3
Logical expression
Y S S I S S I S S I S S I
1 00 1 0 1 1 02 1 03
Implementation of higher order MUX with lower order MUX
Implement 4 : 1 MUX using 2 : 1 MUX
In 4 : 1 MUX, number of 2 : 1 MUX required = 3

Implement 8 : 1 MUX using 2 : 1 MUX
8  4  2 1
 16  1  15 (2  1) MUX
32  16  8  4  2  1
 64  1  63 (2  1) MUX
128  64  32  16  8  4  2  1
 256  1   255 (2  1) MUX
 Therefore for 2n : 1 MUX the number of 2 : 1. MUX required is 2n  1 .
16 x 1 MUX from 4 x 1 MUX
16 4
Number of MUX =   4 1 5
4 4

16  4  1
 64  1 MUX  21 (4  1) MUX
 64 x 1 MUX   9 (8 : 1) MUX

64 8

8 8
MUX as Universal gate
2 : 1 MUX
NOT Gate
Y  S I  S I  A 1  0  A  A
00 01
 1 (2:1) MUX is required to implement NOT

gate

AND Gate
Y  A * 0  AB = AB
1 (2 : 1) MUX is required to implement AND gate.
OR Gate
Y  AB  A  1 = A + B
1 (2 : 1) MUX is required to implement OR gate.
NAND Gate
Y  A  1  BA  A  B  AB
For B : 
2 (2:1) MUX required for NAND gate.

NOR Gate
Y  AB  A * 0  A  B
2 (2:1) MUX required for NOR gate as 1 MUX is required for B
EXOR Gate
Y  AB  AB
2 (2 : 1) MUX required for EXOR gate as 1 MUX is required for B
EXNOR Gate
Y  AB  AB
2 (2 : 1) MUX required for EXNOR gate as 1 MUX is required for B

Note
 For EXOR number of 2 x 1 MUX required =2

 For AND gate number of 2 x 1 MUX required =1
 For Half Adder number of 2 x 1 MUX required =3
 For Half Subtractor number of 2 x 1 MUX required =3
4 : 1 MUX
Any two variable function is implemented with 4 : 1 MUX.
AND Gate
OR Gate
EXOR Gate
EXNOR Gate

Solved Examples
Determine minimized output logical expressions
Problem:
   
Solution: Y  ABC  ABC  ABC  ABC  AC B  B  AC B  B  AC  AC  AC
Problem:
Solution: Y  ABC  AB  AB * 0  ABC  ABC  AB  ABC  AC  BC
Implement following Logical Expressions using Multiplexer
Problem: f  A,B,C    m 0,1, 4,6,7 

Solution:
A B C
0 0 0  C B A
0 0 1  C B A
0 1 0  C B A
0 1 1  C B A
1 0 0  C B A
1 0 1  C B A
1 1 0  C B A
1 1 1  C B A
AB AB AB AB
I0 I1 I2 I3
C 0 2 4 6
C 1 3 5 7
1 0 C 1
1 – 4 : 1 MUX and 1 – NOT gate required.
Problem: Implement logical expression f A,B,C    m1,2,3,5,6,7 with

i) AB as select line
ii) AC as select line
iii) BC
Solution: i) AB AB AB AB
I0 I1 I2 I3
C 0 2 4 6
C 1 3 5 7
C 1 C 1
1 – 4 : 1 MUX required

ii) AC AC AC AC
I0 I1 I2 I3
B 0 1 4 5
B 2 3 6 7
B 1 B 1
iii) BC Control:
BC BC BC BC
I0 I1 I2 I3
A 0 1 2 3
A 4 5 6 7
0 1 1 1
Important Points
Any two variable function is implemented

 Using one 4 : 1 MUX 
Some of three variable are implemented
All two variable functions are implemented
 Using one 4 x 1 MUX and one NOT 
All three variable functions are implemented
Any three variable function is implemented
 Using one 8 : 1 MUX 
Sum of four variable functions are implemented
All three variable functions are implemented
 Using one 8 x 1 MUX and one NOT 
All four variable functions are implemented

DEMUX (Demultiplexer)
 Single input and multiple outputs.
 DEMUX is combinational circuit which has one Input and multiple outputs and depending
on select Input, data Input is transferred to any of the outputs.
 Also known as 1 to many circuit or data distributor
Truth Table
S Y Y
1 0
0 0 I
1 I 0
Logical Expression: Y0  SI and Y0  SI
Implementation:

1 : 4 DEMUX
Implementation of higher of DEMUX from lower order DEMUX
3
1 x 4 DEMUX  1 x 2 DEMUX
7
 1 x 8 DEMUX 
 1 x 2 DEMUX
5
 1 x 16 DEMUX  1 x 4 DEMUX
21
 1 x 64 DEMUX 
 1 x 4 DEMUX
9
 1 x 64 DEMUX 
 1 x 8 DEMUX
17
 1 x 256 DEMUX 
 1 x 16 DEMUX
DECODER
 Decoder is a combinational circuit which have multiple Inputs and multiple outputs.
 It is used to convert binary data to other code (binary octal)
Ex.
Binary to octal (3 x 8)
BCD to Decimal (4 x 10)
Binary to Hexadecimal
BCD to Seven Segment
 2 to 4 decoder is minimum possible decoder.

2 x 4 Decoder:
Truth Table
E A B y y y y
3 2 1 0
0 x x 0 0 0 0
1 0 0 0 0 0 1
1 0 1 0 0 1 0
1 1 0 0 1 0 0
1 1 1 1 0 0 0
Logical expression: Y  ABE, Y  ABE, Y  ABE, Y  ABE

0 1 2 3
 Decoder and DEMUX internal circuit remains same.
Solved Examples
Problem: Implement half adder using 2 x 4 decoder.

Solution:

We implement HA using 1–2 x 4 decoder and 1 OR gate and some for HS.
Binary to octal DECODER

 Also called as 3 x 8 Decoder
Solved Examples
Problem: Implement using 3 x 8 decoder make F.A.
Solution: SUM  m1,2, 4,7  ABC  ABC  ABC  ABC

CARRY =  m 3,5,6,7  =AB+BC+CA

Implementation of higher order decoder using lower order decoder
4  16 
5
2  4
1  16 
5
1  4 (Since 2 x 4 decoder means 1 x 4 DEMUX using 2 select line)
16  1  4  1
5
ENCODER
 Encoder is the combinational circuit which have multiple Inputs and multiple outputs.
 Encoder is used to convert other code to Binary.
Ex. octal to Binary, Decimal to BCD, Hexadecimal to Binary
Octal to Binary Encoder

 In normal encoder one of the Input line is high and corresponding binary code is available
at the output.
 But this may create a problem when more than one Input line is high. So we design Priority
Encoder.
 In priority encoder more than one Inputs is high but binary output corresponds to the
highest priority input.
Truth table
I I I I I I I I Y Y Y
7 6 5 4 3 2 1 0 2 1 0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1
Logical expression
Y I I I I
0 1 3 5 7
Y I I I I
1 2 3 6 7
Y I I I I
2 4 5 6 7

Hazards
Hazards are unwanted switching transients that may appear at the output of a circuit due to
different paths exhibiting different propagation delays. Hazards occur in Combinational
Circuits where they may cause a temporary false value at the output.
Hazard
Static Dynamic Essential

Occur in two level circuit Occur in multilevel circuit Occurs in
Asynchronous
Sequential circuit
Occur in Combinational circuit Occur in Combinational circuit
Avoid by adding redundant term
Static’1’ Hazard Static ‘0’ Hazard

And-OR circuit OR-AND circuit
In SOP form In POS form
 To avoid static and dynamic hazard redundant terms are added in a combinational circuit.
 Essential Hazard cannot be avoided but feels essentials
 For the given circuit determine o/p wave form when
Case 1: No Propagation Delay

Case 2: If there is propagation delay of 1ns in NOT gate and no delay in AND gate.
Case 3: If there is propagation delay of 1ns in NOT gate and 2ns in AND gate
Similarly, if the output is expected to be static at “Logic 1” but it exhibits a small glitch of
“Logic 0” then it is called as Static-1 Hazard.

Digital Electronics (K-Wiki - Combinational Circuits)

Uploaded by

Copyright:

Available Formats

Digital Electronics (K-Wiki - Combinational Circuits)

Uploaded by

Document Information

Original Title

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

Digital Electronics (K-Wiki - Combinational Circuits)

Uploaded by

Copyright:

Available Formats

Digital Electronics (Combinational Circuits)

Combinational Logic Circuits

 It is used when output can be 0, 1 and x (don’t care)

Each successive term is changed by only one bit

© Kreatryx. All Rights Reserved. 1 www.kreatryx.com

For Two variables

For Three variables

For Four variables

© Kreatryx. All Rights Reserved. 2 www.kreatryx.com

Procedure to simplify Boolean Expression using K-Map

i) Octets (group of 8 adjacent squares)

f  A,B  A  B (+ is put due to SOP form)

Solution: f(A, B)=1

In k – map if all are one means the function is 1.

Problem: f  A,B    m 1,3   d 2

Problem: f  A,B    0,3   d 2,1

In SOP form if all are 1’s means o/p is 1.

© Kreatryx. All Rights Reserved. 3 www.kreatryx.com

Problem: f  A,B,C    m 1,3,5,7 

Problem: f  A,B,C    m 0,1,3,6 

Problem: f  A,B,C    m 1,3,6,7 

Problem: f  A,B,C    m 0,1,5,6,7 

Problem: f  A,B,C    m 0,1,2,5,7    d 3,6 

© Kreatryx. All Rights Reserved. 4 www.kreatryx.com

Problem: f  A,B,C,D    m 0.2,8,10,14    d 5,15 

© Kreatryx. All Rights Reserved. 5 www.kreatryx.com

Problem: For the k – map minimize POS expression is

Implicant, Prime Implicant and Essential Prime Implicant

Implicant: It is the set of all adjacent min terms

Eg. Pair, quad, octants

© Kreatryx. All Rights Reserved. 6 www.kreatryx.com

Prime Implicant: It is an implicant which is not a subset of another implicant.

Classification of Digital Circuits

Combinational Circuit Sequential Circuit

Procedure to Design Combinational Circuits

© Kreatryx. All Rights Reserved. 7 www.kreatryx.com

Half Adder (HA)

SUM = AB  AB  A  B and CARRY = AB

 Logical expression for SUM = A  B , CARRY = AB

© Kreatryx. All Rights Reserved. 8 www.kreatryx.com

Half Adder implementation using NAND gate

=> Number of gates required =

Half Adder implementation using NOR Gate

=> Number of gates required=5

© Kreatryx. All Rights Reserved. 9 www.kreatryx.com

Half Adder and Half Subtractor

 If control = 0, then A  0  A , Y = AB and circuit is HA.

 Number of NAND gate required = 5

Half Subtractor using NAND gate

Number of NAND gate required = 5

© Kreatryx. All Rights Reserved. 10 www.kreatryx.com

Half Subtractor using NOR gate

Number of NOR gate required = 5

CARRY = ABC  ABC  ABC  ABC = AB + BC + AC=  m  3,5,6,7 

output, it requires to 2tpd delay.

© Kreatryx. All Rights Reserved. 11 www.kreatryx.com

Using Half Adders

 Logical expression for SUM = A  B  C, CARRY  AB  BC  AC

© Kreatryx. All Rights Reserved. 12 www.kreatryx.com