CS3351-DIGITAL PRINCIPLES AND COMPUTER

ORGANIZATION

UNITI COMBINATIONALCIRCUITS:

-Combinational Circuits
– Karnaugh Map - Analysis and Design Procedures
– Binary Adder – Subtractor
– Decimal Adder
- Magnitude Comparator
– Decoder
– Encoder
– Multiplexers
- Demultiplexers
INTRODUCTION:
The digital system consists of two types of circuits,namely
(i) Combinational circuits
(ii) Sequential circuits

Combinationalcircuitconsistsoflogicgateswhoseoutputatanytimeisdeter
mined from the present combination of inputs. The logic gate is the most
basic building block of combinational [Link] logical function performed by a
comb inationalcircuitisfullydefinedbyasetofBooleanexpressions.

Sequential logic circuit comprises both logic gates and the state of
storage elements such as flip- [Link] a consequence,the output of a
sequential circuit depends not only on present value of inputs but also on the
past state of inputs.
In the previous chapter,we have discussed binary numbers,codes,and
simplification of Boolean function and logic [Link] this chapter,formulation
andanalysisofvarioussystematicdesignsofcombinationalcircuitswillbediscussed.
 A combinational circuit consists of input variables,logic gates,and output
variables. The logic gates accept signals from inputs and output signals are
generated according to the logic circuits employed in it. Binary information
from the given data transforms to desired output data in this process. Both
inputand output are obviously the binary signals, i.e., both the input and output
signals are of two possible states, logic1andlogic0.

Blockdiagramofacombinationallogiccircuit

Fornnumberofinputvariablestoacombinationalcircuit,2npossiblecombinatons
of binary input states are [Link] each possible combination,there is one
andonly one possible output combination. A combinational logic circuit can be
described by m Boolean functions and each output can be expressed in termsof
n input variables.
DESIGNPROCEDURE:
Anycombinationalcircuitcanbedesignedbythefollowingstepsofdesignprocedure.
1. The problem isstated.
2. Identify the input and output variables.
3. Theinputandoutputvariablesareassignedlettersymbols.
4. Constructionofatruthtabletomeetinput-outputrequirements.
5. Writing Boolean expressions for various output variables interms of
input variables.
6. ThesimplifiedBooleanexpressionisobtainedbyanymethodofminimization
—algebraic method,Methodological,or tabulation method.
7. Alogicdiagramisrealizedfromthesimplifiedbooleanexpressionusing
logic gates.

The following guidelines should be followed while choosing the preferred form for
hardware implementation:
1. Theimplementationshouldhavetheminimumnumberofgates,with the gates
used having the minimum number of inputs.
2. There should be a minimum number of interconnections.
3. Limitationonthedrivingcapabilityofthegatesshouldnotbeignored.
 ARITHMETICCIRCUITS–BASICBUILDINGBLOCKS:

In this section,we will discuss those combinational logic building blocks

that can be used to perform addition and subtraction operations on binary
[Link] and subtraction are the two most
commonly used arithmeticoperations, as the other two,
namely multiplication and division, arerespectively the
processes of repeated addition and repeated subtraction.
The basic building blocks that form the basis of all hardware used to
perform the arithmetic operations on binary numbers are half-
adder,fulladder,half- subtractor,full-subtractor.

Half-Adder:
A half-adder is a combinational circuit that can be used to add two
binary bits. It has two inputs that represent the two bits to be added and two
outputs, with oneproducingtheSUMoutputandtheotherproducingtheCARRY.
Blockschematicofhalf-adder

The truthtable of a half-

adder,showingallpossibleinputcombinationsandthecorrespondingoutputs are shown

below.

Inputs Outputs
A B Carry(C Sum(S)
)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
Truthtableofhalf-adder
K-mapsimplificationforcarryandsum:
TheBooleanexpressionsfortheSUMandCARRYoutputsaregivenbytheequations,
Sum,S =A’B+AB’=AB
Carry,C=A.B The first one representing the SUM output is that
of an EX-OR
gate,thesecondonerepresentingtheCARRYoutputisthatofanANDgate.
The logic diagram of the half adder is,

Full-Adder:
Afulladderisacombinationalcircuitthatformsthearithmeticsumofthreeinput
bits.Itconsistsof3inputsand2outputs.
Two of the input variables, represent the significant bits to be added. The
[Link] block
diagram of full adder is given by,

Blockschematicoffull-adder

The full adder circuit overcomes the limitation of the half-adder, which
can be used to add two bits only. As there are three input variables, eight
different input combinations are [Link] truthtable is shown below,

TruthTable:

Input Output
s s
A B Ci Sum(S) Carry(Co
n ut)
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

ToderivethesimplifiedBooleanexpressionfromthetruthtable,the Karnaugh map

method is adopted as,
 ons,TheBooleanexpressionsfortheSUMandCARRYoutputsaregivenbytheequati

Sum,S =A’B’Cin+A’BC’in+AB’C’in+ABCin
Carry,Cout =AB+ACin+BCin.

