3130704

Digital Fundamentals

Module 2:
Combinational Digital
Circuits
Topics to be covered
Standard representation for logic functions
Simplification using K-Map
Multiplexer/De-multiplexer, Decoder
Adders, Subtractors
Combinational Circuits
Q-M Method
Boolean functions & representation

Boolean functions & representation


Minterm: Value of Minterm = 1

Boolean functions & representation

Boolean functions & representation
4. Standard product-of-sum form (Maxterm)
 Derived by considering the combinations of which f = 0
 Each term is a sum of all the variables
 Variable appears in uncomplemented form if it has a value of 0
in the combination and appears in complemented form if it
has a value of 1 in the combination

Maxterm: Value of Maxterm = 0

Boolean functions & representation

Introduction to K-Maps
 Simplification of Boolean functions leads to simpler (and usually
faster) digital circuits.
 Simplifying Boolean functions using identities is time-consuming
and error-prone.
 This special section presents an easy, systematic method for
reducing Boolean expressions.
Karnaugh Maps (K-Maps)
 A K-Map is a matrix consisting of rows and columns that represent
the output values of a Boolean function.

 The output values placed in each cell are derived from the
minterms of a Boolean function.

 A minterm is a product term that contains all of the function’s

variables exactly once, either complemented or not
complemented.
2 – Variable K-Map
The two variables A and B have four possible combinations that can
be represented by the map as follows

A
0 1
B
A B Minterm 0 2
0
0 0 m0 = A’B’
1 3
0 1 m1 = A’B 1
1 0 m2 = AB’
1 1 m3 = AB
3 – Variable K-Map
The three variables A, B and C have eight possible combinations that
can be represented by the map as follows

A B C Minterm
AB
0 0 0 m0 = A’B’C’ 00 01 11 10
C
0 0 1 m1 = A’B’C 0 2 6 4
0
0 1 0 m2 = A’BC’
1 3 7 5
0 1 1 m3 = A’BC 1
1 0 0 m4 = AB’C’
1 0 1 m5 = AB’C
1 1 0 m6 = ABC’ Minterm Number
1 1 1 m7 = ABC
4 – Variable K-Map
The four variables A, B, C and D have sixteen possible combinations
that can be represented by the map as follows

A B C D Minterm A B C D Minterm
0 0 0 0 m0 = A’B’C’D’ 1 0 0 0 m8 = AB’C’D’
0 0 0 1 m1 = A’B’C’D 1 0 0 1 m9 = AB’C’D
0 0 1 0 m2 = A’B’CD’ 1 0 1 0 m10 = AB’CD’
0 0 1 1 m3 = A’B’CD 1 0 1 1 m11 = AB’CD
0 1 0 0 m4 = A’BC’D’ 1 1 0 0 m12 = ABC’D’
0 1 0 1 m5 = A’BC’D 1 1 0 1 m13 = ABC’D
0 1 1 0 m6 = A’BCD’ 1 1 1 0 m14 = ABCD’
0 1 1 1 m7 = A’BCD 1 1 1 1 m15 = ABCD
4 – Variable K-Map

AB
CD 00 01 11 10
0 4 12 8
00
1 5 13 9
01

3 7 15 11
11

2 6 14 10
10
Function plotting in K-Map
 Consider function
F = AB + A’B

A
0 1
B
0 2
0 0 0
1 3
1 1 1
Reduce Boolean Expression


AB
00 01 11 10
C
0 2 6 4
0
1 3 7 5
1 1 1 1 1
Reduce Boolean Expression


AB
00 01 11 10
C
0 2 6 4
0
1 3 7 5
1 1 1 1 1
Examples

AB AB
CD 00
00 01 11 10 01 11 10
C
0 4 12 8
0 00
1 5 13 9
1 1 01 1 1
1
3 7 15 11
11 1 1
2 6 14 10
10
Examples

