Ei, LI.i EEiNG.RESEiRC:i i4L iT'ld WE UlliVER~-iTlY OF -)iC'1IIGP] COOTiPLETE DECODING NETS: GENlERAL THEORY AiND ~ilINIi~i1ALITY By ARTHUR W. BURKS ROBERT McNAU UHTON CARL~ H. POLLN1iAiR DO&N W o W i'ARREiN JESSE B3, WRiGIHT Project 1828 BURROUGHS RESEARCH CEINTER PAOLI, PENN SYLVANIA 15 July 1954

;? g A \ /

ii, TABiJ!;J Oii' CO0F-IT'ITS Page 1i Introduction 1 2. The Net Language 4 3o Complete Decoding Nets 11 4. Multiplicative Switch Nets 17 5 ~IinimaClity 25 6. The Equation Language 33 7, A Proof of the Minimality Theorem 41 7.1. Some Basic Concepts 42 7,~2 Quasi Balanced M.S. Nets 50 7o3, Proof of the Main Theorem 62 Footnotes 77 Appendix 1 81 Appendix 2 82

1. Introduction0 A dital comut circuit is a physical device with'- input ansd output wires aild which functions as followso At any momnent of time each wire assumes one of a finite number of discrete states. Mloreover, the state of the output wires is determined by the past history of the states of the input wires0 A telephone exchange, a digital electronic computing machine and probably the human nervous system are all digital computing circuits~ Fior reasons of simplicity we will consider only digital computing circuits in which every wile has one of two states- i e, is either activated or not activated0 We will be coicerned in this paper exclusively with digital computing circuits without memory or useful internal delays0 Specifically, we w dill deal with com.plete decoding circuits0 Such a circuit may be roughly char, Ccterized as follows. Its inp)ut wires may be partitioned into two or more sets ecch consisting of one or more wireso Moreover, it is such that when exactly one wire of each input set is activated exactly one of the final output wires is activated, and no two different ways of activating exactly one wire of each input set cause the same

2. final output wire to be activated. The present paper falls into two parts. In the first part (consisting of the following five sections) we will define precisely three important kinds of complete decoding circuits (exponential switch circuits, tree circuits, and balanced multiplicative switch circuits) and study their interrelations. In the second part (consisting of the last section) we will establish a minimality result concerning complete decoding circuits which may be approximately stated as follows: on certain assumptions concerning the relative costs of different kinds of components, the balanced multiplicative switch circuit is the most economical type of complete decoding circuit. Some of the ideas of this paper are already employed by computer engineers; what we have done is to extend, systematize, and make rigorous what is already known in this field. We will treat the subject matter of complete decoding circuits rigorously by using the methods of symbolic logic. This is done as follows. A digital computing circuit may be (and often is) represented by a diagram or net which gives the logical structure of the circuit in abstraction from many physical features of the circuit that are not relevant to this logical structure (e.g.,

actual voltage levels, certain time delays)o These diagrams may be regarded as symbols irl a non-linear language, this lalguage cacn be formalized in somewhat the same manner as the languages of symbolic logic. and then theorems can be proved about this formal languageo This was done in a previous paper,2 and in the present paper we will use these results to define preciselyq and to prove various theorems about, complete decoding circuits. Since certain modifications need to be made in cur earlier theory of logical nets to make it most convenient for the probleml at l>hand (in particular, we do not need cielay ele-iments in the present paper) and, since we desire that the present paper be independent of the earlier one, we will construct tihe theory anewv

40 2. The net language. The basic symbols of our formal net language consist of brackets of various sizes, the truth constants "0" aid "1'l, and an infinite number of primitive elements. Each element consists of an enclosure or nucleus containing a function symbol representing a twovalued truth-functional logical operation of M_ arguments, Mi inwardly directed line segments or input wires, and a single outwardly directed line segment or output wire.. —Some examples are: the two-input alternation ("or") element (Fig. la), the three-input conjunction ("and") element (Fig. lb), the stroke element (Fig. lc), the negation ("not") element (Fig. ld), the material implication ("if-then") element (Fig. le), where "A_", "K"t, "St"1 "Nt", and G"C" represent alternation, conjunction, the stroke function, negation, and material implication respectively.3 (a) _ (b) (d) --- (e) Fi I Fig. 1

5o The reader may find it strange to consider this system of diagrams a language. For (1) he usually thinks of a language as treating linearly arranged entities: letters are strung together to form words, words to form sentences, etc., all in one direction. And (2) he usually thinks of a language as a vehicle for expressing complete thoughts in sentenceso Clearly neither of these is the case in our net ianguageo To justify the use of the word tilanguaget" we note that as explained below the diagrams do represent objects in the same sense that some words of ordinary language (like "cat"t, "moont", etco) represent objects. We also note that, although a diagram does not literally make any assertion, in effect it can tell us much about the circuit which it represents; for example, whether two wires are joined together. Also, engineers do use such diagrams to communicate with each other~ The linear language introduced in Section 6 is more like ordinary language in all these respects0 The elements of our formal net language represent electronic, relay, or neural devices that perform the functions indicated by the symbols of the nuclei0 Circuits constructed from these devices may be represented by symbols compounded out of the elements, as in Figo 2o

6. Fig. 2 Such a diagram as that of Fig. 2 is called a "plain net"; the reason for the qualification "plain" will become apparent in a moment. In some applications, such as decoding (see the next section), the inputs of a circuit are operated in groups. To represent digital computing circuits used in this way we use diagrams called "partitioned nets." The diagram of Fig. 3 is a partitioned net and represents a complete decoding circuit with two pairs of inputs and four outputs. I I F. -3gI Fig. 3

o70 Both plain nets and partitioned nets are called "nets tt" It is sometimes useful to symbolize not merely a digital computing circuit but that circuit in a particular state. We do this by means of diagrams called "net states" which are derived from nets by labeling each junction with the truth constant ("t" or Tltt); "Ot" indicates that the junction labeled is inactive, t"l" that it is active. Fig. 4 is a net state of Fig, 3, and represents a complete decoding circuit with one input from each pair activated and one output activated. o 1 1 O O 0 1 0 Fig. 4 We proceed now to define formally the concepts of plain net, partitioned net, and net; the concept of net state will be defined formally in the next section. A plain net consists of elements (possibly one) and a finite number of points called junctions, such that the at least one every junction is on ct.: outer end of fa wire of some element, and such that the outer end of any wire of

8o any element is on at least one junction~ If there is no arrowhead at a junction, it is an input junction; otherwise, it is an output junction. An output junction to which only one wire is connected is a final outut unction A partitioned net is a plain net plus a bracketing of all input junctions into two or more disjoint sets (called bracketed sets). A b-d net is a partitioned net with bracketed sets each of which contains b junctions. A net is either a plain net or a partitioned net. The definitions of "junction", "input junction", "output junction", and t"final output junction" are extended in the obvious way to cover partitioned nets as well as plain nets. are Not all nets; physically realizableo is therein Fig. 5aAEE not, for example, for the conjunction elementA represents a component whose input and output wires are in the same state while the negation element represents a component whose input and output wires are in opposite stateso (a) F. 5 (b)

