Digit al Desi gn a nd Comp uter Organ izat ion

M o dule 1:

Num b er S ystem s an d Codes

: B inary Number syst em, B inary to decim al, decim al to binary, he xa decim al,
ASC II cod e, Exc ess,3 C ode, Gray cod e. Digit al Logic: The B asic Gates, NOT, OR, AND,
Unive rsal
Logic
Gates, NOR, NA ND.

Com b in atorial L ogic Circu its

: B oolean Laws and Th eor ems. , S um of P roducts method ,Tr uth table to
Karnaugh Map

P airs, Quads, O ctets

S im pli ficati ons

Com b in ation al Circu its

Analysi s and Design P r ocedures, B ina ry Adde r, S ubtractor, De cim al Add er,
Magnit ude C omparator, Decode r, Encod er, Multi plexers, Demul ti plexers

Number Sy stems a nd Codes

N umber Systems

I na digital system,the systemc an understand only the

optionalnumbersystem.I nthesesy stems,digits
sy mbolsareused to representdiff erentvalues, dependingon theindexfromw hic hit settledin
thenumber
sy stem.

Types ofN umber Sys tem

I nthe digitalc omputer, there arevarious ty pesof

numbersy stemsused for representinginfo rmation.
1.

Bina ryNu mberSyst em

2.

DecimalNu mberS yste m

3.

Hexad ecimalNu mber System

4.

OctalNu mberSy stem

Bi na ry Numbers ys tem

binary numbersy stemisused inthe digitalc omputers. I nthis numbersystem,it c arriesonly

two digits,
either 0 or 1.

Thereare two ty pesof elec tronic pulsespresentina binary numbersystem.

i.

the absenc eof anelec tronic pulserepresenting'0 '

.

ii.

the presenc eof elec tronic pulserepresenting'1 '.

E ac hdigitiskno wnas abit.

A four
-
bitcollec tion (1 101 ) isknow nas a nibble.

A c ollec tion of eight bits (11 00 10 10 ) isknow nas a by te.

Cha r a cter istics :

1.

I t ho ldso n lytwo values, i.e., eith er 0o r 1.

2.

It
isalso kn o wn asth e ba se2 nu mbers ystem.

3.

Th epo sition o fadigit repr esen tsth e0 po wer o fth eba se(2 ).E xamp le: 2
0

4.

Th epo sition o fth ela stdigitrepr esen ts th exp o wero fth eba se (2).E xamp le:2
x
,wh erexrepr esen ts
th elast po sition , i.e., 1

D eci mal Number Sys tem

Thedec imalnumbersy stem c ontains tendigitsfrom0 to 9(ba se1 0).

Here,the succ essiveplacevalue orposition, leftto thedec imalpointholds units,tens,

hundreds,
thousands,andso on.

Theposition inthe dec imal numbersy stem

specifiesthe pow erof the base(1 0). The 0 is theminimum
value of thedigit,and9 is themaximumvalue of thedigit.

Fo r examp le, th e decimal n u mber 254 1 consist o f th e digit 1 in th e u n it po sition, 4 in

th e tens
po sition , 5 in th e h un dreds po sition , an d 2 in th e th o u san d po sition s an d th e valu e
will be written
as:

(2×1000) + (5×100) + (4×10) + (1×1)

(2×10
3
) + (5×10
2
) + ( 4× 10
1
) + (1×10
0
)

2000 + 500 + 40 + 1

254

Octal Number Sys tem

Theoc tal number system has base8(means ithas only eightdigits
fro m0 to 7 ).

With the help of only three bits, an oc tal number is represented.

E ach set of bits has a distinc t value

betw een0 and 7.

Cha r a cter istics :

1.

A n o ctaln u mbersyste mcarr ies eigh t digits s tar tin g fro m0, 1, 2, 3, 4, 5, 6, an d 7.

2.

I t isalso
kn o wn asth e ba se8 nu mbers ystem.

3.

Th epo sition o fadigit repr esen tsth e0 po wer o fth eba se(8 ).E xamp le: 8
0

4.

Th epo sition o fth ela stdigitrepr esen ts th exp o wero fth eba se (8).E xamp le:8
x
,
wh erexrepr esen ts
th elast po sition , i.e., 1

Num b er

Octal Nu m b er

0
000

001

010

011

Exam ples:

(273)
8
, (5644)
8
, (0.53 65)
8
, (1123)
8
, (1223)
8
.

100

101

110

7
111

Hexa deci mal N umber Sys tem

Thenumbersy stemhasa baseof 1 6 means there aretotal16 symbols(0 , 1, 2, 3,4 , 5, 6, 7 , 8,

9 , A, B,
C, D ,
E , F) usedfo r representinga number.

Thesingle
-
bitrepresentation of dec imalvalues10 , 11 ,1 2 ,1 3, 14 , and1 5 arerepresented by A,B ,
C,D , E ,
andF.

Only 4 bitsare requiredfor representinga number ina hexadec imalnumber.

E ac hset of bitshas a distinc tvalue betw een 0and 15 .

Cha r a cter istics :

1.

I t hasten digits fro m0 to 9an d 6letters fro m A to F.

2.

Th eletters fro mA to F definesn u mbers fro m 10 to 15.

3.

I t isalso kn o wn asth e ba se16n u mbersyst em .

4.

I n h exad ecimaln u mber, th epo sitiono fa

digitrepr esen tsth e0po wero fth eba se(16).E xample:16
0

5.

I n h exad ecimal n u mber, th e po sition o f th e last digit repr esen ts th e x po wer o f th

e ba se(16).
E xamp le: 16
x
, wh erex
repr esen tsth e last po sit ion , i.e., 1

Binary N um ber

Hexadecim al Num ber

0000

0001

0010

0011

0100

0101

5
0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Exam ples:
(FA C2)
16
, (564)
16
, (0A BD5)
16
, (1123)
16
, (11F3)
16
.

N umber Ba se Co nversi o n

1.

Bina ryto o th er Nu mber

System s.

2.

Decimalto o th er Nu mberSyste ms.

3.

Octalto o th er Nu mberSyst ems.

4.

Hexad ecimalto o th er Nu mberSystem s.

Bi na ry toD eci mal Co nversio n

Theproc essstarts frommultiplying thebitsof binary numberw ithits

correspondingpositionalw eights.
And
lastly, w eaddall thoseproduc ts.

Exa mp le 1: (10110.001)
2

We multiplied each bit o f (10110 .0 01)

2

with its respectiv e po sition al weigh t, an d last we add th e

pr o du ctso fallth ebits with its weigh t.

(1 01 1 0 .0 01 )
2
=(1×2
4
)+ (0×2
3
)+(1×2
2
) +(1×2
1
)+

(0×2
0
)+

(0 ×2
-
1
)+(0 ×2
-
2
)+(1×2
-
3
)
(1 01 1 0 .0 01 )
2
=(1×16)+(0×8)+ (1×4)+ (1×2)+

(0×1)+

(1 01 1 0 .0 01 )
2
=16+0+4+2+0+0+0 +0. 125

(1 01 1 0 .0 01 )
2
=
(2 2 .1 2 5 )
10
D eci mal to o th er N umber System

Th edec imaln u mbercan be

an int eger o rflo ati n g
-
po int int eger. Wh en th edecima ln u mberi sa flo atin g
-
po int int eger, th en we con vert bo th pa rt (in teger an d fractio n al) o f t h e decimal n u
mber in th e iso late d
for m(ind ividu ally). Th e re ar e th e follo w ing st eps th at ar e u sed to c o n vert t
h e decimal n u mber int o a
similar n u mbero fan y ba se

'r'
.

1.

I n th e first step, we pe rfo rm th e division o pera tio n on int eger an d su cces sive pa rt
with ba se

'r'
.
We wil l list do wn all th e remain ders till th e q u o tien t is zero . Th en we fin d o u t th e
remain ders in
reverse o rd er for getti n g th e int eger pa rt o f th e equ ivalen t n u mber o f ba se

'r'
. I n th is, th e least
an d mo st sign ifican t di gitsar edeno tedby th efirst an d thelast r em ain ders.

2.

I n th en extstep, th emultiplicatio n o peration isdo n ewith ba se

'r '

o fth efractio n alan dsu ccessiv e

fractio n . Th e carr ies ar e n o ted u n til th e resu lt is zero o r wh en th e requ ired n u
mber o f th e
equ ivalen t digit is o bt ain ed. Fo r getting th e fractio n al pa rt o f th e eq u ivalen t n u
mber o f ba se