AB
CD 00 01 11 10
0 4 12 8
00 1 1
1 5 13 9
01 1
3 7 15 11
11

2 6 14 10
10 1 1
Examples

AB
CD 00 01 11 10
0 4 12 8
00 1
1 5 13 9
01 1 1
3 7 15 11
11

2 6 14 10
10
Examples

AB
CD 00 01 11 10
0 4 12 8
00 0 0
1 5 13 9
01 0 0
3 7 15 11
11 0 0
2 6 14
10 0 0 10
Don’t care conditions
 Suppose we are given a problem of implementing a circuit to
generate a logical 1 when a 2, 7, or 15 appears on a four-variable
input.
 A logical 0 should be generated when 0, 1, 4, 5, 6, 9, 10, 13 or 14
appears.
 The input conditions for the numbers 3, 8, 11 and 12 never occur
in the system. This means we don’t care whether inputs generate
logical 1 or logical 0.
 Don’t care combinations are denoted by ‘x’ in K-Map which can be
used for the making groups.
 The above example can be represented as
Examples

AB
00 01 11 10
CD
0 4 12 8
00 x x
1 5 13 9
01

3 7 15 11
11 x 1 1 x
2 6 14 10
10 1
Examples

WX
00 01 11 10
YZ
0 4 12 8
00 x
1 5 13 9
01 1 x
3 7 15 11
11 1 1 1 1
2 6 14 10
10 x
Variable-Entered Maps
 Variable-entered map can be used to plot an n-variable problem
on n – 1 variable map
 Possible to reduce the map dimension by two or three in some
cases
 Advantage of using VEM occurs in design problems involving
multiplexers
Plotting Variable-Entered Map


A A
B 0 1 B 0 1
X=1 if X=1 if C’ C’
0 0
C’=1 C’=1
1 X=0 X=1 if C’=1 1 0 C + C’
or if C = 1
Reducing Expressions with VEM
 Choose groups of similar terms to cover all nonzero terms
appearing in the map except “don’t care” terms.
 Rest complete process is similar to K-Map
Reducing Expressions with VEM

AB
00 01 11 10
C
0 D D D

1 D
D+D’
Reducing Expressions with VEM

AB
00 01 11 10
C
0 D D+D’
D’ D’

1 D’ D+D’
D’
Reducing Expressions with VEM

AB
CD 00 01 11 10

00 E E+E’
E’

01 E E+E’

11 E’

10 E+E’
E’
Realizing Logic Function with Gates
 Implement AB’ + C’D using AND, OR & Invert Gates

A
B

C
D
Converting AND/OR/Invert Logic to NAND/NOR Logic
1. Draw the circuit in AOI logic.
2. If NAND hardware is chosen, add a circle at the output of each
AND gate and at the inputs to all the OR gates.
3. If NOR hardware is chosen, add a circle at the output of each OR
gate and at the inputs to all the AND gates.
4. Add or subtract an inverter on each line that received a circle in
steps 2 or 3 so that the polarity of signals on those lines remains
unchanged from that of the original diagram.
5. Replace bubbled OR by NAND and bubbled AND by NOR.
6. Eliminate double inversions.
Converting AND/OR/Invert Logic to NAND/NOR Logic
 Implement the following AOI logic using a) NAND logic and b) NOR
logic
Converting AND/OR/Invert Logic to NAND/NOR Logic

a) NAND logic
Put a circle at the output of each AND gate and at the inputs to all OR gates
Converting AND/OR/Invert Logic to NAND/NOR Logic

a) NAND logic
Add an inverter to each of the lines that received only one circle at input so that
polarity remains unchanged.
Converting AND/OR/Invert Logic to NAND/NOR Logic

a) NAND logic
Replace bubbled OR gates and NOT gates by NAND gates.
Multiplexer
 A multiplexer(MUX) is a device that allows digital information from
several sources to be routed onto a single line for transmission
over that line to a common destination.
 Consider an integer ‘m’, which is constrained by the following