We will next define a certain class of nets, called "well-formed nets" ("w.fn,") which will exclude these as well as other kinds of nets we are not interested in here, and which is sufficiently large to. include representations of almost all digital computing circuits without delays.4 To define this class precisely we need the following notions, Any junction which is common to two or more output wires is a multiple unction A junction o< directly drives a junction?3 if and only if there is an element such that Or is on an input wire and,3 is on the output wire of this element, O( drives (' if and only if there exists a sequence c<l, 1~,CxI such that O 1 is OC, OC is K5, and O( directly drives cO each i1such that 1 i4l forAl i I. Note that the driving relation is transitive: if O< drives (3 and (3 drives Lf then Oc drives.o A cycle is a sequence of junctions <, oo ~9 a1-1 such that Ci Mod I directly drives C(i l)Xod I' i.e., such that each junction of the cycle directly drives the next junction of the cycle, We can now define: a net N is well-formed (w.fo) if and only if N has (1) no multiple junctions and (2) no cycleso The nets of Figs, 1, 2, 3, and 4 are wofono, while the nets of Fig, 5 are not wofono We will often be concerned with the following

Note For page 10 refer to file copy.

11o iZ eComplete decoding nets. A function that digital computing circuits are often constructed to perform is that of code conversion0 We will make a few remarks about code conversion in general as a background for our discussion of complete decoding circuits. The heart of the process of code conversion is a character by character translation or transliteration, based on a unique assignment of a character of the second code to each character of the first code~ Transliterations are realized by circuits which will translate or convert any arbitrary character (sequence of digits) of the first code into the corresponding character of the second code0 The code conversion of a complete message will then consist of a sequence of these character conversions plus, perhaps, other minor operations. A standard procedure for converting a character from one code to another is first to decode and then to encodeo We will illustrate this process with a conversion from one six-bit code to another. Suppose a six-bit character is represented on six input junctions going to a polarizing circuit whose output consists of six pairs of junctions, exactly one junction of each pair being activatedo These six pairs ofi junctions are inputs to a complete decoding circuit with

12 o sixty-four outputs, of which exactly one is activated9 and such that for two different ways of activating exactly one junction of each input pair two diff"erent output junctions are activatedo These sixty-four junctions in turn become the inputs to an encoding circuit with six output junctions on which are represented the converted ch-laracters o This example makes clear the role of a complete decoding circuit in the general process of' code conversion0 This is only one way of making a code conversion, of course9 and there may be other more direct nld efficient ways, depending on the circumstances, the equipment available, etc. But this particular technique lias certain advantageso The complete decoding circuit may be constructed entirely of conjunction elements (and lhence may be represented by a wifcon.) connected in any one of a numnber of systematic ways, and the encoding circuit can be constructed entirely of alternation elements (anld hence may be represented by a w f.a.n ) connected in a systematic way0 Complete decoding circuits are also of interest in their own right9 for in many instances a decoding is needed without a subsequent encoding0 It is evident from the preceding example tlihat complete decoding involves the use of a circuit in a certain way: the input wires are partitioned into subsets and exactly one wire of each subset is activated~ Circuits

13o used in this way are represented by partitioned nets; the partitioning of the input junctions of the partitioned net represents the partitioning of the input wires of the circuit. Thus the complete decoding circuit of the preceding example may be represented by a partitioned net with six bracketed sets of two junctions each. Only partitioned nets with bracketed sets of two junctions each are needed for code conversion of the type just illustrated, but we allow bracketed sets with any number of junctions in the interest of greater generality. The various states which a complete decoding circuit has when operated in this way may be symbolized by what we called "net states," We will now formally define this concept, for plain nets as well as for partitioned nets, so we may be able to symbolize the states of circuits represented by plain nets and by partitioned nets A net state (n.s.) of a w fno N is the net N plus truth constants inserted according to the following rules(la) If N is a plain net, label the input junctions of N arbitrarily with the truth constants,tO,, and "tl"T (lb) If Ni is a partitioned net, label exactly one input of each bracketed set with the truth-constant "1" a-and label all other input junctions with the truth-constant tO""o1 (2) Repeat as many times as possible the following operation:

14o Find an element of N all of whose input wires are joined to labeled junctions. Let these labels be CXl( ooo0 O<Ml respectively, counterclockwise from the output wire of the element, and let the function symbol contained in the nucleus of the element be (3i, Label the junction to which the output wire of the element is joined with C, where The definition of "julictiont, "tinput junction"' "output junction", and tfinal output junction" are extended in the obvious way to cover nos. as well as nets. It is worth noting that we have defined no s only for wofono, and that an application of the rules of the above definition to a wfno will result in a diagram in which every junction is labeled with exactly one truth-constant 5 We can now define precisely the kind of symbol of our net language which represents a complete decoding circuit0 N is a commplete decoding net if and only if N is a wofo partitioned net such that for every nos IN of N there exists a junction (called a decodin Junction) of N which is labeled 1 in Nt and in no other nos. of N6 Figo 3 is a complete decoding net, The kind of complete decoding circuit described at the beginning of this section has the special property that the

150 sets into which its input wires are partitioned have the same number of elements. Complete decoding circuits of this special kind are represented by L-d decoding nets, defined as follows. IN is a b-d decoding net if acnd only if N is a complete decoding net which is a b-d net. Fig. 3 is a 2-2 decoding net. Let N be a b-d decoding net and let K be a set of junctions of N_ obtained by selecting for each n.s. N of N exactly one decoding junction which is labeled The set 1 in N'. ~ K since any has bd d has bd elements,=;h~_ there are b nos. off A b-d ~Fa.~rc: net. Each of these n.so can be represented by a d-digit base-b number, of which the i th digit tells which of the b junctions of the itth bracketed set is activated. This shows the relation of a b-d decoding net to a type of code conversion more general than that of the example given earlier in this section. We are usually interested in b-d decoding nets in which the elements of K are all the final output junctions of the net. However, we do not require that the elements of K be final output junctions nor that a b-d. decoding net have exactly bd final output junctions, We thus broaden the scope of some of our theorems without complicating their proofs, One could also allow for extra

16. input junctions, but here the complexity introduced does not seem warranted by the gain in generality.

17v &0 Multiplicative switch nets. We will study three different species of complete decoding circuits (exponential switch circuits, tree circuits, and balanced multiplicative switch circuits) that are in common use. These turn out on careful analysis to belong to the same genus, that of multiplicative switch circuitso In this section we will define precisely a class of nets (called nmultiplicative switch nets") which represent circuits of this genus and then define classes of nets (called "exponential switches" "ttrees" and "balanced multiplicative switch nets", respectively) representing these three species of this genus in such a way as to bring out their interrelations. compounds Luitiplicative switch nets areA -_ of multiplicative switches, so we will define this concept first The il, i 2 ooo, id multyip icaOtive swityh (mOS) is the partitioned net consisting of (1) -1 + i2 + ooo + id input junctions, bracketed into d sets of il e o, 1id members respectively; (2) il i2 ~ id output junctions; (3) i o i2 ~.. - id elements, each of which is a d-input conjunction,

180 The AdA connection of the wires of the elements to the junctions can be described as follows: (4) By "representative set", we mean a set of d input junctions, one from each bracketed set; there are i I o oo - id representative sets. Each representative set is the set of input junctions on the input wires of exactly one elementO (5) Every output junction is on the output wire of exactly one elemento7 Note that an moso is a wofocono and also a complete decoding neto Fig. 3 is an moso, as is also Fig. 6ao I.... i i (a) (b) Fig~ 6 The structure of the moso of Figo 6a is more clearly a modification. shown in Fig. 6b. Fig0 6b is =: of Figo 6a. modify We will hereafter -Oif m s0 in a similar way when it is convenient to do so0 u"an s net Roughly, anA..z —. is composed of m so

190 mn0 s0 net (m s n.) lMore precisely,A is defined recursively as follows: (1) An m.s. is an m0s0n. (2) Assume 1 and N2 are disjoint msOnO with rl co rJP the final output junctions of N and 1' ~J A1., A a bracketed set of N2 Then the result of dropping the bracket around A1 9 O A and joi.ning (ie,'identifying) r to A6 F' 00 to A is an m s,,no J Fig. 7 is an m s~n. composed of two m.s. II f K.16~~~~ Fig0 7 An.m.s~no is a complete decoding net and hence an m.sono with d bracketed sets of b junctions each is a b-d decoding net, An m ss, n is a wof ocono It is obvious that an mos,,n has sufficient regularity of structure to permit abbreviation of it. An m s0 may be abbreviated by a single symbol as follows0

20 An i1 ooo, id m.s. symbol consists of a box with d input cables labeled l, 0, id and a single output cable labeled il ~ ido It abbreviates an il,., id m.So Thus Figo 8 abbreviates Fig. 3. 2 Fig8 8 Fig. 9 abbreviates Fig. 6o 2 6 Fig. 9 An ms, net diagram is defined recursively as follows: (1) An m.so s ymbol is an m. s. net diagram. An input (output) cable of tihe mos, symbol is a net input (outt) cable. (2) If M1 is an mo so net diagram with a net output cable labeled x and 2 is an mO s net diagram with a net input cable labeled x, the result of joining the two cables is an mos. net diagramo An input (output) cable of any m.s, symbol is a net input (output) cable if and only

21 if it is not joined to the output (input) cable of another moso symbolo For example, in Fig. 10 below there are three input cables each labeled 2, and two output cables one labeled 4, the other 8o It is clear that every moson0 is abbreviated by exactly one m0so net diagram and that every mos. net diagram abbreviates exactly one moSono Thus Fig0 10 abbreviates Fig0 7. 2 2 Fig. 10 A b-d m s net diaram is an mo so net diagram having d net input cables each labeled bo We are now' prepared to define exponertial switches, trees, and balanced multiplicative switch nets in terms of m sono In what follows we shall not always make a clear distinction between the m0s.n. and the 0. so net dia gram A b-d exponential switch is an mQs. symbol with d input cables each labeled b or a net which is abbreviated by such0 Fig0 3 is a 2-2 exponential switch

22 0 while Fig. 11 is a 3-5 exponential switch. 3.243 Fig. 11 The bd tree is the m.s, net diagram (or the net abbreviated by it) composed of a b,b mos. symbol, a b 2,b m.s. symbol, o, and a bd-l,b m.s. symbol; these d-l m.s. symbols are connected in the following way: for every i, i 1,..., d-29 the output cable having the same label of the bj b m.'s, symbol is joined to the input cableA of the b+l,b m.s0 symbol. Fig. 10 is a 2-3 tree while Fig. 12 is a 3-5 tree, i' 9 I- 127 2? ~w243 3 -3 3 3 Fig. 12 It should. be noted that the kind of tree defined here is the so-called standard tree as contrasted to a folded tree. A folded tree, while composed of mos., is not uan mo sOn.8

23 We now define nb-d balanced mrs.nt" To do so, we make use of the commonly used notation n C[x ", which means the integral part of x, ioe., the greatest integer not greater than x. The b-d balanced m.s.n. is the m.so net diagram (or the net which it abbreviates) which can be constructed as follows: (1) A b [d/23 b _[d+ /2 im.s. symbol is drawn. (2) The following step is iterated until all net input cables are labeled b: where there is an input cable labeled bX, a b m.s. symbol is drawn, its output cable joined to that input cable09 256!6~ 16 22 22 22 2 2 Fig. 13 Fig, 13 is a 2-8 balanced m.son while Fig, 14 is a 3-5 balanced m.s.no It should be noted that for each b and d there is a unique balanced m,sono

24. 243 27 9 3 3~ ~3 Fig. 14 b-d exponential switches, b-d trees, and b-d balanced m.s.no are all b-d decoding nets, and hence they all represent complete decoding circuits. (Thus Figs. 11, 12, and 14 are all 3-5 decoding nets.) These three kinds of b-d decoding nets are of particular interest because of the regularity and simplicity of their structure.

note: for page 25 refer to file copy

260 practical engineering skill and judgment0 There are nevertheless problems of pure logic capable of precise formulation and of rigorous solution which h'lave an important practical bearing on these engineering problems~ We will formulate and partially solve one such class of problems, The element-input count of a net N is the number of (element) input wires of NI, ieo,, the number of input wires of each element summed over all the elements of N, A net N is minimal in a given class of nets if and only if the element-input count of N is as small as the element-input count of every other net of that classo The minimality problems we are interested in are those of the form: For any class of b-d decoding nets, to find a net minimal in this class0 For the most part, this problem is quite trivial in any case where b = 1o For the remainder of this paper, therefore, we shall consider only cases in which b 7l l We will make a few remarks to indicate the bearing of these theoretical nminimality problems on practical circuit design0 Certainly one factor in the cost of a complete decoding circuit is measured by the elementinput count of the corresponding net0 In some instances

27~ this is a dominating factor. For example, for a circuit constructed out of crystal rectifiers connected to form logical conjunctions, the element-input count is equal to the number of rectifiers.10 Further, in this case two cost factors which are difficult to compare need not be compared, for, as vwe shall shovws later, the b-d decoding net minimal in the class of b-d decoding woef.cn is very uniform and simple in structure, and there is no probleilm of comparing it with a slightly more uniform net having a few more elements~ We will consider now the element-input counts of our three fundamental kinds of m.seno Let C (bd), CT(b, d), CB(bd) be the element-input counts of b-d exponential switches, b-d trees, and b-d balanced m s n., respectively. These functions are defined only for _bd natural numbers 2 (1) CE(_b, d) - dbd 2bdl 2b2 (2) CT(bd) 2b - 2 We know of no exact, simple formula for CB(b,d), but (3) is a simple recursive formula (derived from thle rules of construction for a b-d balanced m s on) giving the values of this function; (3!) is a non-recursive

28. formula for the case- where d 2k (3) CB(b,2) -b2 C (b 3) 2b3 + 2b2 C (b) - 2 + (b, d/2] ) C (b, 1(d+4-/2J ) (d BcB Bintegral where' |x] t means Ithe rtsaa. part of xl as before. (3) C (b,2k) 22' 2k-jb2j -B jjl The following minimality results may be established by algebraic and inductive proofs from these formulas~ For d = 2 and for d - 3, b = 2: CT(b,d) C CE(bd) In the first case (d 2) this equality holds because a b-2 tree is a b-2 exponential switch. For other values of bd (ioeo, for d - 3 and b * 2, and for d 3) (b,) < CE(b, d) o For _d 2,3 CB(bd) - C(bd) because a b-2 balanced mos.no is a b-2 tree and a b-3 balanced m~son. is a b-3 tree. For other values of d (d 4), CB(_b,d) CT(b,d) o We can summarize: these results by saying that a b-d balanced m0son, is as small (in the sense of having as small an element-input count) as a b-d tree, and in general is smaller, and a b-d tree is as small as a b-d exponential switch, and in general is smaller0 The actual element-input count for each kind of net for b,d - 5 is given in the following tableso We have stopped the development of the table for CT(b,d) as soon as the values become larger than those of _C(b,d), and similarly for C(b,d) with respect to CT(b

29. Values of C d b 2 3 2 8 24 48 96 3 18 72 198 576 4 32 160 576 2240 5 50 300 1350 6600 Table 1 Values of CT(bd) cd b E 2 1 4; 5 2 8 24 56 3 18 72 234 4 32 160 672 5 50 300 Table 2 Values of CE(b,d) b 2 3 2 8 24 64 3 18 81 4 32 5 50 Table 3

30o Though we know of no exact, non-recursive formula for CB(bd), it follows from the results of the preceding paragraph that (4) bCBd' 2 b 2b- for _ 2,3 Approximate information concerning CB(bd) for larger values of d (d > 3) may be gained from the following formulas~ An upper bound on CB(b,_d) may be found by replacing the two subnets driving the final m0s of a b-d balanced mtsono by a b-Ld/27 tree and a b-L(d-l)/23 tree Hence d Ld/ 2 [d-l)/] (5) CB ( _ 2 b + b2-1 b b -2 b-1' for d > 30 A lower bound on C (bmd) may be found by deleting all of the b-d balanced mos nS except the final three mos Hence (6) cB(b,d) 2bd + 2(b Ed/2] b (dfl)/2) for d 3 An approximate formula for CB(b,d) useful for d > 3 may be derived from (5) and (6) by deleting the last term of (5) and averaging the result with (6)0 (7) 2bd 2b-1) (b d/2] + b [(d+l)/2) for d 7 30

31 Except for some of the values of C (b,d) given in B Table 1 (and except for d' 3, of course), this formula is accurate to better than 0.6 of one per cent, decoded The i=-o.-.omm" information produced by a b-d decoding net appears on bd output junctions. A useful criterion of the "costt of a b-d decoding net is the element-input count per used. output of a b-d decoding net, defined as the element-input count divided by bdo.~. Let RE(bd), RT(b,d), and RB(b,d) be these ratios for a b-d exponential switch, a b-d tree, and a b-d balanced m.s.n., respectively0 The fllowing relations may be easily established: (8) R (b,d) - d E (9) 2' aT(_bd) 2 + b-i 4 (10) 2 B_ Rb,d) 30 It may be shown that the element-input count per output of any b-d decoding net is at least 2. The superiority of a b-d balanced m.s.no over the other two types of b-d decoding nets is indicated by the fact that this value of 2 is approached by a balanced mo sn. as it becomes larger and larger, but not in general by an exponential switch or tree: (11) Limit RT(bd) 2 + doo -T- b

320 (12) Limit R (b,d) - 20 d -oo B The latter may be proved from (5)oll The most important result established in this section so far is the minimality of a b-d balanced m0sn. in the class composed of a b-d balanced mos.n., a b-d tree, and a b-d exponential switch. This leads naturally to the question: What is the broadest class of b-d decoding nets with respect to which a b-d balanced mos.n. is minimal? We are able to prove conjunc tion that a b-d balanced m.son. is minimal in the class ofA _b-d decoding nets.::12_ The proof of this result involves some new concepts of interest in their own right, so it will be postponed to the final section0 WVVe also offer the following conjecture, CONJ ECTURE: A b-d balanced m.s n' is minimal in the class of b-.d decoding netso It will be recalled thcat a b-d decoding net was defined to be a wofon. It is possible to extend this definition to include any net, whether wofo or not, which performs essentially the same decoding function, and we conjecture that a b-d balanced m. sn. is minimal even in this wider class of nets0

33~ 6~ The e-quation languaeo Any ordinary language is linear in the sense that its symbols normally occur in a linear order; in contrast, our formal net language is non-linear: its symbols normally require a two-dimensional medium. There are many cases in wfhich the net language permits the simplest and most satisfactory description of a digital computing circuit0 On the other hand, there are some situations where a precise linear language is more suitable.13 In the present section we will introduce such a language, called the euation languaieo The equation language is equal in expressive power to the net language, that is, the same information can be -expressed in each, and every net or net state may be translated into a suitable expression of the equation language and vice-versa, WVie could oive a formal definition of the equation language, and then prove this intertranslatability as a theorem, but in the interest of brevity we will give only an informal exposition of the equation language, usually proceeding by showing how to translate an expression of the net language into it, and usually working in terms of examples rather than general principles0 A plain net N of the net language may be translated into a set of equations of the equation language

34 o as follows. Associate with each junction of N a distinct propositional variable; these variables may also be regarded as associated vdth the wires terminating in the junctions. Consider an element with function symbol G (of degree ~I), variables O(',..o,%O associated with its input wires (numbered sequentially in a counterclockwise direction from the output wire), and variable (3 associated with its output wire. For this element write the equation -- 1..( 14. For example, E'ig. 2 translates into the set of equations " - g2 -' -i~2 4P 3 K23' c4 I 2E 4; see Fig. 150 Pl P2 P3 P4 9q q2 s3,q3 Fig. 15 A few comments on this notation are in order. The equivalence sign "-" means the same as "if and only if," To the right of this sign we write the function symbol found in the nucleus followed by the

35, variables associated with the input wires in the proper order. We use here the symbolism of Zukasiewiczt parenthesis-free notation for the propositional calculus: for example, tApqI for "tp or I", I"Apr for t"I or Y or r" "itKQ"I for "p and I", "Kpqr"t for "I ald E and rt', "Xp" for "not-p", "tCpq" for "if p then I", and "S q"' for "either not-e or not-.." Thus C" _ KilR2" means that the junction associated with "n" is activated if and only if the two junctions associated with "Pl0" and "Po2'' are both activated. Note finally that Fig. 16 P2 Fig. 16 In the case of a completely commutative function symbol 0 the order in which the input variables follow the symbol doesn't matter (e.g., "Apg" is equivalent to "Atqt") but in other cases it does (e.g., "_C1p2I is not equivalent to "Cp21"), and to be uniform we always follow the function symbol by the variables associated with the input wires of the element taken in a counterclockwise direction from the output wire.

36~ Partitioned nets are translated into sets of equations by using both variables with subscripts and variables with superscripts and subscripts in the way indicated by the following example. Fig. 3 translates 11 12 2 1' 2 into ",,1 12SI?1 __: 1 2 3 2 1 _l2 see Fig. 170 P1 P' P2 P2 ql 9q2 Cq3 q4 Fig. 17 Note that,,px, is associated with the xtth member of the y'th bracketed set. A net state NO of a net N may be translated into a set of equations as follows. Translate into a set of equations according to previous instructions. Then for each variable O< associated with an input junction of NJ, add " O(- 0tt or't 0( 1" to this set of equations accordingly as the junction associated with OC is labeled "1" or "0" in Nt', Thus Fig. 4 translates rll 12 K21 22 into "1- t12' t2 1l2' 3 -L2' K4 1 2, 1 2 1 2

37~ An equation expresses the state of an output junction in terms of the states of the junctions which directly drive ito In some cases it is useful to explain the state of an output junction in terms of the states of the input junctions (of the net) which drive ito This may be accomplished for wofono as followso Let N be a w fono First, associate a distinct variable with each input junction of N; if N is a partitioned net these variables must have subscripts as and superscripts,J _. indicated in thle last paragraph. Second, iterate tlhe following step as long as possible: if P is an output junction of Ni on an output wire of an element with function symbol 0 of degree'M and directly driven by junctions to which are counterclo ckwi se associated formulas A 1' ~~0' L (taken in a e order), associate GA 1 0 AM to T o The junctions of the net of Fig0 18 are labeled with formulas associated with them by these rules0 Fig0 18

38. If these rules are applied to a wf.no N, every junction of N will have a formula associated with it.15 The net may then be represented by the set of formulas associated with its final output junctions. We regard such a set of formulas as an abbreviation for the set of equations into which the net translates, Thus ttAKpNqKqr't abbreviates the set of equations into which Fig. 18 translates, i.e., t1 _ N 3 13 r — 3Arr,t16 One may specify the desired structure of a net by specifying a set of formulas. In this case we must proceed in the opposite direction. For example, given "tAKpNqKgr" we would construct the net of Fig. 18 by starting with the input junctions associated with ttt", "tt", and -r" and proceeding through the formulas "tNSq", tKp_ "t, IKtqr, "tAKpNqKqr"t in that order. Similarly, i 11 1i 2 1 12 i 2 21 22 2 i 1 2 1 2 22i o 2 ~KK~1p KiKp~llp2P3, KKP2 21R3 translates into Fig. 10. It should be noted that such a set of f brmulas always translates into a w.f.nn The last mentioned set of formulas is very systematic in structure and consequently permits even further abbreviation. If we denote the three net input cables of Fig. 10 by 2tp, ".,2, and. tp where the superscript ~p1 _2__ a ~ a3

39, t"2"t indicates the degree of the cable, and use "tx" to denote the operation of combining cables in an In.s., then Fig. 10 translates into "(iJ21 xt2)x2)."' We shall call such formulas construction formulas and regard them as abbreviations of sets of equations. for example, "( (PxP)) )" abbreviates the set of equations into which Figs. 10 and 7 translate. Every set of' equations which is a translation of an m.s.n. may be so abbreviated. It will be noted that construction formulas abbreviate sets of equations in very much the same way as m.s. net diagrams abbreviate m.s.n. Construction formulas show the structure of our three basic kinds of m.s.n. very clearly. A construction formula for a b-d m.s. net diagram contains d t1"P"ts each with a different subscript and each with a superscript b. A construction formula for a b-d exponential switch contains only one pair of parentheses; e.g., t?(xPg3xP3xPxP5) 11 represents the 3-5 exponential switch of Fig. 11. Every construction formula for a b-d m.s. net diagram in which all the left-hand parentheses are together and each tiPtt except the first is followed by a single right-hand parenthesis represents a b-d tree, and every b-d tree may be so represented; e.go, "((((P3 xP3)xP3)xP3)xP3" represents the 3-5 tree of MH~L jrY2 ~13 Ih4F~ 5H

Fig. 12. The construction formulas for b-d balanced moson. may be characterized by the following conditions: (1) It is a construction formula which represents a b-d moso net diagram. (2) Every occurrence of the operator "x" in it has exactly two arguments; moreover the number of Pttft1s in the first and the number of 1"P"tts in the second are equal or differ by oneo (((p2p2)x(p2 2 2 2 2 X x(( ) x(7x8))) is the construction formula for the 2-8 balanced m.son. of Fig~ 14, while "((P X2)x( xP 3))" is the construction formula for the 3-5 balanced mosno of Fig0 140

41o 7. A proof of the minimality theoremo In this section we shall prove that tie b-d balanced ra.s.n. is minimal in the class of all conjunction b-d decoding nets, It turns out t-lhat thL e re are other minimaIl nets in this class; these are, however, only slight variations of the b-d balanced m.s.n. We shall define in Subsection 7.2 "quasi balanced ms.n." denoting balanced m.s.n. and these other nets. In Subsection 7.3 we shall prove (in the main theorem) tlhat a necessary and sufficient condition that a net be minimal in the aforementioned class is that it be a quasi balanced m.s.r. It therefore follows as a corollary that the balanced m. s.n. is minimal. Before introducing these nets, we introduce a few helpful concepts and prove some theorems about them. It is hoped that some of these concepts, such as that of prorated cost, level, potential cost, overlap (Subsection 7.1), and quasi balalced configuration (Subsection 7.2), may be useful in the solution of other miinimality problems. One such problem might be to find a conjunction b-d net with a minimal element input count serving some purpose other than that of complete decoding. For example,

42. we might want a net with only a certain subset of the decoding junctions as its final output junctions~ 7.1. Some basic conce-ts. We make use of a reduction procedure, applied to conjunction b-d decoding nets. By considering only nets to which this procedure has been applied, we limit the class somevwhat, but we do not thereby exclude any minimal nets; the result is that our problem of minimality is simplified. The reduction procedure consists of steps which are applications of the following rules in any order and repeated any number of times. Rule 1. If two junctions Oc and S ( j not driving oc) are driven by exactly the same input junctions then delete and the element whose output wire is on ~, reconnecting any input wires on / to OC. Rule 2. Delete a final output junction and tihe element whose output wire is on it if that junction is not a decoding junction, Rule 3. If anl element has two input wires on the siame junction, then delete one of the wires (thus changing an n input conjunction to an n-l

43. input conjunction). An irreducible b-d net is a conjunction b-d decoding net which cannot be reduced by any of the above rules. We prove the following. (A) No two junctions of an irreducible net are driven by exactly the same input junctions, If there were two such junctions, at least one of them would not drive the other, for otherwise the net would contain a cycle and not be well-formed. Therefore, Rule 1 is applicable and the net is not irreducible. (B) No junction is driven by two distinct members of the same bracketed set. Such a junction could not drive a decoding junction. It would, therefore, either be a final output junction or drive a non-decoding final output junction~ In either case, Rule 2 could be appliedo (C) The element input count is decreased by an application of Rule 1, 2, or 3 to a conjunction b-d decoding net and the resulting net is also a conjunction b-d decoding net. This is obvious from the rules.. (D) Anly net which is minimal in the abovementioned class is irreducible. This follows directly from (C).

44. In what follows, because we are interested in iinimality, we shall, in the light of (D), consider only irreducible nets. We shlall sometimes make use of (A), (B), (C), and (D) without explicit reference to them. We say that an (element) input wire W directly drives a junction Cc if W is part of an element whose output wire is on OQ. We say that an input wire W drives a junction A( if the junction 16 directly driven by W either is Qc or drives oc. The use of an input wire W, u(W), is the number o f final output junctions driven by W. it is convenient to prorate the cost of a net C(LI) among the final output junctions of the net. To this end, where C( is a final output junction, the prorated cost c(xO) is the sum of the reciprocals of the uses of all the wires driving Q(. Note the 3-2 net, a portion of which is shown in Fig. 19. W (Wl) drives the final output junctions ( anrd (. The use of W (W'e) is 2. The use of every other input wire shown is 1. The prorated cost of (ft) is therefore 3.

45 IIW Fig. 19 THEORE1 I. C() = Z c(c<), suimning over all the final output junctions CO in N. Proof: C(i) is the number of input wires in N. Consider any input wire W in N. There are u(W) final output junctions driven by W. To the prorated cost of each of these W contributes 1 and to the prorated cost of all the other final output junctions W contributes nothing. Therefore, to the sum of the prorated costs of all final output junctions W contributes exactly 1, which is what it contributes

46. to C(I ). Since this is true of all input wires W, Theorem 1 follows. A junction CO represents a bracketed set when some net input junction of the bracketed set eithier drives, or is identical to, O<. The level of a junction is the number of bracketed sets represented by the junction (i.e., assuming the net is irreducible, the number of input junctions driving it). The configuration of a junction Oc is the subnet consisting of Q( itself and all junctions driving 0o, together with all elements whose output wires are on such junctions. Thus, all input wires driving O< will be in the configuration of v; and, conversely, any input wire in the configuration of 6X drives A. Any junction /( in the configuration of Q( which is not OC itself is of lower level than a<; any bracketed set represented by (j is also represented by OC Corresponding to the concepts of driving, use and prorated cost, we have the concepts of potentially driving, potential use, ad potential cost. We say that a junction c pootentially drives a junc tion, when OC is not t and every input junction driving 0

47. also drives. We say that an input wire W potentially drives a junction ~, if the junction O( directly driven by W either is A or potentially drives &. The potential use of an input wire W is the number of final output junctions potentially driven by W. We shall use the fact that, in an irreducible b-d net, the potential use of a wire directly driving a junction of level i is bd-i The potential cost of a final output junction OC is equal to the sum of the reciprocals of the potential uses of all wires driving Qc. Note the portion of a 3-2 net in.Fig. 20. The junction CX and tihe wires W and Wt potentially drive g and O, but drive only 6. The use of W (W') is 1 while the potential use is 2. The prorated cost of 5 is 4; the potential cost of 6 is 3. Fig, 20

48. TihEORav 11io The prorated cost of a final output junction OC equals the potential cost of O( if and only if every wire in the configuration of CO drives all the final output junctions which it potentially drives. Otherwise the prorated cost is greater. The proof of this is obvious from the definitions of the concepts involved. (Note, in Fig. 20, that the prorated cost of / is greater than the potential cost of d because W and W, which are in the configuration of /, potentially drive but do not drive We define n(i,,S) to be the number of wires directly driving junctions of level i (2 - i) in the configuration of a junction { of level i (2 _ i < d) W'Jhere there are no junctions of level i, n(i,~) o0; in particular, this is so wthere i vio Let m( 2) n(i,;o ) 1 The following theorem shows i=2 bj-i the importance of m(g) where 3 is a final output junction. THEORA III. For a final output junction /4 of an irreducible net, m(1) is equal to the potential cost of /5.

49. The proof is direct from the definition of m(j) and the observation made above that, in an irreducible net, the potential use of axiy wire directly driving a junction of level i is bd-i Where / and / are in a net, then the configurations of 6 and / overlap if there is at least one wire W driving both P and so We are interested in the case where p and / each directly drive a junction 0( o Note that such a situation exists in Fig. 21. (Fig. 21, and all the diagrams which follow are abbreviated. The nuclei and output wires of elements, all of which are conjunction elements, are omitted, the input wire being drawn directly from one junction to another, Junctions are represented by small circles. Arrowheads are omitted, always being understood as pointing upward. Finally, junctions of the same level are placed on the same horizontal level.) Fig, 21

50. THEORHU IV. if,1' ~,,' r of levels Jil,'.00' r respectively, are the r junctions directly driving a junction oC of level i in an irreducible net, then m(O<) r + m+ + ( ) biJl bi-Jr The equality holds if and only if the configurations of no two of the I s overlapo Proof: Suppose first that there is no such overlap Then n(iK,() - r. For each 2, 2 < i n(,O<) n() -+.. - n(p,, r) + Hence (by definition of m(O() ), the equality in the theorem holds. Where there is such overlap, suppose there is a wire W driving /bk and 1k' (kI k' )o Suppose that the level of the junction which W directly drives is a, which will be greater than 1. Then n(-,o<) < n(P,!3) 3 1. + n(-,'Pr). Hence the inequality in the theorem holds. 7.2. Quasi balanced m. S nets, We now define "quasi balahiced configuration,"t The significance of this concept is contained in Theorem VI below. A configuration is quasi balanced if every one of its output junctions / is directly

51o driven as follows, assuming i is the level of /3 (1) if b = 2 and i = 3, either by one junction of level 1 and one of level 2 or by three junctions each of level 1; (2) in all other cases, by two junctions of level [ and F. 1 Thus Fig. 22(a) is a quasi balanced configuration of ~ of level 3 in any net, while Fig. 22(b) is quasi balticed in a 2-d net but not in a b-d net for which b > 2. (a) (b) Fig. 22 (Note that a quasi balanced configuration of a junction of level i is like the configuration of a junction of level in a balanced r. sn. in every respect except possibly in the case of' junctions driving junlctions of level 3 in: 2-d nets.)

52 I Note that in a quasi balwaiced configuration no two configurations of junctions directly driving aLnother junction overlap, as cacn be seel as follows~ Suppose the configurations of " and, directly driving of level j, overlap. Then the sum of the levels of 6/ and a would be greater than i, whereas in a quasi balanced configuration the sum is always equal to or less than j We note that, for a given b and 1, for all junctions,of level i in b-d nets (regardless of d) which have qluasi balanced configurations, m( ) has a constant value, Let m_(i,b) be this value. The following theorem summarizes some properties of m:(l,_b). iHIEORE V. (a) m(2,b) = 2 (b) m(3,b) = 2 + 2 (c) For 2, (2,) 2 + 2mn Uxb) (c), m(2,) b. 0.. bJ (d) For i j 2 m_(2i+,b) - 2 + mj-_b) + "L l+b)_ bJ 1 bj (e) m(4,b) - 2 + blb b2 (f) m(5,b) - 2 + _ + 2 b3 b2 (g) For all i m 2, mi,b) 3, (h) For i > 2, m(Q,b) > 2, (i) For all i (b) - m(2i+l,b)( < ~.~~~~. -. o 9

530 (a) and (b) are obvious. The proofs of (c) and (d) are direct..,from Theorem IV a nd the definition of a quasi balanced configuration, since there is no overlap in a quasi balanced configuration which would lead to an application of the inequality of Theorem IVo (e) follows directly from (a) and (c). (f) follows directly from (a), (b), and (d) (h) follows from the fact that in the configuration of any junction of level 3 or more, there must be at least two wires directly driving 1& and at least one other wire somewhere in the configuration. The proofs of (g) and (i) are given in Appendix 1o Note that (a), (b), (c), and (d) resemble (3) of Section 5, the recursive formulas for the elementinput count of the balanced m.,s,n The former characterize m(1,b) which will be the potential cost of a junction with a quasi balanced configuration. i ow, as we show later, the potential cost equals the prorated cost of' a final output junction of a balanced mo.sn,n. and every configuration of an ILms.n. is quasi balanced. Since there are bd final output junctions in a b-d m.s.n., one can find the element input count from m(idb) by multiplying by bdo

54, TIEORfi'1 Vi. For a given b, if a junction 4 of level does not have a quasi balanced configuration, then > (> b The proof of this theorem is given in Appendix 20 It follows from this theorem that in the class of all conjunction b-d nets, in order that a final output potential junction have a minimalAcost, it is necessary and sufficient that it have a quasi balanced configuration~ We proceed to define "b-d quasi balanced m.s.no" in several steps. We define first "2-3 quasi balanced msont" Our definition proceeds by describing the alternative ways in which the junctions of level 2 are driven. Once the junctions of level 2 have been specified, a unique 2-3 decoding net is determined as follows, Each pair of junctions, one of level 2 and the other Xan input junction in the bracketed set not represented by the first, is put on the inputs of a conjunction whose output wire is on a final output junction. Then each set of three input junctions, one from each bracketed set such that no two directly drive a junction of level 2, is put on the input wires of a three input conjunction whose output wire is on a final output

550 junction. (Note that Fig. 26 below is determined in this way from Fig. 25.) Supposing that Ca i, Co I of the first bracketed set, c(2, c<2 of the second, and a 3' CX of the third are the input junctions of a net N, N is a 2-3 quasi balan ced m.s.n. if and only if' it is determined by the following. (1) There are four junctions, /4', and 4'" such that 4 is driven by X 1 and Oc 2, 13 by C(1 and C(y2' I by CX. and C' and /&'" by' and (X2. (See Fig. 23.) ~11 i 2 310 o1 3 Fig. 23 (2) There are four junctions ~1, 49, 43, S such that /41 is driven by C1 land Oc 2' (t by QC 1 and OC2, (3 by. Ci o 23.n by o 2 and C > (See Fig. 24.)

56o, (53 ~110 (3 LJ3 Fig. 24 (3) There are three junctions 13' 2' n1 such that 3 is driven by 0( and 2 by 1 anld 0(, and 31 by GC2 and 0( 3 (See Eit. 25.) iL 0(23 Fig. 25 (4) The same as (1), (2), or (3) except that one or more (possibly all) the junctions of level 2 are deleted,

57 The reader, with some effort, canl ascertain that there are exactly ten 2-3 quasi balanced mo.s.n The net determined by (1) is the 2-3 balanced m.s.n. The net determined from (1), (2), or (3) by deleting all junctions of level 2 is the 2-3 exponential switch~ The net determined from (3) is pictured in Fig. 26. cx Figo 26 A b-3 net N (b > 2) is a quasi balanced imns.on if and only if it satisfies one of the following conditions. (1) N is a b-3 balanced moson,o (2) N is constructed as follows. Let the three bracketed sets be I1, 2 and 3 Take any subset K of Icardinaiity k, I' k - b Construct the m.s. which has as its bracketed sets Il and K_ Construct the m.s. which has as its bracketed sets I -K and 13o Let 01 and 02

5so be, respectively, the sets of outputs of these moso Construct a third mros. whose bracketed sets of inputs are 01 and I3, and a fourth mrns whose bracketed sets of inputs are 2 an d I The outputs of these two m. s. are the final outputs of N in nwhich I2 is bracketed and superfluous brackets are deleted. (Cf. the 3-3 net of Fig. 27.) ~1<I 2 Fig 27 Figo 27

59. Note that the radical difference between the definition of tb-3 quasi balanced r..son." for b = 2 and the definition for b > 2 is related to the difference between the case in which b = 2 and that in which b > 2 in the definition of "quasi balanced configuration.tt A net N is a b-5 quasi balanced m.son. if and only if it satisfies one of the following conditions. (1) Where N1 is a b-3 quasi balanced mt.son. and Ni2 is a b-2 m.s. with output sets O1 and 0 respectively, and where 3 is anr m.s. having O1 and Q2 as its bracceted sets of inputs, the net N consists of N 2, nd N3 with superfluous brackets deleted. (2) A has five bracketed sets of inputs,1!, o., _L5, each rwith b junctions, I3 consisting of K and I3-K. NI is the net consisting of N1,'''' N6 (described as follows) with superfluous brackets deleted. N1 is the mrs. having I1 and _I2 as its bracketed sets of inputs. N2 is thie m.s. having I and I as its bracketed sets of inputs. Where a1 and 02 are the output sets of N1i N2, respectively, ij is the m.s, having 21 and K as its bracketed sets of inputs, and N4 is the m.s. having 02 and L3-K as its bracketed sets

60. of inputs. Where 0 and 04 are the out)ut sets of N3' e4 respectively, i!5 is the m.s. having as its bracketed sets of inputs 03 and 2, and N6 is the m.s. having as its bracketed sets of inputs O1 and 0 The outputs of N are, of course, those of Ni5 together with N6. (Cf. tile 2-5 net of Fig. 28.) WI _-K I l k -2 -3 -4 -5 Fig, 28

61 A b-d balanced m.s.n. N1 may have ia b-3 or b-5 balanced m.s.no is' as a pa rt N.i has in common with the remainder of N just the set of b3 or b5, junctions which are the final output junctions of N' (See the definition of "balanced m.s.n." in Section 4.) The operation which consists of reoplacing N', by aiiother b-3 or b-5 quasi balanced m.s.n. is used in the definition below, We define b-d quasi balailced moSoln. for d * 3 andd t 5 as follows: (1) The b-d balanced m.s.n. is a b-d quasi balanced m%. sn. (2) The result of replacing any number of b-3 and b-5 balanced mos.n. by b-3 and b-5 (respectively) quasi balanced m.son. in the b-d balanced mo.s.n. is a b-d quasi balanced mos.n. Note that ac b-d gquasi balanced mo.sn., if it is not a b-d balanced m.s.n., differs from it only in junctions of level 5 or lesso Thus, we are justified in saying that a quasi balanced mt.s.no is either a balanced m.s.n. or a slight variation thereof. It is also interesting to note that a b-d quasi balanced m.s.n. where d is a power of 2 must be a bailanced m. s,n., since ill thiis case there

62. are no b-3 or b-5 subnets, all jtulctions ini such a balanced rm.s.n. being of level 2r, for some nonnegative integer r. Niote, finarlly, that a quasi balanced m.s.n. is not necessarily an m.s.n., as defined in Section 4. (The word, "quasi," is used as an adjective modifying the phrase, "balanced m s.n,". not as an adverb modifying "balanced.t") 7.3. Proof of the main theoremo MAIN THEOREM. A net is minimal in the class of conjunction b-d decoding nets if and only if it is a b-d quas'i balanced m.s.n. This thleorem fol-lows directly from Lemmas 2 and 7 below since we know that minimal nets inust be irreducible and since any quasi balanced mri.s.n. is irreducible. The series of lemmas refers to the presence and absence in nets of two important properties. The first minimizing property of a net is that every final output junction has a quasi balanced configuration. We note that, by Theorems III and VI, a net has the first minimizing property if and only if eacEh final output junction has a minimal potential cost. The second minimizig property of a net is that

630 the potential cost of every final output junction equals the prorated cost. Before presenting the lemmas we state an important corollary of the main theorem which depends on the fact that the balanced m.s.n. is a quasi balanced m.s.n. COROLLARY. The b-d balanced m.sOn. is minimal in the class of conjunction b-d decoding nets. Note that the corollary requires only the first two of the following lemmas, since a balanced m.s.n. is a quasi balanced m.s.n. and is irreducible. IMost of the complication in the proofs of Lemmas 3 through 7, as well as that in the definition of "quasi balanced m.s.n." itself, is included in this paper because we wished to give a condition which is necessary, as well as sufficient, for minimalityo LEMMA 1. A quasi balanced m.s.n. has both minimizing properties o Proof: It is possible to check all the cases to see that each quasi balanced m.s.n. has, for every final output junction, a quasi balanced configuration. It is also possible to check that every junction (and

64. thus every wire) in such a net drives every final output junction which it potentially drives. Therefore, by Theorem II, a quasi balanced m.son. also has the second minimizing property. LE~~LvA 2. A net is minimal in the class of irreducible b-d nets if and only if it has both minimizing properties. Proof: Lemmna 2 can be established if we cCan establish the following: (1) there exists a b-d net having both minimizing properties; (2) if N has both minimizing properties, then C(K1) = bdm(d,b); (3) if 14 lacks either of the two properties, then C(i)> bdm(d,b). (1) follows from Lernma 1. Suppose N has both minimizing properties; consider any final output junction o( o c (c) equals the potential cost of O(, by the second minimizing condition, which equals m(c),, by Theorem II, which equals m(d,b) by the first minimizing condition. Hence, (2) follows by Theorem Io Suppose that NJ lacks the first minirmizing property. Then there is at least one junction S which does not have a Kuasi balaniced configuration. Then c(6)' m~(i, by Theorem II, r m(d,b) by Theorem VI, For every other junction

65. Oc of N, c(O) m m(db), by similar reasoning, Hence, C(a) > bdm(d,b)o If N lacks the second minimizing property, then there is a junction 4 whose potential cost is not equal to c(,). By Theorem II c(3) is greater than the potential cost, which is - m_(d,b) by Theorem VI. Again, by Theorem I, C(N) > bdm(d,b). Hence (3) follows. LEfMiA 3, In an irreducible b-d net N (d 3) having both minimizing properties the following is impossible: a junction ( is driven by O( and o(t, and /1" by ol' and o(", where O(, l, O( " are input junctions of distinct bracketed sets, and & and ~" are of level 2. Proof: OC, Q(', and %("t together drive at least one final output junction o. Yand,6" potentially drive d. Therefore, we can assume that 3 and i4" must each drive ~, since N has the second minimizing property. But then the configuration of K would not be quasi balanced, which can be seen as follows. There must be a junction & in the configuration of i which is driven by both 6 and 4", such that there are no junctions driven by {4 and ~' which drive S o ( i may be ~ itself.); is directly driven by a junction which is driven by,

66. or identical to, 3 but not /3f" and a junction " driven by, or identical to, it but not. Now if there is at least one other junction directly driving S, then the configuration of would not be quasi balanced (for no junction in a quasi balanced configuration is driven by more than two junctions, unless it is a junction of level 3 in a 2-d net driven by three junctions of level 1) We can, therefore, assume that C and "t are the only junctions directly driving o For the configuration of / to be quasi balanced, the sum of the levels of 1 and 9 must be equal to the level of 5. But this is impossible here, since oca drives both 9 and 3 ". L MEIA 4. If an irreducible 2-3 net has both minimizing properties, then it is a quasi balanced mSo.n Proof. In defining "2-3 quasi balanced msnot we characterized the net by enumnerating the junctions of level 2, and specifying how they were to be driven, The manner in which the eight final output junctions were to be driven was completely determined by the condition that a junction of level 2 drive every

67. final output junction which it potentially drives. Clearly a net can be determined in this manner if and only if it has the second minimizing property. For the purposes of this proof we can restrict ourselves to such nets. Consider nets N and N2 such that N2 contains all the junctions of level 2 that N1 has and one more besides. If N1 has the first (as well as the second) minimizing property, and if every such N2 lacks the first minimizing property, we say that N] is a maximal net having both minimizing properties, It is not difficult to see that if N2 has the first minimizing property then so does N1. And, finally, if N2 is a quasi balanced m.s.n., then so is N1o It follows that if there is a net which has both minimizing properties which is not quasi balanced then there is a maximal such net. Consider now any maximal net i hlaving both minimizing properties. it is not diff icult to see that the following three cases are exhaustive, Case I There are two bracketed sets 11 and 12 of N such that all juwctions of level 2 represent only these. The reader can check that the only maximal such case is (1) of tihe definition of

68. "2-3 quasi balanced m.s.n." Case II: All bracketed sets are represented by junctions of level 2, but there is an I2 which is represented by all such junctions. Making use of Lemma 3, the reader can check that the only maximal such case is (2) of the definition. Case III: Every pair of bracketed sets is represented by a junction of level 3. Again, by Lemma 3, one can see that the only maximal such case is (3) of the definition. We say that two junctions or and /3 in a conjunction net N are conjoined when there is a junction / such that 2a and P directly drive and no other junction directly drives I o LELAh 5. For b > 2, if an irreducible b-3 net has both minimizing properties, then it is a quasi balanced m. s n. Proof: For b > 2, since every junction of level 3 must have a quasi balanced configuration, there must be junctions of level 2. Either there are only two bracketed sets which are represented by the junctions of level 2 (Case I) or. all bracketed sets are so represented (Case II). Case I: Suppose that Il and I2 are the

69. bracketed sets. It is easy to see in this case that every pair C 1 and ~ 2 of junctions Il and 1 respectively, are conjoined. For take any junction O3 of 13: 0(1, (2, and OC3 must drive a final output junction d; since has a quasi balanced configuration, there must be a junction 3 of level 2 in it; but d cannot be driven by 0(3, so it must be driven by O(1 and 0(2. Since every such pair drives a junction of level 2, and since there are no other junctions of level 2, the net is a balanced m.s.n. and a fortiori a quasi balanced m.s.n. Case II: There must be t least one bracketed set, say 12, containing a junction 0(2 conjoined with a junction 0(1 of I1 and containing a junction O conjoined with a junction o<Q of 2 3 I3. It is then impossible that any junction o0( of I be conjoined with a junction oQ3 of I3. For consider the junction d driven by 6', 0(2, 3 and 3' 0(1 and OC ( ~C 2 and Oq2) ( O( 3 and OCQ) would be distinct by Lemma 3; neither OC( and nC2, nor O and O (, nor Q~2 and QOQ could be conjoined, by Lemma 3; and, therefore, 6 would not have a quasi balanced configuration.

70. Now let K be the set of a11 junctions of I2 which are conjoined with a junction of 1. Let X 1' 0(2, (2, and X3 be any four junctions of, -K_ and I3, respectively. Let / ( 6') be the junction driven by 6C1, 62 ((), and C3' The configuration of /(') must have a junction g! (/') of level 2 in order to be a quasi balanced configuration. ~ must be driven by d(1 and 6~ 2; the other possibilities are excluded by the definition of "K", Lemma 3, and what was established in the above paragraph. Likewise't must be driven by OI and 0(i Since the O.'s were arbitrary junctions, it follows that there are m.s., one whose bracketed sets are Il and K, the other whose bracketed sets are I3 and I 2-. It is easy -2 to see then that N fulfills (2) of the definition of' "b-3 quasi balanced m.s.n.T" (b S 3). This completes the proof of Lemma 5. LERIL:A 6. An irreducible b-5 net l with both minimizing properties is a quasi balanced m.s.n. Proof: N, must have junctions of level 3, in order that its final output junctions have quasi balanced

71. configurations. Let ~ be such a junction and suppose it is driven by O(l of 1l o( 2 of I2 and 0( 3 of 13. Consider any O(4 of 14 and o 5 of 1I. The fiinal output junction S driven by all the O('s mentioned must be driven by the wires driving (, and thus by /4 itself, because of the second minimizing property (by Theorem 11). Since the configuration of' is quasi balanced, / must be conjoined with a junction of level 2. Therefore, OC and 0(5 must be conjoined. But oc ~4 - 5chosen and w 5 were arbitrarily~ it follows that there is an m.s. whose bracketed sets of inputs are I4 and I5. Now either all junctions of level 3 represent 11, I2, and I3 (Case I) or there is a junction of level 3 which represents either I4 or I5 (Case II). Case I; For fly 1,.., ~5, the final output junction S driven by all these must have a junction ( of level 3 in its quasi balanced configuration, which is driven by C(1, O(2, and 0(3. This means (since Gl', 20( and 03 -are arbitrarily chosen) that the subnet N1 of' N consisting of all such junctions /3 and junctions which drive

72~ them is a b-3 decoding net. To show that N fulfills (1) of the definition of "b-5 quasi balanced m.s.n." it suffices to prove that N1 is a b-3 quasi balanced m.s.no But every configuration of a junction in a quasi balanced configuration is quasi balanced; hence N1 has the first minimizing property because N has it. But by Theorem II it is easy to see that, because N has the second minimizing property, N1 also has it. By Lemmnas 4 iand 5 then AL1 must be a b-3 quasi balanced m.s.n. Case II: Let l be a juction of level 3 representing,'say, I. By reasoning similar to the first paragraph of the present proof there is an m.s. whose bracketed sets of inputs are the two bracketed sets not represented by / tov Neither of these can be 15, by Lemma 3, since I4 an d I5 are the bracketed sets of an m.s. So o'1 represents 4,!5 Cand, say, 3. Ald there is an m.s. whose bracketed sets of inputs are I1 and 12o Let the set of outputs of this m.s. be 01 and the set of outputs of the m.s. of the first paragraph be 02~ Let K be the set of all junctions of I3 which are conjoined with a member of l1. It is easy to

73, see that no member of K is conjoined with a member /32 of 02. This can be seen as follows. Suppose o3 of K were. Then there would be an 1 and a(2 of ni aid 12 driving 1 of 01 which together with or'3 drives C1 of level 3. Aild there would be an ~(t4 and 5 of I and I 5 driving 2 of 2 which together with O 3 drives 2 of level 3. The final output junction S driven by 61, ~2, 3, O(4, and 0(5, by the second minimizing property, would h ave to be driven by 41 and d/2; but then the configuration- of S would not be quasi balanced. Now in order that the configurations of be quasi balanced every member of K must be conjoined with every member of 01, and every member of 13-K must be conjoined with every member of 02 (No member of 11 or 12 can be conjoined with any member of I4 or 15, by Lemma 3.) It is now easy to see that N must fulfill (2) of the definition of tb-5 quasi balanced m.sn,"ot This completes the proof of Lemma 6.

74. LEMiA 7, For all b and d (b,d - 2), an irreducible b-d net has both minimizing properties if and only if it is a quasi balanced m.s.n. Proof: By Lemma 1 it suffices to prove that any such net having both minimizing properties is a quasi balanced m.s.n. We prove this by induction on d. For each b, there is only one irreducible b-2 decoding net, within isomorphism. That net is obviously a quasi balanced m.s.n. and has both minimizing properties. We assume, as an inductive hypothesis, that any b-d decoding net, for d <s, having both minimizing properties is a quasi balanced m.s.n. We must show from this that any b-s decoding net NI having both minimizing properties is a quasi balanced m.s.n. We distinguish two cases according to whether s is even (Case I) or odd (Case II). Case I: Put r -- Take any final output 2 junction ( of I,. Since the configuration of 26 is quasi balanced, / must be directly driven by two junctions 41 and /12 each of level r. Let _1 (S2) be the set of junctions conjoined with /2 (/1)' ~By the second minimizing property S1 (S2) has br junctions, otherwise /32 (/1)

75, would not drive all the junctions of level 2r which it potentially drives. For, since thkere can be no junctions whose level is between r and 2r, in order for /'2 (/1) to drive a final output junction, it has to directly drive it. By the first minimizing property and definition of "quasi balanced configuration", all the junctions of Si (S2) are of level r. Every junction of S1 ( must represent just those r bracketed sets of inputs of N which /,2 (Y1) does not represent. It is easy to see that every junction of S! is conjoined with every junction of S2, otherwise some junctions would not drive all the final output junctions they potentially drive. Furthermore, such account for all the b2r final output junctions. The two subnets N_ and N2 whose final output junctions are S and -2S2, respectively, must account for all the junctions of N, except N's final output junctions. By definition of "balanced m.s.n." (Section 4) and "quasi balanced m.s.l", we can prove that N is a quasi balanced m.s.n. if we can prove that N1 and N2 are. But since N has both minimizing properties, N1 and N must have them (cf. Case I of Lemma 6).

76. By inductive hypothesis N1 and N2 must therefore be quasi balanced m.s.n. Case 11: Put r 2- s1. For r 1 and r - 2, Case II has already been proved in Lemmas 4, 5, and 6. WNe car assume, therefore, that r - 3. Paralleling Case I, take any final output junction of N. Since N has the first minimizing property, I must be directly driven by 1 of level r and 42 of level r+l, by definition of "quasi balanced confiiguration.t" Let (2) be the set of all junctions conjoined with /2 (l1)' Neither 31 nor 2 can drive any junctions except final output junlctions, otherwise some configuration would not be quasi balanced. (Note that for r = 2 or 1, l could drive a junction of level r+l; this is whiat makes b-3 nets and b-5 nets exceptional.) Thus, by the second minimizing property, S1 (S2) has br (brtl) junctions. By the first minimizing property, and by definition of "quasi balanced configuration," all the junctions of S1 (S2) are of level r (r+l). From here on, the proof is similar to the proof of Case I o This completes the proof of Lemma 7. Arthur W. Burks Robert McNaughton Carl H. Pollmar Don W. Warren Jesse B. Wright University of iichiigan

77, Footnotes 1. The writing of this paper aind thie research which it reports were done under the sponsorship of the Burroughs Corporation. The authors wish to thank Dr. J. Richard Buchi for many helpful suggestions. 2. Burks, Arthur W., and Jesse B. Wright, "Theory of Logical Nets," Proceedings 1._.E., Vol. 41 (1953), pp. 1357-1365. 3. The reader unfamiliaCr with the notatioil of' symbolic logic may find it helpful to read part of the section, I"The Equation Language," at this point, Burks and Wright, op. cit., pp. 1361-1365. 5. Buirks and Wright, op. cit., p. 1362. 6. Note that, according to this definition, there are complete decoding nets which have bracketed sets of only one junction. Although this is contrary to ordinary usage, the inclusion of these nets facilitates the development of the theory. Note that the decoding junctions need not be final output junctions. Note also that there may be, for a net state N', more than one decoding junction labeled 1 in Nt. 7. The word "multiplicative" derives from the settheoretic definition of multiplication in whlich the

78. cardinality of the Cartesian Product (here the collection of representative sets) of a nwuber of given sets is the product (i. id) of the cardinalities of the given sets. 8. Shailnon, C. E, "The Synthesis of Two-Terminal Switching Circuits," Bell System Technical Journal, Vol. 28 (iNo. 1, January, 1949), pp. 59-98. 9. Browni, D. R., and N. Rochester, "Rectifier Networks for Multiposition Switching," Proceedings I.R.E., Vol. 37 (1949), pp. 139-147, give definitions of 2-d m.s.n. and 2-d balanced m.s.n.; their definitions are in terms of crystal rectifiers and are more complicated than the ones we give. Synthesis of Electronic ComrAuting and Control Circuits, by the staff of the Computation Laboratory (Harvard University), p. 137, gives some informal rules of construction for the realization of a 2-d balanced m.s.n. by vacuum tubes or crystal rectifiers that are similar to the above definition. 10. Brown and Rochester, op. cit. 11. Synthesis of Eiectronic Computing and Control Circuits gives (11) and (12) for the case b = 2. 12. Brorwn and Rochester, o. cit., state and prove the theorem that a 2-d balanlced m.s.n. is minimal in the class of 2-d m.s.n.

79. 13. One possible use of a linear lanlguage is in computing minimality on a digital computer, Gand for this purpose a linear language would be much nore convenient than the net language. The process by which this could be accomplished is rou hly as follows. The machine is instructed to construct ail sets of equations (or sets of formulas -- see below) of a given type, and then to determine for each such set the element-input count of the circuit it represents and whether the circuit it represents realizes the desired transformations. 14. The eleIents of a set of equations are equationtokens rather than equation-types, in the sense of Peirce (The Collected Papers of Charles Sanders Peirce, edited by Charles Hartshorne and Paul Weiss, Vol. 4 (193'), paragraph 537). Thus, a network composed of two two-input conjunctions connected in parallel from junctions with associated variables "p" and t"g"t to junction with associated variable "r"tt translates into f"r -- K pqr -KpqT." 15. In some unimportant cases two or more junctions of a w.f.n. may have the same formula associated with them; in what follows we assume that these formulas are distinguished by appropriate uses of superscripts on the function symbols in them.

o80 16. It should be noted that a net does not translate into a unique set of equations inasmuch as different variables may be associated with the junctions of the net. For a similar reason, a given set of formulas in general abbreviates many sets of equations.

81. APP ENDIX 1 Proof of (g) of Theorem V. By (a), (b), (e), and (f), (g)' holds for i C 6. By induction we prove it for all j Assume that, for any i' 6, (g) holds for all numbers less than j. Case I: j - 2i. Here, e _ 3. By (c) nm(i,b) 2 2mib) 2 + 2-3 3. Case II: j - 2i + 1. bi 23 Again, i = 3. By (d), m(j,b) - 2 + (i~b) + m(i+l,b) bi+ 1 bi 2 + ~ + 4- c 3. (Note that the equality of (g) holds 24 2 only for b = 2 and j - 3, 4, or 5.) Proof of (i) of Theorem V. Case I: i - 2, 3, or 4. Here (i) can be established directly using (a), (b), (e), and (f) of Theorem V. Case 11: J 2i, i a 3. By (c) and (d), m(2i,b) - m(2i+l,b) 2bm(i,b) - m(i.b) -bm(ilb) < b-2 b+1...i+l bil applying (g) and (h) of Theorem V. The latter is easily shown to be less than 1/2. Case III: ji 2i + 1, i 2. By (c) and (d), ri(2i+l,b) - m(2i+2,b) m(i,b) - (b-2)mr(il.b) 3b-3, by applying (g) b1+1 bi+l of Theorem V. The latter is easily shonv to be less than 1/2.

82. APPENDIX 2 Proof of Theorem VI Tile proof is by induction on j. We prove Theorem VI first for ij 2 and 3. Then we show that the inductive hypothesis that (for i' 4) Theorem VI holds for all i' < j implies that it holds for ]o Proof for j — 2. Here Theorem VI holds because a junction of level 2 in Gn irreducible net cannot have a configuration which is not quasi balanced. Proof for = 3. Suppose first that b - 2. By (b) of Theorem V, m(3,2) - 3. With reference to the definition of "quasi balanced configuration", we know that 3 is not directly drivenl by exactly one junction of level 2 and exactly one junction of level 1; nor is it directly driven by exactly three junctions of level 1. The following possibilities remain, since, is of level 3: (1) A4 is directly driven by exactly one junction of level 2 and more than one junction of level 1; (2) is directly driven by more than one junction of level 2 (and possibly junctions of level one). In either of these cases, it is easy to see, m(i/) ~ 3.

830 We now consider the case in which b > 2. By (b) of Theorem V, m(3, ) 2 2or there are the two possibilities of the preceding paragraph and another, namely, (3) ~ is directly driven by exactly three junctions of level lo In any of the three cases, it is easy to see that m(4 )> 2 + 2. Inductive proof. Case I: i 2n (n - 2). We divide thlis into four subcases, according to whether (Ia) there are exactly two junctions / and & directly driving ~ each of level n, (Ib) the same but b is of level n+l and S is of level n-i+k (n > i > 0 and n-i-l'- k > 0), the configurations'of ~ and S not overlapping, (Ic) the same as Ib except that the configurations do overlap (k > 0), or (Id) there are three or more junctions directly driving S o That the first three cases are exhaustive when there are exactly two junctions is implied by the fact that, in order that 2n bracketed sets be represented by 5, the sum of the levels of the two junctions must be at least 2n; apart from this, the two junctions may be of any two levels, each less than 2n. Subcase Ia: Since iand S are each of level n, and / is of level 2n, the configurations of

and S do not overlap. If the configurations of Y arnd were both quasi balanced then /4 would have a quasi balanced configuration. Therefore, either I or S does not have a quasi balanced configuration. By inductive hypothesis either m( ) > m(n,b) or m( )> m(L,b), and inequality in the reverse direction holds for neither. But m(2nb) = 2 F 2m(n, by (c) of Theorem V. Hence, bn by Theorem IV, m(/3) 3 2 + t t m( ) > m(2n,b). n bn Subcase Ib: Here, by inductive hypothesis, mt() m (2n+i,_ ) and m( ) - mn(L-i_+k,b). Now, by (a) of Theorem V and Theorem IV, in(2n,b) 2 2m(nb), and m(j) 2 +- m(i) bk bn bn-i n+i-k Therefore, in order to prove that m(/~4) m(2n,b), it will be sufficient to prove that 2m (nb) m (n i, b) m(n-i-kb tr b <(n b) + It suffices, bn bn-i bn+i-k therefore, to prove that 2m(n,b) -_iim(n+!,b) iiLkk For i' 2, the left side must be negative since b _ 2, r (n,b) = 3 (by (g) of Theorem V) and m(n+i-,,b) 2 (by (h) of Theorem V). The inequality

85. in that case holds because the right side is positive. For i 1 aad b' 3, the left side for similar reasons is at most 0. For i = 1, b -2, n 2, the left side is negative by (a) and (b) of Theorem V. It remains to consider the case vwhere i - 1, b - 2, alnd nl 3; here the inequality becomes 2(e(n_,2) - m(n+l,2)) < _m(n-l.b). By (i) of Theorem V, the left side must be 1-k 2 less than 1, and, by (h), the right side must be greater than 1, since n-l - 2, and k'- 0 Subcase Ic: This subcase is disposed of by showing that it can be transformed into Subcase Ia, Subcase Ib, or a quasi balanced configuration; and in all of these possibilities d will have a smaller potential cost as a result of the transformation. The transformation will proceed in several steps, Since the configurations of / and ~ overlap, there is a wire V which drives both a and X; V must directly drive a junction 6C of level 2 or more. Take any wire W which does not drive d but which is on (. Delete W. If W is part of a 3-input (or more) element, then this element is chaniged into a 2-input (or more, correspondingly) element. If it is part of a 2-input element, then delete the element

86. and the output junction M' of this element, reconnecting the wires originally on OI to the j ulction 0o" other than X lwhich, originally, directly drove the element. It is not difficult to see that under this first step of the transformation the configuration is still well-formed, each junction drives an, and no input junctions are deleted. Furthermore, wires are either deleted or drive junctions of lower level, so that the estimated cost will decrease. This step is repeated for each junction O(of level 2 or more in the configurations of both atnd l. Subcase Id: Since ta ere are three wires directly driving /5, _m(S) > 3. Thus, m(g),> m(2n,b), by (g) of Theorem V. Case II: i - 2n t 1 (n' 2). Again there are four subcases, according to whnether (IIa) there are exactly two junctions d<and ~ directly driving 4 such that ~ is of level n_+1 and g is of level n, (IIb) the same, but / is of level n+ll-i and is n-ik (n > i > and n+ i k O) the configurations of / and a not overlapping, (IIc) the same as lib except that the configurations do overlap

(k > 0) and (IId) there are three or more junctions directly driving 3. Subcase IIa: Reasoning as in Subcase Ia, either m(O); m(n_+l,b) or m( )> m(nl,b), and inequality in the reverse direction holds for neither. Since m_(2n+1,b) - 2+ m(n-l,b), m(nb) bn bn'+l'( 2 m(b) r neL) > m(2n+l,b). bn bn+l Subcase IIb: Here m(r )' m(n+l1+i,b)., and m_( ) (n-i+kb). But, m(2+2l,_) 2+ t(nl b) n.....,bn+ and m() -- 2 + m~ b + m ( k) Therefore, in order n-i n+i+i-k' to prove m() m(2n+l,b), it will be suificient to prove that m(n-l.b) + m(n,b) m(n+l+ib) + m(n-ink, b) bn + bn+1 b- bn+l+i-k It suffices, therefore,to prove that bm(n+l,b) + m(n, b) - bi+lm(n+l+i,b) C m(n-i+kkb). By (g) and (h) of Theorem V, the left side is negative if b -? 3 and it is negative if i - 2. In these cases the inequality holds because the right side is positive. Also, if n = 2, i = 1, b = 2, the left side is negative. It remains to consider the case where - 1, b -2, and

88. n = 3; here the inequality becomes 2m(n+1,2) + m_(n,2) - 4(n+2,2) < m(n-14k,2). Here the left side 21-k is less than 1, by (g) and (h) of Theorem V. The right side is greater than 1, by (h) of Theorem V, since k - 0. Subcase Iic and lId:; The proofs here are exactly the same as in Subcases Ic and Id, respectively. This completes the proof of Theorem VI.