Implementationoffull-adderinSumofProducts

The logic diagram of the full adder can also be implemented with two
half- adders and one OR [Link] S output from the second half adder is the
exclusive-OR of Cin and the output of the first half-adder,giving

Sum=Cin (AB) [xy=x‘y+xy‘]

=Cin(A‘B+AB‘)
=C‘in(A‘B+AB‘)+Cin(A‘B+AB‘)‘ [(x‘y+xy‘)‘=(xy+x‘y‘)]
=C‘in(A‘B+AB‘)+Cin(AB+A‘B‘)
=A‘BC‘in+AB‘C‘in+ABCin+A‘B‘Cin.
andthecarryoutputis,
Carry,Cout=AB+Cin(A’B+AB’)
=AB+A‘BCin+AB‘Cin
=AB(Cin+1)+A‘BCin+AB‘Cin [Cin+1=1]
=ABCin+AB+A‘BCin+AB‘Cin
=AB+ACin(B+B‘)+A‘BCin
=AB+ACin+A‘BCin
=AB(Cin+1)+ACin+A‘BCin [Cin+1=1]
=ABCin+AB+ACin+A‘BCin
=AB+ACin+BCin(A+A‘)
=AB+ACin+BCin.
Implementationoffulladderwithtwohalf-addersandanORgate
Half-Subtractor:Blockschematicofhalf-subtractor

Ahalf-
subtractorisacombinationalcircuitthatcanbeusedtosubtractonebinarydigitfroman
other to produce a DIFFERENCE output and a BORROW [Link] BORROW
out put here specifies whether a‗1‘has been borrowed to perform the
[Link] truth table of half- subtractor,showing all possible input
combinations and the corresponding outputs are shown below.
Input Output
A B Difference( Borrow(Bout)
D)
0 0 0 0
01 1 1 1
Do
1 1 0 0

The logic diagram for the above functions is shown as,

 K-map simplification for half subtractor:

The Boolean expressions for the DIFFERENCE and BORROW outputs

are given by the equations,
Difference,D= A’B+ AB’=AB
Borrow,Bout =A’.B

The first one representing the DIFFERENCE (D)output is that of an

exclusive -ORgate, the expression for the BORROW output (Bout) is that of
anAND gate with input A complemented before it is fed to the gate.
The logic diagram of the half adder is,

LogicImplementationofHalf-Subtractor
Comparing a half- subtractor with a half-adder, we find that the expressions for the
SUM and DIFFERENCE outputs are just the same. The expression for BORROW in
the case of the half- subtractor is also similar to what we have for CARRY in the
case of the half-adder. If the input A, Be used to implement the BORROW output.
Full Subtractor:
Afullsubtractorperformssubtractionoperationontwobits,a minuend and a
subtrahend, and also takes into consideration whether a ‗1‘ has already
beenborrowedbythepreviousadjacentlowerminuendbitornot.
As a result, there are three bits to be handled at the input of a full
subtractor,namely the two bits to be subtracted and a borrow bit designated as
Bin. There are twooutputs,namelytheDIFFERENCEoutputDandthe
BORROWoutput Bo. TheBORROW output bit tells whether the minuend bit

needs to borrow a ‗1‘ from the nextpossiblehigherminuendbit.

Block schematicof full-adder
Thetruthtableforfull-subtractoris,
Input Output
s s
A B Bi Difference(D Borrow(Bo
n ) ut)
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
K-map simplification for full-subtractor:

TheBooleanexpressionsfortheDIFFERENCEandBORROWoutputs are given

by the equations,
Difference,D =A’B’Bin+A’BB’in+AB’B’in+ABBin
PreparedByKAVIARASAN.S/[Link].,PIT

Borrow,Bout =A’B+A’Cin+BBin.
The logic diagram for the above functions is shown as,

Implementationoffull-adderinSumofProducts

The logic diagram of the full- subtractor can also be implemented with two
half-subtractors and one OR [Link] difference,D output from these cond half
subtractor is theexclusive-ORofBinandtheoutputofthefirsthalf-subtractor, giving
Difference,D=Bin (AB) [xy=x‘y+xy‘]
=Bin(A‘B+AB‘)
=B‘in(A‘B+AB‘)+Bin(A‘B+AB‘)‘ [(x‘y+xy‘)‘=(xy+x‘y‘)]
=B‘in(A‘B+AB‘)+Bin(AB+A‘B‘)
= A‘BB‘in+ AB‘B‘in+ ABBin+A‘B‘Bin.
And the borrow output is,
Borrow,Bout=A’B+Bin(A’B+AB’)’[(x‘y+xy‘)‘=(xy+x‘y‘)]
=A‘B+Bin(AB+A‘B‘)
= A‘B+ABBin+A‘B‘Bin
=A‘B(Bin+1)+ABBin+A‘B‘Bin [Cin+1=1]
=A‘BBin+A‘B+ABBin+A‘B‘Bin
= A‘B+ BBin(A+A‘)+A‘B‘Bin [A+A‘=1]
=A‘B+BBin+A‘B‘Bin
=A‘B(Bin+1)+BBin+A‘B‘Bin [Cin+1=1]
=A‘BBin+A‘B+BBin+A‘B‘Bin
=A‘B+BBin+A‘Bin(B+B‘)
=A‘B+BBin+A‘Bin.
Therefore,
 wecanimplementfull-subtractorusingtwohalf-subtractorsandORgateas,