relation:
m = 2n, where m and n are both integers.
 A m-to-1 Multiplexer has
• m Inputs: I0, I1, I2, ................ I(m-1)
• One Output: Y
• n Control inputs: S0, S1, S2, ...... S(n-1)
• One (or more) Enable input(s)
Such that Y may be equal to one of the inputs, depending upon
the control inputs.
4-to-1 Multiplexer
2n inputs
Select Inputs Output
I0 S1 S0 Y
I1 I0 0 0 I0
4x1
MUX
Y 0 1 I1
I2 1 output
1 0 I2
I3
1 1 I3

Enable (G) Y = S1’S0’I0 + S1’S0I1 + S1S0’I2 + S1S0I3

S1 S0
0 0
n control inputs
4 x 1 MUX Actual Circuit
I3

I2

Y
I1

I0

S1 S0 Enable (G)
Application of Multiplexer
 Logic function generation
 Data selection
 Data routing
 Operation sequencing
 Parallel-to-serial conversion
 Waveform generation
Logic function generator
Implement the following function using 8 to 1 MUX
F(x,y,z) = Σ m(0,2,3,5)
S2 S1 S0
F z S0
x y z
y S1
0 0 0 1 x S2
0 0 1 0
1 D0
0 1 0 1 0 D1 8x1 Output = F
0 1 1 1 1 D2 MUX
1 D3
1 0 0 0 0 D4
1 0 1 1 1 D5
1 1 0 0 0 D6
0 D7
1 1 1 0
Logic function generator
 Multiplexer with n-data select inputs can implement any function
of n + 1 variables.
 The first n variables of the function as the select inputs and to use
the least significant input variable and its complement to drive
some of the data inputs.
 If the single variable is denoted by D, each data output of the
multiplexer will be D, D’, 1, or 0.
 Suppose, we wish to implement a 4-variable logic function using a
multiplexer with three data select inputs.
 Let the input variables be A, B, C, and D; D is the LSB.
Logic function generator
 A truth table for the function F(A, B, C, D) is constructed with ABC
has the same value twice once with D = 0 and again with D = 1.
 The following rules are used to determine the connections that
should be made to the data inputs of the multiplexer.
1. If F = 0 both times when the same combination of ABC occurs, connect
logic 0 to the data input selected by that combination.
2. If F = 1 both times when the same combination of ABC occurs, connect
logic 1 to the data input selected by that combination.
3. If F is different for the two occurrences of a combination of ABC, and if F =
D in each case, connect D to the data input selected by that combination.
4. If F is different for the two occurrences of a combination of ABC, and if F =
D in each case, connect D to the data input selected by that combination.
Implement the following function using 8 to 1 MUX F = Σ m(0,1,2,3,4,10,11,14,15)
S2 S1 S0
D F
A B C
0 0 0 0 1 C S0
F=1
0 0 0 1 1 B S1
0 0 1 0 1
A S2
F=1
0 0 1 1 1
1 D0
0 1 0 0 1 1 8x1
0 1 0 1 0
F = D’ D1 Output = F
D’ D2 MUX
0 1 1 0 0
F=0 0 D3
0 1 1 1 0 0 D4
1 0 0 0 0 1 D5
F=0 0
1 0 0 1 0 D6
1 0 1 0 1 1 D7
F=1
1 0 1 1 1
1 1 0 0 0
F=0
1 1 0 1 0
1 1 1 0 1
F=1
1 1 1 1 1
Demultiplexer
 A demultiplexer(DEMUX) is a device that allows digital information
from one source to be routed onto a multiple lines for
transmission over different destinations.
 Consider an integer ‘m’, which is constrained by the following
relation:
m = 2n, where m and n are both integers.
 A 1-to-m Demultiplexer has