'r '
,
th en o rmalsequ en ceo fcarr ying is con sidered .

D eci mal to Bin ar yC on ver si on

Fo r co n vertin g decimalto bin ar y, th erear etw o stepsrequ ired to per for m, wh ich ar eas
foll o ws:

1.

I n th e first step, w e pe rfo rm th e division o peratio n on th e int eger an d th e su cces

sive qu o tien t with
th eba seo f
bin ar y(2).

2.

Next, we perfor m th e multiplicatio n o n th e int eger an d th e su ccessive qu o tien t with

th e ba se o f
bin ar y(2).

Exa mp le 1: (152.25)
10

Step 1 :

D ividethe number152 andits suc c essivequotientsw ithbase2 .

Oper a ti on

Quoti e nt

Remaind er

1 52 /2

76
0
(LSB)

7 6 /2

38

3 8 /2

19

1 9 /2

9 /2

4 /2

2 /2

1 /2

0
1 (M SB)

(152)
10
=(10011 000 )
2

Step 2 :

No w, perfo rmth emultiplicatio n o f0. 27 an d s u ccessiv efractio n with ba se2.

(0.25)
10
=
(.01)
2

H exa
-
d eci mal to Deci mal Con ver sion

Th epr o ces so f con vertin gh exad ecimalto deci mali sth e sam ea sbin a ryto dec imal.Th
epr o c ess star ts
fro m multiplying th e d igits o f h exad e cimal n u mbers with its cor res po n din g po
sition al wei gh ts. A n d
lastly, w eadd all th o se pr o du cts.

Let'stak ean examp l et o u n derstan d ho wth econ version isdo n efro mh exad ecimalto d
eci mal.

Exa mp le 1: (152A .25)

16
Step 1 :

Wemultiplyeach digito f

1 5 2 A.25

with itsres pectivepo sition alweig h t, andlastweadd

th epr o du cts
o fallth ebit swith its w eigh t.

(1 52 A.2 5 )
16
=(1×16
3
)+(5×16
2
)+(2×16
1
) +(A ×1 6
0
)+(2×16
-
1
)+(5×16
-
2
)

(1 52 A.2 5 )
16
=(1×409 6)+(5×256 )+(2 ×16)+(10 ×1)+(2×16
-
1
)+ (5×16
-
2
)

(1 52 A.2 5 )
16
(1 52 A.2 5 )
16
=541 8+0. 125+0.1 25

(1 52 A.2 5 )
16
=541 8.1 44531 25

So, th edecimaln u mbe r ofth eh exad ecimal n u mber152 A .2 5 is

5 4 18.1 4 45 31 25

Hexade cimal to Binary C onv ersi on

Th e pr o cess o f con vertin g h exad ecimal to bin ar y is th e reverse pr o cess o f bin ar y to

h exad ecimal.
Wewrit eth efou r bits bin ar y
cod eo feach h e xad ecimaln u mberdigi t.

Exa mp le 1: (152A .25)

16

Wewrit eth efou r

-
bit binar ydigitfor 1, 5, A , 2, an d 5.

(1 52 A.2 5 )
16
=(
0 00 1 01 0 1 00 10 1 01 0 .00 10 0 1 01 )
2

So, th ebin ar yn u mbero fth eh exad ecimaln u mber152 .2 5 is

(1 0 1 0 10 0 10 10 10 .00 10 01 01 )
2
Oper a ti on

Result

car ry

0 .25 ×2

0 .50

0 .50 ×2

ASCII Cod e

TheASCII standsfor Americ an StandardCodefo rInformationI nterc hange.

TheASCII c odeisan alphanumeric c odeusedfo rdata communication indigital c omputers.

TheASCII isa 7
-
bitc odec apableof
representing2
7

or 1 28 number of different c harac ters.

TheASCII c odeismadeupof a three
-
bitgroup,w hic hisfollow ed by a four
-
bitc ode.

Th e A SCI I cod e star ts fro m 00h to 7Fh . I n th is, th e cod e fro m 00h to 1Fh is u sed
for con tro l
cha ra cters,an d thecod efro m20h to 7F h is u sed fo r grap h icsymb o ls.

Th e 8
-
bit cod e h o lds A SCI I, wh ich su pp o rt s 256 symbo ls wh ere m ath an d gr ap h ic
symb o ls ar e
add ed.

Th era n geo fth eexten dedA SCI I is80h to FF h .

Con trol C harac t ers

Th e
non
-
pr intab le chara cters u sed for sen di n g comman ds to th e PC o r pr int er are kn own as
con tr o l
cha ra cters. We can set tab s, an d lin e br eak s fun ctio n ality by th is cod e. Th e con tr o l
ch ar acters ar e ba sed
o n telex te chn o log y. No wadays, it's n o t so m u ch po pu lar i
n u se. Th e cha ra cter fro m 0 to 31 an d 127
comesu n dercon tr o lcha ra cters.

Special C harac t ers

A ll pr int ab le cha ra cters th at ar e n eith er nu mbers n o r letters come u n der th e special

cha racters. Th ese
cha ra cters con tain tech n ical, pu n ctuatio n, and math ematical cha ra c ters with spa ce
also . T h e cha ra cter
fro m32 to 47, 58 to 64, 91 to 96, an d 123to 126 c
o mesu n derth is categor y.

Num bers C hara cters

Th iscategor yo f A SCI I cod econ tain sten A ra bicn u mera lsfro m0 to 9

.

Lett ers Ch arac t ers

I n th is categor y, two
gro u ps o f letters ar e con tain ed, i.e., th e gr ou p o f u pp ercase letters a n d th e gr oup
o flowercase letters. Th era n gefro m65 to 90 an d 97to 122 comesu n derth iscategor y.

Excess
-
3 Code

Th e exc es s
-
3 cod e is also tr eated as

XS
-
3 code
. Th e exce ss
-
3 cod e is a

non
-
weigh ted an d s elf
-
complemen tar y BCD cod e u sed to repr esen t th e dec imal n u mbers. Th is cod e h as
a bias ed
repr esen tat ion . Th is c o de plays an impo rt an t ro le in ar ith meti c o peratio n s becau
se it re so lves
deficien ci es en cou n tered wh en w e u s e th e 84 21 BCD cod
e for add in g two deci mal digit s w h o se su m i s
gr eater th an 9. Th e E xcess
-
3 cod e u s es a s pecial typ e o f a lgo rith m, wh ich differ s fro m th e bin ar y
po sition aln u mbersyst emo r no rmaln o n
-
biased BCD.

We can eas ily get an e xcess

-
3 cod e o fa deci maln u mberby si mply add ing 3 to each deci maldigit. A n d
th en we write th e 4
-
bit bin ar y n u mber for each digit o f th e decimal n u mber. We can fin d th e exces s
-
3
cod eo fth egiven binar yn u mberbyu sing th e follo wing

steps:

1.

We findthe dec imalnumberof thegivenbinary number.

2.

Thenw eadd3 ineachdigitof thedec imalnumber.

3.

Now,w efind thebinary c odeof eachdigitof thenew ly generated dec imal number.

Wecan al so add 001 1 i n each 4

-
bit BCD cod e o fth edecimal n u mberfor getting exce ss
-
3 c o de.
The Excess
-
3code for the decima lnu mber is as follows :

Decim al Di git

B CDCo de

Ex cess
-
3 Cod e

0 00 0

0 01 1

0 00 1

0 10 0

0 01 0

0 10 1

0 01 1

0 11 0

0 10 0

0 11 1
5

0 10 1

1 00 0

0 11 0

1 00 1

0 11 1

1 01 0

1 00 0

1 01 1

1 00 1

1 10 0

Gray Code

Th e

Gra yCode

is ase qu en ceo fbin ar yn u m ber

sy stem s,wh ich is al so kn o wn as

refl ectedbin ar ycode

.
Th e reaso n for callin g th is cod e as re flected b i n ar y cod e is th e fir st N/2 valu es
compa red wi th th o se o f
th elast N/2 valu e s inr everse o rd er. I n th is cod e,twocon se cut iveval u esar e dif fered
by o n ebit o fbin ar y
digits. G ra y cod es ar e u sed in th e gener
al s equ en ce o f h ar dware
-
generated bin ar y n u mbers. Th ese
n u mberscau se ambigu ities o rerr o rs wh en th e tr an sition fro mo n e n u mberto it s su
cce ssiv ei sdo n e.Th is
cod e simpl y so lves th i s pr o blem b y cha n gin g o n ly o n e bit wh en t h e tr an sition
is betwe e n n u mbers
is
do n e.