Implementationoffull-subtractorwithtwohalf-
subtractorsandanORgate
Four –bit BinaryAdder(ParallelAdder):
The4-bitbinaryadderusingfulladdercircuitsiscapableofaddingtwo4- bit
numbers resulting ina4-bit sum and a carry output as shown in figure below.

4-bitbinaryparallelAdder

Sinceallthebitsofaugendandaddendarefedintotheaddercircuitssimultaneou
slyandtheadditionsineachpositionaretakingplaceatthesametime,this circuit is
Known as parallel adder.

Letthe4- bit words to be added be represented

by,A3A2A1A0=1111andB3B 2B1B0=0011.

Thebitsareaddedwithfulladders,startingfromtheleastsignificantposition,to
formthesumitandcarrybit.TheinputcarryC0intheleastsignificantpositionmustbe
0. The carry output of the lower order stage is connected to the carry input of the
[Link]-carryadder.
In the least significant stage, A0, B0 and C0 (which is 0) are added
resulting insumS0andcarryC1.ThiscarryC1becomesthecarryinputtothesecond
[Link] in the second stage, A1, B1 and C1 are added resulting in sum
S1 and carry C2,in the third stage, A2, B2 and C2 are added resulting in sum
S2 and carry C3, in the thirdstage, A3, B3 and C3 are added resulting in sum
S3 and C4, which is the output [Link] circuitresultsin a
sum(S3S2S1S0) and acarry output(Cout).
Though the parallel binary adder is said to generate its output
immediately afterthe inputs are applied, its speed of operation is limited by the
carry propagation delaythrough all stages. However,there are several methods
to reduce thisdelay.
One of the methods of speeding up this process is look-ahead carry
additionwhicheliminatestheripple-carrydelay.
BinarySubtractor(ParallelSubtractor):
The subtraction of unsigned binary numbers can be done most
conveniently bymeans of complements. The subtraction A-B can be done by
taking the 2‘s
complementofBandaddingittoA.The2‘scomplementcanbeobtainedbytakingthe1
‘scomplementandadding1totheleastsignificantpairofbits.
The1‘scomplementcanbeimplementedwithinvertersanda1canbeaddedtoth
esumthroughtheinputcarry.
ThecircuitforsubtractingA-
Bconsistsofanadderwithinvertersplacedbetween each data input B and the
corresponding input of the full adder. The
[Link]
ormed becomes A, plus the 1‘s complement of B, plus1. This is equal to A plus
the2‘scomplementofB.
 4-bitParallelSubtractor

4-Bit ParallelAdder/Subtractor:
The addition and subtraction operation can be combined into one circuit
withone common binary adder. This is done by including an exclusive-OR

gate with eachfulladder.A4-bitadderSubtractorcircuitisshownbelow.

[Link]=0,thecircuitisanadderand
whenM=1,[Link]-
ORgatereceivesinputMand one of the inputs of B. When M=0, we have B 0=
B. The full adders receive
thevalueofB,theinputcarryis0,[Link]=1,wehave
B 1= B‘ and C0=1. The B inputs are all complemented and a 1 is added
through theinput carry. The circuit performs the operation A plus the 2‘s
complement of B. Theexclusive-ORwithoutputVisfordetectinganoverflow.
DecimalAdder(BCDAdder):
The digital system handles the decimal number in the form of binary
codeddecimalnumbers(BCD).ABCDadderisacircuitthataddstwoBCDbitsandpro
ducesasumdigitalsoinBCD.
Considerthearithmetic additionof twodecimal digits in BCD,togetherwith
aninputcarryfromaprevious [Link] inputdigitdoes not exceed9,the
outputsumcannotbegreaterthan9+9+1 =19; the1isthesumbeinganinputcarry.
Theadderwillformthesuminbinaryandproducearesultthatrangesfrom0through19.
These binary numbers are labeled by symbols K, Z8, Z4, Z2, Z1, K is the
carry.
Thecolumnsunderthebinarysumlistthebinaryvaluesthatappearintheoutputsofthe4-
[Link].
 BinarySum BCD Sum
Decimal
K Z Z4 Z2 Z1 C S8 S S2 S1
8 4
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 2
0 0 0 1 1 0 0 0 1 1 3
0 0 1 0 0 0 0 1 0 0 4
0 0 1 0 1 0 0 1 0 1 5
0 0 1 1 0 0 0 1 1 0 6
0 0 1 1 1 0 0 1 1 1 7
0 1 0 0 0 0 1 0 0 0 8
0 1 0 0 1 0 1 0 0 1 9
0 1 0 1 0 1 0 0 0 0 10
0 1 0 1 1 1 0 0 0 1 11
0 1 1 0 0 1 0 0 1 0 12
0 1 1 0 1 1 0 0 1 1 13
0 1 1 1 0 1 0 1 0 0 14
0 1 1 1 1 1 0 1 0 1 15
1 0 0 0 0 1 0 1 1 0 16
1 0 0 0 1 1 0 1 1 1 17
1 0 0 1 0 1 1 0 0 0 18
1 0 0 1 1 1 1 0 0 1 19

