A New Approach to the Solution of Switching Functions Having Cyclic Prime Implicant Tables

INTRODUCTION

Standard techniques of designing minimal two-stage combinational networks consist in first generating all possible prime implicants corresponding to the speci- fied _switching function and then selecting minimal subsets of these prime impli- cants which will be actually used in the design of the networks (Aiken, 1951;

Quine, 1952; 1955; Veitch, 1952; Karnaugh, 1953; McCluskey, 1956; Urbano and Mueller, 1956; Petrick, 1956; 1959; Roth, 1957; Svoboda, 1957; Ghazala, 1957;

Troye, 1959; Mott, 1960; Pyne and McCluskey, 1961; 1962; l\fokhopadhyay, 1962; Choudhury and Basu, 1962; Scheinman, 1962; Hall, 1962). For th.is latter purpose, a prime implicant table first suggested by Quine and later greatly syste- matised by McCluskey is commonly used (Quine, 1952; 1955; McCluskey, 1956).

The problems for which the prime implicant tables have row and column domi- nances and essential rows can be solved readily. Generally, removal of an essen- tial row from the prime implicant table gives rise to row dominances while removal of the dominated rows yields essential rows. In this way, for a large class of problems, the tables are gradually reduced in size until the solution is obtained.

However, there are problems for which a stage is ultimately reached when there occur no further row dominances and hence no further progress can be made.

Such tables are said to be cyclic in nature or simply cyclic.

The prime implicant table method of McCluslcey for cvclic tables b · · l

• . • J egins wit, 1

the selection of a. column with least number of crosses and a ro ^r f tl t bl

c " 0 le a e cor

responding to any of these crosses is selected as a trial basis . I .1 -

• • • • . c •• low. n t le next steµ

the selection is made readily if row donunances ocenr ai l tl t f ' Le 1 ta a ter re.ntoving 31

INSTITOTE OF RADIO PHYSICS A..."ID ELECTRONICS UNIVERSITY OF CALCUTT.<\.

(Reccivecl November 11, 1963)

ABSTRACT. A method for finding one of the minimal solutions to a cyclic prime implicant table is suggested in the paper. The cyclic prime implicant table is first split up into a number of sub-tables such that each of the sub-tables corresponds to a parbicular open connected cover term matrix. All the irredundnnt solutions associated with each such open connected cover term matrix can be readily obtainod. The knowledge of the irredundant solutions of these open connected cover term rnabrices (i.e., of the sub-tables) is then ~1itably utilized to arrive at a minimal solution.

A. K. CHOUDHURY, SUJ\TJL RANJAl"\T DAS ^{AND M.} S. BASU 6

A NEWe APPROACH TO THE SOLUTION OF SWITCHING FUNCTIONS HAVING CYCLIC PRIME

IMPLICANT TABLES

Splitting a Cyclic Prime Implicant Tuble into a Number of Sub-tables

Any prime implicant table can be represented in Boolean form (.McClu~k~y, 1956; Petrick, 1956; 1959) as a product of sums expression, called the minin11zI11g function (Caldwell, 1958) where each of the ^Slim terms is called the cover term.