• One Input: D
• m Outputs: O0, O1, O2, ................ O(m-1)
• n Control inputs: S0, S1, S2, ...... S(n-1)
• One (or more) Enable input(s)
Such that D may be transfer to one of the outputs, depending
upon the control inputs.
1-to-4 Demultiplexer

O
0 Select code Outputs
O S1 S0 O3 O2 O1 O0
D 1x4
DEMUX 1 0 0 0 0 0 D
O 0 1 0 0 D 0
2 1 0 0 D 0 0
O
1 1 D 0 0 0
3

S1 S0
1-to-4 Demultiplexer
D S1 S1 ’ S0 S0 ’

O0 = D S1’ S0’

O1 = D S1’ S0

O2 = D S1 S0’

O3 = D S1 S0
Decoder
 A decoder is a logic circuit that accepts a set of inputs which
represents a binary number and activates the only output that
corresponds to the input number.
 In other words, a decoder circuit looks at its inputs, determines
which binary number is present there, and activates the specific
output which corresponds to that number; all other outputs
remain inactive.
Decoder
 In its general form, a decoder has N input lines to handle N bits
and M output lines such that only one output line is activated for
each one of the possible combinations of inputs.

I0 O0
I1 O1
I2 O2
. .
N inputs Decoder M outputs
. .
. .
IN-2 OM-2
IN-1 OM-1
3-Line to 8-Line Decoder
 3 to 8 line decoder can be implemented using AND gates to
achieve active-HIGH output.
 For active-LOW outputs, NAND gates are used.
3-Line to 8-Line Decoder
Truth Table
Inputs Outputs
D0 D1 D2 D3 D4 D5 D6 D7
A B C
A’B’C’ A’B’C A’BC’ A’BC AB’C’ AB’C ABC’ ABC
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1
A A’ B B’ C C’

D7 = ABC

D6 = ABC’

D5 = AB’C

D4 = AB’C’

D3 = A’BC

D2 = A’BC’

D1 = A’B’C

D0 = A’B’C’
Half Adder
 A combinational circuit which adds two one-bit binary numbers is
called a half-adder.
Inputs Outputs A
B S=A⊕B
A B Sum Carry
0 0 0 0
0 1 1 0 C = AB
1 0 1 0
1 1 0 1
 The sum column resembles like an output of the XOR gate.
 The carry column resembles like an output of the AND gate.
Limitation of Half-Adder
 In multi-digit addition we have to add two bits along with the
carry of previous digit addition. Such addition requires addition of
3 bits. This is not possible in half-adders.
Full Adder
 In a full adder, three bits can be added at a time. The third bit is a
carry from a less significant column.
Inputs Outputs S = A’B’Cin + A’BCin’ + AB’Cin’ + ABCin
A B Cin S Cout = (AB’ + A’B)Cin’ + (AB + A’B’)Cin
0 0 0 0 0 = (A ⊕ B)Cin’ + (A ⊕ B)’Cin
0 0 1 1 0
= A ⊕ B ⊕ Cin
0 1 0 1 0 Cout = A’BCin + AB’Cin + ABCin’ + ABCin
0 1 1 0 1 = AB + (A ⊕ B)Cin
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Full Adder
Logic diagram for full adder S = A ⊕ B ⊕ Cin
Cout = AB + (A ⊕ B)Cin

A
S = A ⊕ B ⊕ Cin
B

Cin Cout = AB + (A ⊕ B)Cin

Half Adder Half Adder

Half Subtractor
 Subtracts one bit from the other and produces the difference.
 Other output is to specify if 1 is borrowed

Inputs Outputs A d=A⊕B

B
A B d b
0 0 0 0 b = A’B
0 1 1 1
1 0 1 0
1 1 0 0
Full Subtractor
 Half subtractor can be used only for LSB subtraction.
 Borrow from LSBs affects the subtraction in the next higher
column.
 Subtrahend bit is subtracted from minuend and consider borrow if
generated from preceding column.
 Full subtractor is a combinational circuit with 3 inputs (A, B, bi)
 Subtraction = A – B – bi
