ENGINEERING RESEARCH INSTITUTE UNIVERSITY OF MICHIGAN ANN ARBOR LANGUAGE CONVERSION FOR DIGITAL COMPUTERS General Introduction ard Volume I The Logical Realization of Transliterative Functions by, -,.': ARTHUdR W. RKS CARLH. POLJ-AR DON W...WARREN JESSE B. WRIGHT Project M828 BURROUGHS ADDING MACHINE COMPANY DETROIT, MICHIGAN 1 June 1952

LA-i\A K 1-7 aaa

ABSTRACT The aim of this report in general is to present some theories concerning code conversion and the design of code conversion equipment for digital computers. Volume I deals with a restricted type of character-to-character conversion represented by the Transliterative Function. Such conversions do not require remembering previous states nor any time-space transforma-e tions. Some theory and a number of effective techniques are given for designing the required equipment-such design being presented at a level of considerable logical abstraction. The remainder of the report, to be published subsequently, will cover the following topics: Volume II will discuss the use of various types of equipmenttubes, relays, etc.,-as means (1) for carrying out the logical designs of Volume I, and (2) for effecting more general code conversions and format conversions —e.g., those involving serial-parallel transformations, shift codes. etc. Volume III will present detailed proofs and some relevant discussion of two topics presented in Volume I, concerning (1) minimal networks —in particular, the Balanced MS Net, and (2) the theory behind and validity of the technique for folding trees. ii

TABLE OF CONTENTS LANGUAGE CONVERSION FOR DIGITAL COMPUTERS Page ABSTRACT ii GENERAL INTRODUCTION iv VOLUME I, THE LOGICAL REALIZATION OF TRANSLITERATIVE FUNCTIONS 1 Section 1. Introduction 1 Section 2. Definition of Logical Elements and Networks 3 Section 3. Logical Design of Networks 9 3.1. Conjunctive Switches: MS (Multiplicative Switches) and MS Nets 9 3.2. Alternative Switches Using Other Logical Elements 22 Section 4. Techniques for Realizing Transliterative Functions 25 4.1. Decoding Functions 27 4.2. Encoding Functions 30 4.3, Arbitrary Transliterative Functions 31 4.4. Modifications to Provide Pulse Output 36 Section 5. Characteristics of Function Switches 39 5.1. Element Input Count and General Loading Properties 39 5.2. The Folded Tree Technique 43 Bibliography 53 Index of Terms 54 (To be published subsequently) VOLUME II. THE PHYSICAL REALIZATION OF CODE AND FORMAT CONVERSIONS VOLUME III. MINIMAL SWITCH THEORY AND THE FOLDED TREE iii

LANGUAGE CONVERSION FOR DIGITAL COMPUTERS General Introduction It is the purpose of this report to make a general survey of code and format conversion. This will not be a complete survey of the problem, but only a preliminary investigation which is designed to make clear the general nature of the problem, to formulate some of the chief available techniques, and perhaps to serve as a foundation for more detailed studies of such conversions and the design of equipment therefor. Code conversion is a special case of language translation, and it is useful to consider it in this light. While no sharp lines can be drawn between what is normally called a code conversion and an ordinary linguistic translation (e.g., German to English), the difference can be indicated roughly. Basically, a code conversion is a translation at the character level, while an ordinary linguistic translation takes place at the sentence level. Later in this section the concept of message transliteration will be defined; put in terms of this concept, the difference is that code conversions are primarily message transliterations, while ordinary language translations are not.In accounting work the initial data and end result are expressed in a natural language whose alphabet (in this part of the world) consists of Latin letters, Arabic numerals, and a few auxiliary characters such as the dollar sign. Since electronic and electro-mechanical circuits generally work most easily in a binary system, most machine languages have two basic characters: represented in this report by'0','1'. Thus, an adequate machine language is an artificial language with two basic characters (bits), which characteristically represents alphanumeric characters by relatively short sequences of bits so chosen that the translation between the natural language and code (and hence between codes) is essentially a message transliteration. It should be noted that many machine languages are not quite binary but are almost so. Consider for example a representation of data on a magnetic tape which is six channels wide. On such a tape there is a natural grouping of bits into sequences of six; the edges of the tape constitute, so to speak, parentheses. This grouping provides information in the technical sense of that term, since a machine when turned on in the middle of a message finds, not a continuous sequence of O's and l's, but iv