The cover terms are the disjunctions of prime implicants covering particular terms of the function. Multiplying out this product of sums expression according to the laws of Boolean algebra, viz., A(A+B) =A and A . ^{.(l =} A, all the irredundant solutions can be obtained. But such a direct multiplication procedure has the disacl vantage of generating many non-minimal solutions, in general. So when the uujcctive is to ~cl only one of tho minimal solutions, the prime implicant ta!Jlc itself can be ~mtably :¹~ed to obtai~ that, without entering into such an elaborate process of cletermuung all the irredundant solutions.

In the present paper a method has been suggested for obtaining the minimal solution of a cyclic prune implicant table with reduction in the number of trial steps. The method consists essentially in splitting a cyclic prime implicant table into a number of sub-tables such that the complete solution of each of these sub-tables (all the irredundant covers of the terms included in the representation of each of the sub-tables) can be obtained readily. From a know- ledge ef the irredundant solutions associated with each of the sub-tables, a minimal solution of the original table can be obtained with very little trial procedure.

If, starting with any prime implicant of any of these sub-tables, difficulty arises at some intermediate stage regarding the definite selection of any particular prime implicant, then in general, all the possibilities of coverage of the sub-table in question are first included and at a later stage, a definite conclusion regarding the selection of a particular one of them in the minimal solution is arrived at.

Further, in every stage of selection minimality condition is ensured and we can say definitely that of all the solutions which include the prime implicant we started with, we have found one of these containing the least number of prune implicants. The method as suggested in the present paper not only reduces the total number of trials required for finrling one of the minimal solutions but at the same time diminishes the labour involved in each trial.

the dominated rows, the dominating rows become essential. ^If in any interme- diate stage of selection the table becomes again cyclic, then there ^wiJl occur dif- ferent possibilities of choice and a trial basis row will have to be selected again.

nI this way, depending on the nature of the problem, a large number of; trials may be required to arrive at a minimal solution. In general, different alternate possible solutions have to be tested to obtain a minima.l solution. Number of possible trials can be minimised, to some extent, if a prior information regarding the total number of prime implicants required for a minimal solution and the surety of occurrence of the prime implicants as basis rows in the minimal solution is at hand.

32

A. K. Choudhury, Swnil Ranjan Das and M. S. Basu

*The example has been taken from "Minimization of Boolean F ti ,, . - unc ions by E J :.\le Cluskey, Jr., Bell System Technical Journal, Vol. 35, No. 6, November,

1956. · " · 5

(ix) (4, 5, 20, 21)

=

^I (xvii) (9, 13, 25, 29)

=

Q (x) (5, 7, 13, 15) ^=J (xviii) (16, 18, 24, 26)

=

R (xi) (5, 7, 21; 23)

=

!( (xix) (16, 20, 24, 28)

=

^S

(xii) (5, 13, 21, 29)

=

L (xx) (18, 19, 26, 27)

=

T (xiii) (6, 7, 14, 15)

=

M (xxi) (20, 21, 28, 29)

=

U (xiv) (8, 9, 24, 25)

=

N (xxii) (24, 25, 28, 29)

=

V (xv) (9, 11, 13, 15)

=

0 (xxiii) (24, 26, 28, 30)

=

W (xvi) (9, 11, 25, 27)

=

P (xxiv) (24, 25, 26, 27)

=

X (xxv) (19, 23)

=

Y

(xxvi) (14, 30)

= z

Prime Implicants (i) (0, 1, 4, 5) =A

(ii) (0, 1, 8, 9)

=

^B

(iii) (0, 2, 4, 6)

=

0 (iv) (0, 2, 16, 18)

=

D (v) (0, 4, 16, 20)

=

E (vi) (0, 8, 16, 24)

=

F (vii) (1, 5, 9, 13)

=

^G

(viii) (4, 5, 6, 7)

=

H

The prime implicants and the prime implicant table of the function are given below.

20, 21, 23, 24, 25,26, 27,28,29,30)* (1)

A prime implicant table can, in general, be split up into a number of sub-tables corresponding to the division of the minimizing function into a number of sub- functions. This division of the minimizing function can be made in many but finite number of ways. Of all the different possible ways of. splitting a cyclic prime implicant table, we shall consider only those for which each of the sub- tables corresponds to an open connected cover term matrix.· An open connected cover term matrix is an array of only two rows and a number of columns obtained by arranging the cover terms in the minimizing function such that the element ⁱⁿ the (1, i)th position of the array is identical with the element in the [2, (i-l)]th position for i ;;;;:. 2 and the element of its (1, l)th position is not identical with the element in the ^(2, n)th position, n being the number of columns in the matrix. The complete solution of each of the sub-tables is then the complete solution of the respective open connected cover term matrix which can be readily obtained by following the procedure suggested in an earlier communication (Choudhury and Das, 1963, in the press).

To illustrate, we shall consider the following example : . Example:

F(x4, x3, x2, x1, x0)

= ~

(0, 1, 2, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 18, 19,

A New Approach to the Solution of Switching, etc. 33

TABLE I ~ Prime Implicant Table '~

0 2 4 5 6 7 8 9 11 13 14 15 16 18 19 20 21 23 24 ·25 26 27 28 29 30

::i:..

A x x x x

B x x x x ~

a

c

x x x x

;;:i-.

0 ~

D x x

x x R..

;;:i-.

E x x

x x ~

~

F x x x x 'l

~

G x x x x ~

H x x x x -~

""·

.,...

I x x

x x

~

J x x x x ~

K- x x x x

-~.

_~

L x x x x ~

M x x

x

x

b

N x x x . x ~

(/:>

---

0 x x x x

~

p _Q x _x x _x x x ·~ ~

x x

R x x x x x ~

s

_{x ·x x x}

.v.:i

T x -x x x

x x .. x x ^bj

u

x x x x ~ ^v,

v

x x x x ~

w

x

_{x x x x}

y x x

x x

'"L

I • • • (3) The above nine opeq "connected cover term matrices correspond t. th d' · -,

. . . · ·. . o e 1v1s10n of

thfi} pnme implicant 'ta;ble·(Table I) mto rune sub-tables as shown in (4).

(IV) (V) (VI) (VII) (VIII) (IX)

. -- _{- -}

rrx} ^{¥ .. {K}}

¹¹¹

^{~.}

^..

^{~}

^B

^{IL} u}