Full Subtractor
Inputs Outputs d = A’B’bi + A’Bbi’ + AB’bi’ + ABbi
A B bi d b = (AB’ + A’B)bi’ + (AB + A’B’)bi
0 0 0 0 0 = (A ⊕ B)bi’ + (A ⊕ B)’bi
0 0 1 1 1
= A ⊕ B ⊕ bi
0 1 0 1 1 b = A’B’bi + A’Bbi’ + A’Bbi + ABbi
0 1 1 0 1 = A’B(bi + bi’) + (AB + A’B’)bi
1 0 0 1 0 = A’B + (A ⊕ B)’bi
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
Full Subtractor
d = A ⊕ B ⊕ bi
b = A’B + (A ⊕ B)’bi

A
d = A ⊕ B ⊕ bi
B

b = A’B + (A ⊕ B)’bi
bi
Binary Parallel Adder

B4 A4 B3 A3 B2 A2 B1 A1

C3 C2 C1
FA4 FA3 FA2 FA1 Cin

C4 S4 S3 S2 S1
Binary Parallel Subtractor

B4 A4 B3 A3 B2 A2 B1 A1

C3 C2 C1 Cin= 1
FA4 FA3 FA2 FA1

Cout S4 S3 S2 S1
Binary Adder-Subtractor
B4 A4 B3 A3 B2 A2 B1 A1

C3 C2 C1 Cin
FA4 FA3 FA2 FA1

C4 S4 S3 S2 S1

• When M = 0, Circuit is an adder.

• When M = 1, Circuit becomes a subtractor.
Look Ahead Carry Adder
 Speeds up the process by eliminating the ripple carry delay.
 The method of speeding up the addition process is based on: carry
generate and carry propagate functions.
 Consider one full adder stage; say the nth stage of a parallel adder
shown in below Figure.

An B n = G n
An Cn+1 = (An ⊕ Bn) Cn + An Bn
HA An ⊕ Bn = Pn Pn Cn = C0
Bn
HA S n = A n ⊕ B n ⊕ Cn
Cn
Look Ahead Carry Adder
Sn = Pn ⊕ Cn where Pn = An ⊕ Bn
Cn+1 = Gn + Pn Cn where Gn = An Bn
Possible to express the output carry of a higher significant stage in
terms of applied input variables A, B and carry-in to the LSB adder.
Based on these, the expression for the carry-outs of various full adders
are as follows:
C 2 = G1 + P 1 C 1
C 3 = G2 + P 2 C 2
= G2 + P2 (G1 + P1 C1)
= G2 + P2 G1 + P2 P1 C1
C4 = G3 + P3 C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 C1
C5 = G4 + P4 C4 = G4 + P4 G3 + P4 P3 G2 + P4 P3 P2 G1 + P4 P3 P2 P1 C1
B4
A4 P4 C5 C5

P4
C4 S4
G4

B3
A3 P3

P3
G3 C3 S3

Look ahead
B2 carry generator
A2 P2

P2
G2 C2 S2

B1
A1 P1

P1
G1 S1
C1 C1
Serial Adder

SI
Shift SO
control Shift register A
CLK x S
y FA
SI C
Serial z
input SO
Shift register B

Q D

Clear
 Arithmetic Logic Unit (ALU)

A B

A4 A3 A2 A1 B4 B3 B2 B1
S2 (Mode - select)

S1
Cout Arithmetic Logic Unit
(Function - select)
(Output carry) (ALU) S0

Cin (Input carry)

F4 F3 F2 F1

