Computer Hardware (Chap 2)

(Combinational Circuits)
1. Decoder
i) A n–to–2n decoder is a combinational circuit that converts binary information
from n input lines to a 2n or less unique output lines.
ii) The output lines of the decoder correspond to the minterms of any n-variable logic
function. Therefore, decoders are sometimes called minterm generators.

Applications:

i) Conversion of a specific input combination into its equivalent decimal, octal or

hexadecimal digit.
ii) Address decoding (Memory Address Decoder)
iii) Program instruction decoding (Instruction Decoder)
iv) Making of Multiplexers
v) Traffic Light Control

2 X 4 (2 – to – 4) line Decoder:

a) Symbol:

b) Truth Table:
Binary Inputs Decoded Outputs
X Y O3 O2 O1 O0
0 0 0 0 0 1
0 1 0 0 1 0

CN XII – SR Page 1
 1 0 0 1 0 0
1 1 1 0 0 0

c) Logic Circuit:

X’.Y’

X’.Y

X.Y’

X.Y

d) Working:
The two inputs along with their corresponding inverters are decoded by AND gates
into four outputs, each representing one minterm. For each of the input
combinations, exactly one output is 1 while the remaining output lines are 0.
Hence,
O0 = X’.Y’, O1 = X’.Y, O2 = X.Y’ and O3 = X.Y

3 X 8 (3 – to – 8) line Decoder: [ISC 2K10]

It is used for binary to octal conversion.
a) Truth Table:
Binary Inputs Octal Outputs
X Y Z O
0 0 0 O0
0 0 1 O1
0 1 0 O2
0 1 1 O3

CN XII – SR Page 2
 1 0 0 O4
1 0 1 O5
1 1 0 O6
1 1 1 O7

b) Logic Circuit:

X’.Y’.Z’

X’.Y’.Z

X’.Y.Z’

X’.Y.Z

X.Y’.Z’

X.Y’.Z

X.Y.Z’

X.Y.Z

c) Working:
The three binary inputs along with their corresponding inverters are decoded by
AND gates into eight outputs (O0 – O7), each representing an octal digit. For each
of the input combinations, exactly one output is active or 1 while the remaining
outputs are inactive or 0. Hence, the corresponding generated minterms are:

CN XII – SR Page 3
 O0 = X’.Y’.Z’, O1 = X’.Y’.Z, O2 = X’.Y.Z’, O3 = X’.Y.Z, O4 = X.Y’.Z’, O5 = X.Y’.Z,
O6 = X.Y.Z’ and O7 = X.Y.Z

4 X 16 (4 – to – 16) line Decoder:

It is used for binary to hexadecimal conversion. The four inputs represent a binary
number and the decoded outputs represent the sixteen digits of hexadecimal number
system.
Truth Table:

2. Encoder [ISC 2K5,]

n
i) A 2 –to–n binary encoder is a combinational circuit encodes information
from 2n or less input lines into n–bit output lines. It performs the inverse
operation of a decoder.
ii) At any one time, exactly one of the 2 n inputs is active, and the output lines
represent the n – bit binary code that identifies which input is equal to 1.

Applications:

CN XII – SR Page 4
i) Communication Systems - converts of one type of coded information into another
form. For example, converting a decimal number to binary.
i) Data compression for transmission or storage.

8 X 3 (Octal – to – Binary) Encoder: It is used for octal to binary conversion.

a) Truth Table:
Input Octal Digit Binary Outputs
I O2 O1 O0
I0 0 0 0
I1 0 0 1
I2 0 1 0
I3 0 1 1
I4 1 0 0
I5 1 0 1
I6 1 1 0
I7 1 1 1

b) Working:
An Octal–to–Binary encoder takes 8 inputs, each representing an octal digit and
provides 3 outputs that generate the corresponding binary number. At any one
time, only one input line has a value of 1, which gets converted to a coded output
Thus, for an 8-to-3 binary encoder with inputs I0 – I7, the logic expressions of the
outputs O0 – O2 are:
O0 = I1 + I3 + I5 + I7
O1 = I2 + I3 + I6 + I7
O2 = I4 + I5 + I6 + I7

c) Logic Circuit:

CN XII – SR Page 5
10 X 4 (Decimal – to – Binary) Encoder: It is used for decimal to binary conversion.
a) Truth Table:
Input Octal Digit Binary Outputs
I O3 O2 O1 O0
I0 0 0 0 0
I1 0 0 0 1
I2 0 0 1 0
I3 0 0 1 1
I4 0 1 0 0
I5 0 1 0 1
I6 0 1 1 0
I7 0 1 1 1
I8 1 0 0 0
I9 1 0 0 1
b) Working:

CN XII – SR Page 6
 A Decimal–to–Binary encoder takes 10 inputs, each representing an decimal digit
and provides 4 outputs that generate the corresponding binary number. At any one
time, only one input line has a value of 1, which gets converted to a coded output
Thus, for a 10-to-4 binary encoder with inputs I0 – I9, the logic expressions of the
outputs O0 – O3 are:
O0 = I1 + I3 + I5 + I7 + I9
O1 = I2 + I3 + I6 + I7
O2 = I4 + I5 + I6 + I7
O3 = I8 + I9

c) Logic Circuit:

CN XII – SR Page 7
3. Multiplexer (Data Selector or MUX) [ISC 2K15, 2K12]
i) A 2n–to–1 line multiplexer is a combinational circuit that selects binary
information from one of the 2n input data lines and directs it to a single
output line.
ii) Also there are n selection lines whose bit combinations determine which input is
selected. In general, a 2n–to–1 line multiplexer is constructed from an n–to 2n
decoder by adding to it 2n lines, one to each AND gate.
Applications:
i) Data Communication Systems - Multiplexers send information from multiple data
streams (e.g., voice, data, video) to a single communication line (Parallel to serial
conversion).
ii) Data Routing and Digital Signal Processing - Multiplexers route data and control
signals from multiple sources to a single point.
iii) Memory addressing
iv) Telephone networks.
v) TV broadcasting systems.
4 X 1 (4 – to – 1) line MUX:
a) Symbol:

b) Truth (or Function) Table:

Selection Inputs Output
S1 S0 O
0 0 I0
0 1 I1
1 0 I2
1 1 I3

CN XII – SR Page 8
 i) A 4 X 1 multiplexer has two sets of inputs:
(a) 4 data input lines.
(b) 2 select lines, to pick one of the 4 data inputs.
ii) The MUX output is a single bit, which is one of the 4 data inputs.

c) Logic Circuit:

O = S1’ .S0’. I0 + S1’ .S0 .I1 + S1 .S0’. I2 + S1. S0. I3

d) Working:
Each of the four data input lines I0 – I3 is applied to one input of an AND gate. The
selection lines S0 and S1 are decoded to select a particular AND gate i.e. the
selection bits S0 and S1 control which of the data bits I0 – I3 is chosen. The outputs
of the AND gate are applied to an OR gate to provide a single output.

8 X 1 (8 – to – 1) line MUX: [ISC 2K17, 2K10]

a) Truth Table:
Selection Inputs Output
S2 S1 S0 O
0 0 0 I0
0 0 1 I1

CN XII – SR Page 9
 0 1 0 I2
0 1 1 I3
1 0 0 I4
1 0 1 I5
1 1 0 I6
1 1 1 I7

b) Logic Circuit:

O = S2’S1’S0’I0 + S2’S1’S0I1 + S2’S1S0’I2 + S2’S1S0I3 + S2S1’S0’I4 + S2S1’S0I5 +

S2S1S0’ I6 + S2S1S0I7

Question: From the given diagram, find the Boolean function F(x, y, z) and express it in
canonical SOP form.

CN XII – SR Page 10
Solution:
S1 S0 Product
O Term
(y) (z)
0 0 I0 y’.z’.0
0 1 I1 y’.z.1
1 0 I2 x.y.z’
1 1 I3 x.y.z

F = S1’ S0’ I0 + S1’ S0 I1 + S1 S0’ I2 + S1 S0 I3

= y’.z’.0 + y’.z.1 + x.y.z’ + x’.y.z
= y’.z.1 + x.y.z’ + x’.y.z [a.0 = 0, a+0 = a]
F = y’.z.(x’ + x) + x.y.z’ + x’.y.z [a’+a = 1]
= x’y’.z + x.y’.z + x.y.z’ + x’.y.z [Dist. law]
 F(x,y,z) = m (1,5,6,3)