⁰

- !-. ^L~ _\---

^·-

---

^{- -· --.-·}

^~--

^-

^{l~ .}

·-{i} ^{j}

_...J.

{!HU

_~

^{g\{fl

^{. -}

^{B {~} UH} LS}

^D

=

.{~}

{ E~1}

{~}

. (I)

(II) ·: (III)

- -

-

{t}~K:Y

^{. ']'}

^{~}

^{- { ~ } -{~ } . · 111 z}

^{w {~}{~}p}

. Open connecte:tt·cover ^.terfn matrices

l ' term matrices.

The minimizing function (2) shows that the cover terms (C+D) and (A+B+C

+ n+

^E

+

F)" when illurtiplfocl ·an.cl· reduced according "to the la WS ofBoolean, algebra become (G+D}. Similarly, the ·cover terms .(O+P)-ancl. (B+G+N +O+P+Q) when multiplied .. and .reduced becom~ (O+P) .. -Iri the prime -imp~cant table re- presentation, this is a cas_e of column dominance __ where the cover terms (A+B+O +D+E+F) ancl(B+G+N+O+P+Q) correspond to the dominated columns and hence can be rejected 1;e€ain.ii1g till') cover terms-(Q.+D) ·and (O.+P)-. -·Th~ resulting minimizing function is-then ·-arranged in_~he following nine open connected-cover

.

^.

F~ __

^=::_ (!1.+B±-9.:t:P_+JiJ±P:)iA+B+G)(C+..Q)Vl_+.Q+.E+Ii+.IL - - -

(.Ao+G+H+l+J+K+L)(<f+H+111)(H+J+K+111)(B+:F+N) '-- - ·· (B-FG+N+O+P+.(J)(O+P)(G+J+DtO+Q}(M+Z)(.!+111+0) _{. ..} ~ .

-· - ·- (D+E+1i'+R+-S)1l?=FR+T)(T+ Y)(EfTfS+U)(l+K+L+"U) ..

-- -- --(J(=j= Y)"(F-fl\T +R:.rs+ v

+w

+X)(N+P+Q+ v +X)(R+T+

w+x)

·- - •(P+T+.X)Cs+u+y+W)(L+Q+V+Y)(W+Z) .. :

(2)

function as

From the prime implicant table : (-Table I), we can write the minimizing

. . (4) (IX)

--

2

c

^x

--

D x

--

x x

-x-1--;-

x

1=

'-~

x

x x

x

x x

30 28 (II)

(VI) (VII) (VIII)

4 6 1 8 20 29

,

__ _{--1 -- --}

A

_-- x _-

^A

x _-I

^E

_-- x _--

c _-- x _- x

^B

_-- x x

^I

x

--

^{-- --}

E _--

x _-

^F

_- x

^L

_{-- --}

^x

H

_--

x

_--

x _G

-- x -- ^--

^{Q --}

^-- x

I

-

x

^--

N

- ^- x ^s

^--

x ^--

M

x

---

^u _v

^--

^x

^{-- x} _x

,__,_____

-. -

(III) (IV)

11 26 27 24 25

-·-1- '-x1-1

0

x I

^{F A}

---

x / x

p

_xj_ x

^{N G}

R

I ^x --

^p

x

^H

----

1- ^--

T J

x

^{x Q}

^x

^I

w ^--- -/-x -I

^R

-- ^{x --}

^J

x

1

x x ^s x

^K

--.--1-- --

^--

v _--,-- x ^I x

^L

w _x,_

.M

x x x

----

Q

s

u

v

G J

L M 0

13 14 15

--·--,·-

^x

^I

_x j_x-=J=

-x--

I

----,-

^{x x}

-x

,-1-x -,-

-'---,-

_x l--x-1-

sub-tables

W

---x-,-~

z =-x =j=J x

(V)

5 7

y R

F E

x

D 1

_1_1_

x

I I

x =:_1_1=

_x __

/_l_· ^I_

I. I'

I

x

I

K

-,-,--x ^,-x

. r i= xi=

x I x

I I

s x 1=,==1=

T I x x

I

--1--·---

u __

l

^{x _}

I

^{x x}

--,---,--- ---

19 21 23

18 16

(I)

36 A. K: Choudhury, 'Sunil' Ranjan Das and M. S. Basu

3 cannot occur in the first or the last column position,

3 in any intermediate column position must be preceded by 2 in the column position and followed by 1 in the f ll .

1 ..

o owing co umn pos1t1on, 1 can not occur immediately after 2, and

0 cannot occur in any column positio n.

(iii) (iv) (i) (ii) previous

The irredundant solutions associated with the different sub-tables are the irredundant solutions of their respective open connected cover term matrices.

To obtain the irredundant solutions of the different open connected cover term matrices, first their reduced matrices are obtained such that each of the reduced matrices contain all the prime implicants as contained in the original matrix but none of the prime implicants in each occur more than once. For an open connected cover term matrix with odd number of columns, the reduced matrix is obtained by deleting all the even-numbered columns from the left whereas for an open connected cover term matrix with even number of columns, all the even-numbered columns excepting the rightmost one are deleted and for the rightmost column, the prime implicant (or group of prime implicants for sub-column elements) not appearing in the remaining columns is retained and the others are rejected to obtain the reduced matrix. The different irredunclant solutions associated with each matrix which are certain possible subsets of the set of all the prime implicants of the function present in it are then obtained from the cover conditions of the miuterms included in it and the eliminability conditions of its prime implicants when the other matrices are assumed to be absent. By adopting a decimal mode of representation, these different irredundant solutions can be obtained by filling the column positions of each of these reduced matrices with decimal numbers 0, ^1, 2 and 3, giving clue weight to the eliminability conditions of the prime implicants and the cover conditions of the min terms. While such filling the column positions of the reduced matrices, a "O" below any column position of a reduced matrix will imply the absence of all the prime implicants of the column, a "l"

the presence of the prime implicant (or group of prime implicants) from the lower row, a "2" that of the prime implicant (or group of prime implicants] from the upper row whereas a "3" will imply the presence of the prime implicants from both the rows of the column of the reduced matrix. For an open connected cover term matrix with odd number of columns, restrictions imposed by the elimi.

nability conditions and the cover conditions \~tle filling the column positions of the reduced matrix with 0, 1, 2 and 3 are,

Irredunda;,t Soliitions of the Sub-tables

The minimizing function (2) has also other possible open connected cover term matrices corresponding to the division of the Table I into other different sub-tables.

A new Approach to the Solution of Switching, etc. · 37

'i\Te shall next show how the knowled~e of the irredundant solutions ass·ociated with each of the sub-tables (i.e.,. Wit4. e'arch: of the open .connected cover -", tenu

·_ ··· The purpose of these restrictions, as can be easily understood, is tomaintain the v~lidity of the covers avoiding redundancy.' For an open- connected cover term matrix with even number of columns, these restrictions are the same as above.

excepting that the last column position can befilled with only O or 2 and when 2 occurs in the last column position, only 2 can occur in the immediately preceding column position. . Bearing these restrictions in mind, the column. positions of the different reduced matriees can be filled up in all possible admissible ·ways to.

give the different irredundant solutions. The irredundant solutions associated.

1~th each of the matrices in (3) are obtained ^Ly following the procedure as stated

~bov~ and are given below. . · .

3S'- A. K; Ok~udhury; Sunil Ranjan Das and' M. · S .. Basu

with KT for the full coverage of the matrix. After selection of KT, all these alte~na~e p~ssib~ties of choice are at once evident from the matrix. If from

the _prune nnplicant table for the function as shown in Table I , , 1 t T

. . . , . . , ,, e se ec at the

first stage, without· selecting Y, the essentialitv of K t tl .

• • J l. a ie next step can be

seen, readily. In the prune implicant table method ft . 1 .

. . , a et se ection of KT d

cancelling the columns thus covered we will delet ll an ' e next a the d . ·

and then search if any of the rows or prime ., l' . onunatecl rows

. . . iinp icants 1wcmnes ' -. .

this stage. If none of the prune implicants b ·· ES:sent1al

a.t

econ1es essential ^{t ,} l

, u rec ^UUl" the .the column [~], we can take any one of R, D, E, F or S in conjunction prime implicant ^T makes the prime implicant Kan essential one whereas from The selection of the To start with in finding a minimal solution of the given function, we note that its cover terms (C+D), (O+P), (111 +Z), (T+ Y), (K+ Y) and (W +Z) each consists of only two prime implicants whereas the rest consist of more than two prime implicants. \iVe will begin covering the terms of the function by taking

ra:

prime implicant from any of the above cover terms consisting of two prime impli- cants. The prime implicant we take at the first step ⁱⁿ covering the function may or may not occur in any minimal solution. In general, we shall have to make alternate trials with the other prime implicants of the cover term. So if we start with a cover term consisting of only two prime implicants, we shall have to make the least number of trials in arriving at the ^minimal solution. To begin with, let us consider the cover term (T+ Y). Ifwe start by taking the prime implicant T of this cover term and decide not to take the prime implicant Y, then the different possible solutions of the matrix (I) are KTR, KTD, KTE, KTF and KTS. We will write all the prime implicants associated with KT in these solutions .in a column. Thus all possible solutions of the matrix (I) after Method of Finding One of the M·inimal Solutions

matrices) will help us in finding at least one of the minimal solutions of a given function. For this we shall again take the Example (1) and consider its open connected cover term matrices and their different irredundant solutions.