F
Arithmetic Logic Unit (ALU)
Selection
Output Function
S2 S1 S0 Cin
0 0 0 0 F=A Transfer A
0 0 0 1 F=A+1 Increment A
0 0 1 0 F=A+B Addition
0 0 1 1 F=A+B+1 Add with carry
0 1 0 0 F=A–B–1 Subtract with borrow
0 1 0 1 F=A–B Subtraction
0 1 1 0 F=A–1 Decrement A
0 1 1 1 F=A Transfer A
1 0 0 X F=A+B OR
1 0 1 X No
Image XOR
1 1 0 X F=A.B AND
1 1 1 X F = A’ Complement A
Comparators

1-bit Magnitude Comparator

1-bit Magnitude Comparator
 Truth table and logic diagram are as follows

A0 B0 L E G
0 0 0 1 0
A < B(L)
0 1 1 0 0
1 0 0 0 1
1 1 0 1 0 A0
B0 A = B(E)

A < B : L = A0’B0
A > B(G)

A > B : G = A0B0’
2-bit Magnitude Comparator
 Let the two 2-bit numbers be A = A1A0 and B = B1B0
1. If A1 = 1 and B1 = 0, then A > B or
2. If A1 and B1 coincide and A0 = 1 and B0 = 0, then A > B.
A > B : G = A1B1’ + (A1 ⊙ B1) A0B0’
§ If A1 = 0 and B1 = 1, then A < B or
§ If A1 and B1 coincide and A0 = 0 and B0 = 1, then A < B.
A < B : L = A1’B1 + (A1 ⊙ B1) A0’B0
§ If A1 and B1 coincide and if A0 and B0 coincide then A = B.
A = B : E = (A1 ⊙ B1)(A0 ⊙ B0)
2-bit Magnitude Comparator
 Logic diagram for a 2-bit comparator is as follows
A1
B1’
A0 A > B(G)
B0’

A1
B1
A = B(E)
A0
B0

B0 A0’
A < B(L)
A1’
B1
Parity Generator
 Binary data, when transmitted and processed is susceptible to
noise that can alter its 1s to 0s and 0s to 1s.
 To detect such errors, an additional bit called parity bit is added to
the data bits and the word containing the data bits and the parity
bit is transmitted.
 At the receiving end the number of 1s in the word received are
counted and the error, if any, is detected.
Even Parity Odd Parity
0 0 1 1 0 0 1 0

Data Parity bit Data Parity bit

3-bit parity generator using even parity bit
 Let the 3-bit input be A, B and C.
 For even parity, a parity bit 1 is added such that the total number
of 1s in the 3-bit input and parity bit together is even.
3-bit parity generator using even parity bit
Truth Table K - Map
Inputs Outputs AB
parity bit 00 01 11 10
C
A B C (f)
0 0 0 0
0 1 1
0 0 1 1
1 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
3-bit parity generator using even parity bit

Logic Diagram

A
B f
C
Binary to Gray Code 4-bit Binary 4-bit Gray
B4 B3 B2 B1 G4 G3 G2 G1
Converter 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 1 1 1 1 0
1 1 0 0 1 0 1 0
1 1 0 1 1 0 1 1
1 1 1 0 1 0 0 1
1 1 1 1 1 0 0 0
Binary to Gray Code Converter
 K-Map for G4, G3, G2, G1 function and their minimization are as follows:

B4B3 B4B3
00 01 11 10 00 01 11 10
B2B1 B2B1
0 4 12 8 0 4 12 8
00 1 1 00 1 1
1 5 13 9 1 5 13 9
01 1 1 01 1 1
3 7 15 11 3 7 15 11
11 1 1 11 1 1
2 6 14 10 2 6 14 10
10 1 1 10 1 1
G4 = B4
Binary to Gray Code Converter

B4B3 B4B3
00 01 11 10 00 01 11 10
B2B1 B2B1
0 4 12 8 0 4 12 8
00 1 1 00
1 5 13 9 1 5 13 9
01 1 1 01 1 1 1 1
3 7 15 11 3 7 15 11
11 1 1 11

2 6 14 10 2 6 14 10
10 1 1 10 1 1 1 1
Binary to Gray Code Converter
 Logic diagram for binary to Gray code converter is as follows:

G4 = B4 B4 G4

B3 G3

G2
B2

G1
B1
BCD to Excess-3 Code Converter
8421 BCD XS - 3
B4 B3 B2 B1 X4 X3 X2 X1
0 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0
BCD to Excess-3 Code Converter
 K-Map for X4, X3, X2, X1 function and their minimization are as follows:

B4B3 B4B3
00 01 11 10 B2B1 00 01 11 10
B2B1
0 4 12 8 0 4 12 8
00 x 1 00 1 x
1 5 13 9 1 5 13 9
01 1 x 1 01 1 x 1
3 7 15 11 3 7 15 11
11 1 x x 11 1 x x
2 6 14 10 2 6 14 10
10 1 x x 10 1 x x
X4 = B4 + B3B2 + B3B1 X3 = B3B2’B1’ + B3’ B1 + B3’ B2
BCD to Excess-3 Code Converter

B4B3 B4B3
00 01 11 10 B2B1 00 01 11 10
B2B1
0 4 12 8 0 4 12 8
00 1 1 x 1 00 1 1 x 1
1 5 13 9 1 5 13 9
01 x 01 x
3 7 15 11 3 7 15 11
11 1 1 x x 11 x x
2 6 14 10 2 6 14 10
10 x x 10 1 1 x x
X2 = B2’B1’ + B2B1 X1 = B1’
BCD to Excess-3 Code Converter
 Logic diagram for a BCD to Excess-3 is as follows
B4
B3
B2 X4
B3
B1
B3
B2’
B1’
B3’
B1 X3
B’3
B2
B2’
B1’
X2
B2
B1
B1’ X1
Code Converters Exercise
 Binary to BCD converter
 BCD to Gray code converter
Encoder
 Device to convert familiar numbers or symbols into coded format.
 It has a number of input lines, only one of which is activated at a
given time, and produces an N-bit output code depending on
which input is activated.
 Figure shows the block diagram of an encoder with M inputs and
N outputs.
I0 O0
I1 O1
I2 O2
. .
M inputs Encoder N outputs
. .
. .
IM-2 ON-2
IM-1 ON-1
Priority Encoder
 A priority encoder is a logic circuit that responds to just one input
in accordance with some priority system, among all those that
may be simultaneously HIGH.
 The most common priority system is based on the relative
magnitudes of the inputs; whichever decimal input is the largest,
is the one that is encoded.
 For example, if both decimal 3 and decimal 4 are activated
simultaneously, then a priority encoder would encode decimal 4.
Priority Encoder
Truth Table
Inputs Outputs
D0 D1 D2 D3 A B V
0 0 0 0 x x 0
1 0 0 0 0 0 1
x 1 0 0 0 1 1
x x 1 0 1 0 1
x x x 1 1 1 1
Priority Encoder

D0D1 D0D1
00 01 11 10 00 01 11 10
D2D3 D2D3
0 4 12 8 0 4 12 8
00 x 00 x 1 1
1 5 13 9 1 5 13 9
01 1 1 1 1 01 1 1 1 1
3 7 15 11 3 7 15 11
11 1 1 1 1 11 1 1 1 1
2 6 14 10 2 6 14 10
10 1 1 1 1 10

A = D3 + D2 B = D3 + D2’ D1
Priority Encoder

D0D1
00 01 11 10
D2D3
0 4 12 8
00 0 1 1 1
1 5 13 9
01 1 1 1 1
3 7 15 11
11 1 1 1 1
2 6 14 10
10 1 1 1 1

V = D3 + D2 + D1 + D0
Priority Encoder
D3 B = D3 + D2’ D1

D2
D1

A = D 3 + D2

V = D 3 + D 2 + D1 + D 0
D0
Tabulation Method (Quine McCluskey Method)


= A’B’(C + C’) + AB’(C + C’)