rather a sequence of clearly defined sequences each of which consists of six O's and/or l's. The same point holds with regard to the usual organization of characters into "words" inside a machine. Thus a typical machine language has two primary basic characters ( 0 and 1 or their equivalents) and sometimes secondary basic characters-e.g., ) or its equivalent. As a consequence it is convenient in discussing code conversion to apply a notion of character broader than that of basic character. For example, in discussing the tape language mentioned above it is often convenient to regard the characters not as l's and 0's but as ordered sextuples of l's and O's. For the purposes of this report and from a syntactical point of view, a language L consists of character-type* class, C, and formation-rule class, F, determining a set of message types {Ml, each message being a finite sequence of character-tokens of class C:m, m2,..., mn Though code conversion is largely a matter of syntax rather than of semantics, it should not be overlooked that a language has a semantic (meaning) dimension, as well as a syntactic (formal) one. The concluding statement of the previous paragraph does not constitute an entirely adequate definition of'language' because, among other things, it ignores this dimension. Thus the statement in question does not establish the proper identity (or diversity) criteria for codes. For example, there are two teletype codes, each comprised of the same character-type class (thirtytwo five-bit sequences) and the same formation-rule class (i.e., the same sequences of characters are allowable messages in both), which nevertheless are different because different five-bit sequences ( 01000 and 00101 ) are employed to represent a'~' Not all the syntax of a machine language is represented by the use of basic characters other than 0 and 1. Often, perhaps usually, * As used herein, the terms'character-type' and'character-token' are synonymous with the terms'character-design' and'character-event' respectively. Since there is no standard terminology on this point, either set of terms seems permissible although'type' and'token' would appear to be preferable to'design' and'event' for the following reasons. First, the former terminology is older (cf. The Collected Papers of Charles Sanders Peirce, vol. IV, paragraph 537) and an existing terminology should not be changed without due cause. Second.,'type' and'token' may be used alone as abbreviations for'expression-type' and'token-type', whereas'event' and'ldesign' are somewhat misleading. Third, it is often desirable in semantic work to take as a token, not a single event (e.g., a single reading of'red'), but a substantive or sequence of events (e.g., one occurrence on a given page of a specific token of a book throughout the life of that book). v

syntax is represented by sequences of bits in the same way that alphanumeric characters are represented. Thus, spaces, paragraphs, indentations, and various kinds of brackets that occur in a message written in a natural language may be coded in the same way that alphanumeric characters are coded. There is an interesting consequence of this: namely, a coded "message" can contain two or more syntactical structures. Consider as an example a message written in a natural language which is organized into unequal-length words, sentences, paragraphs, and pages. This message can be translated into a machine language which is organized syntactically into equal-length words and blocks in such a way as to preserve the syntactical structure of the original message, in the sense that the original message can be recovered by translating back into the natural language. Thus the coded machine repre-. sentation of the original message contains both the original syntactical structure and the syntactical structure of the machine language.* The concept of translation can now be applied to languages whose characters are finite sequences of two basic characters. Consider two languages, L and Lt, consisting of character-type classes, C and C' and formation-rule classes, F and Ft' determining sets of message-types [Ml and I{Mt3. Any function, ~, which maps )M1 into M'tl is called a translation function. Such a function is called reversible if and only if Mle M2. D. M(M2) X 0(e) If ~ is a reversible translation function from L to L', no information is lost in translating by means of it; that is, any message M1 may be completely recovered from its translation O(M1) In this report we are interested only in translation functions which are reversible or almost reversible. ** Furthermore, we are not interested in all such functions. Thus translation functions such that for long messages M any character of Mt requires for its determination simultaneous storage of all characters of M, or even such that the first character mi cannot be produced until all of M is scanned, are not very useful from the point of view of mechanized accounting. However, we know of no sharp lines dividing the translation functions which are useful in mechanized accounting from those that are not. The most that can be said is that the interesting translation functions belong either to the special See for example the internal language of the Michigan report, The Languages for an Electronic Accounting System, Sec. 2.3.1 and 2.3.2. ** For example, the translation discussed in the report previously cited is not completely reversible. E.g., 37.00 and 37 would both translate into the external language as... 037.000 vi

class of message transliteration functions (to be defined below) or strongly resemble members of this class. It is now possible to define the concept of a transliterative function: a single-valued function whose domain and range are sets of finite sequences of O's and l's -each set (domain and range independently) consisting of sequences of equal length. (Later this definition will be restricted to exclude non-information-carrying bits-see section 4.),Consider now a translation function 0 from L to L' which is explicitly defined as follows: (ml,m2,...) = ~(ml), ~(m2),..., where P is a transliterative function and ml,m2,... is an arbitrary message of L (the individual mi being character-tokens of class C of L ). Any function,,, so defined is a message transliteration function. So far, the format arrangement of a message has not been discussed. Indeed it will be noted that our concept of translation function has no place for changes in format, since any two messages which differ only in format arrangement will be related to one another by the identity translation function, However, it may be assumed for the present that the messages are transmitted a character at a time, bits of a sequence representing a character-an mi -all being available at one time (compare the definition of a language given earlier). Under these circumstances a message transliteration could be most simply executed as a character-by-character translation. For this purpose the following kinds of equipment would be required: (1) a function switch to realize A, (2) memory for one character, (3) whatever memory is needed for buffering purposes (i.e., velocity matching), and (4) a few fairly simple control circuits. Since we are interested in code conversions that are message transliterations, or nearly so, it is clear that a function switch is an essential part of all code converters discussed in this report. But function switches have other uses than in code conversion, so it seems desirable to study function switches per se. This will be done in Volume I. Function switches may be realized (constructed) with various circuit elements: relays, vacuum tubes, mechanical lever arrangements, etc. Not all such elements are equally flexible, however. For example, crystal rectifier "and's" and "or's" cannot be combined as freely as can, say, d-c vacuum-tube "and's" and "or's". On this account it is useful to think of the designing of a function switch as progressing through three stages. The first is the construction of an abstract logical design based on logical operation. The second is the translation of this design into one in terms of elements which are idealized representatives of equipment. The vii

theory developed by Shannon (6, 5, 4, 12), Aiken (11), and Brown and Rochester (8) is essentially at this second level, for to a large extent they base their work on relays, tubes, and diodes, respectively. The third stage is the construction of the complete circuit design with all details indicated that are needed for actually assembling the physical switch. The last of these three stages is beyond the scope of the present report. The first two stages will be treated in Volumes I and II, respectively. In code conversions which are not message transliterations, memory circuits often play a more dominant role. For example, if the incoming message is expressed in a shift code, the last shift character to have occurred must be remembered. Again, in converting from unequal-length to equal-length numbers an incoming number must be scanned (and hence remembered) before it can be positioned properly and before dummy characters can be added. It should be noted that while such a converter realizes a non-trivial translation function (one in which it is not the case that 0(M) = M ) it requires only a rudimentary function switch, so that the circuit emphasis is upon memory. For this reason it is doubtful that it should be called a "code converter" at all. It is perhaps more properly called a "format converter". There are other conversions which doubtless should be called format conversions and not code conversions. All merely space-time conversions fall in this class: e,g., a "serial-serial to parallel-parallel conversion". The translation function governing such a conversion is completely trivial, since for all messages, M, O(M) = M (at least if the ordinary concept of character is maintained), and it is for this reason that such conversions are not properly called code conversions. Nevertheless, any study of code conversion should be extended to include these format conversions for two reasons. First, such conversions involve the same kinds of equipment as are required for code conversion. Thus in a "serial-serial, parallel-parallel" conversion, where the instantaneous rate of flow of information out of a converter is not always equal to the input rate of flow, memory for buffering is required as well as distributing circuits for rearrangement of the data. Second, in actual practice such conversions are often combined with bona fide code conversions. For these reasons it is convenient to make a rough-and-ready classification of conversion into three kinds, depending on the characteristics of the equipment required: Code Conversions-those requiring primarily function switches; e.g., conversions between six-bit codes, four-eight codes, and five-bit shift codes. See for example The Design of the Languages for an Electronic Accounting System, Sec. 2.3.2 and 2.3.3; and The Prograi Translations: Tape Language to Internal Language. viii

Format Conversions-those requiring primarily memory units and distributing and arranging equipment; e.g., space-time conversions and simple equal-length-unequal-length conversions. Code-and-format Conversions —those requiring a substantial amount of both function switch equipment and memory and distributing equipment; e.g., a conversion from a serial-parallel, unequal-length-word, five-bit shift code to a parallel-parallel, equal-length-word, foureight code. It is desirable to have a single name for all of these conversions.'Language translation' seems too restrictive, since a mere format conversion hardly involves a translation between two different languages. On the other hand,'language conversion' seems satisfactory, since'conversion' is flexible enough to cover all the cases, and we are certainly dealing with languages. Another example of a conversion that is both a code and a format conversion is that between the coded language and the internal language designed by the Michigan Project.** In fact, an appreciable proportion of the translation which will occur in a highly developed automatic accounting system is of a comparable degree of complexity. Under these circumstances one would expect in a report of this character a discussion of the logical design of converters for all three types of conversion. But it must be remembered that general design techniques for such converters are being discussed rather than the design of specific converters. Now the logical components of code-and-format converters are the components of code converters and format converters as well. Hence it seems fairly sufficient at this level of generality to discuss the design of code converters and format converters, omitting any detailed discussion of codeand-format converters as such. An additional reason for this omission is that any example of a code-and-format converter is likely to constitute enough material by itself for a fairly substantial report. In reading this report, however, it should be kept in mind that the individual code converters (Volume I) and format converters (Volume II) are emphasized primarily because this seems a suitable way of discussing the logical components (and their interconnections) for all three kinds of converters. The term'language conversions' was suggested by Don Stevens. See the references in the penultimate footnote preceding. ix

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN VOLUME I THE LOGICAL REALIZATION OF TRANSLITERATIVE FUNCTIONS 1. Introduction Volume I is a study of the design of equipment for realizing Transliterative Functions (essentially, single-valued functions of sequences of O's and l's of uniform length to sequences of O's and l's of uniform length-see Def. 4, section 4). Such devices will be called Function Switches. They may also be defined in more customary terms as IRE (1)** function switches*** modified by requiring (1) that a simultaneous application of signals to the input will cause the simultaneous appearance of the corresponding output signals and (2) that none of the auxiliary circuits for timing, pulse generating, etc., be regarded as part of the Function Switch. These requirements do not prevent the bits of a sequence from coming serially into the mechanism (of which the Function Switch is a part). The circuits for handling such an input, however, would not be part of the Function Switch proper as the term is used here. The term Realization is formally defined in section 4. This formal meaning, however, is simply an attempt to make precise, in a particular context, the generally understood meaning of the term which is adequate for all but the most'formal' occurrences of the term throughout the report. In general, technical terms when used in special sense peculiar to this report will be capitalized and will be underlined at the first occurrence. The index will show where the term is introduced or defined. Such numbers appearing in parentheses after an author or term refer to the bibliography at the end of the volume. The IRE definition states that a function switch is "a network or system having a number of inputs and outputs and so connected that signals representing information expressed in a certain code, when applied to the inputs, cause output signals to appear which are a representation of the input information in a different code". In the- terminology of this report the IRE function switch is a "language converter".

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN As was pointed out in the General Introduction, the design of Function Switches is broken down into three stages: logical, idealized equipment, and. complete circuit design.. The present volume is devoted exclusively to the first of these stages. The principles of the propositional calculus are used freely. "Logical elements" (assumed realizable in equipment) are defined having the properties of conjunction, disjunction, and nagation, and symbolic networks are constructed by "wiring" these elements together to produce switches. The aim of the volume is achieved by first giving constructive procedures for a few basic component-or "building-block" — switches which may not in themselves constitute a useful realization technique; next, in terms of these components, defining switches for certain special kinds of Transliterative Functions; and finally, giving techniques for combining and modifying these switches to give switches realizing an arbitrary Transliterative Function, In section 2, the basic concepts used in the construction and study of the abstract logical circuits are defined. All the methods for constructing Function Switches are given in sections 3 and 4 with the exception of that for the folded tree, which is discussed in section 5 in connection with minimality and loading properties of switches. 2

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN 2. Definition of Logical Elements and Networks This section introduces the basic logical elements which will be combined into symbolic circuits (representing physical Function Switches) by techniques to be considered later. It gives rules for the combination of these elements into networks and places some restrictions on the types of circuits to be considered. Finally, it defines and discusses some general properties of these logical networks, which may have some significance for their physical realization and which may be used as a basis for comparison. The logical operators: conjunction, disjunction, and negation, are chosen as the basic elements. It is assumed (and will be shown in a later volume) that they can be realized by physical equipment (e.g.o, pulse control units, relays, tubes, etc.). Each such piece of equipment is represented by a geometric figure or enclosure along with a'set, W, of directed line segments associated with it (see Figure 1). The line segments correspond to the Inputs and Outputs of the physical element and will be referred to as Wires. The figure together with its wires is called a Logical Element. Consider a Logical Element, E. Let W represent the set of wires associated with it. Then the inputs of E form the subset, WI, composed of all the wires of W directed toward E (i.e., with the arrowheads pointing toward E ). Only the inputs may be'driven —i.e., put into one or the other of two electrical states, 0 or'1 t, by connection to an outside source. Any subset Wo of W may be denoted as the set of outputs of E provided. that the union of inputs and outputs is the set W. The output will be the single arrow (wire) directed away from the Element unless otherwise specified, The Logical Elements are defined as follows: The square in Figure l(a) represents a piece of equipment with two or more inputs and a single output which is in the 1 state if and only if all of the inputs are in the 1 state. Thus it represents the logical operation, conjunction, and is referred to as a Conjunctive Element. The triangle of Figure l(b) represents a Disjunctive Element: its single output is in the 1 state if and only if at least one of its inputs is in the 1 state.' The circle enclosing an'Nt, Figure 1(c), is a Negation Element-a device with a single input and a single output having the property that the state of the output is opposite to the state of the input. The above three Primitive Elements are sufficient for constructing all of the networks to be considered and all such networks will be assumed, 35

(n INPUTS) (r INPUTS) CONJUNCTION DISJUNCTION NEGATION (a) (b) (c) PRIMITIVE LOGICAL ELEMENTS FIGURE I. P'pq q p 1 q,' p.q N P'q P{=p~p} P{=p plq ~~~~~~~P =P STANDARD NOTATION ABBREVIATED NOTATION RELAY REALIZATION (a) (b) (c) AN AUXILIARY LOGICAL ELEMENT THE "DOUBLE-AND" FIGURE 2.

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN in the interests of simplicity, to be compounds of these Primitives even though, in certain applications, another choice of Primitives would seem to serve as well or better. As an example of an auxiliary compound element, the Double-and is introduced in Figure 2. This element is a logical interpretation of the relay (Figure 2c) as it is frequently used in contact networks (cf. section 5). It is represented as a compound of Primitive Elements (Conjunctive) in 2(a) and in convenient abbreviated symbolism in 2(b). The labelling of the input pair (sp, p) represents the standard relay interpretation which is the only mode of operation to be considered. If tubes are to be used. it is natural to define enclosures (elements) representing the stroke functions. With the proper interpretation of voltage levels, a double triode corresponds to the disjunctive and the pentode to the conjunctive stroke function; these elements are discussed in section 3.53. Although such compound elements as the two above are of secondary importance to this report, the possibility of such alternatives deserves emphasis because of their usefulness in more specialized applications. The Function Switches considered in Volume I will be compounded from the Logical Elements exclusively, though not all possible combinations will be considered. The allowable combinations are defined by the following rules whose primary purpose is to ensure that each output will be a function of the inputs. Such a combination is called a Network. 1. Any one of the Primitive Logical Elements, or-the "degenerate element" —a single wire with terminals labelled'input' and'output', constitutes a Network whose Inputs, Outputs, and Wires are those of the Element, 2. If F1 and F2 are distinct Networks with designated inputs and'outputs, they can be combined to form a compound Network F as follows: Al1 All inputs of F1 are designated inputs of F.2 Each input of F2 must be designated an input of F or it must be connected to a single output wire of F1. (Several inputs of F2 may be connected to the same output wire of F1 ).3 No other connections between FL and F2 are permittedo, --- ~~5

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN B.1 All outputs of F2 are designated outputs of F.2 Every output of F1 which is not connected to an input of F2 must be designated an output of F.3 Any inputs of F1 or F2 may also be designated outputs of F C. The Wires of F are defined to be its inputs together with its outputs. The force of 2C is that the internal connections of a network — unless they are Network outputs-are not called Wires of F but must be referred to as Wires of the components, F1, F2, etc. The rules B.1 and B.2 (omitting B.3) define a set of outputs which is adequate for all specific Switches* discussed in this report and will be referred to as the Natural Outputs. Rule B.3 will, of course, be assumed in any general remarks or theorems concerning the class of Networks. Some typical examples of Networks are shown in Figures 3a, 3b, and 5b. Figure 5c is an application of the Double-and notation to the Network of Figure 5b. It is the philosophy of this volume to treat Networks as logical entities. Nevertheless, there are frequent allusions to concrete applications and it is to be expected that some readers will carry this translation into physical equipment even further. It should be pointed out, therefore, that the Networks are most easily interpreted in terms of static operation; i.e., the 1 and 0 signals or states of the Wires should be thought of as "high" and "low" d-c levels rather than as pulses, The ramifications of the pulse or dynamic interpretation are taken up in section 4.4. Although the general question of which of a number of circuits or Networks is "best" for a particular job must remain unanswered (or, perhaps even unformulated), two criteria for comparison which appear to be of some use are presented below. The first is the Element Input Count denoted by'C'. It is the total number of inputs for all of the Logical Elements of the Network. The term'Switch' will be used frequently in referring to a specific Network. 6

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN The network of Figure 5(a) has 12 three-input Conjunctive Elements and so C= 36, while the "tree" of Figure 5(b) has 28 two-input Elements and C = 56. The Element Input Count is considered a rough index of the complexity of the circuit relative to the type of Element used in its construction. Its significance depends on the particular physical elements used in its realization. Thus in trees (pyramids) designed by Aiken's (1) techniques the number of control grids is a specific interpretation for the Element Input Count of the corresponding abstract circuit. The second property to be defined is a loading property. Two types of loading are distinguished for each Input of a Network, serial loading and parallel loading. To determine the serial loading of an input q, consider the set of all sequences of Logical Elements of the Network, J(E1,E2,...,Em)., where (1) q is an input of E1, (2) the output qi of Eil is connected to an input of Ei (and possibly to other elements), and (3) the output of Em is an output of the Network. Such sequences are called Chains. (A Conjunctive Chain is one composed entirely of Conjunctive Elements.) The length of a Chain is the number of Logical Elements it contains. Pick out any Chain L of this set which has a length equal to or greater than that of any other Chain in the set, Then the length of L is defined to be the Serial Loading Coefficient of q Although no use is made of it here, it is interesting to note that the idea of serial loading may be extended by defining the "serial loading coefficient of a logical element, E" in an analogous fashion, the output of E replacing q in the definition given above. The Parallel Loading Coefficient of a Network input, q, is defined as the number of Logical Elements to which q is directly connected. As in the case of serial loading, this idea may be extended to any Logical Element. The parallel loading of an input, q, does not describe the situation completely. This can be done only by considering the parallel loading coefficients of all the Logical Elements appearing in Chains having as a first term a Logical Element with q as an input. These coefficients might be displayed in the form of a matrix to be associated with q. For the special cases to which it will be applied in this report (with one exception in section 5), the concept as defined is adequate. The loading characteristics of a Network will be presented as a set of Loading Couples: number pairs, (S,P), one for each Network input, where S is the Serial and P the Parallel Loading Coefficient. In Figure 3b, the Loading Couples for all Network Inputs are the same, (1,8)., In Figure 5b the loading of the two wires of a pair is the same: for a 7

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN wire of P or of P2, the couple is (3,2); for P3, (2,4); and for P4, (1,. The significance of these numbers varies with the physical equipment considered for the realization. For example, in a relay tree the serial loading and the parallel loading for Logical Elements is of little significance, while the Parallel Loading Coefficient for the switch inputs is of great importance: it is the number of transfer contacts operated by an input relay. It is studied in section 5 and more extensively in Volume III. On the other hand, serial loading is of considerable interest if the circuit is to be realized by crystal rectifiers. 8

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN 3. Logical Design of Networks The purpose of sections 3 and 4 is to present techniques for "?constructing'l-at the abstract level of design-switches which realize Transliterative Functions. It has been found possible to realize all Transliterative Functions by simple combination of a very small number of components (Switches). Since these components may have wider application than it is the purpose of this report to consider, they will be presented separately in the present section, independently of their use in realizing Transliterative Functions.. In section 4 this application will be considered in detail. Section 3 will, however, anticipate the subject matter of section 4 to the extent that the components are capable, without modification, of realizing functions. The present section will be divided into two subsections: 3.1. "Conjunctive Switches: MS (Multiplicative Switches) and MS Nets" showing first the construction and operation of thesecomponents, and, second, a more detailed discussion of two -important specific examples, the "Tree" and the "Balanced MS Net". 3.2. "Alternative Switches Using Other Logical Elements" which describes, primarily, the use of stroke function elements. The definitions of Switches in this section (with one exception) have the form of constructive procedures: i.e., given the proper specification of input sets, use of the rules laid down by a definition will produce a unique Switch. This aspect will be pointed out specifically for each definition as it is presented. 3.1. Conjunctive Switches: MS (Multiplicative Switches) and MS Nets The Multiplicative Switch-hereafter referred to as'MS' —derives its name from the mathematical concept Cartesian Product.* The Cartesian Product idea, which is fundamental to this volume, is most frequently applied to sets of wires. To facilitate its application to Networks, a Given a sequence, 4, of sets, S1,...,S, the Cartesian Product of J is the set of all possible n-term sequences such that the ith terms of any sequence belong to Si Note for future reference that this operation is associative: (S1 X S2) X S3 = S1 X (S2 X S3).

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN closely related Concept called the "Cartesian Conjunction" will be defined. Consider a Switch A, a collection, B, of disjoint sets, I...In, each consisting of two or more input wires of A, and the set, O, of the output wires of A; then Def. 1. A subset, S, of 0 is called a Cartesian Conjunction of a, denoted'CC( )', if there is a 1-1 correspondence between the Cartesian Product of V and S such that if we is the wire of S corresponding to e, an element of the Cartesian Product, then all Conjunctive Chains with we as output originate in e and at least one Chain is connected to each wire of e (e. g., see Figure 3a or 5g).* In all the Switches explicitly discussed in this volume CC(S) will be unique and will be referred to as the Cartesian Conjunction of | although in general there may be several distinct sets which are Cartesian Conjunctions of a given. The Cartesian Conjunction operation can be iterated: i.e., the Ii sets may themselves be Cartesian Conjunctions. This leads to: Corollary to Def. 1. Cartesian Conjunction is associative; i.e., (CC( 1) X CC(y)) X CC(93) = CC(~) X (CC($2) X cC(P3)) This follows directly from the relation to Cartesian Products which is associative. Throughout the report, the number of elements in a set or sequence, S, will be denoted by the expression N(S). Applying this notation to the present case, clearly n N(CC(4)) = fl N(Ij). j=l The following property is also worth noting. Given an input set, I, a grouping into a collection,', of disjoint subsets Il,.,In, such that I = U I.,and the resultant CC(;), it is not possible, on j=1 n the same I, to form a different grouping, 4' (of subsets I', I = -U It) p j=l J such that CC(') = CC(;); and, conversely, two unequal output sets The operating condition being established here is that, to each e corresponds an output wire which is in the 1 state if and only if every wire of e is in the 1 state. Note that CC(J), unlike the Cartesian Product, is independent of the order of the sets in. 10

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN cannot be the Cartesian Conjunction of the same A. These statements follow easily from the definition of Cartesian Product. An MS is a Switch for producing the Cartesian Conjunction — specifically: Def. 2.* A Multiplicative Switch (MS) is a network whose set of inputs, I, can be grouped into a collection, &, of n disjoint subsets such that I = U Ij, (N(Ij)' 2) in such a way that the set of outputs is CC(A), each output wire being the output of a single n-input Conjunctive Element whose inputs are the wires of the corresponding element, e, of the Cartesian Product of 4. The constructive force of this definition is that, given an input set I and a partitioning, 2, then one and only one MS can be\ produced.** Figure 3a shows an MS with the input set I of 7 wires grouped into subsets, Il of 3 wires and 12 and 13 of 2 wires each, ahd with the Cartesian Conjunction represented by the 12 output wires in accordance with formula (1). For MS's' in general the number of Logical Elements (Conjunctive) n required is equal to the number of output wires, jTF N(Ij), and the Element Input Count is given by the formula n C = n f N(I) j=1 One of the essential characteristics of a Multiplicative Switch is that every sequence of states appearing on its inputs has the same number, k of l's. This property might be taken as the basis for defining a broader class of switches which includes the class of MS's as a subclass, Such Switches would realized Transliterative Functions whose domain sequences each have a fixed number, k, of l's, and whose range sequences, as for the MS (cf. Decoding Function, section 4), each have a single 1 A switch of this class would consist of a set of k-input Conjunctive Elements, one for each sequence in the domain, the Element inputs being connected to the k switch inputs which register l's corresponding to the associated domain sequence. This type of switch would, for example, decode a 2-out-of-5 code which cannot be handled by the MS. For this purpose, Switches with inputs or outputs permuted are not considered distinct- the problem is discussed in more detail in connection with MS Nets (last footnote, p. 19). 11

01 02 Li ttt12 ~ P~ P2 P3 P4 MS NET Lj C-~c'L~r) PI PZ P3, P4 f,~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Ier EXPONENTIAL SWITCH MS (b) (c) (a) FIGURE 3. EXAMPLES OF NETWORKS

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN The Serial Loading Coefficient for any input wire is obviously 1; the parallel loading, however, is dependent on the subset, Ij, to which the wire belongs and the loading characteristic is expressed, for a wire w — of I., by the Couple J n (l5 T (I (J) j=l,Eog., for the MS of Figure 3b, the Loading Couple for any wire of Il is (1,4); for any wire of 12 or I, (1,6). The MS shown in Figure 3b deserves special mention, It is a familiar piece of decoding apparatus and is characterized by the property of having its set of input wires grouped into pairs (i.e., for all j=l,,..,n, N(Ij) = 2 ). Henceforth, such input pairs will be referred to as Polar Pairs because of the common mode of operation which uses such a pair to represent a truth value-variable (or a binary digit-position): a signal on one wire meaning ttrue' (or 1 ) and a signal on the other meaning'false' (or 0 ), which requires that the two wires be in opposite states, i.e., polarized. The Switch itself will be called an Exponential Switch because of the analogy between its relation to the general MS and the mathematical relation of exponentiation to multiplication.* The concept of Polar Pair provides motivation for the introduction of a component which, though not itself a conjunctive switch, is frequently used as an auxiliary to such switches: the Polarizer. The purpose of this Network is to convert a set of inputs representing one variable per wire into the Polar Pair representation. This is done by the obvious device, shown in Figure 4, of introducing a negation element in parallel with each original wire. Clearly, given a set of inputs, the Polarizer is unique. The primary importance of the Polarizer in the development of the present theory is that it allows the existence of Polar Pair inputs to be assumed, without loss of generality, whenever it is convenient to do so. The analogy is particularly interesting if the set-theoretic basis for exponentiation (as related to Cartesian Product) is considered where, letting m and n represent the cardinality of two sets, Sm and Sn, mn is interpreted as the number of possible mappings of Sn into Sm, which is also the cardinality of the Cartesian Product, Sm X...n factors...X Sm The analogy can be followed through easily to produce a 1-1 correspondence between the set of mappings and the set of switch outputs. In the present case, n is, as before, the number of subsets of the set of inputs, and m is 2. Note that the definition could apply equally well for any integer, m, other than 2 (N(I1) = N(I2) =... = N(In) m); the restriction to m = 2 is merely to effect a slight simplification in the present report. 13

ENGINEERING RESEARCH INSTITUTE *~ UNIVERSITY OF MICHIGAN'' I......... -....' [ n Input Wires Figure 4. Polarizer The final definition of this subsection provides a means for interconnecting MS's to give greater flexibility and at the same time provides limitations which keep the resultant class within reasonable bounds for purposes of analysis. Def. 3. An MS Net is a Network composed entirely of MS's and (1) having a set of input wires, I, which can be grouped into a'collection,, of subsets, I = U I, such that CC(a) is:a subset of the set of Network outputs;* and with the MSts connected as follows: (2) If IM is a subset of the input set of an MS (as in the definition of MS) and if S is the set of outputs Df an MS or one of the I.j of the MS pet, then any connection between the two sets requires that I. = S (i.e., the two sets have the same number of wires and the wires of Io are connected to those of S in 1l1 fashion), And similarly if a wire of S is designated.oas a Net output, then the entire set S must' be so designated. This definition is the exception to the constructive procedure policy. The rules of the definition do not lead to a unique switch, given specified input sets. The definition merely defines a broad class of networks to which some of the most useful Switches (e.g., Trees) belong. The set of outputs of an MS Net may consist of any outputs allowed by the definition of Network which satisfy (1); however, most of the useful examples explicitly referred to will have as their designated output set the set of Natural Outputs. Similarly with inputs: only the Polar Pair case will be considered in detail, 14

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Some of the conditions of this definition will bear amplification. The explicit requirement that the MS Net be a Network is necessary to rule out feed-back loops which are unnecessary in code transliteration. Condition (2) is of some interest and will be discussed in more detail in Volume III of this report. For the present it may be said that its purpose is to prevent Splitting of MS output sets-some wires connected to one MS sub-input, some connected to another —a situation which has thus far resisted general analysis to a degree altogether out of proportion to any advantages apparent in the procedure. It should be pointed out, however, that condition (2) does permit a phenomenon which shall be referred to as Branching: in the terms of the definition, an S, if taken in its entirety, may be identified, in the prescribed manner, with more than one Io and/or be designated a Net output. Figure 3c is an MS Net (with Branching), the shaded enclosures representing the MSt's, 01 = CC('), o, = tP1,,P2 and 02 = cC), y = lP1,P2,P3 3 The output set consists of the union, 01 u 02 Figures 5 and 6 represent a type of MS Net which is of particular importance and is characterized by having no Branching; i.e.,, an MS output (or Net input) is directly connected to exactly one MS input subset or is a Net output (not both). Most MS Nets to be dealt with are of this type and will be referred to as Simple MS Nets. In such a Net it is easily seen that the outputs are the Natural Outputs and constitute precisely the Cartesian Conjunction of the input subsets. The construction of an MS Net can be expressed notationally by a Construction Formula. This formula gives the output of the Net as a function of its inputs,. The connective, tX', denotes Cartesian Conjunction, a parenthesized expression denotes and MS (if an expression occurs more than once it represents a Branching of the output of the MS), and the connective, u, indicates that the Switch output set is the union of the output sets of the MS's so joined —no additional connections being made. (The symbol Pj will be used rather than Ij whenever the input subsets are Polar Pairs.)* The MS Net of Figure 6 for n = 4 is expressed by the formula (P* X P2) X (P3 X P4) Although no such cases arise in this report, it should be pointed out that the occurrence of identical MS's (i.e., described by identical Formulas) has not been provided for. The situation can be handled easily by attaching subscripts to the parentheses if distinct MS's are to be formed. 15

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN and that of Figure 3c by (P X P) u (PP1 X P2) X Pu). (3) The'u' in formula (3) indicates that the output is produced by two MS's. Note that (2) represents a Simple MS Net (no Branching), since no expression is repeated, but that (3) has Branching as indicated by the repeated occurrence of'(P1 X P2)' The associative property of Cartesian Conjunction offers a method of constructing a variety of Nets to produce the same output function. For example: (P1 X P2 X P3 X P4) (2') (((P1 X P2) X P) X P4) (2") represent alternative methods (i.e., alternative MS Nets) for realizing the output given by formula (2). Formula (2') yields the Exponential Switch of Figure 3b, and (2") the Tree of Figure 5. Having established all of the basic conjunctive components and discussed some of their general properties, two specific MS Nets of particular importance will now be considered. The Standard Tree. The most succinct characterization of a Standard Tree ie by means of its Construction Formula, ((...(((Pi X P2) X P3) X P4) X...) X Pn) From this formula it can be seen that the input set (I) consists of a collection ($) of n (Polar*) Pairs, P i,...Pn; that Pj is conjoined with the preceding P's by constituting one of two input subsets for an MS whose other input subset is (in effect) P1 X... X P.j_; and that the Tree output is the output of the "final" MS —the one having Pn among its Inputs. It is clear, also, that the Standard Tree is a Simple MS Net, since no expression is repeated in its Construction Formula and the Formula expresses precisely CC(1). The only mode of operation to be considered for the Tree (as well as for most other Switches) is with Polar Pair inputs; therefore it is convenient to use the P. notation from this point on. It must be pointed out, however, that, for purposes of constructing the switch it is not intended to impose any restriction on the manner in which the inputs are energized —it is required only that the input set satisfying I = U I has N(Ij) = 2 for all j. 16

++ Pi P2 P3 P4 (a) 1 I I I ~~~~(b) V C Pi P2 PP2 PP FIGURE 5. STANDARD TREE

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN As a constructive procedure, it is clear that, given the input set, I, and its collection of subsets, 4 = Pj}, a "unique' switch is determined —unique, that is, with the usual minor qualifications concerning permutations (see last footnote, p. 19). Figure 5 represents a typical Standard Tree. In 5a the basic elements are MS's. In 5b the MS's are isolated by the heavy-line enclosures and their internal Elements shown in detail. Figure 5c shows the abbreviated Double-and notation which derives its simplicity from two important characteristics of the Standard Tree: (1) the Conjunctive Elements always occur in pairs; and (2) all of the Conjunctive Elements (or, equivalently, the Double-ands) of an MS (those constituting a vertical column in the diagrams) are connected directly to one and only one Pj -each such column is said to form a Bay. Characteristic (1) is common to the larger class of "Folded Trees" (which is discussed in section 5 and includes the Standard Tree), while (2) is peculiar to the Standard Tree. In Figure 5c all the Double-ands in a column are associated with the Pj appearing below it. The element input count for the Standard Tree (and, in fact, for Trees in general)- is given by the formula C - 8(2n-1 - 1) * where n is the number of pairs in the input. The number of conjunctive elements is, of course, C/2 The loading figures will be given for a Pj, since they are identical for the two wires. Both the serial and parallel loadings vary with the input pair and are given in the usual Couple notation by (n-j+l, 2j-l) for j-2. For P1 the value of the Couple for j=2 applies. The second (parallel) Coefficient here is of special interest (particularly in relay networks), since it may become excessively large as j increases. The folding process, described in section 5, is an effective method for distributing this load over the Pj The Balanced MS Net. The second of the specific Switches to be described is, again, a Simple MS Net. The designation'Balanced' is In line with the general policy of this section, this formula is for a "'static" tree. The "dynamic" tree, which is more common in the literature and which is discussed extensively in section 5 and in Volume III, has the formula C = 4(2n-1) The concept of this Switch was derived from Brown and Rochester (8), where a crystal diode version was presented and discussed in somewhat unprecise language. 18

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN derived from the fact that each of its MS's has exactly two input subsets*I = I, u 12 -and that N(I1) is as nearly equal to N(I2) as possible. Here, as in the case of the Tree, the definition is in terms of Polar Pair inputs. The switch will be defined recursively by giving rules for its construction starting with the output and proceeding systematically to the input. n The Balanced MS Net with input set I = U P. is constructed as follows: j=l 1) Designate a set of 2n wires as Network outputs. They will con itlute the output of a si.ngle MS with I = I u 12 and N(I1) = 2 2(n, i)/ 2 **, fN(I2) =2Ln/2] 2) Let I be an input set of an MS of a partially completed Net such that I has not as yet been connected to any other MS,- and N(I) = 2x for some integer x.*** a) If x - 2 then connect in 1-1 fashion to I the output, O, (N(O) = N(I) = 2X) of an MS with input set[x2~ I, u 12 having N(I1) = 2[(x+l)/21 and N(I2) b) If x - 1, then designate the wires of I as an input pair of the Net. Figure 6 shows a number of Balanced MS Nets. Consider the case of n = 5, I = P u P2 u... u P5. There are 25 = 32 output wires for M4 The inputs of M4 are split as evenly as possible into Ii, N(I1) = 2[(5+1)/2J= 23 = 8 and I2, N(I2) = 2[5/2] = 22 = 4. In turn, the inputs of M2 are split into Ill, with N(Ill) = 2[(3+1)/2] = 4 and I12, with N(I12) = 2[3/2 = 2. The Construction Formula for this switch is obviously (((Pi x P2) X P3) X (P4 X P5)) SuchMS'smay be referred to as'two-dimensional'.'Ex]' means'the integer part of x'; this notation will be used frequently throughout the report. It can be established inductively that every I will satisfy this condition. ****ote that in such a Net as this, the Construction Formula might have been written with any permutations of the subscripts on the P's without in any way changing the form of the Net. For present purposes (and there seems to be no reason in practice for doing otherwise) all such permutations of inputs which have no effect on the outputs (other than permutation) nor on the construction of the switch, will be identified —i.e., a switch for given input conditions specified by the definition will be considered unique. 19

1III Ii Pi P ts 2 a 1 3 1 p2 8 16 P3 112 64 P4 P5 8 12 n=2 n=3 n=:4 n=5 n=:6 C =8 C=2(4+8) =24 C=2(4+4+16)-48 C= 2(4+4+8+32)=96 0=2(4+4+8+8+64)= 176 P21 1 6 1 I 1 6 1 6 I IP -'~~~~~~~~~~~~~~~~~~~~~~~3 256 128 P4~~~~~,1P _1 31~ l2 8! 16 F6 i S2 Pe 3 13 111 3P —'m7 fl — 8-"2(4+4+4+4+8+16+32+512)=I168 10 C=2(4+4+4+16+8+ 128)=328 C=2(4+4+4+4+16+16*256)=608 0C2(4*4+4*4-18+8+32+32+1024):2240 LOADING FIGURE 6. BALANCE MS N IHP nPU PR1282.O n=10 P,2,p3,p, ~p9 - (4).10 FIGURE 6. BALANCED MS NETS WITH n nPTPIS~=,.,0

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN It is not entirely obvious from the rules of construction that the resultant Net will have the required n input pairs. That this is actually the case can be demonstrated conveniently by means of the Construction Formula. Start with the output set expressed as the 5-term Cartesian Conjunction (P1 X P2 X P3 X P4 X P5), (the example of Figuse 6). Then the rule for inserting additional parentheses corresponding to the construction rule for adjoining MS's is to'bifurcate' the smallest parenthetical expression into two such which differ at to number of P's by at most one. The resultant formula obviously denotes the proper number of inputs ( P's ), and the correspondence to the actual rules of construction can be verified readily. The above definition defines the Balanced MS Net by telling how to built it. An alternative. definition which is primarily descriptive rather than constructive and will be used in the discussion of minimality properties in Volume III may be stated as follows: The Balanced MS Net with input set I = Pi u... u Pn is an MS Net (a) having 2n final outputs from a single MS, (b) using 2-dimensional MS's throughout, and (e) such that each MS has its input sets'balanced'; i.e., for 2x outputs; the two input sets have N(I1) = 2[(x+1)/2] and N(I2) = 2[x/2] The two definitions have been proved equivalent but, in the interests of brevity, the proof is omitted. The Element Input Count and Loading Couples for the Balanced MS Net cannot be conveniently stated for the general cas. For the case n = 2k however, the Element Input Count is C = 2 W 2(2ki+l) Figure 6 presents schematic diagrams of the Nets with n input pairs for values of n ranging from 2 to 10 with the Element Input Count, C computed for each and the Loading Couples given for the case of n = 10 The most important characteristic of this switch is stated formally as follows: Theorem. The Element Input Count of a Balanced MS Net with n input pairs is less than or equal to the Element Input Count of any n-input-pair MS Net. The proof of this theorem is rather lengthy and will be reserved for Volume III. 21

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN 3.2. Alternative Switches Using Other Logical Elements The construction of Networks consisting exclusively of Disjunctive Elements is quite straightforward. Such Nets are important in encoding, but because of their simplicity and because no alternative modes of construction are considered, the treatment of section 4.2 in connection with realization suffices without additional treatment here. In section 2 the use of logical elements other than conjunction, disjunction, and negation was suggested, although these three were accepted as the "vocabulary" for the report. One slight digression from this policy was made with the introduction of the Double-and in the discussion of Standard Trees. The present section will consider some additional alternatives. All of the elements introduced are definable in terms of the standard vocabulary (e.g., see Figures 7a' and 7b'). While the alternatives could have been tied into the general theory of the report by this means, they have not been so treated and the present section can be considered as an appendix upon which one of the subsequent theory will depend, The use of vacuum tubes leads naturally to the logical stroke functions; two examples of these functions will be discussed below. The so-called "Sheffer" or Conjunctive Stroke (non-conjunction), p/q = def. (p-q), is realized by a plate-loaded pentode without a phase inverter. It is represented diagrammatically as in Figure 7a, whose definition is the same as the definition of the standard network of Figure 7a'. The Disjunctive Stroke (non-disjunction), p4q = def.' (pvq), is realized by a pair of triodes in parallel. This function is diagrammed in Figure 7b, with the corresponding standard network as in Figure 7b' or as in 7b" by the duality, (pvq) = p-~q. These elements can be combined into Networks, following the rules of section 2. In partjcular, switches similar to the MS may be constructed: the Conjunctive Stroke MS (CSMS) as in Figure 7c and the Disjunctive Stroke MS (DSMS) as in Figure 7d. These switches give the same result as the standard MS with the qualification that the CSMS produces the negations of the outputs of an MS and the DSMS produces the output which would be produced by an MS with each of its inputs negated —cf. Figure 7b". (In other words, the CSMS with a negation on each of its outputs and the DSMS with a negation In the two realizations below it is assumed that a high voltage level represents'true and a low level'false'. These conventions could, of course, be reversed with a resultant interchange in the functions realized. 22

(a] ( b) 0 CONJUNCTIVE STROKE ELEMENT DISJUNCTIVE STROKE ELEMENT () Pt (d)p P2 DISJUNCTIVE STROKE (c) (d) MS CONJUNCTIVE STROKE MS pq P2 P3 (e) STROKE TREE FIGURE 7 23

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN on each of its inputs would produce exactly the result of a standard MSthis is obvious from a consideration-.of the stroke elements themselves.) One practical example of the use of these Stroke MS's is in the tree type of Netwdrk. Figure 7e shows a Stroke Function of 2 Bays (3 input pair-s). The CSMS and DSMS are each enclosed in heavy-line boxes with their internal elements represented as in 7a' and 7b" in order to show how the interconnection effects a cancellation of the negations. In the case of a switch input connected directly to a DSMS the effect is to negate the signal on each wire of the pair, but since these are Polar Pairs, the situation is perfectly symmetric and amounts merely to interchanging the labels of the two wires. A Stroke Tree of any number of Bays may be similarly constructed by using a DSMS for the final (output) Bay and then alternating CSMS and DSMS for the remaining Bays. 24

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN 4. Techniques for Realizing Transliterative Functions The purpose of the present section is to present effective techniques for constructing, in terms of the components of the preceding sections, switches for realizing all of the transliterative functions. These functions are considered in three categories with one or more realization techniques for each category: "Decoding Functions' in section 4.1, "Encoding Functions" in section 4.2, and the general case, "Arbitrary Transliterative Functions" in section 4.3.* Up to this point Volume I has been concerned exclusively with the static mode of operation. Pulse operation is discussed separately in section 4.4, "Modifications to Provide Pulse Outputs". First some terminology will be established. Both "realizations" and "transliterative functions" have been referred to previously, with varying degrees of formality. The formal definitions will now be given. One might naturally ask at this point why the title of this section is not expressed in a more direct manner in terms of switches (e.g., Design of Transliterative Switches) with the internal organization of the section based on types of switches rather than on functions. This approach was attempted in the initial study of the subject and was discarded for reasons which, if is felt, warrant the present digressive explanation. The difficulty is clearly exemplified by the IRE definition: "Function Switch, One-Many. A function switch in which only one input is excited at a time and each input produces a combination of outputs."t (sometimes referred to as an "Encoding Switch"). Note that, in general, this definition describes a "mode of operation" rather than a type of switch-i.e., it merely defines the type of Transliterative Function the switch is to realize. Specifically, it says of the switch itself simply that it has "outputs" whose state is in some way dependent on the'state of its "inputs". Under suchna defitnition, any Function Switch (e.g., a "many-one" or "decoding" switch) would be a none-many" switch if its inputs were properly activated. Since this type of definition offers no means for distinguishing various kinds of switches per se, there appear to be two alternatives: (1) the method of this report, which relies on functions since functions can be distinguished, and does not attempt to classify the switches; and (2) the formulation of definitions which do permit the classification of switches (perhaps from a consideration of their output under all possible input states)-an undertaking which, in the light of a cursory investigation, appears to be somewhat formidable. 25

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Def. 4. A Transliterative Function, T, is a single-valued function (mapping) from a set of sequences of O's and l's all of the same length (the domain of definition) onto another set of sequences of O's and l's also all of the same length (the range) with the condition that there are no "dummy" digits in either the domain or the range; i.e., for any digit-position, x, of a sequence, the set (range or domain) must contain two sequences, s~ and s', such that s has a 1 in position x and s' has a 0 in position x The domain of T will be denoted by'D(T)', its range by'R(T)f, and an element (sequence) of the domain or range, respectively, by'di(T)' or simply'di' and'ri(T)' or simply'ri' -i.e., D(T) = tdi(T)3, R(T) = tri(T) Def. 5. A network is said to Realize or tao be a Realization of a Transliterative Function, T, if there exists an ordering w1,w2,...,wn of the set of input wires and a corresponding ordering w-1,...wk of a subset (perhaps proper) of the output wires having the property that whenever the sequence of states of Wl,..o,wn is equal to a di, diE D(T), then the sequence of states of w1,.,W7k is equal to T(di) This definition postulates the existence of a 1-1 correspondence between the bit positions of the domain sequences and the set of input wires, and a similar one between range sequences and a subset of the output wires. There is another important aspect of domain sequences: they may be thought of as representing information impressed on the inputs from outside, If this information is presented on n Polar Pairs of wires, it is not to be considered an n bit sequence but instead a 2n bit sequence. The concept of Realization defined here is, admittedly, a narrower concept than the ordinary intuitive one.** It is, however, adequate for the purposes of this report and has the advantage of stating precisely the kind of realization which the given techniques produce. This condition could be omitted, enlarging the class of Transliterative Functions, but the functions thus admitted would hardly be of sufficient interest to warrant even the slight modifications that would be necessary in the subsequent theory. ** A definition closer to the intuitive idea of realization would, for example, admit, under certain circumstances, realizations in which a proper subset of the inputs is activated in accordance with di(T) 26

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN The term'technique' is used here in a special sense. Techniques are constructive procedures, each associated with a specified class of Transliterative Functions, describing step by step a fully effective method for building a switch to Realize a given Function of the class. Furthermore, it is desirable, and will be a characteristic of all techniques presented., that the relation between inputs and outputs required by the given function be made explicit by means of a labeling of the wires as in the definition of Realization. The application of these Techniques together with simplifications of the Switch produced may result in "Disjunctive Elements" with but a single input. When this occurs the "Disjunctive Element" is to be eliminated and its input designated a Switch output. It is also possible that a Technique will produce a switch with a "dead-end" inputone which is neither a Switch output nor an input to a Logical Element (e.g., if an Encoding Function —see section 4.2 —has the all-zero sequence in its range). Such a switch is not strictly a Network by the formation rules of section 2. However, the status of such a wire is so obvious, and the treatment so simple-merely ignore or eliminate itthat it seemed advisable to admit the discrepancy rather than to complicate the theory further in order to treat this special case with full rigor. 4.1. Decoding Functions Def. 6. A Decoding Function is a Transliterative Function, Td, such that: (a) every ri(Td) contains a single 1, and (b) N(D(Td)) = N(R(Td.)) The effect of condition (b) is to make Decoding Functions 1-1. Functions satisfying condition (a) alone are handled by the techniques for arbitrary functions. The inputs of the Switches constructed in section 3 were in Polar Pair form. In order to consider such input sets it is useful to define a Polar Sequence as a sequence a,a2...,a2k having a2j1_,a2j either 0,1 or 1,0 for j =1,2,...,k Def. 7. A Complete Decoding Function, Tc, is a Decoding Function satisfying the following: (a) every element of D(Tc) is a Polar Sequence, and (b) every Polar Sequence of length N(di(Tc)) is an element of D(Tc ) 27

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN It follows clearly from this definition that N(D(Tc)) = 2N(di(Tc))/2 N(R(Tc)) Theorem 1. A Complete Decoding Function, Tc, with N(di(Tc)) = 2n can be realized by any MS Net with I = n U Pj (i.e., with input set consisting of n Polar j=' Pairs). Corollary. If T is realized (in accordance with Theorem 1) by a Simple MS Net, then there are no extraneous output wires, i.e., the set of output wires, 0 L-1R(Tc) * Proof. D(Tc) is the Cartesian Product of n sets, each consisting of the two pairs, (0-,1) (1,0), i.e., D(Tc) = ((0ol), (10))n and is represented by the states of the pairs of wires of 4, the set of n P' s of the Net. The Network output, 0, by definition contains the Cartesian Conjunction, CC(&), i.e., a distinct output wire of CC;) is activated for each sequence of the Cartesian Product, D(Tc), represented on the inputs. Each wire of the CC(J) may be assigned an integer, x, as follows: Consider the image sequence, Tc(di), for di D(Tc) It contains a single 1, Denote the position in which the 1 appears by x, and assign x to the wire of CC($) which is in the 1 state for di. If this is done for all die D(Tc), all wires of CC(;) will be labeled by an x 1 i x - 2n The wires of CC(S) then, considered in the sequence of the x's, clearly effect a Realization of Tc The corollary follows immediately from the fact that for a Simple MS Net 0 CCQ) With the result of this theorem, the following specific Realizations are immediately available: Technique 0. A Complete Decoding Function, Tc a with domain sequence of length 2n ( N(di(Tc)) = 2n ) can be Realized by (a) an Exponential Switch, (b) a Tree, or n (c) a Balanced MS Net, with input set I = U P.j= Since explicit Construction Procedures were given in section 3 for each of the switches, (a), (b), and (c), and since the labeling of the wires described in the proof of Theorem 1 gives an ordering of input 28

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN and output sequences which establishes the functional correspondence, Technique O is fully effective as required. Note that since the three Switches are simple MS Nets, the Corollary to Theorem 1 indicates that there will be no extraneous output wires. A Decoding Function, T, may fail to be Complete by violating either of the two conditions characterizing a Complete Decoding Functioni.e., (1) The elements of D(T) are not all Polar Sequences. (2) Not every Polar Sequence of length N(di(T)) is an element of D(T) In the technique given below, step A provides for failures of type (1) and step C for those of type (2). Technique 1. A. Examine the sequences of D(T) 1. If not all the sequences of D(T) are Polar Sequences, provide a Polarizer with N(di(T)) inputs.* Its outputs are to be connected, in the obvious manner, to the Switch constructed below. Define n = N(di(T)) 2. If every di(T) is a Polar Sequence, define n N(di(T))/2 and proceed to B. B. By Technique 0(a), (b), or (c) construct a Switch for the Complete Decoding Function with n Polar Pair inputs. C. From the Switch produced by A and B remove any Logical Element which is not in a Chain terminating in any one of the N(D(T)) required outputs. Technique 1 is illustrated in Figure 8a (disregarding Switch M2 ) by applying it to the function Td defined in Table II of section 4,3. It may be the case that some part of every domain sequence-the same part for each —is a Polar Sequence and the remainder not. In practice it would he possible in this case to provide a Polarizer of less than N(di(T)) inputs for use with only the "unpolarized" positions, althoiugh formally this simplification has been ignored in the interests of presenting a unified general theory. 29

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Clearly the sequences of D(Td) are not all Polar Sequences and so according to step A.1l a 4-input Polarizer, P, must be provided. Step B requires the construction of a Switch for the Complete Decoding Function with N(di(T)) = 4 Polar Pair inputs by Technique O(a), (b), or (c) —ie,, by an Exponential Switch, a Tree, or a Balanced MS Net. In the example a Tree is used — M1 in the figure. The inputs of P may be labeled in any order and the outputs of P are connected to the inputs of M1 in the obvious manner. After a particular labeling of the inputs of P has been chosen, the outputs of M1 are labeled by considering the di(Td). Assign the label'w.' to the output wire which is activated whenever the sequence of states of the input wires, w,w2,w3,w4, is di (the state of wk corresponding to the kth bit of di ), where j is the position number of the 1 in Td(di). Finally, proceeding according to step C,. the unnecessary Logical Elements are eliminated-in the figure they are drawn with broken lines. Simplifications may be possible in Switches constructed by this technique. No comprehensive study of simplification procedures has been made, but examples illustrating some of the possibilities are given in section 4,3, 4.2. Encoding Functions Defo 8. An Encoding Function is a Transliterative Function, Te, such that every di(Te) contains a single 1 The following technique provides a Realization for any given Encoding Function, Te, where n is the number of domain sequences, n is the number of range sequences, and di is defined to be the domain sequence whose ith bit is a 1. Techniqaue 2, (1) Provide n input wires and n Disjunctive Elements. Designate the Element outputs as switch outputs; assign the integers from 1 to n to the input wires, and those from 1 to n to the Disjunctive Elements. (2) Connect the ith input wire to a distinct input of the jth Disjunctive Element if the jth bit of Te(di) is a 1 Nothing was stated about the number of inputs of the Disjunctive Elements, since this would depend on the nature of Te o In general, it is clear (by virtue _ofLthe exclusion of "dlummy" digits in Def. 4) that no Element will require more than N(D(Te)) -l inputs. In the "most efficient" 30

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN case-a 1-1 function with N(D(Te)) = 2x, N(ri(Te)) = x -every Element will have 2 inputs, since each output must be in the 1 state for exactly half of the 2x input states. Technique 2 is illustrated in Figure 8a for the function, Te 9 defined iw;Tabe II of section 4.3. The Switch produced is M2. The input wires may be numbered wl,..,wn in any order-'the order here being chosen merely for convenience in the example of section 4.3. Note that in Figure 8b the single-input Disjunctive Element has been eliminated. A Switch produced by Technique 2 can often be simplified. Such a Switch will consist of Disjunctive Elements whose inputs are wires of I the set of input wires for the Switch. Suppose some subset, I., of I is contained in the input set of several of these Disjunctive Elements, say El,.y..Ek Then let I be the input set for a new Disjunctive Element, E, and replace each Ei (i=l,..,-k) by a Disjunctive Element Ei- having the same input set as Ei except that the output of E replaces the subset I of inputs of Ei This procedure will reduce the Element Inj put Count, C, by an amount AC (k-l) (C(E)-1) - 1 from which it is apparent that AC > 0 if k - 2 - C(E) but not k = C(E) =2 -for which AC = O 4.3. Arbitrary Transliterative Functions While the Technique of this subsection is intended, as the title implies, to Realize any Transliterative Function, the functions of primary interest are those which are neither Decoding nor Encoding Functions. For the special functions previously dealt with, the present Technique degenerastes to either Technique 1 or Technique 20 The procedure for an arbitrary Transliterative Function requires two stages: first "decoding'!, then "encoding".. That is). for a given arbitrary function, T, define a Decoding Function, Td, and an Encoding Function, Te. such that for any x ED(T) Te(Td(x)) = T(x). This requires that R(Td) = D(Te). These conditions fully specify the two functions.* Note that the definition of Decoding Function, plus the exclusion of "durmmy digits" in the definition of Transliterative Function requires that R(Td) be constructed of exactly N(ID(T)) sequences, each of N(D(T)) digits* and each having exactly one 1 in a unique position. The specific correspondence between range and domain for each of the two functions, so long as it satisfies the conditions that Td is 1-1 and that Te(Td(x)) = T(x), is irrelevant since such distinctions can all be resolved by the proper labeling of the wires of the same Switch.. 31.I

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Technique 3, Given an arbitrary Transliterative Function, T, form the related Decoding Function, Td, and Encoding Function,. Te. Realize these functions,~ respectively by Technique 1 and Technique 2. Then connect the outputs of the switch for Td to the inputs of the switch for Te, joining wires with corresponding labels. The Switches constructed by the application of this and the preceding Techniques may often be simplified. Some of the ways in which this may be done are given by the following examples Consider the fiunctiort T defined below.: TABLE I d T T(d) 111111 -.> 110 0000 1100) 111032 >iI a o001 000 10103 1101 - 010 000 1001 0110. 000 110 0100 3 0000 " -- 000 001 1000.; - > 001 110 Applying Technique 3 will yield the Switch of Figure 8a (if a Tree is used to realize ITd ) as is shown below. The related Decoding Function, Td, and Encoding Function, Te are given in Table II on the following page. The labeling of the input wires of P and the output wires of M1. and the construct.ion of the Switches P and M1, are as discussed in the example following Technique 1. The Switch M2, for Te is constructed by Technique 2. Ten input wires and six Disjunctive Elements are provided. Input and output wires may be labeled in any order (the ordering of the input labels in Figure 8 was chosen merely to facilitate the drawing of the diagram), After the wires have been labeled, M2 is constructed by connecting the Switch inputs to the Disjunctive Elements:'in step (2) of Technique 2. The Switch for T is completed by connecting the input wires of M2 to the output wires of M1: wi to wi 32

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN TABLE II d(Td) Td Td(d) = d(Te) Te Te(Tc(d) =T(l) 1111 > 1 000 000 0 > 1 00'zrl'~I —-— c~ ~ so0 oooP - -'j 110 000 1100 > 01 00.000 000 j 1110 0 010 000 000 1010 > 0 001 000 000 1101 0 000 100 000 -- - 010 000 1001':...> 0 0010 0'00 0.110 > 0 000 001 0Q0 > 000 110 0100 - - 0> 0 000 000 1003 0000 --— 0 000 —---- 000 010 > 00 001 1000 > 0 000 000 001 001 110 The Simplification of this Switch is carried out by a sequence of steps-, each illustrated by a figure, Figure 8a represents the switch as constructed by Technique 3 and Figures 8b and 8c present further simplificatio ns. In the Switches of Figure 8 some of the Elements and wires are drawn in broken lines and some in "x-edn lines, The former represent the omissions and the latter the additions effected at the stages of simplification represented. In Figure 8b the simplifications carried out are the elimination of the "Disjunctive Element" with one input and the omission of five Conjunctive Elements, each of which has an input that is not an input of any other element (this is not always possible, as is pointed out- in the second paragraph following), Another type of simplification is illustrated in Figure Bc, Here two Disjunctive Elements contain. as a subset of their inputs: the output of all the Conjunctiv Elements with a given input ~. In this example these Conjunctive Elements may be eliminated and i connected directly into the Disjunctive Elements (since if i is in the. "1" state one of the possible combinations of i must be in the "1" state), Caution must be exercised in the process of simplification. Flor example, the function T may have in its range the zero sequence. No connections are necessary for the switch to realize this output, Thus an input 33

T~~~~~~~~M IW 1I WI1 1 mwl W2 Ws Ml | e 2 Ws W Mi ~~~~~~~1 —-HI, W2 ~ ~ ~ ~ ~ ~ ~ W..~~~~~~~~~~~~~~~~~~~-[._._. W4~~~~~~~~~~~W WI~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ W2 W:5 W 4 I 2 W(..W (a) (b) FIGURE 8.

MI M2 WI (w W3 k W7 -.. Wl WrLi W4 r 8 (C) FIGURE 8 FIGURE 9

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN to the switch for Te, the corresponding output of the switch for Td, and its Conjunctive Element mary be eliminated (possibly othersa depending on the function). Consider Figure 9. It shows a Double-and in the output MS of the Tree realizing Td wi is in the one state for di on the inputs and wj is in the one state for d. Suppose T(dj) is the zero sequence; then this output and Conjunctive Element may be eliminated. However, although the Element for wi has an input, k, connected to no other Conjunctive Element, it cannot be eliminated since both di and. da may occur on the inputs. Thus the simplifecation effected for the switch of Figure 8b is impossible here. Unfortunately no technique is known for producing the simplest switch for an arbitrary Transliterative Function or even, in terms of this report, a switch with minimal element input count. The application of Boolean Algebra and the methods of Aiken (l1) and Veitch (13) are aimed at this problem but are heuristic in natures not effective as the term is -used here., For any given case, further methods of simplification may be obvious~ and trial and error procedure is in order. *4Q Modifications to Provide Pulse Output It has been mentioned before that,l whenever such. an assumption is required-, the switches of this volume are to be considered as static. Primarily this qualification is a precaution against raising questions of. pulse-matching whose answers might lie far beyond the scope of this report. It is clear, howevery that if equipment is available which is sufficiently flexible to gate pulses with pulses or with static signals without requiring prohibitive conditions of simultaneity, then the preceding theory can be considered applicable to pulse as well as static operation or a combination of the two. Since the general problem is closely dependent on detailed engineering considerations, the present discussion will be limited to a few simple methods for producing pulse outputs from a system designed for static operation, An obvious method which canm be applied to any static switch whatsoever is to connect a "dynamic gate" (a 2-input conjunction with one static and one pulse input) via its static input to each output of the switch and'then connect all of the pulse inputs in parallel to an external source which will produce a pulse whenever the switch is to be "read". For Simple MS Nets it is possible to introduce the pulse at the input rather than at the oputpt —or, for that matter, at the input (of an entire I, ) of any MS of the Net. This procedure is shown in Figure lOa' ~3~36 - - ~~~~~~~~~~56

6I 3 13 616 (a) TREE (Mi* DENOTES AN MS EACH OF WHOSE CONJUNCTIVE ELEMENTS HAS I PULSE AND I PULSE STATIC INPUT) SOURCE p pz p p4 Np4 PI P2 P3 P4P" P4 32 I|(b) BALANCED MS NET PULSE SOURCE MI PI PP P3 P. P, MODIFICATIONS FOR PULSE OUTPUT FIGURE 10

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN for a Tree and in. Figure l0b for a Balanced MS Net. Under this method every Clhain Of Logical Eleaments in- which a pulse is introduced must be composed entirely of dynamic gates from the point of occurrence of the pulse to the output. The method is restricted. to Simple M Nets for two reasons: (1) an element must not have more than one pulse input in order to avoid the difficulty of matching pulses against pulses-this is assured. by the restriction against Branching; and (2) it must be possible for the pulse to reach any output-this is assured since every output is an element of the Cartesian Conjunction and therefore is fed by each input. An effective comparison of the relative desirability of these methods depends ultimately on such considerations as relative cost of dynamie and static gates. The following examples however. may help to clarify the problem. Consider Figure 10b. The method depicted requires four additional dynaic gates and the replacing of forty static gates by dynamic gates — eight in M2, thirty-two in M4: Represent the'cost" of conversion by 4G + 40AG -- G representing the "cost" of dynamic gates and AG the "cost" of dynamic gates less the cost of static gates. The method is clearly a poor one for this particular switch —assuming that dynamic gates cost more -than static gates (i.e., AG > 0 )-since the same effect could be produced., for example, by inserting the pulse at the input pair P at a cost of only 2G + 36AG. But if the pulse were introduced at the output of M2 at cost 8G + 32.A7G the comprsison between this and the other two methods could not be made without knowledge of the ratio of G to AG 38

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN 5. Characteristics of Function Switches The object of this section is to compare in terms of the Element Input Count and loading properties some of the different Switches introduced in sections 3 and 4. The Techniques of section 4 combine an MS Net with, perhaps~ a Switch for an Encoding Function and possibly a Polarizer to realize an arbitrary Transliterative Function. The only choice is in the selection of an MS Net which may be an Exponential Switch, a Tree, or a Balanced MS Net. It is primarily these switches which are to be studied. In the case of a Tree, loading is an obvious problem and a Technique is presented here for designing a Switch —the "folded tree"-closely related to the Standard Tree but having more desirable loading properties9 Although its Element Input Count is the samne as that of a Standard Tree and its set of outputs is the Cartesian Conjunction of its inputs, it is not necessarily an MS Net and the theory behind it is somewhat different. For thes'e reasons it is discussed in this section rather than as a part of the theory presented in section 3. ~5J. Element Input Count and General Loading Properties _-~'.....:: ---:-.' -' -,'.........'7-.:-.','~' ".....'! The problem of selecting the "best" switch for a given purpose cannot be dealt with. A switch is "best" only with respect to some welldefined set of properties (probably requiring specifications of actual physical equipment) and usually with respect to a certain class of switches. Two properties, Element Input Count and Loading, have been defined for symbolic Networks which under proper interpretation may have a certain general significance for. their physical counterparts. The Element Input Count is considered first. The Element Input Count of an Exponential Switch is given by the -formula C m TT N(Pi) = m 2m - where m is the number of input pairs. i=l For a Standard Tree (with static output) the formula is C = 8(2-I -) 1 For the Balanced MS Net the only formula available is C = 2 k' 2(2k-i + i) I where the number of input pairs is restricted to n= 2k l=0 However, the three may be Compared for various values of m. 39

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Element -Input Count Comparison Switch 2 4 5 8 Exponential Switch 8 64 16o 2048 Standard Tree 8 56 120 1016 Balanced MS Net 8 48 96 608 Switches may be judged on the basis of this property alone, the "best" switch being the one with the smallest C In this sense, the example suggests that the Balanced MS Net is "best", the Exponential Switch worst, Switches "best" in this sense are called.'minimal" a switch for a given Transliterative Function is Minimal with respect to a set of switches, S, which realize this function if its Element Input Count is at least as small as that of any other switch in S It was stated in section 3 as a theorem and will be proved in Volume III that in the set of all M Nets whose input consists of m input pairs the Balanced MS Net is Minimal. The generalization of the idea of minimization to switches for arbitrary Transliterative Functions is very difficult. It is partly at this problem that the methods of Aiken and Veitch are directed, These methods are heuristic and ineffectiye in the sense that while they are methods for simplifying they do not lead directly to the desired "minimal" switch. This general problem of Minimization is formulated and a possible approach indicated in Volume III. The second characteristic to be considered is Loading. This property (as defined. in section 2) is described by a set of Loading Couples of the form (SP) y one for each input, where S is the Serial Loading Coefficient and P the Parallel Loading Coefficient, All the Switches considered in this section have the property that both inputs of a pair, i have the same Loading Couple, which will be referred to as the Loading Couple of - For the Exponential Switch the Loading Couple is (1,2m-l) for every input, where m is the number of input pairs. If the inprut pairs of a Standard Tree are numbered in the "natural way (i.e ~, starting with tho$se farthest from the Switch Output), then for the ith input pair (i >), -40

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN it is (m-4i+l. 2-1). The couple for i= 1 is the same as that for i = 2. Again, no general formula has been developed for the Balanced MS Net because the mode of construction makes it impractical. The Loading Couples for an example are compared below. Comparison of Loading Couples* PI P2 P5 P4 P5 1. Exponential Switch (1,24) (L,24) (1,24) (1,24) (1,24) 2 31 1i24 2. Tree (4,2) (4,2) (3,22) (2,23) (1,24) 3. Balanced MS Net (3,2') (3,2) (2,4) (2,2) (2,2)..11 is,1,,..;:!1 i..:.. The Parallel -Loading Coefficient of every input of the Exponential Switch is inordinately large for even a moderate number of input pairs though its serial loading is' ideal, The Tree also has poor loading characteristics but they can be improved by the "folding Technique" of'section 5,2, While these Coupler give sone insight into the loading properties of a switch, a more' cempleteb picture is given by considering the parallel loading properties of the individual Logical Elements. This can be done easily for any MS Net because of the followings Remark: If'I = I u um is the input set of an MS Net, then the input wires constituting Ij all have Parallel Loading Coefficient Lj (j= ll...,m) Furthermore, all outputs (i..e,y. Element Outputs) of a given MS of the MS Net have the same Parallel Loading Coefficient. The truth of this statement derives from the "non-splitting" condition in the definition of M Net, Let M be an MS Net. Label the MSt's of M. M1,,,Mk and let the corresponding Parallel Loading Coefficients he LLe,...Lk. Then define LiMi to mean that every Element Output of Mi has Loading Coefficient Li (e.g.,- 3ML would mean that every element in Mi has Coefficient 3 ). For the input.4res the corresponding notation is KjI Cf.- Figures 3b, 5, and 6 for examples of Switches 1, 2, and 3, respectively. Note, however, that the first two figures are Switches of 4 rather than 5 input pairs. 41

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN where Kj, is the Parallel Loading Coefficient of each wire in the set Ij The parallel loading properties of the entire MS Net, M., can then be described by a sum S(M) = LiMi + LKjIj. (1) i=l j=l In the cases to be considered the I will be Polar Pairs and so will be replaced by Pj. Formula (1) may e thought of as a simplified form of the following sum, which may be defined for an arbitrary Network, A S(A) = i_ Ei + ZKj w l (2) where Ei ranges over all of the Logical Elements of A, over all its inputs, and L and Kj are the corresponding Parallel Loading Coefficients. If A - M, formula (1) may be deri:ved from (2). Group together the Logical Elements of each Mi of the Network: for exampley let LEl1 +.. + -Er be the expression for Mi. Since this is an MS, L{ L =.. = Lr represent this common value by Li and substitute it for the LIs Replace the resulting expression, LiEl +... + LiEr by LMi The derivation is completed by doing this for each MS of the Network and proceeding similarily for the input wires. Many variations of formula (2) exist, In this report we are primarily interested in switches whose inputs are Polar Pairs, the two wires of a pair having the same loading coefficient. Consequently, we are interested in formulas of the form n't m S(A) = LlEi + KjPj, (3;) There will be many occasions for referring to- the second of these sums, mh is nsequentl defined to be the Load Distribution of the Switch A. The term, Load Distribution, may be used without reference to a particular switch to refer to any expression of this form (since there will always exist some switch, D, with this as the Load Distribution of D ) ~ If S is a given Load Distribution and D is a switch having S as its Load Distribution (there may be many such D ) then S is said to be associated with D It is sometimes desirable in studying a Network, A, to "break" it into two or more subnetworks", to consider the Load Distributions of these parts, to add the Load Distributions together when the Networks are combined, aynd so on. In general Load Distributions may be added together 42

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN (when the corresponding switches are combined.) as linear, expressions. For example, (,3P1 + P2 + 8P4 + 1P3) + (1P4 + F5P + 7P = 5P1 + 5P2 + 6P3 + 9P4 + 7P5 Consider S for the Standard Tree, T, and the Balanced MS Net, B, constructed on 5 input pairs (see Figures 6 and 11, respectively). For the Tree: S(T) = (2I+ 2M2 + 2M3 + PM4) + (2P1 + 2P2 + 4P3 + 8P4 + 16P5) For the Balanced.MS Net: s() = (2M+ 4M2 + 8M + OM4) + (2P1 + 2P2 + 4P3 + 2P4 + 2P5) The Load Distribution of the Tree is: 2P1 + 2P2 + 4P3 + 8P4 + 16P5 For the Balanced MS Net it is; 2P1 + 2P2 + 4P3 + 2P4 + 2P5 In the case of the Tree the parallel loading is good except for the input pairs with higher subscript (e.g., P4 and P5 ). The loading for the Balanced MS Net is good except for the elements in the MS's near to the output MS (eog., M3 ). The problem is more acute for the Tree and has serious physical implications. For example, in a relay tree the Parallel Loading Coefficients of the inputs may be interpreted as the spring load on the corresponding relay coils. Because the Load Distribution, KjPj, for the Standard Tree has these undesirable properties, the next section considers a method for modifying the Tree Network to give a better Load Distribultion 5.2. The Folded Tree Technique The folding process for improving Load Distribution and the resulting "folded tree'" Network are not new, A folded tree is generally considered to be a modification of a Standard Tree, but in this report a slightly different point of view is taken. The Folded Tree is considered as a distinct and independent Network and is defined as one having as its outputs the Cartesian Conjunetion of its inputs and differing from a Stand.y ard Tree, if at all, only in the assignment of its Double-ands to input pairs, (A Double-.and, A, is assigned to input pair Pk if Pk is connected to the inputs of A.) 43

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN By making the assignments in different ways, different Load Distributions may be obtained. The distribution desired in a given case involves consideration of the load limitations of the driving components, the operating characteristics of the Conjunctive Elements of the Network, the available sizes of the conjunctive components if they are in package units, etc. The remainder of this section is devoted to (1) describing a simple method for determining if a given Load Distribution can be realized in a Folded Tree, and (2) describing a practical method for constructing a Folded Tree with any desired realizable Load Distribution. Consider a Standard Tree, T, and label its Double-ands iAj where i specifies the Bay or MS in which the Double-and appears counting from the left, and j the position in the Bay counting from the top. The "subnetwork" whose Double-ands all belong to Chains passing through iAj and have "prescript" k' i ("prescript" refers to the k in kAj ) is a Network which is itself a Tree. It is called a Minor Tree of T and is denoted T'(i,j).* The Double-and, iAj, is called its Key (see Figure 11). Standard Trees do not themselves have Keys. However, if they are modified for pulse output by inserting dynamic gates at the P1 input, they will have a Key (see section 4.4). In the remainder of this section, the words Tree, Standard Tree, and Folded Tree will always refer to Trees with Keys unless otherwise specified. Furthermore, the method of construction given is designed to yield a Folded Tree with a Key. The modifications needed to apply the method to Trees without Keys are indicated at the end of this section. A Folded Tree may be drawn exactly as a Standard Tree except for the connections of input pairs to Double-ands. If these connections are omitted and the Double-ands labeled as for the Standard Tree, then the definitions and notation for Minor Trees, Keys, and so on may be used in the same manner as for a Standard Tree. This is true because these concepts depend on the "internal" connections of the Network and not on the connections of Double-ands to input pairs. Consequently, in the remainder of this volume the terms Tree, Minor Tree, etc. will refer to Folded Trees (of which the Standard Tree is a special case). With every Minor Tree, T(i,j), of T is associated a Load Distribution denoted'S(i,j)'. Since the Key of T is lAl, the Load Distribution of T is denoted'S(l,1). Included in this definition of a Minor Tree are the Networks containing a single Double-and with outputs which are outputs of T 44

P.iP P3 T(4T(,2 P P T(3,1) SAO P TCE4' - cuff ~ ~Ps T(5.4) T(I~~~~~t) M2J~~~~~~~~5 P. / t(~~~~~~~~~T(4,4.." KT(5i5) elm 4 P4 / ~ / NcT(s5.6 PsI T(41) Ae~ P, Ff~ eb'I b(,oCT(597) Ps ap'T Pt TP IT5,3 4 4 A3 P5 P\',.AT(5,II) P 4 P4'I "'c(T(5,I2) ir %MP4 2AP(X5 ~~4T(5,I4) Ps YP6 ftZ~~2)T54.AT(5,15) PsT5,16) (O) (b) (c) (d) (e) S(4,I)z2Fq tiIP ~-c= S(5,1):IP, S(4,I0r+22 9 S4IPP, sc2~"'l~'+sP~+1Pr+4P~ S~n~31;~slg+'Ps S(4,4)II1;+2FS — e~ S(5)SlPI S(492)-xl S~g ~ c S(5,3)21p3 S(P"O= 4P, +6P3+'p4+C4AI 2I4 - S(5,15): 1P3 S(4v3)z —p3+'5 S 56)-lp S~~2)~ 4q lg~g~q+41 SSPA:, W, + -3%+ 3% S (5,7) = I PS)tl S(5,1)=445 S(FIGURE2P, + 1 II.550)1% SPAPM, II

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN The. Load. Distribiution of a Tree contains a. single.term with- coefficient 1. It will be necessary to refer to this term often, and so it is denoted tU(S(i,j))t which is read'the term with unit coefficient in S(ij)' or'the unit term of S(i,j)'. These concepts are illustrated in Figure ll, where the Pk above each iAj is the input pair to which iAj is assigned. Figure lla is a Folded 5-bay tree with Load Distribution S(111) 8P1 + 1P2 + 7P3 + + 8P5 (A 5-ay Standard Tree has S(1,1) = 1P + 2P2 + 4P + 8P4 + 16.) Figure llb shows the two 4-bay Minor Trees of T, T(2,1) and T(2,2), with Load Distributions S(2,1) = 4PL + 6P3 + 1P4 + 4P and S(2,2) = 4P1 + P3 + 6P4 + 4P5 respectively. Clearly, U($S(2,1)) 1P4 and U(S(2,2)) = 1P3. The assignments of input pairs in Figures lb, c, d,: and e are the same as in lla. Method for determining if a desired Load Distribution can be -. realized in a Folded Tree. A Load Distribution S = diP + d2P2 +.. + dnPn is called Admissible if and only if nA n A.1 d 2=iA.2 di - k= 1~2y...n where the di refers to the di in monotonic nondecreasing order; and A.3 there is but a single 1 among the di Using this concept, the following theorem* holds. The theory behind the methods given here was suggested by Shannon (10), Part II. It is fully developed in Vollume III, where the problem of folding and the procedure given here are fully discussed. Conditions Ai! to A-.3 for Admissibility are given by Shannon, and he also proves that any Admissible sequence can be derived by folding (i.e.,, the "if-" or "suffi-cing-statement" in the theorem), although he does not give an effective method for doing it. The proof win Volume III that the effective procedure described in this section is a valid one affords a new and constructive proof of the "if statement" of the theorem. The n-e-essity or "only if" statement in the theorem (i.e., any sequence derived by folding is Admissible) does not appear in Shannon's article but is proved in Volume III.

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Theorem: A Load Distribution, S, of n terms is the Load Distribution of a Folded n-Bay Tree if and only if S is Admissib1e. Thus to decide if a desired Load Distribution can be realized in a Folded Tree it is necessary only to determine its Admissiblity. Admissible Load Distributions are those which can be associated with Folded Trees. Consider S(1l1) 1P1 + 12P2 + 12P + 12P4 + 13P + 13P6 as such a desired distribution. Conditions A.1 A.3 are satisfied for (1) 1 + 12 + 12 + 12 + 13 + 13 = 63 = 2i- satisfying A.l. i=l (2) The partial Etmis of S computed in monotonic order are 1, 13, 25, 37, 50, 63 and those of the powers of 2 are I, 3, 7, 15, 31, 63. Comparison shows that condition A.2 is satisfied. (3) S(ll) has a single 1 satisfying A.3. Hence S(1,l) is Admissible and so can be realized in a Folded Tree, These conditions can be applied to classes of Load Distributions to determine if the members of the class can all be realized in Folded Trees. For example, consider the set of Load Distributions, tS(ll)n] The'n, indicates the number of input pairs and the lower bar denotes the Load Distribution which, for the given n, has its maximum coefficient as small as possible. There is just one such distribution for each n and it is obviously an important one. The Load Distributions of this class are given by the following rules: (1) Let l,,d,...d,dy,...,d be the n coefficients of S(1,1)n (we are not interested in the correspondence between Loading Coefficients and input pairs here and so consider only the coefficients). (2) Determine d from d+ F = (2n-2)/(n-1), where d is the integral and F the fractional part of the quotient. If the denominator of F is (n-l) then the numerator of F gives the number of its in the sequence an d - dt+l The distribution, S3(ll), considered in the preceding example is the element of [S(l,l)nI} for n=6, for d+ F = (64-2)/(6-1) = 12-2/5; d=12, d=13 and the number of 13's is 2. Although the Load Distribution for this example is Admissible, it is not obvious that every Load Distribution in the set, IS(1,1)n}

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN is Admissible. However, there is the following: Theorem.. The Load Distributions of t-S(1,1)n} are Admissible. Proof. Conditions A.1 and A.d hold obviously for all S(1,)n A.2 can be shown to hold by assuming that there exists a k< n at which it fails. This can be shown to imply that it fails at k=n (i.e., that A.1 fails), but this is impossible. Hence A.2 is satisfied. Q.E.D, Constructing a Folded Tree with a given Admissible Load Distribution. Since a Folded Tree differs from a Standard Tree with the same number of inputs only in the way in which its inputs are connected, a Folded Tree with Admissible Load Distribution S(1,l) may be constructed by first building a Standard Tree with the appropriate number of input pairs but without giving the connections of the Double-ands to these input pairs; second.x determining from S(1,1) the assignment of the iAjts to the inputs; and, third, making the connections indicated. Clearly the major problem is the determination of the assignment of the iAj. For a given Load Distribution, alternative assignments will in general be possible, The procedure here presented leads, somewhat arbitrarily, to one possible assignment. The bare method is presented here, the theory behind it being reserved for Volume III. The method may be considered as falling into two parts, The first,is the determination of the Load Distributions, S(ij), for every Minor Tree of the Folded Tree T(l,l) being constructed., The second is the determination of the assignment of iAj from S(i,). Consider part I. We are given an Admissible Load Distribution and are to determine from it the Load Distributions of the Minor Trees of T(ll) This is accomplished by repeated application of a process called "splitting".* If S(i4j) is the Load Distribution of T(i,j), a Minor. Tree of T(l,l), splitting will yield S(i+l,2j-l) and S(i+l,2j) > the Load Distributions of T(i+l,2j-l) and T(i+l,2j), the Minor Trees into which T(i,j) divides. Table III is the work sheet for a specific example showing how successive, splitting of Load Distributions beginning with S(l,1) will yield all the S(ij). Load Distributions with labels in the first column and with the unit term deleted (the reason for this will be apparent later) are those to be split) the two into which it splits appear immediately below. Each S(i j) appears twice, first with label in * Nlot to be confused with the Splitting of MS outputs discussed in section 3. 1$4

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN the second column as the product of a splitting and then with label in the first as a Load Distribution to be split. Figure 11 shows the same example diagrammatically. Figure lla is the Folded Tree being constructed with the assignments indicated (by the Pk above iAj -these assignments would not be known, of course, until the entire process has been completed). Figures llb-e show its decomposition into Minor Trees. Below are the corresponding S(i,j) -the arrows indicating how the splitting took place. The S(i,j)'s shown in Figure 11 were calculated on the work sheet and used to determine the assignments given in Figure ila. They are given there so that the relation of T(ij), S(i,j), and iAj may be seen. Consider now the following procedure for splitting. It is convenient to think of it as consisting of three steps: Step One. Delete U(S(i,J)) from S(i,j). (In the Table, these reduced Distributions, which are the ones to be split, are labeled S(i,j)* in column 1, the two determined by the split are labeled in column 2, and appear in the immediately following lines. ) Step Two. Consider the coefficients of the terms of S(i,j)* in monotonic increasing order. Suppose there are r terms: denote the coefficients in their monotonic order by'ala2,...ar, and denote the corresponding coefficients of S(i+l, 2j-l) by'bl,...br' and those of S(i+l,2j) by'C1t,.,. crr Step Three. Determine the bi and ci by the following rules: (A) If al =2 then bi = Aa At and ci = Cai + 1 - AT for all i where Ai (c. -b) j=l J (B) If al> 2 then b = al-l b2 =; C1= 1 c2 =a2-l and bi and ci are given by the formulas of (A) for i>2 The- idea behind these formulas is quite simple and they are easy to apply after a very little practice. It is: (1) to provide for the'11 in each set of coefficients, and (2) to split the ai, i>2, in such a way that the sum of the "b" coefficients determined through i is as The asterisks (stars) appearing in Steps One and Two are part of the symbolism. The brackets represent the greatest integer in the contained quantity as before. 49

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN nearly equal as possible to the sum of the corresponding "c" coefficients with the somewhat arbitrary proviso that at every step Ai' 0. It is worth pointing out that in actual calculation the work is even simpler than it appears from this description, because all terms (except possibly the first three) are split as evenly as possible. If aj is even, then b. = c = aj/2. If aj is odd, then consider Aj if it equals 0 Let the larger part of aj be ec;if it equals 1 let it be bj. This does not mean that it is necessary to compute the sums each time; it is only necessary to keep track of the difference (which can be only 0 or 1 for j - 3 ). The method is now applied to splitting S(1l1) of the example into S(2,1) and S(2,2) Step One, Delete U(S(ll)): S(l,l)* = S(1,1) - U(S(l.l)) = 8P1 + 7P4 + 8P5 Step Two. Assign the labels'a.i so that the i's represent the monotonic order of the coefficients of S(l,l)* a4 a1 a2 a3 8P1 +7P3 + 7P4 + 8P5 b4P + blP3 + b2P4 + b3P 5 c4P1 + clP3 + c2P4 + 3P5 Step Three. Calculate bi and c Since 7 = a1 > 2 we apply rule (B) b1 = al- = 6; b2 = 1 C; c2a2-1 = 6; b= [8+ (7-7)4 —77) = 4 = 8=[8+1(T )1 2 2 b4= [8+(l-ll)] = 43 4 [a+l(2l )] = 4 Repetition of this 3-step procedure will yield all S(ij) Table..III illustrates a systematic work sheet for recording the calculations. The two sequences determined above appear on lines 2 and 3 respectively. After practice all the necessary calculations can be performed mentally and the results written directly onto the sheet. Now'nsider part II, the assignment of the Double-ands of T(11l) to input pairs, The rule is simple: Assign iAj to U(S(ij)) 50

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Thus if the assignment of 2A2 is desired, consider S(2,2) = 4P1 + 1P3 + 6P4 + 4P5. Clearly U(S(2,2)) = 1P3 and so by this rule 2A2 is assigned to P. The assignments of all the iAj of the example are given in Diagram lla. The Folded Tree, T(1,1), constructed by this method will have a Key. The following Technique summarizes the procedure and indicates, parenthetically, the modifications needed if a Key is lacking. Technique 4. 1. Test the desired Load Distribution for Admissibility. If it is Admissible, call it S(1,1) and proceed to step 2. (If the Load Distribution has no unit term, it may be an Admissible Load Distribution for a Tree without a Key. There must, however, be at least one term with coefficient 2. Choose one of these, say 2Pk, replace the 2 by a 1, and apply the criteria to the resulting Load Distribution.) 2. Construct a Standard Tree with Key adjoined (unless the Key is lacking as indicated above) with the appropriate number of input pairs but without connecting them to Double-ands. 3. Determine. the assignments of the iAj by: a. Generating the set of S(i,j) from S(1,1) and b. Assigning iAj to U(S(i,j)). (If T(1,1) does not contain a Key, then S(1,1), reduced by eliminating 2Pk, is defined as S(1,,l)* and handled accordingly. In all other respects the method is unchanged.) 4.. In the Standard Tree constructed in step 2 make the connections indicated in step 3. 51

TABLE III Column Colunn Column Column Pi P2 P3 P4 P5 P1 P2 P3 P4P5 1 2 1 2 S(1,1) S(1,1) 8 1 7 7 8 S(4,2)* 2 S(2,1) 4 6 1 4 S(5,3) 1 I S(2,2) 4 1 6 4 S(5,4) I I S(2,1)* I 4 6 4 S(4,3)* 2 s(3,1) 3 3 1 S(5,5) 1 S(3,2) 1 3 3 S(5,6) 1 S(2,2)* 4 6 4 s(4,4)* 2 (3,3) 3 3 1 (5,7) I I I I 1 S(3,4) 1 3 3 s(5,8) 1 s(3,.,1)* 3 3 s(4,5)* 2 S(4,1) 2 1 S(5,9) 1 s(4,2), I 2 1 I s(0, ) 1!S(3,2)* 3;3 s(4,6)* I I I 2 S(4,3) I I I S(5,11) I I I S(4,4) 1 2 s(5,12) 1 S(3,3)* 3 3 S(4,7)* 2 s(4,5) 2 1 s(5,13) 1 S(4,6) 2 1 I (5,14) 1 s(3,4)* 3 3 s(4,8)* S(4,7) 2 1 s(5,15) S(4,8) 1 2 1(5,16) I 1 S(4,1)* 2 S(5,1) 1 Total number 8 1 7 7 8 S(5,2) 1 of'l's' These are S(i,j) without the term with unit coefficient. 52

BIBLIOGRAPHY 1. "Standards of Electronic Computers-Definition of Terms, 1950", The Institute of Radio Engineerst, 1 East 79th Street, New York 21, N.Y. 2. Keister, Wm., "Logic of Relay Circuits", Trans. AIEE (Part I), 68, 571-576 (May, 1949); Ritchie, A.E., "Sequential Aspects of Relay Circuits"', Trans, AIEE (Part I), 68- 577-581 (May, 1949); and Washburn, S.1H., "Relay tTrees t and Symmetric Circuits", Trans. AIEE (Part I), 68, 582-586 (May 1949). 3. Buffery, G.H., "A Contribution to the Algebra of Relay and Switch Contacts", Proc. IEE (Part I), 97, 357-363 (November, 1950). 4. Montgomerie, G.A., "Sketch for an Algebra of Relay and Contactor Circuits", Proc. IEE (Part III), 95, 303-312 (July, 1948). 5. Lewis, I.A.D., "A Symbolic Method for the Solution of Some Switching and Relay-Circuit Problems", Proc. IEE (Part I), 98, 181-191 (May, 1951). 6. Shannon, Claude E., "A Symbolic Analysis of Relay and Switching Circuits", Trans. AIEE, 57, 713-723 (1938). 7. Rjachman, J,* "The Selective Electrostatic Storage Tube", RCA ReV. (No. 1), 12 (March, 1951). 8. Brown,: D.R., and Rochester, N., "Rectifier Networks for Multiposition Switching", Proc. IRE, 37, 139 (1949). 9, Synge, J.L., "The Fundamental Theorem of Electrical Networks", Quart. App. Math, (No. 2), 9, 113-127 (July, 1951)* 10, Shannon, C.E., "The Synthesis of Two-Terminal Switching Circuitst'". Bell System Tech. Jour. (No. 1), 28, 59-98 (January, 1949). 11, Staff of Computation Laboratory, "Synthesis of Electronic Computing and Control Circuits", Annals of Computation Laboratory of Harvard Univ., 27, Harvard Univ. Press, Cambridge Mass., 1951. 12. Keister, Wm, Ritchie, A.E., and Washburn, S.H., Synthesis of Switching Circuits, D. Van Nostrand Co, Ine., New York, 1951. 13. Veitch, Edward W., "A New Method of Logical Equation Minimization", Burrou;ghs Adding Machine Co., Research Division (unpublished). 53

INDEX OF TERMS The page numbers refer to occurrences of the terms where they are defined or explained. Term Page Term Page Admissible 46 Function, Transliterative 26 Bay 18 Input 3 Bits iv Language v Branching 15 Load Distribution 42 Cartesian Conjunction 10 Loading Couple 40 Cartesian Product 9 Minimal 40 Chain 7 MS (Multiplicative Switch) 11 Chain, Conjunctive 7 MS Net 14 Character v MS Net, Balanced 19 Character basic iv MS Net, Simple 15 Character-token v Natural Outputs 6 Character-type v Network 5 Coefficient, Parallel Loading 7 Output 3 Coefficient, Serial Loading 7 Polar Pair 13 Construction Formua. 15 Polarized 13 Conversion, code viii Polarizer 13 Conversion, code-and-format ix Polar Sequence 26 Conversion, format ix Pulse output 36 Conversion, language ix Realization 26 Double-and 5 Splitting (Folded Tree) 48 Element, Conjunctive 3 Splitting (of MS output) 15 Element, Disjunctive 3 Switch 6 Element Input Count 6 Switch, Conjunctive 9 Element, Logical 3 Switch, Exponential 13 Element, Negation 3 Switch, Function 1 Element, primitive 3 Switch, Multiplicative (MS) 11 Function, Decoding 27 Switch, unique 19 Function, Decoding, Complete 27 Technique 27 Function, Encoding 30 Tree, Folded 43 Function), message transliteration vii Tree,: Minor 44 Function, Stroke 22 Tree, Standard 16 Function, Strokei, Conjunctive 22 U, u Union (Set Theoretic) Function, Stroke, Disjunctive 22 Wire 3 Fun-tion, translation vi X Cartesian Product or Cartesian Conjunction 54

UNIVERSITY OF MICHIGAN 3 901 5 02947 50531111111 3 9015 02947 5053