· A nei~ Approach to the Solution- of Switching, etc.

·39

{~} -

{f}

M

(VI)

(II) (III) (IV)

.111

w -

{ ~} { fv}

^p

{U ^{j}

{~} ^z ft} _LV x{~}

⁰

{XI

~J

have not decided which one should be included for occurrence in a minimal solu- tion. The decision will be made at later stage. The procedure to be followed to arrive at a decision regarding selection of the prime implicant or prime impli- cants from this column for occurrence in minimal solutions will be clear front subsequent discussions. The procedure as suggested corresponds in effect to the method of Column branching as suggested by Pyne and McCluskeJ (1962). We shall now delete the matrix (I) which has been com- pletelJ covered and also other matrices which are thus covered due to selection l · 1 · atri2' of K, T or KT. In the present case we see that due to t 11s se ection, JU

· · d 1 t d I tl · · matrices, (V) becomes completely covered and hence it is e e e . n ¹⁸ remammg . the sub-column elements (or in general, elements) containing either K or T ⁰¹ both are also deleted. The resulting appearances of the matrices are as follows :

selected definitely but regarding the prime implicants from the column [

f ^J

^we

By such a representation we mean that the prime implicants KT have been

rRJ

(6) KT

lf

number of trials in finding the minimal solution, the obvious step here would be to select a prime implicant from a column of the table containing the least number of crosses as basis row and to proceed as above. But in the present method we will make a departure from this procedure and consider all the alternate possibilities of choice for the coverage of terms included in matrix (I) after selection of KT, that is,

40

A. K. Choudhury, Sunil Ranjan Das and M.

S.

Basu.

(a) Row dominance and essential prime implicant

The procedure of searching the prime implicants thus becoming essential after removal of the prime implicants which cover sets of terms forming p_roper subsets of the sets of terms covered by other prime implicants is discussed below.

Let there be a prime implicant Pi which occurs in one or more than one of the remaining matrices. Then for each of these matrices there will be some solu- tions which include Pi. For example, we may consider the prime implicant R which occurs in (III) and (IV) of the reduced matrices in (7). There is at least one solution of each of the matrices in which R occurs. Let there be another prime implicant pj such that in all the solutions of the different matrices con- taining Pi, Pi can be replaced by P; without impairing the solutions (redundant or iiredundant); in addition, let P; also occur in the solutions of some other matrices.

Then the set of terms covered by the prime implicant P, will form a proper subset of the set of terms covered by the prime implicant P;. In the present example, the prime implicant W occurs in the matrices (IT), (III) and (IV). The solutions of the matrices (III) and (IV) with R as one of the prime implicants are respec- tively RP and R [ ~] whereas with W are respectively WP and W [ ~) . In

addition, W occurs in some of the solutions of the matrix (II). Hence we conclude that the set of terms covered by the prime implicant R forms a proper subset of the set of terms covered by the prime implicant W. If P; occurs only in the·

matrices in which P, occurs and the solutions remain valid when Pi is substituted for P;, then the set of terms covered by Pi forms an improper subset of that covered by P;, i.e., both of them cover identical set of terms. The conclitions which p.

and P; must satisfy such that the set of terms covered by p. forms a '

i c proper or improper subset of that covered by P;, are :

(i) In ·an the reduced matrices derived from the ope · t l .

. . n connec ec cover

term matrices with odd number of columns in which the .: ·

. . 1)11111e nnp 1. ieant p.

occurs,1tmustappearrnthe(l,l)thorthe(2,ni)thr)osition