Th egr ay cod ei sa very ligh tweigh tedcod ebe cau seit do esn 'tdepen do n th evalu eo f th
edi gitspec ified
by th e po sition . Th is cod e is also call ed a cyclic var iable cod e as th e tr an sition o f on e
valu e to its
su cces sivevalu e carr ie sacha n geo fo n ebit o n
ly.

How to gen erat e Gray c ode ?

Th epr ef ixan dr efle ctm eth o dar erecur sive ly u sedto generate th eG ra ycod e o f a n u
mber. Fo rgeneratin g
gr aycod e:

1.

We findthe numberof bitsrequired to

representa number.

2.

Next, w efind thec odefor 0, i.e., 00 00 ,w hichisthe same as binary .

3.

Now,w etake thepreviousc ode,i.e.,0 000 , andchange themost significantbitof it.

4.
We performthis proc ess rec lusively untilall thecodes arenotuniquely identified.

5.

I f by c hangingthe mostsignific antbit,w efind thesamec odeobtained previously, thenthe

second most
signific antbitw illbec hanged,andso on.

Pr ocess o f ge n eratin g Gra y Co de

Gray C ode T abl e

Decim al Numb er

B i nary Numb er

Gray
Co de

0 00 0

0 00 0

1
0 00 1

0 00 1

0 01 0

0 01 1

0 01 1

0 01 0

0 10 0

0 11 0

0 10 1

0 11 1

0 11 0

0 10 1

0 11 1

0 10 0

8
1 00 0

1 10 0

1 00 1

1 10 1

10

1 01 0

1 11 1

11

1 01 1

1 11 0

12

1 10 0

1 01 0

13

1 10 1

1 01 1

14

1 11 0

1 00 1

15

1 11 1
1 00 0

Dig ital Lo g ic:

The Bas ic
Ga tes

The

basic

gates ar e

AN D , OR

& NOT

gates.

AND

gate

An AND gate is a digi tal circuit that has two or more input s and produces an output ,

which

is

the
logi cal

AND
of

all
those

input s.

It

is

opti onal

to

represent

the
L ogical

AND

with

the

The

following t able shows the

tru th tabl e

of 2
-
i nput AND

gate.

Y
= A.B

then

o nly the

output , Y

is

combi nati ons of inputs ,

the output, Y
is

The following figure shows the

sym b ol
of an AND gate, which is having two input s A, B

and one

output ,
Y.

This AND gate produ ces an output (Y), which is t he

logi cal AND
of two i nputs A, B.

S im il arly, if there

AND of all those input s. That

are

OR

gate

AnORgate isadigi talci rcuit thathastwo ormor e input sandproduc esan o utput ,

whichisthelogi c al
OR of all those input s. This
logi cal O R
is represe nted wit h the symbol
The

following t able shows

the
tru th tabl e

of

2
-
input OR gate.

=A

+B

1
1

Here

A,

ar e

the

input s

and

is

the

output

of

two

input

OR

gate.

If

bo th

input s
are

then

only t he

output , Y

is

remaining combinations of

input s,

the

output , Y

is

The following figure sho ws the

sym b ol
of an OR gate, which is h aving t w o input s A, B
and

one

output , Y.

This OR gate produ ces a n output (Y), which is the

logi cal OR
of two inpu ts A, B . S im il arly,
input s, then the OR gate produces an output , whi ch is the logi cal OR of a ll

those input s. That means, the

output of an OR

input s

NO T

gate

NOT

gate

is

digi tal

circuit

that

has

singl e

in put

and

singl e
output .

T he

output

of

NOT

gate

is t he

logi cal i n version

of input.

Hence, the

NOT

g ate is

also call ed

as
inverter.

The

following

table shows

the
tru th

tabl e

of
NOT gate.

Here

and

ar e

the

in put

and

output

of

NOT

g ate

r especti vely.
If

the

in put,

is

then

the

output , Y

S im il arly, if the

input, A

output ,

The

following

figure

sho ws

the

sym b ol
of

NOT

g ate,

which

is

having

one

input ,

and

on e

output , Y.

This

NOT

gate produc es

an output

(Y), which

is t he
com p lem en t
of

input ,
A.

U n iver sal

gate s

NAND&NOR gatesar ecall edas

u n iversalgates
. B ecausew ecanim pleme ntany

B ooleanfuncti on,
which is in sum of products form by using NAND gates alone. S im il arly,

we can im plement any B oolean

functi on, which is i n product of sums form by us ing NOR

gates

alone.

NA ND

gate

NAND

gate

is

digi tal

circuit

that

has
two

or

m ore

input s

and

produc es

an

output ,

which

is t he

in version

of logical AND
of all those

input s.

The

following t able

shows the

tru th tabl e

of 2
-
inp ut

NAND gate.
A

Here A, B ar e the inputs and Y is t he output of tw o input NAND gate. Wh en both i nputs
are
just

opposi tetothatof

tw oinput
AND gate

ope rati on.

The following i mage sho ws the

sym b ol
of NAND gate, which is having t w o input s A, B and

one

output , Y.

N A ND

gate
symb ol i s represented lik e that.

NO R

gate

NOR

gate

is

digi tal
circuit

that

has

two

or

m ore

input s

and

produces

an

output ,

which

is t he

in version

of logical OR

of all those input s.

The

following t able shows

the
tru th tabl e

of 2
-
i nput NOR gate
A

Ifatleas toneof

input

OR gate operati o n.
The following figure sho ws the
sym b ol
of NOR gate, which is having t wo input s A, B and

one

output , Y.

NOR

gate op erati on is

s a me as

that o f OR

gate fo ll owed

NOR

gate symb ol
is represent ed li ke that.

COMB INAT IONAL

LOG IC CIRCUIT

B oole an

Laws

and
T heorem s

B ooleanAlgeb ra
isanalgebra,whichde alswithbinarynumbers&binaryvariables.

H ence,it isalso
call ed as B inary Algebr a or logi cal Algebra. A mathematician, named

George B oole had dev eloped thi s

algebra in 1854. Th e vari ables used in t his algebra are also

call ed

as B oolea n variables.

volt ag es

correspondi ng to l ogic

Pos tulates

and

B asic Laws

of

B oolean

Algebra

In

thi s

secti on,
let

us

discuss

about

the

B oolean

post ulates

and

basic

law s

that

are

used

in

B oolea n

algebra.
These

are

us eful

in m ini mi zing B oolean functi ons.

B oole an

Postulates
C onsi der the binary nu mbers 0 and 1, B oolean variable (x ) and it s

the

B oolean

variable

or

compl em ent

of

it is

known

as
li teral
.

The four possi ble

logi cal

OR

op erati ons among thes e

li terals and

binary numbe rs are

sho wn below.

x+0=x

+
1

x+x=x

S im il arly,

the

four

possi ble
logi cal

AND
op erati ons

among

those

li ter als

and

bina ry

numb ers
ar e

shown
below.

x.1 = x

x.0 = 0

x.x = x

These

are

the

sim ple

B oolean

post ulates.

We

ca n

verify

these

post ulates

easil y,
by

subst it uti ng

the B oolean

or

Note

The

compl ement

of

compl ement

of

any

B oolean

variable

is

equ al

to

the

variable

it self.

i.e.,
B asic

Laws

ofB oole an

Alg eb ra

Foll owing

are

the

three

b asic

laws

of

B oolean

Alg ebra.

C omm utative

law

Associative

law
Dist ributi ve

law

C omm utative

Law

If any logi cal op erati on of two B oolean va riable s give the same result ir respecti ve of

the orde r o f
those two vari ables, then that logi cal ope rati on is said to be
Com m u tative
. The

logi cal

OR &

logi ca l AND

operati ons

of two B oolea n

variables x &

y are

sho wn

below

x +y =y +x
x .y =y .x

A ND op erati on
and it is op ti onal t o repre sent. C omm utative law obeys for logi cal OR &

lo gical

AND

operati ons.

Associ ativ e

Law

If

logi c al

oper ati on

of

any

two

B oolean

va ria bles

is

performed
first

a nd

then

the

same

op er ati on

is

performed

with

the

rem aini ng

variable