In examining the contents of the table, it is apparent that when the binary
sum isequal to or less than 1001, the corresponding BCD number is identical, and
therefore noconversionis needed. When the binarysum is greaterthan 9(1001),we
obtain a nonvalidBCDrepresentation.Theadditionofbinary6(0110)to
thebinarysumconvertsittoth
ecorrectBCDrepresentationandalsoproducesanoutputcarryasrequired.
The logic circuit to detect sum greaterthan
9canbedeterminedbysimplifyingthebooleanexpressionofthegiventruthtable.
ToimplementBCDadder werequire:
 4-bitbinaryadderforinitialaddition
 Logiccircuittodetectsumgreaterthan9and
 Onemore4-bitaddertoadd01102inthesumifthesumisgreaterthan9orcarryis1.

The two decimal digits, together with the input carry, are first added in the
top4-bit binary adder to provide the binary sum. When the output carry is equal
to zero,nothing is added to the binary sum. When it is equal to one, binary0110
is added to the binary sum through the bottom 4-bit adder. The output carry
generated from the bottom adder can be ignored, since it supplies information
already available at the output carry
[Link] carry of the
next higher-order stage.
 BlockdiagramofBCDadder

MAGNITUDECOMPARATOR:

A magnitude comparator is a combinational circuit that compares two

given numbers(AandB)and determines whether one is equal to,less than or greater
than the [Link] output is in the form of three binary variables

Blockdiagramofn-Bit magnitudecomparator

Representing the conditions A=B,A>B and A<B,if A and B are the two
numbers being compared.
For comparison of two n-bit numbers,the classical method to achieve the Boolean
expressions requires a truth table of 22nentries and becomes too lengthy and cumber
some.

1- Bit Magnitude Comparator:

A comparator used to compare two bits is called a single-bit comparator. It consists

of two inputs each for two single-bit numbers and three outputs to generate less than,
equal to, and greater than between two binary numbers.
The truth table for a 1-bit comparator is given below:

From the above truth table logical expressions for each output can be expressed as
follows:
A>B: AB'
A<B: A'B
A=B: A'B' + AB
From the above expressions we can derive the following formula:
By using these Boolean expressions, we can implement a logic circuit for this
comparator as given below:

2-bitMagnitudeComparator:
Thetruthtableof2-bitcomparatorisgivenintablebelow—
Truthtable:
Input Outputs
s
A A2 A1 A0 A>B A=B A<B
3
0 0 0 0 0 1 0
0 0 0 1 0 0 1
0 0 1 0 0 0 1
0 0 1 1 0 0 1
0 1 0 0 1 0 0
0 1 0 1 0 1 0
0 1 1 0 0 0 1
0 1 1 1 0 0 1
1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 0 0 1
1 1 0 0 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 1 0

K-mapSimplification:
 LogicDiagram:

2- bitMagnitudeComparator

ENCODERS:

An encoder is a digital circuit that performs the inverse operation of a

[Link],the opposite of the decoding process is called [Link]
encoder is a combinational circuit that converts binary information from 2n input
lines to a maximum of n‘unique output lines.
 The general structure of encoder circuit is–

GeneralstructureofEncoder

It has 2n input lines, only one which 1 is active at any time and
n‘ output lines. It encodes one of the active inputs to a coded binary output
with
n‘ bits. In an encoder,the number of outputs is less than the number of inputs.

Octal-to-BinaryEncoder:
It has eight inputs (one for each of the octal digits) and the three outputs
that generate the corresponding binary number. It is assumed that only one
input has avalueof1atanygiventime.

Inputs Outputs
D D D D D D D D A B C
0 1 2 3 4 5 6 7
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1
The encoder can be implemented with OR gates whose inputs are
determined directly from the truth table. Output z is equal to 1, when the
input
octal digit is 1 or [Link] y
is 1foroctaldigits2,3,6,or7andtheoutputis1fordigits4,5,6or
[Link]:

z=D1+D3+D5+D7
y=D2+D3+D6+D7
x=D4+D5+D6+D7
The encoder can be implemented with three OR gates. The encoder
defined in the below table, has the limitation that only one input can be active
atany given time.
If two inputs are active simultaneously,the output produces an undefined
combination.
For eg., if D3 and D6 are 1 simultaneously, the output of the encoder
may be [Link] does not represent either D6 or D3. To resolve this problem,
encoder circuits must establish an input priority to ensure that only one input is
encoded. If we establish a higher priority for inputs with higher subscript
numbers and if D3and D6are 1 at the same time, the output will be 110
becauseD6hashigher priority than D3.