1 b · tl '

' n emg 1e n1u11ber of

6

Now we shallssoan the above matrices to see whether any of the prime impli- cants in them becomes essential after deleting a prime implicant (or a group of prime implicants) covering a set of terms forming a proper· subset of the set of terms covered by one single prime implicant. This is equivalent to observing row dominance in the prime implicant table method.

A new A ^pproach. to the Solution of Switching,

etc.

·41

(VIT) (VITI) (IX)

r~B) ^{{~} {~} {1} a}

⁽⁷⁾

u

^D

[ RJ

^{D ·}

^ne

(b) Selection of prime implicant from the column E

J

or occurrence in

°

.of the minimal solutions ~

We shall make a search of the remaining matrices at this stage to see if soJ'.)le of the prime implicants amongst R, D, E, F and S included in the selected coluJJ1~

in (6) are absent in them; those prime implicants of the nolnmn which will be abse~

in the matrices will then be all deleted from the column. Such a search revea ⁸ that of the prime implicants R D E F and S only the prime implicant D does

' ' ' ' ·s

:::e~:::m~h~~ol:: '[ei"Jim:6:•~::e:cM:e::: ,::: ::::::::i:::.t• •

¹

s ..

. t ge the set· of terms covered b h . .

K'fCJJ

rhis s a ' Y t e corubmation of prime implicants

columns ⁱⁿ the reduced matrices. In case the reduced matrices are obtained from the open connected cover term matrices with even number of columns, Pi must occur either in the (1, l)th or the (1, m)th position.

(ii) Whenever Pi occurs ~i~ the (l,'l)th position in the reduced matrices, 1\must occur in the (2, l)th position. .

(iii) If in the reduced matrices obtained from the open connected cover term matrices with odd number of columns, Pi occurs in the (2, m)th position, P; must occur in the (1, m)th position. If in the reduced matrices obtained from 'the open connected cover term matrices with even number of columns, pi 'occurs 'in the (1, m)th position, P; must occur in the [2, (m-l)]th position.

If, in addition, the prime implicant P¹ is. to be essential, after deleting the prime implicant Pi, then there must not be any other prime implicant other than Pi in those positions of the matrices.

From an observation of the reduced matrices in (7), we see that in the matrix (IX), the prime implicants D and G appear; of these D only occurs in the matrix (IX) 'whereas 0 also occurs in the matrix (VI). Hence the set of terms covered by D forms a proper subset of the set of terms covered by C'. After cancellation of the prime implicant D, the prime implicant 0 becomes essential. At this stage we cannot say definitely whether we will have to proceed along the branch KTC or along the branch KTD to obtain solutions with miniiuulll number of prime implicants in associotion with KT. We shall have to proceed with C and also with D. We will show how the selection will be made in the .subsequent stages if we first include C in the list of selected prilll⁰ implicants. The matrices (VI) and (IX) are thus completely covered and ·⁸⁰ they are deleted. In the remaining matrices, the sub-column elements containing 0 (if there be any) are also deleted.

42 A. _K .. ?houdhury, Sunil Ranjan Da~ and M. S. Basu

We shall now search if any of the prime implicants of tl b .

. . . ie a ove matrices

(9) becomes essential or any of the pnme implicants from tl ., l

ie se ected column can be deleted. But search reveals no such possibilit,

II

3 . ence we have to

(II) (IV) (VII) (VIII)

{U

¹¹¹

^w {U ^{{~} {~} {~}} U} r' ^~j

^{... (9)}

{~} _{z {~}} {~}

^B

^u

Amongst the remaining matrices search is again made to see~ whether any of the prime implicants in them becomes essential. But we can see that such ^1:J.

situation does not occur here. At this stage, of the existing matrices, we shall consider any one and include in our selected set of prime implicants all the possibi- lities of its coverage. Taking the matrix (III), for instance, we see that since the prime implicant ^T of it has already been included in our selection so far made, we shall include the combination [~

J

for the coverage of the remaining terms of the matrix (Ill), because either of ⁰ and ^P in conjunction with ^T will completely cover the matrix. By deleting the matrix (Ill) which becomes covered, we get the following uncovered matrices :

(c) · Repeated. appli~ation of the selection. procedure as outlined in (a) a,J,a, (b) above:

I '

e

(II) (III) ^(IV) (VII) (VIII)

I

{~}

^~

^w1

^-;

^{~}

^p

{i} ^{{~} {~} {~} {~} {~}}

rs} rx} ^·u

{~} z l~·

^{x {~} 0}

^{~ v} LN

^B

(8)

forms a proper subset of the set of terms covered by either of the combinations · KTCR KTCE KTCF or KTCS. The matrices still remaining uncovered are : .

' '

·A new App;oach to the .Sol~tio~ 'of Switching,· etc: - • 43

(l_Z~

[fl

.

^·.,

r-: .. •.. .

· h · · 1· t Ed t · ln any oft 'existing We now see that t e pnme imp roan oes no appear ^{1 ,}

[

~F¹

J

^{in (10). _.A_ ft~.r}

matrices, and so its presence is deleted from the column

; : s

r» \ t "' oa

\:. I . • t . i•

this, all tµe alternate possibilities of covering the matrix (IV) are taken into cous · deration tn~ written in a column in the list of selected prime implicants as sho'Yll below:

-

(IV) (VII) (VIII)

xH} _LW ^{{j} {i} {tr {n Vj {~}}

(11)

rl

^Nj

^{v ~}

^B

^u

w

(II)

in· the list of prime implicants selected for one of the minimal solutions so far, there .ocour prime implicants REFS in one of the columns. Also the prime · implicant E in the matrices ⁽⁹⁾ covers a set of terms which form a proper subset of the set of terms covered by S. Hence the prime implicant E in the sub-column

element [~] in matrix (VIII) and the 'uh-column element

[i J

^{of matrix}

(IV) are deleted. The appearance of the matrices at this stage becomes : (10)

KTG [

n

t~st all the branches at this stage. The prime implicants selected for one of the -.

minimal solutions upto this stage for one of the branches are :

44 _A. K. Choudhury, Sunil Ranjan Das and M. S. Basu

(II) (VIII)

{~}

^M

^w r'

^.Q

^{VJ r { ~}}

{

^~

}- ^z

{n ^u

⁽¹⁵⁾

c ,

Searching amongst these remaining matrices we see that the set of terms coyered"by either F'oi· Nat this stage forms

a

proper subset of the set of terms covered by B. If we delete F and N in matrix (VII), then B becomes an essential prime implicant. Weselect Band delete the matrix (VII) which becomes covered The following 1~atrices r~main unc~vered ~t this··stage. . .

(II) (VII) (VIII)

{~

^..

}·

^{M .W}

^{{ ~·} ·{ ~}} _{t_i} IL} {~}

rs}

^{. (14'.)}

{~} ^z

^B

^u

l~

The matrices still remaining ur~covered are given below :

0 (13)

KTOm [:

rnJ J

( .

The matrix (IV) '~Ill.ch is fully covered is now deleted and the appearances of those prime implicants which do not occur in any of -the remaining matrices

ale

.<1,,

d;leted from the columns

m , [ ~ ]

^~nd

[!]

^{in (12). Since the}

prime implicants ^R and ^X do not appear in any matrix, they are deleted. Re- garding theprime implicant P which is also absent in the remaining matrices, we cannot come

to

any conclusion whether it is· to be deleted or not because ^if Pi.s retained and included in. the selected set of prime implicants, we can get the coverage or the terms so far made with lesser number of prime implicants tha.n tli:i,t ..

whichis 'obtaiiied by deleting P and including 0. So, for the present, we keep both these possibilities and our selection takes the form

·' .A. new Approach to the ·Solution of Switching, etc. . 45

But if we consider the selected set of prime implicants containing P instead of 0,

we have to include one of the prime implicants amongst [

! J

^for the co.er·

age of the matrix (VIII) and at least two prime implicants for covering tl~e matrix: (II). ~he total number of prime implicants required being greater ¹¹¹ this case than m the former, we need not consider this solution.

At this .stage, we ~annot say definitely whether the solutions we have arrived

. roirumal solutions of th f to

at are . h h . e unction. To say definitely we shall have k trials with t e ot er prime :im. li . . I'

ma e P cant. Beginning with other prime rmP ^1•

t we see that none of the sol t· .

can s, u ions contains lesser number of prune

(18)

KTCSBO [~] Z

At this stage we see that if we include Z in the list of selected prime impli- cants, matrix (II) becomes covered. Hence matrix (II) is also deleted. The prine implicants reauired for the coverage are hence :

(II) (GI 1.1

w

l Lr _Qj

_{.. . (17)}

rs 1

x{~} _z i.u _VJ ^x

Since we have selected S and also [ ~ ] in the selected set of prime impli- cants ·containing 0, the matrix (VIII) becomes covered if we take 0. The matrix (VIII) and the sub-column elements of the remaining matrix containing S or O are deleted. The appearance of the remaining matrix, after this, is as follows :

... (16) Kj;GSB

I

The prime implicants F and N do not appear anywhere in the above matrices.

So they are deleted from (13) and the selection becomes :

46'

A. K~ Choudhury, Sunil Ranjan Das and M. S. Basu

Aiken, n, H., 1951, Annals of the Computation Laboratory of Harvard University, XXVII.

Choudhw·y, A. IC and Basu, M. S., 1962, Indian Jo'Urnal of Physics, 36, l; 1962, Tmns.

Inst. Radio Engrs., N. Y., E0-11, 713.

Choudhury, A. K. and Das, S. R., 1963, Trans. Inst. E. E. Eng1·s., N. Y. (In Press).

Caldwell, S. H., 1958, Switching Ourcuits and Logical Design, John Wiley and Sons, Inc., New York, 156.

De Troye, N. C., 1959, Philips Res. Rep., 14.

Ghazala, M. J., 1957, I.B.M. Journal. of Research mid Development, 1, 171.

Hall, F. B., 1962, Trans. A.I.E.E., Part I (Oommunication and Electronics), 58, 709.

Karnaugh, M., 1953, Trans. A.J.E.E., Part I (Oom1mmication and Electronics), 72, 593.

Mott, T. H. (Jr.), 1961, Trans. Inst. Radio Eng·rs., N. Y., E0-9, 245.

McCluskey, E. J. (Jr.), 1956, Bell System Technical Journal; 35, 1417.

Mukhopadhyay, A., 1962, Doctoral Thesis to the University of Calcutta.

Mukherjee, T. and Sarkar, P., 1963, Electronics ancl Control, 14, 563.

Petrick, S. R., 1956, Air Force Cambridge Research Center, Report No. AFCRC-TR.56.

llO; 1959, Proceedings of the International Conference on T.1f .1 t' p .

.u or na ion rocessmg

March (UNESCO Publication). '

Pyne, I. B. and McCluskey, E. J. (Jr.), 1961 Journal of ti S · j . Applied Mathematics, 9, 604. 1962 Tra~s In t R d' ieE ociet.y or lndiistriril and

. . ' ' . s. a io 'ngrs., N.Y., EC-11

Quine, V•l. V., 1952, American Mathematical 1VIonthly 59 591 1 __ ' 473.

• • ~ · 900 Ame · i\

matical Mont.lily, 62, 627. ' ' ncan Ha.the-

REFERENCES

The authors take this opportunity to express their indebtedness td' Prof.

J. N. Bhar, D.Sc., F.N.I., M.Brit. I.R.E., for his guidance and interest in the work. One of the authors, Shri Das, also thankfully acknowledges the award of a Senior Research Fellowship by the Council of Scientific and Industrial Research, Government of India.

ACKNOWLEDGMENT CONCLUSIONS

A method has been presented for finding one of the minimaJI solutions to a cyclic prime implicant table. For this, the cyclic table has been broken up into a number of sub-tables such that each of the sub-tables corresponds to an open connected cover term matrix. All the irredundant solutions associated with each of the matrices or sub-tables are found out easily. The lmowledge of these dif- ferent irredundant solutions renders possible selection of the prime implicants at

-every step of the process ensuring minimality and with very little trial procedure.

Adoption of this technique not only reduces the total number of trials but also helps making trials at a much faster rate.

implicants than that in (18). Hence the solutions obtained in (18) are minimal solutions.

A

new. Approach to the Solution of Switching, etc. A7

48 A . K . Ghofudhuryf Sunil Banjan Das and M, 8. Basu J- P-) 1957, Proceedings of the International Symposiuin on tho Tbsory

^of

Swit*

ohing, Part I, in the Annals of the Computation Laboratory of Harvard University, XXIX, 57.

Svoboda, A., 1967, Ibid,, 293.

Seheinman, A. H., 1962, Bell System Technicd Journal, 41, 1337.

Urbano, K. H. and Mueller, R. K., 1956, Trans. Inst. Radio Ertgrs., N . Y ., EC-b, 126.

Veitch, E. W., 1952, Proceedings of the Association for Computing M achinery, Pittsburgh,

127.