gives

the

same

result ,

then

that

logi cal

oper ati on

is

said
to

be

Associative
.

The

logi cal

OR

&

logi cal

AND

op erati ons

of

th ree

B oolean variables x, y

& z ar e

sho wn
below.

x +(y +z)= (x +y )+
z

x. (y.z)

=(x.y ).z

Associative
law

obeys

fo r

logi cal

OR &

logical AND

oper ati ons.

Dist ribu tiv e

Law

If any logi c al ope rati on c an be dist ributed to all the terms pr esent in the B oolean

functi on, then tha t

logi cal

operati on is said to be
Distrib u tive
. The dist ributi on of logi cal

OR

& logi cal AND

operat ions of
three

B oolean v ariables x ,

y & z are

shown b elow.

x .(y
+ z)=

x .y +x .z

+ (y .z)=

(x +y ).(x

+ z)

Dist ributi ve

law

obeys fo r

logi cal OR

and logi cal

AND
oper ati ons.

These

a re

the

B asic

l aw s

of

B oolean

algebr a.

We
can

ve rify

thes e

laws

easil y,

by

subst it uti ng

the B oolean

or

T he orem s

of

B oolean

Alg eb ra

The

following

two
theorems

are

used

in

B oolean

algebra.

Duali ty

theorem

theorem

Duality

The orem

This

theorem

states

that

the
d u al
of
the

B oolean

functi on

is

obtained

by

int erchanging the logi cal

AND oper ator with logi cal OR oper ator and ze r os with ones. For

ev ery

B oolean

functi on, ther e

will

be

correspondi ng Du al

funct ion.

Let

us

make

th e

B oolean

equati ons
(relations )

t hat

we

discussed

in

the

secti on

of

B oolean

post ul ates

and
basic

laws

int o two

groups. The

following t able s hows

these

two groups.

Group 1

Group 2

x+
0=

x.1 =

x+

1=

x.0 =

x+

x=

x.x =

x+

x+

y=

y+
x

x.y =

y.x

(y + z) = (x +

y)

x.(y.z)

(x.y).z

x.(y +

z)

x.y +

x.z

(y.z)

=
(x

y ).(x

z)

In

ea ch

row,

th ere

a re

tw o

B oolean

equati ons

and

they

ar e

dual

to

each

oth er.

We
can

ve rify

all

thes e

B oolean
equati ons of Group1 and

Group2 by usi ng duali ty t heorem.

„Pv[’

T heorem

Thistheoremisusefulinfindingthe
com p lem en tofB ooleanfun ction
.Itstatesthat

thecompl ement
of logical OR of at l east t wo Bool ean
variabl es is equal t o the logical AND

of

each

compl emented

v ariable.

theor em
with

B oolean

variables

x a nd

can

be

repr esented

as

(x

The

dual of

the

abov e

B o olean functi on

is
Therefo re, the compl em ent of
logi cal AND of two B oolean variables is equal to the logi cal

OR of each

than

2 B oolean variables
also.

Sim plific ation

of

B oolean

Fun ctions

Till

now,

we

discussed

t he

post ulates,

basic

laws

and

theorems

of
B oole a n

algebra.

Now,

let

us

sim pli fy

some

B oolean

functi ons.

Eg

Let us
sim p lify

We

can
sim pli fy this functi on in two methods .

Method

Given

B oolean

functi on,

=
+p qr.

S tep

In

first

and

seco nd

terms

is

comm on

and

in

thi rd

and

fourth

terms
pq

is

comm on.

S o,

take

the
comm on terms by usi ng

Distrib u tive

law
.

f=

r)

S tep

The

terms

present

in
first

parenthesis

can

be

sim pli fied

to

Ex
-
OR

operati on.

The

te rms

present
in second par enthesis

can be

using
B oolean p ostul ate

f=

(p
R
q) r

+
pq(1)

S tep

The

first

term

be

sim pli fied

furth er .

B ut,

the

second

term

can

be

sim pli fied

to

pq

using
B oolean p ostul ate
.
œ

f=

(p

R
q)r

pq

Therefo re, the sim pli fied B oolean functi on is

f = (p
R
q )r + p q

Method

Given

B oolean functi on,

f=
p qr.

S tep 1

Use the
B oolea n p ostul ate
, x + x = x. That
means, the Logic al OR operati on with

any B oolean

term

pqr two more

ti mes.

f=

pqr +
pqr

pqr

S tep

Use

Distrib u tive

law
for

1
st

and 4
th

terms,

2
nd

and

5
th

terms,

3
rd

and

6
th

terms.

f=

p) +

q) +

r)

S tep

Use

B oolean

p ostul ate
,

+
=

f or

sim pli fying

the

terms

present

in

ea ch

pa rent hesis .

f=

qr(1)

pr(1 ) +

pq ( 1)

S tep

Use

B oolean p ostul ate

,
x.1 =

for

sim pli fying the

above

three

terms.

f=

qr +

pr

pq

f = pq + qr + pr

Therefo re,

the

sim pli fied

B oolean

functi on

is

f
=

pq

qr

+pr
.

S o, we got two different B oolean functi ons after sim pli fying the given B oolean functi on
in

each

m ethod.

Functi onall y,

those

two

B oolean

functi ons

are

s a me.

S o,

based

on

the

req uirement,
we

c an choos e

one

of
those

two B oolean functi ons.

Eg

Let

us find the

com p lemen t

of the

B oolean

functi on, f

The

compl ement

of

B oolean functi on

is
+

S tep

Use

theorem,