Octal-to-BinaryEncoder
Another problem in the octal-to-binary encoder is that an output with all 0‘s
is generated when all the inputs are 0; this output is same as when D0is equal to 1.
The discrepancy can be resolved by providing one more
output to indicate that atleast one input is equal to 1.

PriorityEncoder:
A priority encoder is an encoder circuit that includes the priority
function.
In priority encoder,iftwoormoreinputsareequalto1atthesametime,the input having
the highest priority will take precedence.
In addition to the two outputs x and y, the circuit has a third output, V
(validbit indicator).It is set to 1 when one or more inputs are equal to [Link] all inputs
are0, there is no valid input and V is equal to [Link] higher the subscript
number,higher the priority of the [Link] D3,has the highest priority. So,
regardless of the values of the otherinputs, whenD3is 1, theoutputforxyis11.
D2hasthenextprioritylevel.Theoutputis10,ifD2=1providedD3=[Link] output for D1
is generated only if higher priority inputs are 0,and so on down the priority levels.
Truthtable:
Input Outputs
s
D D D D x y V
0 1 2 3
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
Although the above table has only five rows, when each don‘t care
condition is replaced first by 0 and then by 1, we obtain all 16 possible input
combinations.
For example,the third row in the table with X100 represents minterms 0100 and
[Link] don‘t care condition is replacedby0and 1asshown in the table below.
Modified Truthtable:
Input Outputs
s
D D D D x y V
0 1 2 3
0 0 0 0 x x 0
1 0 0 0 0 0 1
0 1 0 0
1 1 0 0 0 1 1
0 0 1 0
0 1 1 0
1 0 1 0 1 0 1
1 1 1 0
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
 1 1 1 1

K-mapSimplification:
ThepriorityencoderisimplementedaccordingtotheaboveBooleanfunctions.

InputPriorityEncoder
DECODERS:

A decoder is a combinational circuit that converts binary information

from
n‘input lines to a maximum of 2n‘unique output [Link] general structure of decder
circuitis–
Generalstructureofdecoder
The encoded information is presented as n‘inputs producing 2n‘possible
outputs. The 2noutput values are from 0 through 2n-1. A decoder is provided
with enable inputs to activate decoded output based on data inputs. When any
one enable input is un asserted,all outputs of decoder are disabled.

BinaryDecoder(2to4decoder):
A binary decoder has n‘ bit binary input and a one activated output out

of 2noutputs. A binary decoder is used when it is necessary to activate exactly

one of 2noutputsbasedonann-bitinputvalue.
2- to-4Linedecoder
Herethe2inputsaredecodedinto4outputs,each output representing one of the
minterms of the two input variables.

Input Output
s s
Enabl A B Y Y Y Y
e 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

As shown in the truth table,ifenableinputis1(EN=1)only one of the outputs

(Y0– Y3),is active for a given input.
TheoutputY0isactive,ie.,Y0=1wheninputs
A=B=0,Y1isactivewheninputs,
A=0andB=1, Y2isactive,when input
A=1andB=0, Y3isactive,
When inputs A=B=1.
3 to-8LineDecoder:
A3-to-8linedecoderhasthreeinputs(A,B,C)and eight outputs(Y0-
Y7).Basedonthe3inputsoneoftheeightoutputsisselected.
 The three inputs are decoded into eight outputs,each output representing one
of the [Link] decoder is used for binary-to- octal
[Link] input variables may represent a binary number and the outputs will
represent the eight digits in the octal number system. The output variables are
mutually exclusive because only one output can be equal to 1at any [Link]
output line whose value is equal to 1 represents the minterm equivalent of the binary
number presently available in the input lines.

Input Output
s s
A B C Y Y Y Y Y Y Y Y
0 1 2 3 4 5 6 7
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
 3- to-8linedecoder
BCDto7-SegmentDisplayDecoder:
A seven-segment display isnormally usedfordisplaying any one of the
decimaldigits,[Link]-to-
sevensegmentdecoderacceptsadecimaldigitinBCDandgeneratesthecorrespondi
ngseven-segmentcode.
 Each segment is made up of a material that emits light when current is passed
through [Link] segments activated during each digit display are tabulated as—

Digit Display Segments

Activated

0 a,b,c, d,e,f

1 b,c

2 a, b, d, e, g

3 a, b,c,d,g

4 b,c,f, g

5 a,c,d,f,g
 6 a,c,d,e,f,g

7 a,b,c

8 a, b,c,d,e,f, g

9 a,b,c,d,f,g

Truthtable:

BCDcode 7-
Segmentcode
Digi A B C D a b c d e f g
t
0 0 0 0 0 1 1 1 1 1 1 0
1 0 0 0 1 0 1 1 0 0 0 0
2 0 0 1 0 1 1 0 1 1 0 1
3 0 0 1 1 1 1 1 1 0 0 1
4 0 1 0 0 0 1 1 0 0 1 1
5 0 1 0 1 1 0 1 1 0 1 1
6 0 1 1 0 1 0 1 1 1 1 1
7 0 1 1 1 1 1 1 0 0 0 0
8 1 0 0 0 1 1 1 1 1 1 1
9 1 0 0 1 1 1 1 1 0 1 1
K-mapSimplification:

PreparedByKAVIARASAN.S/[Link].,PIT
Logic Diagram

BCDto7-segmentdisplaydecoder

Applicationsofdecoders:
1. Decoders are used in counter system.
2. They are used in analog to digital converter.
MULTIPLEXER:(Data Selector)

A multiplexer or MUX, is a combinational circuit with more than one

input
line,one output line and more than one selection line.A multiplexer selects
binary information present from one of many input lines, depending upon the
logic status of the selection inputs, and routes it to the output line. Normally,
there are 2n input lines and n selection lines whose bit combinations determine
which input is selected. The multiplexer is often labeled as MUX in block
diagrams.
A multiplexer is also called a data selector, since it selects one of many
inputs and steers the binary information to the output line.

BlockdiagramofMultiplexer

2-to-1-lineMultiplexer: The circuit has two data input lines,one output line and one
selection line,[Link]
S=0,theupperANDgateisenabledandI0hasapathtotheoutput.
When S=1,the lower AND gateisenabledandI1has a path to the output.

Themultiplexeractslikeanelectronicswitchthatselectsoneofthetwosources.
 4-to-1-lineMultiplexer:
A 4-to-1-line multiplexer has four (2n) input lines, two (n) select lines
and one output line. It is the multiplexer consisting of four input channels and
information of one of the channels can be selected and transmitted to an output
line according to the select inputs combinations. Selection of one of the four
input channel is possible by two selection inputs.
EachofthefourinputsI0throughI3,is applied to one input of AND
[Link] lines S1and S0are decoded to select a particular AND gate. The
outputs oftheANDgateareappliedtoasingleORgatethatprovidesthe1-lineoutput.

4-to-1-LineMultiplexer

Functiontable:

S1 S0 Y
0 0 I0
0 1 I1
1 0 I2
1 1 I3

To demonstrate the circuit operation, consider the case when S1S0= 10. The
ANDgateassociatedwithinputI2hastwoofitsinputsequalto1andthethirdinputconnecte
dtoI2.TheotherthreeANDgateshaveatleastoneinputequalto0,whichmakestheiroutput
sequalto0.TheORoutputisnowequaltothevalueofI2,providingapathfromtheselectedin
puttotheoutput.
 Y= I0S1‘S0‘.The data output is equal to I1 only if S1= 0
and S0= 1; Y= I1S1‘[Link] data output is equal to I2
only if S 1= 1 and S 0= 0; Y=
I2S1S0‘.ThedataoutputisequaltoI3onlyifS1=1andS0=1;Y
=I3S1S0.
When these terms are ORed,the total expression for the data output is,
Y=I0S1’S0’+I1S1’S0+I2S1S0’+I3S1S0.
As in decoder, multiplexers may have an enable input to control the
operation of the unit. When the enable input is in the inactive state, the outputs
are disabled, and when it is in the active state, the circuit functions as a normal
multiplexer.

Quadruple 2-to-1LineMultiplexer:

This circuit has four multiplexers, each capable of selecting one of two
input lines. Output Y0 can be selected to come from either A0 or B0. Similarly,
output Y1 may have the value of A1 or B1, and so on. Input selection line, S
selects one of the lines
in each of the four [Link] enable input E must be active for normal
operation.

Although the circuit contains four 2-to-1-Line multiplexers, it is viewed

as a circuit that selects one of two 4-bit sets of data lines. The unit is enabled
when E=0Then if S=0,the four A inputs have a path to the four [Link] the
other hand ,if S=1, the four B inputs are applied to the outputs. The outputs
have all 0‘s when E=1,regardless of the value of S.

Application:
The multiplexer is a very useful MSI function and has various ranges
of applications in data communication. Signal routing and data
communication are the important applications of a [Link] is used for
connecting two or more sources to guide to a single destination among
computer units and it is useful for constructing a common bus system. One
of the general properties of a multiplexer is that Boolean functions can be
implemented by this device.

ImplementationofBooleanFunctionusingMUX:
AnyBooleanorlogicalexpressioncanbeeasilyimplementedusingamultiplex er.
If a Boolean expression has (n+1) variables, then ‗n‘ of these variables can be
connected to the select lines of the multiplexer. The remaining single variable
along with constants 1 and 0 is used as the input of the multiplexer. For
example,if C is the single variable,then the inputs of the multiplexers are
C,C‘,[Link] this method any logical expression can be implemented.
In general, a Boolean expression of (n+1) variables can be implemented
using a multiplexer with 2ninputs.

0. Implement the following boolean function

using4:1multiplexer,F(A,B,C)=∑m(1,3,5,6).
Solution:
Variables,n=3(A,B,C)
Select lines=n-1=2(S1,S0)
2n-
1toMUXi.e.,22to1=4to1MUXInput
lines=2n-1=22=4(D0,D1,D2,D3)