4. Half Adder [ISC 2K17, 2K15, 2K14]

A half adder is a combinational circuit that adds 2 bits and finds their sum. It also has an
output carry bit to specify if 1 has been carried to a place of next higher significance.

Application:
i) It is used in ALU to compute the binary addition operation on two one-bit numbers.
ii) It is used to make a full adder.

a) Truth Table:
Inputs Outputs
Augend Addend Carry Sum
(X) (Y) (C) (S)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
CN XII – SR Page 11
b) SOP Expression:
i) S(X,Y) = X’.Y + X.Y’ = X Y
ii) C(X,Y) = X.Y

c) Logic Circuit:
i) Using AND, XOR Gates:

ii) Using NAND Gates:

5. Full Adder: [ISC 2K18, 2K16, 2K11, 2K9, 2K6]

A full adder is a combinational circuit that performs the addition of 3 bits, 2 significant bits
and a previous carry bit that specifies if 1 has been carried by a lower significant stage.

CN XII – SR Page 12
Application: It is used to create a circuit that adds N-bit numbers.
a) Truth table:
Inputs Outputs

Augend Addend Previous Carry Carry Sum

(X) (Y) (Z) (C) (S)

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

b) SOP Expression:
i) S(X,Y,Z) = X’.Y’.Z + X’.Y.Z’ + X.Y’.Z’ + X.Y.Z = (1,2,4,7)
ii) C(X,Y,Z) = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z = (3,5,6,7)

c) Reduction:
(i) Using K - map:
1. Sum:

yz y’z’ y’z yz yz’

x 00 01 11 10

x’ 0 1 1
0 1 3 2

x 1 1 1
4 5 7 6
No adjacencies, therefore S cannot be reduced.

CN XII – SR Page 13
 2. Carry:

yz y’z’ y’z yz yz’

x 00 01 11 10

x’ 0 1
0 1 3 2

x 1 1 1 1
4 5 7 6

Pair 1 =  (5, 7) = X.Z Pair 2 =  (3, 7) = Y.Z Pair 3 =  (6, 7) = X.Y

SOP (C) = X.Y + X.Z + Y.Z

(ii) Using Boolean laws:

1. Sum:
S(X, Y, Z) = X’.Y’.Z + X’.Y.Z’ + X.Y’.Z’ + X.Y.Z
= X’. (Y’.Z + Y.Z’) + X.(Y’.Z’ + Y.Z) [dist. law]
= X’. (Y  Z) + X. (Y  Z)’ [(A  B)’ = A ʘ B, A’.B + A.B’ = A B]
=XYZ [A’.B + A.B’ = A  B]

2. Carry:
C(X, Y, Z) = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z
= X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z + X.Y.Z + X.Y.Z [A+A =A]
= X.Y.Z’+ X.Y.Z + X’.Y.Z + X.Y.Z + X.Y’.Z + X.Y.Z [A+B = B+A]
= X.Y.(Z’+Z) + Y.Z(X’+X) + Z.X.(Y’+Y) [Distributive law]
= X.Y + Y.Z + X.Z [A+A’ = 1, A.1 = A]

d) Logic Circuit:
i) Using AND,XOR gates:

CN XII – SR Page 14
 ii) Using 2 Half Adders and an OR gate: [ISC 2K7,2K5]
S(X, Y, Z) = X Y Z C(X, Y, Z) = Z. (X Y) + X.Y

iii) Using a Decoder:

From TT, S(X,Y,Z) = (1,2,4,7) C(X,Y,Z) = (3,5,6,7)

CN XII – SR Page 15
 [ISC 2K19, 2K17, 2K13, 2K11, 2K9, 2K5]

Decoder Encoder Multiplexer

I t converts information
I t converts information It selects binary information from
from from n input lines to
from from 2n or less input one of the 2 n input data lines and
2 n or less unique output
lines to n output lines directs it to a single output line
lines

It is called a minterm It is called a inverse

It is called a data selector
generator decoder

It takes input signals in It provides output signals

---------
binary form in binary form

I t is constructed using It is constructed using OR It is constructed using AND,OR

AND gates gates gates

[ISC 2K18, 2K16, 2K12, 2K13, 2K5]

CN XII – SR Page 16