(x +

S tep

Use
theorem,

S tep 3

Use

the

B oolean

post ulate,

œ
=

{p +

q}

pq

S tep

Use

the

B oolean

f=
0+

pq +

f=

pq +

Therefo re,

the

com p lemen t

of

B oolean

functi on,

is

pq

.
Sum of

produc tMethod(SO P)

canonic al

sum

of

prod ucts

is

boole an

exp ressi on

that

enti rely

consi sts

of

mi nterms. The B oolea n

functi on F is defined on two variables X and Y. T he X and Y are the

input s of the boolean functi on F whose

output istruewhen anyo neofthe input sissettot rue.

The

t ruthtable forB o olean

Expr essi on

is asf oll ows:

In p u ts

Ou tpu t

1
we can form t he mi nterm from t he variabl e's value . Now, a colum n will be added for

the mint erm in

the above table. Th e com plement of the vari ables is t aken whose valu e is 0,

and

the variables whos e

value
is 1 wi ll remain

the

same.

In p u ts

Ou tpu t

Min term

X'Y'

1
1

X'Y

XY'

XY

Now,

we

will add

all the mint erms for

which the

o utput is

true

to

find

the
desired

canonic al

S OP (
S um

of
P roduct) expressi on.

F= X'

Y+X Y'+ XY

Convertin g

Sum

of

Prod u cts

(SOP)

to shorth an d

n otation

The proc ess of conv erting S OP form t o shorthand notation i s the same as the process o f

finding sho rthand

notation for mi nterms. There a re the following st eps t o find theshorthand

notation

of the

given SOP
expressi on.
o

Write

the

given SOP

expressi on.

Find

the

shorthand

notation of

all

the mint erms.

R eplace

the

mi nterms wi th

their

shorthand notations

in

the given

expressi on.
Examp le:

F =X 'Y+XY'+X Y

1.

Firstl y,

we

writ e

the

S OP

expressi on:

X'Y+XY' +XY

2.

Now,

we

find

the shortha nd

notations of
the

mi nterms

X'Y, XY', and XY.

X'Y = (01)
2
=m
1

XY' = (10)
2
=m
2

XY

(11)
2

m
3

3.

In

the end,

we

r eplace all

the
mi nterms

with

their shorthand

notations :

F=m1+m2+m3

C onv erting

shorthand

nota tion

to

SO P

exp ression

The proc ess of conv erting shorthand notation t o S OP i s the reverse p roc ess of
converting

S OP

expressi on

to

shorthand

notation.

Let's
see

an

ex a mpl e

to

understand

thi s

conversion.

Examp le:

Let us
assum e that we h a ve a boolean functi on F, which defined on two v ar iables X and Y.

Th e

mi nterms

for

the fun cti on

ar e

exp ressed as

shorthand notat ion i s as follows:

Now,
from

thi s expressi on,

we

will find

the

S OP expressi on.

The

B oolean

f uncti on

has

two

input

variables X

and y

and th e output of F=1 fo r

m1, m 2, and m3,

i.e., 1
st
,

2
nd
, and

3
rd

combi nati ons.

S o,

F=

m1

m2

m3

F=

01 +

10

11

Now, we r eplac e z eros with eit her X' or Y' an d ones with eit her X or Y. S im ply, the

compl ement variable is used when the variable value is 1 otherwise the non
-
compl ement

variable

is us ed.
F=01+10+11

F=

A'B + AB' +

AB

Karnaugh

Map(K
-
Map)

m ethod

Karnau gh
int roducedamethodforsim pli ficati onofB ooleanfuncti onsinan
easy

way.Thismetho d
isknownasKarnaughm apmethodorK
-
mapmet hod.Itisagraphi cal

met hod,whichconsi sts of2

n

cell sfor

singl e

bit posi ti on.

K
-
Maps

for

2 to

5Variables

K
-
Map

method

is

most

suit able

for

mi nim izing

Boolean

fun cti ons

of

va r iables

to

va riables.
No w,
let us

discuss about t he

K
-
Maps

fo r 2 to

5 variable s one

by

one.

Variable

K
-
Map

The

number

of

c ell s

in

2 variable K
-
map is

four,
s ince

the

number

of v aria bles

is

two.

The

following figure

shows
2 variab le K
-
Map
.

There

is onl y

one possi bil it y

of grouping

4 adjacent

mi n terms.

The

possi ble
combi nati ons

of

grouping

adjacen t

min

terms

are

{(m
0
,

m
1
),

(m
2
,

m
3
),

(m
0
,m
2
) and
(m
1
,

m
3
)}.

Variable

K
-
Map

The

number

of

cell s

in

variable

K
-
m ap

is

eig ht,

since

the

numbe r

of

variables
is

thr ee.

The
following figure

shows
3 variab le K
-
Map
.

There

is onl y

one possi bil it y

of grouping

8 adjacent

mi n terms.

Thepossi blecombi nati onsofgrouping4adjac ent mi ntermsare{(m

0
,
m
1
,m
3
,m
2
),

(m
4
,m
5
,m
7
,m
6
),
(m
0
,m
1
,m
4
,m
5
), (m
1
,m
3
,m
5
,m
7
), (m
3
,m
2
,m
7
,m
6
) and (m
2
,m
0
,

m
6
,m
4
)}.
The possi ble combi nati ons of grouping 2 adjacent mi n terms are {(m
0
,m
1
), (m
1
,m
3
),

(m
3
,

m
2
),

(m
2
,

m
0
),

(m
4
,

m
5
),

(m
5
,

m
7
),

(m
7
,

m
6
),

(m
6
,

m
4
),

(m
0
,

m
4
),

(m
1
,

m
5
),

(m
3
,

m
7
) and

(m
2
,m
6
)}.

If

x=0,

then 3

variable K
-
map

becomes

2 variable K
-
map.

Variable

K
-
Map

The

number

of

cell s
in

variable

K
-
map

is

sixt e en,

since

the

number

of

variables

is

fou r. The

following

figure

shows
4 variab le K
-
Map
.

There
is onl y

one possi bil it y

of grouping

16 adjacent

mi n terms.

Let R
1
,R
2
,R
3
and R
4
represents the mi n terms o f first row, se cond row, thi rd row and

fourth ro w
respecti vely. S im il arly, C
1
,C
2
,C
3
and C
4
represe nts the mi n terms of first

colum n,
second colum n,
thi rdcolum nand fourth c olum nrespecti vely. The possi ble

combi nati onsof grouping8 adjac entmi n

terms are { (R
1
,R
2
), (R
2
,R
3
), (R
3
,R
4
), (R
4
,

R
1
),

(C
1
,

C
2
), (C
2
,C
3
), (C
3
,C
4
),(C
4
,C
1
)}.

If

w=0,

then
4

variable

K
-
map

becomes

variable K
-
map.

Variable

K
-
Map

The

number

of

cell s

in

variable

K
-
map

is

thi rty
-
two,

since

the

numb er

of

variabl es

is

5. The
following figure

shows
5 variab le K
-
Map
.

There

is onl y one possi bil it y of

grouping 32 adjacent m in t erms.

There
ar e

two

possi bil it ies

of

grouping

16

adjace nt

min

terms.

i.e.,

grouping

of

min

terms

from m
0

to m
15

and

m
16

to m
31
.
If

v=0,

then 5

variable K
-
map

becomes

4 variable K
-
map.

In

the

above

all

K
-
maps,

we

used

ex clusi vely

the

min

terms

notation.
S im ilarly,

you

can

use

exclusi vely

the

Max terms no tation.

Min im ization

of

B oolean

Fun ctions

using

K
-
Maps

we

will

g et

the
B oolean

functi on,

which

is

in
stand ard

su m

of

p rod u cts
form

aft er

sim pli f ying

the K
-
map.

then we will get

the Bool ean functi on, wh ich is i n
stand ard p roduct of su m s
form after

sim pli fying

the K
-
map.

Foll ow

these
ru les

for

si m p lifyin g

K
-
m ap s

in

order

to

get

standard

sum

of

products

form.

S elect t he resp ecti ve K

-
map based on the numbe r of variabl es pres ent i n the Boolean

fun cti on.

IftheB ooleanfuncti onisgivenassumofmi ntermsform,thenplacetheonesat

respecti vemi nter m

cell s in the K
-
map. If the B oolean functi on is give n as sum of

produ cts for m, then place the on es in

all possi ble cell s of K
-
ma p for which the given

pro duct

terms are

vali d.

C heck for the possi bil it ies of grouping maximum number of adjac ent o nes. It shoul d

be powe rs of
two. S tart from highest power o f two and upto l east powe r of two.

High est power is equ al to the

number of vari ables cons idered in K
-
map and leas t

power

is zer o.

Each g rouping will give eit her a li teral o r on e pr oduct term. It is known as
p rim e

im p licant
. The
prime im pli cant is said to be
essential p rim e im p licant
, if atl e ast

singl e
is

not

covered

with

any

other

groupings

but onl y

that

grouping

covers.

Note down all the prime im pli cants and essential prime im pli cants. The simpl ified

B oolean functi on
contains all essential pri me impl icants and only t he requir ed prime

im pli c ants.

Note 1

If output s ar e not defin ed fo r some c ombi nati on of input s, then those

output v alues

will be
repres ented wit h

. That m eans, we c an consi de r the m as eit her

Note2

K
-
map.C onsi der

a djacent

ones.

Inthose

cas es,

treat
the

value as

Eg

Let

us

sim p lify
the

following
B oolean

functi on,

f(W,

X,

Y,

Z )=

WY

using K
-
map.

The

given

B oolean

funct ion

is

in

sum

of

products
form.

It

is

having

vari ables

W,

X,

&

Z. S o,

we

requir e

variab le

K
-
m ap
.

The

variab le

K
-
m ap

with

ones

correspondi ng

to

the

given

product
terms i s shown in t he

following figure.

Here,

1s

are

pla ced in

the following cell s

of

K
-
map.
The

cell s,

which

a re

co mm on

to

the

int ersecti on

of

R ow

and

colum ns

&

are

co rrespondi n g

to t he product t erm,

.
The

cell s,

which

ar e

co mm on

to

the

int ersecti on

of

R ows

&

and

col umns

&

are

correspondi ng to t he

pro duct t erm,

WY
.

The

cell s,

which

ar e

co mm on

to

the

int ersecti on

of

R ows

&

and

c olum n

are

co rrespondi ng

to t he
product t erm,

Thereare nopossi bil it iesofgroupingeit her 16adj acenton esor8adjac ento nes.Ther ea re

three possi bil it ies

of grouping 4
adjacent ones. After these thre e gro upings , there is no single

one left as ungrouped. S o, we no

need to check for groupi ng of 2 adjacent ones. The
4

variab le

K
-
m ap

with

these

three
grou p in gs
is shown
in

the foll owing figure.

Here,

we

got

three

pri me
im pli cants

WY

&

All

these

prime

im pli cants

are

e ssential
because

of following rea sons.

Two

ones

(m
8

&

m
9
)

of
fourth

row

grouping

are

n ot

covered

by

any

other

groupings.

Only

fourth
row grouping cove rs those

two ones.

S ingl e

one

(m
15
)

of

square

shap e
g rouping

is

no t

covered

by

any

othe r

groupings.

Only

the
square

shap e

grouping co vers that one.

Two

ones

(m
2

&

m
6
)

of

fourth
colum n

grouping

are

not

cove red

by

any

o ther

groupings.

Only
fourth column grouping covers those

two on es.

Therefo re,

the

sim p li fied

B oolean

fun ction

is

+WY
+

Foll ow

these

ru les

for

si m p lifyin g

K
-
m ap s
in

order

to

get

standard produ ct

of

sums

form.

S elect t he resp ecti ve K

-
map based on the numbe r of variabl es pres ent i n the Boolean

fun cti on.

If
the B oolean functi on is given as product of Max terms form, then place the zeroes

at

r espe cti ve

Max

term

c ell s

in

the

K
-
map.

If

the

B oolean

functi on

is

given

as

pr oduct of sums form, then

place the zero es in all possi ble cell s of K
-
map fo r which

the
given sum ter ms are

v ali d.

C heck

for

the

possi bil it ies

of

grouping

maximum

number

of

adjac ent

z eroe s.

It

shoul d be powe rs of
two. S tart from highest power of two and upto lea st power of

two.

Highest

power

is

equal
to

the

number

of

variabl es

con sidered

in

K
-
map

and

le ast

power is zero.

Each grouping will

give eit her a li ter al or on e su m

term. It is

kno wn as
p rim e

im p li can t
. The prime
im pli cant is said to be
essential p rim e im p li can t
, if atl east

singl e
is

not

covered

with

any

other

groupings

but onl y

that

grouping

covers.

Note down all the prime im pli cants and essential prime im pli cants. The simpl ified

B oolean functi on
contains all essential pri me impl icants and only t he requir ed prime

im pli c ants.

Note

K
-
map.C o nsider
adjacent

z eroes.

In

those

c ases,

treat

the

value as

Pair,

Quad

and

O ctet

Pair Red u ction Rul e

:
R emove the vari able whic h changes it s st ate from c ompl emented to

uncompl emented

or vice
versa.P air r emoves one

v ariable

only.

Qu ad Red u ction Rul e

:
R emove the two variabl e s which chang e their stat es.A quad

r emoves

two
variables.

Octet
R ed u ction Rul e

:
R emove the three v ariabl es which chan ges their st ate.Octet r emoves

thr ee

variables.

Map Rolli n g

:
Map rolling means roll the map consi dering the map as if it s left edges are

touching the
right edges and top edge s are touching
bott om edges.Whil e marking the p airs

quads
and octet, map must
be rolled.

Overlap p in g Group s

:
Overlapping m eans s ame 1 can be encircl ed more than once.

Ov erlapping

always l eads t o si mpl er e xpressi ons.

Red u n d an t Group

:
It i s a group whose all 1's are overlapped by othe r gro ups. R edundant

groups

must

be removed. Remov al

of

redundant

group

leads

to

much simpl er

expressi on .
Eg

R epresent t he

follo wing

boolean expressi on

in

aK
-
map

and

sim pli fy.

x'yz

x'yz'

xy'z'

xy'z

S o luti on
:

The

K
-
map is

as

follows :

Hence th e sim pli fied exp ressi on is

x'y +

xy'

E x.

:
S impl ify the

following

boolean expressi on

using

K
-
map.
F

a'bc

ab'c'

ab c

a bc'

S o luti on

The

K
-
map is

as

follows :

Hence th e sim pli fied exp ressi on is

=
bc

a c'

}v[ ı

Care

C ond itio n

K
-
Map
to form a

grouping of

as

eit he r

or

or

we

c an

sim ply

ignore
that

cell .

Therefo re,

c ondit ion

can

help

us

to

for m

large r

group

of

cell s.

-
Maps r epres enti ng a invalid

combi nati on.

For ex ampl e, in Excess
-
3 code syst em, t he states 0 000, 0001, 0010, 1101, 1110

and
1111

a re

invalid

or

unspecified.

Th ese

a re

c all ed

c ares.

Also,

in

d esign

of

4
-
bit

BCD
-

to
-
XS
-
3 code conv erte r, the in put
combi nati ons 1010, 1011, 1100, 1101, 1110, and 1111 are
car es.

standard

S OP

functi on

having

car es

c an

be

converted

int o

P OS

exp ressi on

by

cares as
they a re, and wri ti ng the mis sing m interms of the SOP form as the

maxterm

of

P OS
form.

S imi larly,

P OS

functi on

having

ca res

can

be

conv erte d

to

S OP

form

keeping

the

c ar es

as

they

a re

a nd
writ e

the

mi ssi ng

maxterms

of

the

P OS

expr essi on

as

the

mi nterms

of

S OP

express ion.

Eg

Minimise

the

following

function

in

S OP
mi nimal

form

using

K
-
Maps:

f =

m( 1, 5, 6, 12,13, 14) +d( 4)

Exp lanat i on

The

S OP

K
-
map

for

the

g iven

expr essi on

is:

Therefo re,

S OP

mi nim al
is,

Eg

Minimise

the

following

function

in

S OP

mi nimal

form

using

K
-
Maps:

Exp lanat i on:

Writing

the

given

express ion

in

P OS

form:
The

P OS

K
-
map

for

the

g iven

expr essi on

is:

Therefo re,

P OS

mi nim al

is,

F(A, B , C , D)

m(0, 1,

2,

3, 4, 5)

+
d(10, 11, 12, 1 3, 14, 15)

F(A,

B , C , D)

M(6, 7,

8, 9)

d(10, 11, 12,

13,

14, 15)

A'(B ' +

C ')

BC'+

B D' +

A'C'D

Eg

Mini mi se
the

following

functi on

in

S OP

mini mal

form

using

K
-
Maps:

F(A,

B,

C,

D)

m(1,

2,

6,

7,

8,

13,

14,
15)

d(3,

5,

12)

Exp lanat i on:

The

S OP

K
-
map

for

the

g iven

expr essi on

is:

Therefo re,

AC'D' + A' D

+
A'C

AB

P rodu ct

of

Sum

Method(POS)

canonic al

produ ct

of

s um

is

boolean

expressi on

that

enti rely

c onsi sts

of

maxterms. The B oolea n

functi onF isdefin edont wo
variabl esX andY.T heXandY ar ethe

input s

of

the

boolean

functi on

whose

output

is

true

when

onl y

one

of

the

input s

is

set

to

true.
The

truth tabl e

fo r B oolean expr essi on

is as
follows:

In p u ts

Ou tpu t

1
0

In ou r
mi nterm and maxt erm secti on, we l earn ed a bout how we can form t h e maxterm from

the va ria ble's

value. A colum n will be added for th e maxterm in the above table. Th e

co mpl ement of the variable s is taken

whose value is 0, and the variables whos e value is 1 will

remain

the same.

In p u ts

Ou tpu t

Min term

X'+Y'

0
1

X'+Y

X+Y'

X+Y

Now, we will mul ti ply all t he mi nterms for which the output i s false to find the desired

canonic al

P OS(P roduct of sum)

expressi on.

F=( X'+Y') .( X+Y)

C onv erting

Produ ct

of
Sum

(PO S)

to

shorthand

notation

Theprocessofconve rtingP OSformtoshorthandnotationisthesameastheprocessof

findingshorthand
notation for maxterms. There ar e the following steps used to find the

shorthand

notation of the

given P OS
expressi on.

Write

the

given POS

expressi on.

Find

the

shorthand notati on

of

all the
maxterms.

R eplace

the mint erms

wi th t heir

shorthand notations

in t he

given expressi on.

Eg

(X'+Y').(X+Y)

1.

Firstl y,

we

will

writ e

the

P OS

expressi on:
2.

Now,

we

will

find the shorthand notati ons

of the

maxterms X'+Y'

and X + Y.

3.

In

the

end,

we

will repla c e

all the

mi nterms wi th t heir

shorthand notations:

C onv er ti ng

s hort han d

nota t ion

to
P OS

ex pre s si on

The proc ess of conv erting shorthand notation t o P OS i s the reverse p roc ess of

conv erting P OS
expressi on to s horthand notation. Let's s ee an ex a mpl e to understand thi s

c onversion.

Eg

Let us
assum e that we h a ve a boolean functi on F, defined on two va riables X and Y.

Th e

maxterms
for the

functi on F

ar e

exp ressed as shorth and notat ion i s as

follows:

Now, from t his expressi o n, we find the POS expre ssi on. The B oolean funct ion F has two

input

variables X

and

and th e

output of F=0
for

M1, M2, and

M3, i .e., 1
st
,

2
nd
, and

3
rd

combi nati ons.

S o,

Next, we r eplac e ze ros w it h eit her X or Y and on e s with eit her X' or Y'. Si mpl y, if the
value

of the v ariable
is 1,
then we take the co mpl ement of that variabl e, and if the valu e of the

variable

is 0, t hen we

tak e

the
variable

"as is" .

=
(X' +Y'). (X+ Y)

X'+Y'

(00)
2

M
0

X+Y

(11)
2

M
3

F=M
0
.M
3

F=

M1.M2.M3

F=

01.10.11
F

F=01.10.11

F=( A+B ').(

A' +B ).(

A'+B ')

P ro duct

of

Su m

S im pl ific at i on

To find the sim pli fied m axterm solut ion using

K
-
map is the s ame as to f ind for the

mi nterm solu ti on.

There are som e mi nor ch anges in t he maxterm sol uti on, which are as

follo ws:

1.

We will populate the K

-
map by entering t he valu e of 0to ea ch sum
-
term i nto t he K
-
map

cell and
fill t he remaining cell s
w it h one's.

2.

We

will

make

the

groups

of 'z eros'

not

for

'ones'.

3.

Now,

we

will

define

the

boolean

expressi ons for

e ach

group as sum
-
terms.

4.

At last, t o find thesim plified boolean exp ressi on i n the POS form, we will combi ne

the

sum
-
terms
of all indi vidual groups.

Let's

take

some

ex ampl e of

2
-
vari able,

3
-
vari able,

4
-
variable and

5
-
v ariable K
-
map
ex ampl es

Eg

Y=(A'+B ')+(A'+B )+(A+ B )

S im pl ified ex pres s ion: A 'B

Eg

Y=(A

+B +

C') + (A

B'+

C') + (A'

+B'+

C)

+ (A' +

B ' + C')

S im pl ified

ex pre s sion:

Y=(A +

C ')

. (A' +
B ')

Eg

A‰~ïU ñU óU ôU í ìU í íU í îU í ï

S imp li fied

exp ressi on :

Y=(A

C')

.(A'

B ')

C o mbi na tio na l Ci rcui ts

Ka rna ug h

ma p:

For e ach sym bol of the E xcess

-

fo r

sim pli fying

B oolean

functi on

:
Ci rcuit

i mplement at i on:

CD+

CD+

(C

+
+

D)

B (C

w=

A+

BC

BD

A+

B (C

D)
Introduct ion tocombi nat ional circuit s
:

A c ombi nat i onal c i rcui t c onsi st s of l ogi c gat e swhose out put s at any t i me are de
te rmi ne df rom onl y t he pre se nt
c ombi nati on of i nput s.

A c om bi na t i ona l c i rcui t pe rform s a n ope ra t ion tha t ca n be spe ci fie d l ogi cal l y
bya se t of Bool ea n func t i ons.

Se que nt i al c i rc uit s:

Se que nti al c i rc ui t s empl oy st orage e le me nt s in addi t i on t o logi c gat e s. The i r out

put s are a f unc ti on of t he
i nput s and t he st ate of t he st orage e le me nt s.

Bec a use t he st a te of the st ora ge el em e nt s i s a func t i onof pre vi ous i nput s, t he

output s of a se que nt ia l c i rc ui t
de pe nd not onl y on pre sent va l ue s of i nput s, but a l so on pa st i nput s, a ndt he c i rc
ui t be ha vi orm ust be
spe c i fi e d bya ti m e se que nc e ofi nput s a n
d i nte rnal sta t e s.

A n al ysi s Pr oc ed ur e

E xplai n th e an alysis procedu re. A n alyze th e combi n ati on al circu it th e follow in g

logic diagram . (May 2015)
The analysi s of a combi nati onal circuit requir es that we dete rmine the fun cti on that the
circuit
im plements.

The analysi s can b e pe rfo rmed manuall y by findi n g the Boolean functi ons or truth t able
or by usi ng a
comput er simul ati on program.

The first s tep in the analy sis is t o make that the given circuit is combi nati onal or
sequenti al.

Once the logic diag ram i s verified to be combi nati onal, one can p roce ed to obtain the
output B oolean
functi ons or the truth t abl e.

To obtain the output B oolean functi ons from a logi c diagram, pro ceed as fo ll ows:

1.

Label all gate output s tha t are a functi on of input variables wit h arbitr ary sy mbol s.
Determi ne the
B oolean functi ons for e a ch gate output.

2.

Label t he gates th at are a functi on of input variable s and previous ly l abeled gates wit h
other arbitr ary
symb ols. Find t he B oolean functi ons for these g ate s.

3.

R epeat t he pro cess out li ned in s tep 2 until the outputs of the circuit ar e obta ined.

4.

B y repeated substi tut ion of previous ly defined fun cti ons, obt ain t he output B oolean
functi ons i n ter ms of
input variables.

E xam ple
:

F1 =
T3 + T2

=í=

The Boo lean func tions for the abo veo utputs ar e,

Der i ve

trut h

tabl e

fr om

logic

d i agr am

We

can

d er i ve th etrut h

tabl e
in

T ab l e

4
-
1

by

u sin g

th e ci r cu it

of

Fi g. 4
-
2.

Design

p roced u re :

Th ed esign

of

comb in at ion al

circu it s

st art s

f rom

t he sp ecificat ion
of

t h e design

ob ject ive an d

cu lmin ates

in

logic

circuit

d iagram

or a

set of

Boolea n

fu n ct ion s

f ro m

w h ich

th e

logic

d iagram

can

be

ob t ain ed .
Th e

pro cedu re

in volved
in volves

the

f ollow in g

step s,

Fro m

t h e sp ecif icat ion s

of

the

circu it ,

d etermine

th e

req u ired

n u mb er of

inp u t s

and

outpu t s

and
assign
a

symb ol

to

ea ch .

D er ive

th e

t rut h

t ab le

t hat

d efin es

th e

req uired

rela t ion sh ip

b etwe en

in pu t s

an d

outp ut s.

Ob t ain

the

simp lif ied

Boole an

fu n ct ion s f or ea ch

ou tp ut

as

f un ct ion

of

th e

inp ut

variab les.

D raw

the

logic

d iagram

an d

verif y

th e

cor re ctn ess

of

the
d esign .

E x a mple :
Design a combi na ti onal logic circuit with three in p uts , theoutp ut is a t logic 1 whe n
more
than one in p uts are at logic 1.

Solution:

Assume

A,

B,

are in puts an d

Y is

outp ut

T ruth

table

K ma p
Simplification
Boole a n
Expression

Y=AC + BC

+
AB

Logic

Diagram

Bi na ry

A dder
-
Subtra cto r:

HALF
-
ADD ER
:

ac omb in ation alc ircu itth atp erform s th e

add ition
of

two

b its

is

c alled a

h alf add er.

H alf
-
ad d er

is

used

to

add

two b it s.

Therefore,

half
-
ad d er

has

two

in p uts and two outp uts, wit h

S UM an d CARRY. F igure shows the t ruth ta b le of a half

-
ad d er.

The

Boolea n

exp ressi ons

for

S UM an d CARRY

are,

S UM =

CARRY = AB

These exp ressi ons shows` that ,

S UM outp ut isE X
-
OR gat e a nd the CARRY outp ut is AND

gat e.

F igure shows the b e i mplemen ta ti on of half

-
add er wit h all the comb in at ions

in clud in g the

imp lement at ion

using

NAND

gat es

only.

Tru t h ta ble

Inputs

Output

0
1

1
1

Inputs

Outputs

Carry

Sum

1
1

FU LL

AD D ER

one

that

per for ms

the

addition

of

thr ee

bits (two

signif ic ant

bits

and

pr evious c ar r y)

is
a

full adder
.

(x

y)

ïï

+
ï

x yz +

±ï

xy

K
-
ma p

simplifications
Inputs

Outputs

Cin

Cout

Sum

0
1

0
1

T ruth

table

Ca rry

Prop a ga t ion

Th e sign alf ro m C
i
t ot h eou tp ut carry C
i+1
, pro p agat est h rou gh an AND and OR

gat es, so,

f or an n
-
b it RCA,t her e are 2n gate levels f or th e carry t o p rop agat e
f rom in p ut

to

ou tp ut .

Becau se

th e

pro p agat ion

d ela y

w ill

af fect

t he

outp u t

sign als

on

d if f erent

t ime,

so

th e

sign als

are

given
en ou gh

t ime

to

get

the

p recise

and

st ab le

ou tp ut s.

The

F ull

Ad d er

can

be

implemen t

using

Two Ha lf

Ad d ers

and OR

gates

The
exp ressi on

for

sum

is

The

E xp ressi on

for

carry

is

Logic

Diagram

T ruth

table of Hal f
adder

Logic
Diagram

K
-
ma p

for Diffe re nc e

a nd
Borrow

Subtractor

S ubt ract or is the logic c ircuit which is

used to subtract two b in ary nu mbe r (di git ) an d p rovides

Differen ce an d Borrow as a outp ut.

In d igital ele ctronics we have two

type s of subtractor, H alf

S ubt ract or

an d F ull
S ubt ract or.

Rule s

for two bit

addition

0
-

= 1 wit h

b orro w

Ha lf

Subtractor

H alf Subt ract or is used for subt ract in g one sin gle b it b inary d igit from an other single
b it b in ary
d igit. The t ruth tab le ofH alf
S ubt ract or is shown b elow.

Inputs
Outputs

Difference

Borrow

0
F ull

Subtractor

logic

Circuit

Which

is

used

for

S ubt ract ing

Three

S in gle

b it

Bin ary

d igit

is known a s F ull
S ubt ract or. The i np uts are A, B, Bin an d the outputs are D and Bout.

K
-
ma p

for D
a nd
Bout

Logic

Diagram

T ruth

table

We

can

further

simp lify

the

functi on

of

the
Differen ce
(D)

S imp lified

L ogic

diagram

Mag nitude

compar ator
:

Th eequ alit y rela t ion o f each p air of b it s can be exp re ssed logicallyw ith an

exclu sive
-
N OR

f un ct ion

as:

=A
3
A
2
A
1
A
0

;
B=B
3
B
2
B
1
B
0

x
i
=A
i
B
i
+A
i

i
ï

for i = 0, 1, 2, 3

(A

B) = x
3
x
2
x
1
x
0

Ma gnitude

Compa ra tor
Definition
A

magni tud e

comp arator

is

comb in at iona l

circuit

that

comp ares

two

numbe rs

&

to
d et ermin e whet her:

>

B,

or A

=
B,

orA<B

Inputs

Outputs

Bin

Bout

1
0

0
0

We in sp ect th e rela t ivemagn itu d es of p airs of MSB. If equ al,w e comp are t he

next

low er

sign if icant

p air of

d igit s

un t ila

pair

of

u nequ al

d igit s

is

re ached .
If the co rrespo nding digit of A is 1 and t hat o fB is0 ,we co nclude that
A>B.

(A>B)=

A
3

3
+x
3
A
2

2
+x
3
x
2
A
1

1
+x
3
x
2
x
1
A
0

(A<B)=

3
B
3
+x
3

2
B
2
+x
3
x
2

1
B
1
+x
3
x
2
x
1

0
B
0

Decoder

Decode r

is

comb in at iona l

circuit . It has N

in p uts an d 2
N
outp uts.

Th e

d ecod er

is

calle d n
-
to
-
m
-
lin e

d ecod er ,

w her e

uGî
n

the

d ecod er

is

also

u sed

in

con ju n ct ion
w it h

oth er

cod e

con vert er s

su ch

as

BCD
-
to
-
seven _se gmen t

decod er.

3
-
to
-
8 lin e d ecod er : Fo rea ch possib le inp u t comb in at ion , th er e are seven

ou tp ut s

t h at

are

equ al

to

0
and

on ly

one

th at

is

eq u al

to

1.

to

Decoder

It

has 2

in p uts an d

2
2

outputs.

C ircuit
Diagram

T ruth

Table

Logic

Diagram

to 4

Dec ode r

wi th

Ena ble
input

T ruth

Table

Logic

Diagram

to
8

Decoder

It

has 3

in p uts

and

2
3

outputs.

Logic

Diagram

Encoders

E ncod ers
is

a combi nat ional

circuit which ta kes

2
N

inp uts

an d gives out N

outp uts,

the e nab le pin should

b e kep t 1 for en ab ling the circuit .

to

Encoder

It

has

2
2

in p uts an d

outputs.

T ruth
Table

P riority

Encoders

A Priorit y

E ncod er

wor ks

opp osite

of the

d ecod er

circuit .

Ifmore

than one in p ut is a ctive, thehigher

ord er inp ut has p riorit y.

to

2
Priori ty

Encoders

D0
-
D3

in p uts
A 1, A 0

outputs

Active (A)

Vali d in d icator. It i nd icat es the outp ut is valid or not Output is i nvalid

when n o inp uts are
act ive . i. e, A=0

Outp ut

is

vali d

when at

lea st

one

in p ut is

act ive

. i, e,
A=1

T ruth

Table

K
-
ma p

simplification

Logic

Diagram

to

Priori ty

Encoder

Mu l tip l exer

(Mux)

M ultip lexer
is

comb inat iona l

circuit

that

select s

b in ary

in formati on

f r om one

of

many in p uts
an d directs it in to sin gle outp ut.

The

select ion

of

p articul ar

in p ut

is

controlled

by

a
set

of

select ion

line Mutlip lexer

has2
n

in p uts,
n se lect lin e (control inp ut) and one outp ut

It

also

called

as

Data

selector
.

2 to 1
Multiplexer

has

2
1

in p uts,

select
line

an d one

output

Circ uit
diagram

4 to 1
MUX

4 to

M UX has 2
2

in p uts, 2

select

line

and

one
output
8 to1
MUX

8 to1 M UX has

2
3

= 8 in p uts,

select line and

one

output

MUX

as

unive rsa l

c ombina tional

modules

E ach

mint erm

of

the

functi on can
be

map p ed

to

d ata

in p ut

of

the

multiplexer.

F or

ea ch

row

in the t ruth tab le, where

the

output is

1, set the corresp ond in g

d ata i np ut of themux to
1.

S et

the remain ing inp uts of the mux to 0.

Ex a mple

1:

Implemen t

the

followin g Boolea n

f uncti on

using

4: 1

ááááá

T ruth

Table

Multiple x e r

Implementation

E x a mple

2:

Impl e me nt

the follow ing

Boolea n

func tion

us ing

8 :1

MUX

F (A, B, C, D)

áá

4,

11, 12
-
15)

Dem ultiplexer

(DEMUX)

Demul tiple xe r

h as

2
n

ou tp ut s

select
lines,

on e

in pu t . A
de multiple xe r
is also calle d a d at ad ist rib ut or .

1
-

to
-
2

demultiplexer

has

2
2

outp uts

select

line s,

one

input.
T ruth

Table

Logic

diagram

1
-
to
-
4

Demultiplexer

It

has

o ne input,2

selec t

lines,4

outputs

T ruth

Table

Logic
Diagram

1
-
to
-
8

Demultiplexer

H as

one

in p ut 3
-
select line s
8
-
outputs

T ruth

Table
Logic

Diagram

1
-
to
-
8

DEMUX

us ing

T wo

1
-
to
-

Demultiplexers

1
-
to
-
8

d emulti p lexer

can

be
imp lement ed

b y using

two

1
-
to
-
4

d emulti p lexers

wit h

a p rope r
cascad in g.

App lications

of

Demultiplexer

Syn ch ro nou s

d at a

tran smission

systems

Boo lea n

fu n ction

implemen t at ion
(as

we

d iscu ssed

fu ll

sub t ract or

fu n ction

above)

D at a

acqu isit ion

systems

Com b in at ion al

circu it

design

Au t omat ic

t est

eq u ip men t

systems
Se cu rit y

mon itor in g

systems

(fo r

sele ct in g

p art icu lar

su rveillan ce

came ra

at

at ime), et c.

In
thefigure
, thehighes tsignifican tb it Aof
the select ion in p uts are conne cted to the
en ab leinp utssuchthat it iscomp lement ed
b efore conne ctin g to one DE MUX and to
the other it is d irectly
conne cted. By

this
configurat ion, when A is se t t o zero, one o f
the outp ut line s

from Y 0 to Y3 is select ed
b ase d on the comb inat ion of select line s B
an d C. S imilarly, whenA isset toone, b ased
on the select line s
one of the outp ut lines

from Y4 to Y 7 will b e se lecte d .