Implementationtable:
Apply variables A and B to the select [Link] procedures for implementing the
function are:
i. List the input ofthemultiplexer
ii. Listunderthemallthemintermsintworowsasshownbelow.
The first half of the minterms is associated with A‘ and the second half with A.
Thegivenfunctionisimplementedbycirclingthemintermsofthefunctionandapplyi
ngthefollowingrulestofindthevaluesfortheinputsofthemultiplexer.

1. If both the minterms in thecolumnarecircled,apply1tothecorrespondinginput.

2. If the bottom intermiscircledandthetopisnotcircled,applyCtotheinput.
3. If the top minterm is circled and the bottom is not circled,apply C‘to the
input.
MultiplexerImplementation:
2.F(x,y,z)=∑m(1,2,6,7)
Solution:
Implementationtable:

Multiplexer Implementation:

3.F(A,B,C) =∑m(1,2,4,5)
 Solution:
Variables,n=3(A,B,C)Seleclin
es=n-1=2(S1,S0)
2n-
1toMUXi.e.,22to1=4to1MUXInputli
nes=2n-1=22=4(D0,D1,D2,D3)
Implementationtable:

Multiplexer Implementation

4.F(P,Q,R,S)=∑m(0,1,3,4,8,9,15)

Solution:
Variables,n=4(P,Q,R,S)Sel
ectlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e.,23to1=8to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)

Implementationtable:
Multiplexer Implementation:

4. ImplementtheBooleanfunctionusing8:1andalsousing4:1multiplexer
F(A,B,C,D)=∑m(0,1,2,4,6,9,12,14)

Solution:

Variables,n=4(A,B,C,D)Se
lectlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e.,23to1=8to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)
Implementationtable:

MultiplexerImplementation(Using8:1MUX):

Using4:1MUX:
6.F(A,B,C,D)=∑m(1,3,4,11,12,13,14,15)

Solution:
Variables,n=4(A,B,C,D)Se
lectlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e.,23to1=8to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)

Implementationtable:

Multiplexer Implementation:
7. ImplementtheBooleanfunctionusing8:1multiplexer.
F(A,B,C,D)=A’BD’+ACD+B’CD+A’C’D.
Solution:
Convert into standard SOP form,
=A‘BD‘(C‘+C)+ACD(B‘+B)+B‘CD(A‘+A)+A‘C‘D(B‘+B)
=A‘BC‘D‘+A‘BCD‘+AB‘CD+ABCD+A‘B‘CD+AB‘CD+A‘B‘C‘D
+A‘BC‘D
=A‘BC‘D‘+A‘BCD‘+AB‘CD+ABCD+A‘B‘CD+A‘B‘C‘D+A‘BC‘
D
=m4+m6+m11+m15+m3+m1+m5
=∑m (1,3,4,5,6,11,15)

Implementationtable:
Multiplexer Implementation:

8. ImplementtheBooleanfunctionusing8:1multiplexer.
F(A,B,C,D)=AB’D+A’C’D+B’CD’+AC’D.
Solution:
Convert into standard SOP form,
=AB‘D(C‘+C)+A‘C‘D(B‘+B)+B‘CD‘(A‘+A)+AC‘D(B‘+B)
=AB‘C‘D+AB‘CD+A‘B‘C‘D+A‘BC‘D+A‘B‘CD‘+AB‘CD‘+AB‘C
‘D+ABC‘D
=AB‘C‘D+AB‘CD+A‘B‘C‘D+A‘BC‘D+A‘B‘CD‘+AB‘CD‘+ABC‘
D
=m9+m11+m1+m5+m2+m10+m13
=∑m (1,2,5,9,10,11,13).
ImplementationTable:

Multiplexer Implementation:

9. ImplementtheBooleanfunctionusing8:1andalsousing4:1multiplexer
F(w,x,y,z)=∑m(1,2,3,6,7,8,11,12,14)

Solution:
Variables,n=4(w,x,y,z)Sele
ctlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e.,23to1=8to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)
Implementationtable:

MultiplexerImplementation(Using8:1MUX):

(Using4:1MUX):
10. ImplementtheBooleanfunctionusing8:1multiplexer
F(A,B,C,D)=∏m(0,3,5,8,9,10,12,14)
Solution:
Variables,n=4(A,B,C,D)Se
lectlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e.,23to1=8to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)

Implementationtable:
Multiplexer Implementation:

11. ImplementtheBooleanfunctionusing8:1multiplexer
F(A,B,C,D)=∑m(0,2,6,10,11,12,13)+d(3,8,14)
Solution:
Variables,n=4(A,B,C,D)Se
lectlines=n-1=3(S2,S1,S0)
2n-1toMUXi.e.,23to1=8to1MUX
Inputlines=2n-1=23=8(D0,D1,D2,D3,D4,D5,D6,D7)

ImplementationTable:
Multiplexer Implementation:

12. An8×1multiplexer hasinputsA,BandC