= A’B’ + AB’
= B’(A + A’)
= B’
Procedure for minimization using Tabulation Method
1. List all the minterms.
2. Arrange all minterms in groups of the same number of 1s in their
binary representation in column 1. Start with the least number of 1s
group and continue with groups of increasing number of 1s.
3. Compare each term of the lowest index group with every term in the
succeeding group. Whenever possible, combine the two terms being
compared by means of the combining theorem. Two terms from
adjacent groups are combinable, if their binary representations differ
by just a single digit in the same position; the combined terms consist
of the original fixed representation with the differing one replaced by a
dash (-). Place a check mark (√) next to every term, which has been
combined with at least one term and write the combined terms in
column 2. Repeat this by comparing each term in a group of index i
with every term in the group of index i + 1, until all possible
applications of the combining theorem have been exhausted.
Procedure for minimization using Tabulation Method
4. Compare the terms generated in step 3 in the same fashion; combine
two terms which differ by only a single 1 and whose dashes are in the
same position to generate a new term. Two terms with dashes in
different positions cannot be combined. Write the new terms in column
3 and put a check mark next to each term which has been combined in
column 2. Continue the process with terms in columns 3, 4 etc. until no
further combinations are possible. The remaining unchecked terms
constitute the set of prime implicants of the expression.
5. List all the prime implicants and draw the prime implicant chart. (The
don’t cares if any should not appear in the prime implicant chart).
6. Obtain the essential prime implicants and write the minimal expression.
Tabulation Method of Reduction
 Consider function

Step – 1: List all minterms

Binary
Minterms
Designation
0 0000
1 0001
6 0110
7 0111
8 1000
9 1001
13 1101
14 1110
15 1111
Tabulation Method of Reduction
Step – 2: Arrange all minterms in groups of same number of 1s

Column 1
Index Minterms Binary Designation
Index 0 0 0000
1 0001
Index 1
8 1000
6 0110
Index 2
9 1001
7 0111
Index 3 13 1101
14 1110
Index 4 15 1111
Tabulation Method of Reduction
Step – 3: Compare each term of the lowest index group with every
term in the succeeding group till no change
Column 1 Column 2
Binary Pairs ABCD
Index Minterms
Designation 0, 1 000_
Index 0 0 0000 √ 0, 8 _000
1 0001 √ 1, 9 _001
Index 1 8, 9 100_
8 1000 √
6 0110 √ 6, 7 011_
Index 2 6, 14 _110
9 1001 √
9,13 1_01
7 0111 √ 7, 15 _111
Index 3 13 1101 √ 13, 15 11_1
14 1110 √ 14, 15 111_
Index 4 15 1111 √
Tabulation Method of Reduction
Step – 4: Compare the terms generated in step 3 in the same fashion
until no further combinations are possible
Pairs ABCD Quads ABCD
0, 1 000_ √ 0, 1, 8, 9 _00_ Q
0, 8 _000 √ --- ---
1, 9 _001 √ 6, 7, 14, 15 _11_ P
8, 9 100_ √

6, 7 011_ √
6, 14 _110 √
9,13 1_01 S

7, 15 _111 √
13, 15 11_1 R
14, 15 111_ √
Tabulation Method of Reduction
Step – 5: List all prime implicants and draw prime implicants chart
Prime Implicants : P(BC), Q(B’C’), R(ABD), S(AC’D)
√ √ √ √ √ √ √ √
PIs 0 1 6 7 8 9 13 14 15
P (6,7,14,15) x x x x
Q (0,1,8,9) x x x x
R (13,15) x x
S (9,13) x x
Step – 6: Obtain essential prime implicants and minimal expression
Essential Prime Implicants : P(BC), Q(B’C’)
Minimal expression : P + Q + R = BC + B’C’ + ABD As minterm 13 is
OR P + Q + S = BC + B’C’ + AC’D covered by R and S
Exercise
 Reduce the function to simplest form using tabulation method