connectedtotheselectioninputsS2,S1,andS0respectively.ThedatainputsI0t
o I7areasfollows
I1=I2=I7=0;I3=I5=1;I0=I4=DandI6=D'.
DeterminetheBooleanfunctionthatthemultiplexerimplements.
Multiplexer Implementation:
Implementationtable:

F(A,B,C,D)=∑m(3,5,6,8,11,12,13).

DEMULTIPLEXER:
Demultiplex means one into [Link] is the process of taking info
rmationfromoneinputandtransmittingthesameoveroneofseveraloutputs.
 Ademultiplexerisacombinationallogiccircuitthatreceivesinformationonasi
ngleinputandtransmitsthesameinformationoveroneofseveral(2n)outputlines.

Blockdiagramofdemultiplexer

The block diagram of a demultiplexer which is opposite to a multiplexer

in itsoperation is shown above. The circuit has one input signal, ‗n‘ select
signals and 2noutput signals. The select inputs determine to which output the
data input will beconnected. As the serial data is changed to parallel data, i.e.,
the input caused to
appearononeofthenoutputlines,thedemultiplexerisalsocalleda―datadistributer‖
ora
―serial-to-parallelconverter‖.

1-to-4Demultiplexer:
A1-to-

4demultiplexerhasasingleinput,Din,fouroutputs(Y0toY3)andtwoselectinputs(S
1andS0).
LogicSymbol
 The input variable Dinhas a path to all four outputs, but the input
information isdirected to only one of the output lines. The truth table of the 1-
to-4 demultiplexer isshownbelow.

Enabl S1 S0 Din Y0 Y1 Y2 Y3
e
0 x x x 0 0 0 0
1 0 0 0 0 0 0 0
1 0
Prepared B yKAVI
0 1
ARASAN.S/A 1 , 0
[Link]. PIT 0 0
1 0 1 0 0 0 0 0
1 0 1 1 0 1 0 0
1 1 0 0 0 0 0 0
1 1 0 1 0 0 1 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 1
Truthtableof1-to-4demultiplexer

Fromthetruthtable,itisclearthatthedatainput,DinisconnectedtotheoutputY0
, when S1= 0 and S0= 0 and the data input is connected to output Y1 when S1=
0 andS0= 1. Similarly, the data input is connected to output Y2and Y3when
S1= 1 and S0= 0and when S1= 1 and S0= 1, respectively. Also, from the truth
table, the expression foroutputscanbewrittenasfollows,

Y0 =
S1’S0’DinY1=
S1’S0DinY2=S1S0

’Din
Y3=S1S0Din
Logicdiagramof1-to-4demultiplexer
 Now, using the above expressions, a 1-to-4 demultiplexer can be
implementedusingfour3-inputAND gatesand twoNOT gates.
Here,theinputdatalineDin,isconnectedto allthe
ANDgates.ThetwoselectlinesS1,S0enableonlyonegate at a
[Link]
atedoutputline.

1- to-8Demultiplexer:
A1-to-
8demultiplexerhasasingleinput,Din,eightoutputs(Y0toY7)andthreeselectinputs( S2,S1
andS0).Itdistributesoneinputlinetoeightoutputlinesbasedontheselectinputs
.Thetruthtableof1-to-8demultiplexerisshownbelow.

Din S S1 S0 Y Y Y Y Y Y Y Y
2 7 6 5 4 3 2 1 0
0 x x x 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 1 0
1 0 1 0 0 0 0 0 0 1 0 0
1 0 1 1 0 0 0 0 1 0 0 0
1 1 0 0 0 0 0 1 0 0 0 0
1 1 0 1 0 0 1 0 0 0 0 0
1 1 1 0 0 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0
Truthtableof1-to-8demultiplexer
Fromtheabovetruthtable,itisclearthatthedatainputisconnectedwithoneoftheei
[Link],theexpressionforeightout
putscanbewrittenasfollows:
Y0=S2‘S1‘S0‘Din
Y1=S2‘S1‘S0Din
Y2=S2‘S1S0‘Din
Y3=S2‘S1S0Din
Y4= S2S1‘S0‘Din
Y5= S2S1‘S
 Y6= S2S1S0‘Din

Y7=S2S1S0Din
Now using the above expressions, the logic diagram of a 1-to-8 demultiplexer
can bedrawn as shown below. Here, the single data line, Din is connected to all
the eight ANDgates, but only one of the eight AND gates will be enabled by
the select input lines. Forexample, if S2S1S0= 000, then only AND gate-0 will
be enabled and thereby the
datainput,[Link],thedifferentcombinationsoftheselectinp
uts,theinputDinwillappearattherespectiveoutput.

Logicdiagramof1-to-8demultiplexer
1. Design1:8demultiplexerusingtwo1:4DEMUX.

2. Implementfullsubtractorusingdemultiplexer.

Input Output
s s
A B Bi Difference(D Borrow(Bo
n ) ut)
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

PreparedByKAVIARASAN.S/[Link].,PIT