ENGINEERING RESEARCH INSTITUTE UNIVERSITY OF MICHIGAN ANN ARBOR Informal Memorandum 4 LANGUAGE CONVERSION FOR DIGITAL COMPUTERS Volume II THE PHYSICAL REALIZATION OF CODE AND FORMAT CONVERSION ARTHUR W. BURKS CARL H. POLLMAR DON W. WARREN JESSE B0 WRIGHT Note: This material is issued as an informal memorandum because it is tentative, it has not been completely checked, and the exposition is unpolished. Administrative circumstances prevent further work on the material. Consequently, it is necessary to present the results so far achieved in this form rather than in a complete regular report. Project M828 BURROUGHS CORPORATION RESEARCH CENTER PAOLI, PENNSYLVANIA August 15, 1954

UM- //o 2

ii. Table of Contents page Acknowledgments........................... iii 1. Introduction..................1 2. Realization of Primitive and Auxiliary Elements.... s................11 2.1. Conjunction (tandl) Elements.......ll 2.2. Disjunction "(org") Elements........19 2.3. Other Elements...............23 3. Code Converters for Transliterative Functions.............................32 3.1. Decoding Functions................ 35 3.2. Encoding Functions.....9..........52 3.3. Arbitrary Transliterative Functions.......................... 58 4. Code Converters Requiring Memory.........73 Bibliography.....................87 Corrigenda for Vols. I and III..............88

iii. Acknowledg Lenuts The organization and semi-final draft of this memorandum were produced by Mr. Pollmar just before he left the project. Final editing, which has been necessarily cursory, has been done by the other authors without benefit of consultation with Mr. Pollmar. Their remarks are inserted in footnotes labeled "Ed." wherever possible. The seeds of this three volume series are to be found in an unpublished paper, dated 1951, by Hugh Livingston of the Burroughs Corporation Research Center. Unlike Vols. I arnd II1 in which Mr. Livingston's ideas performed solely a catalytic service, the present volume incorporates an appreciable portion of his work including a number of only slightly modified circuits for which the authors wish to express their indebtedness. Mr. Livingston did not, however, participate in the preparation of this volume zand is to be relieved of any responsibility for it.

THE PHYSICAL REkALi4ATIOi OF CODE AND FORiET CO i1 Vi EiAiiO0i4* 1. introduction. In Vols. I and III we are concerned with presenting a theory to aid in the first stage of design, i.e., the construction of an abstract logical design based on logical operations. Here we are concerned with the relationship between such logical designs and physical circuits. In the abstract of this series (Vol. I, p. ii) it is stated that in Vol. II would be discussed: (1) the physical realization of logical nets, and (2) circuits for format conversion. However, the considerations that led to the issuaice of this volume as an informal memorandum rathler than as a regular report preclude an elaboration of theory for format conversion and memory equipment. Consequently, only code conversions and a few code-andformat conversions which are predominantly transliterative are discussed here. Section 4 contains three examples involving some format conversion and for this reason the title of the volume has been left unchanged.

This relationship has many aspects with most of which we will not be concerned. For example, a logical net may be used to study the behavior of a physical circuit, each circuit element being replaced by a small net of logical elements. The converse of this, the construction of circuits having the same behavior as a given logical net (ioeo, the "physical realization' of the net), is the problem with which we will be primarily concernedo Some characteristics of the net which are significant relative to circuits may be described by "indices"o Roughly speaking, indices are numbers associated in some manner with nets or with portions of nets0 The number of input pairs, the element count, the'serial loading coefficient, the rank of an element, the "use" of a wire are all indices0 Not all of these need have significance for physical realizations, and the significance of those that do will depend upon the type of circuit element used in the realization0 For example, the element input count in the case of a realization of a conjunction by crystal rectifiers counts the

3. number of crystals. It is less significant in the case of a relay realization where both contacts and coils must be considered. In general, the usefulness of these indices might be extended if (1) more use were made of auxiliary elements, e.g., those with associated functions equivalent to tube operators, and (2) if the appropriate indices, e.g., element input count or some other weighted index, were associated with them. Obviously much work could be done in the study of indices and of their significance for nets and circuits. In this volume, however, only the element count, the element input count, and the parallel and serial loading coefficients will be used. Their significance will be pointed out in the consideration of examples. As noted above, the present report is confined primarily to a survey of the problems of "realization"' in terms of examples and a brief discussion of them. To do this, the concept of realization must be defined explicitly. This requires that (1) a physical interpretation (called the O,1 convention) be associated with the states

4. O and 1, and (2) that each logical element be replaced by a physical circuit (whose components, for example, may be relays, crystals, tubes, etc.) with a single output, with the same number of inputs, and with the same "behavior" as the logical element. To say that such a circuit X has the same behavior as an element X (or is a realization of X) means that (1) the behavior of the circuit's input and output may be described by a function table in terms of two physical states, and (2) if those states are translated into O's and its by the 0,1 convention, then the resulting function table is that of the logical element. Note that the same physical equipment may realize different logical elements if different 0,1 conventions are employed. The truth (function) tables for the common logical elements are Coni untion Di s uncti tion 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 11 1 11 1

5. ConDiunction Stroke Disjnction Stroke 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 I0 1 1 0 It is possible, as the following example shows, to use different 0,1 conventions at different points of a circuit provided that no contradiction arises. When this is the case, a multiple 0,1_ convention is employed. If T is a logical tree with key which is realized by a relay tree (see Fig. 1(D) ), then either of the following conventions is possible. (1)* 14- -high voltage, O*c -ow voltage, everywhere. (2) Convention (1) on the input pairs (the inputs corresponding to the coils) and 1 f - pulse, 0 -absence of a pulse, elsewhere. The first convention defines a converter operated statically, and the second, a converter with static input and pulse output. Here and in several succeeding discussions of relays the convention might more appropriately be expressed as 1-' closed circuit, 04' open circuit.Ed.

P3 P2 P3 P2 (A) P1r (B) Fig. 1

7 Decoding Pulse 12012 1201A ~~~~2P1 P1 P2 P2123 A 1201A 1201A 201A P1 P1 P2 P2 P (C) Fig. 1 Pulse Control Unit Folded Tree

83 R1 2R1 Decoding 1l Pulse 3R2 2R2 3R3 2R3 1R 2R 3R Coded Input (D) Fig. 1 Relay Folded Tree

9. In Section 2 various ways of realizing primitive and auxiliary logical elements are considered. The 0,1 convention for each case is explicitly stated. Among those considered are the conjunction elements, the negation element, the stroke elements, and the double-and. Section 3 contains examples of different physical circuits that are realizations of simple decoding and encoding nets such as the exponential switch, the tree, and the balanced multiplicative switch (MS) net. It also includes two examples of converters for an arbitrary transliterative funuction: the first illustrating tile decoding-encoding techniques, the second illustrating the "direct" method. A circuit produced by substituting a physical realization for each logical element in a net is quite often not as simple as it could possibly be. The simplification which may be carried out depends largely on the types of realization (e.g., relay, crystals, tubes, etc.) employed. We wish to emphasize that we are not engineers and have made no attempt, in general, to simplify the circuits. However, in certain obvious cases, some

10. simplification has been made by example. Throughout Section 3 the discussion is directed toward net characteristics and the significance of the various indices for the corresponding physical circuits. In Section 4 the use of these circuits as components in more complicated code converters, such as those required for conversion involving a shift code, is illustrated by three examples.

11. 2. _ealization of Primitive and Auxiliary Elements. The most important primitive elements for the theory developed in this report are the conjunction ("and") and the disjunction ("or") elements. Subsections 2.1 and 2.2 are devoted to examples of circuits which realize them or logical elements closely related to them. Negation and the stroke element are considered in Subsection 2.3 where also realizations of an MS and ofI an encoding net are discussed for these can be considered as auxiliary elements from which more extensive nets cal be constructed (e.g0, MS nets). 2.1. ConJunction ("and") Elements. A physical unit corresponding directly to the 2-input conjunction is the Burroughs pulse control* Coincidence Detector, Type 1201 A. It is essentially a dynamic gate (ordinarily driven by a flip flop). If the 0,1 convention is for p and r: 1 <: presence of a pulse, 0 * - absence of a pulse, for q: 1-* 0 volts, 0 O > -23 volts, then the operation of a 1201 A is that of a See bibliography, item 3, for details of all pulse control units.-Ed.

12. conjunction and is given by Table I 0 0 O O 1 O 1 0 0 1 1 1 where q 1201A The Type 1202 A Coincidence Detector p1 ip1202A r P5 may operate as a conjunction under the following convention: 1 4 - 0 volts, 0 <- -23 volts. Its behavior table, then, is Table II P1 P2 P3 P1 P5 r 0 0 0 0 0 0 0 0 0 O 1 O. all 11 1i 1 0 1 1 1 1 1 1

13. The 1201 A is a 2-input conjunction and the 1202 A, used as above, is an n-input conjunction, n = 2,...,5. This difference is of little significance in the logical analysis, for an n-input conjunction can always be realized by a net of 2-input conjunctions. A conjunction may also be realized by a relay coil with a make-contact. Consider P' r \q Fig. A If the 0,1 conventions are: 1 -, positive voltage, 0 e ) ground potential (for p the conventions might alternately be: 1 v- pulse, 0 * > absence of pulse), then the behavior of this circuit is described by Table I above. Thus, it is a physical realization of a 2-input conjunction. An n-input conjunction, r- poq1.q2.....qn_1

14. may be realized by putting (n-l) relays in series thus:* p r ql q2 qn-1 If p is connected to a positive voltage source (or a clock pulse source), then r may be considered as the conjunction of ql'''qn-l where the 0,1 convention for the qi is as for Fig. A. If a break-contact is used, then the relay unit is a realization of a net consisting of a conjunction with the q-input negated. Consider the relay, r p q Fig. B Note that this relay realization of an n-input conjunction could also be considered as a compound circuit built up from the relay circuits (Fig. A) realizing a 2-input conjunction.-Edo

Using the same 0,1 convention as before, this relay unit has for its associated behavior table Table III 00 0 0 1 0 1 0 1 11 1 and this is the table for p- *q which in terms of logical elements (see Vol. I) can be represented by P Ax - r. Finally, consider a transfer-contact relay (Fig. C) which is composed of a make-contact, a break-contact, and the coil. (q iK1 rr r2 Fig. C

16 If the 0,1 conventions are for p, rl, r2: i * > pulse or positive voltage, 0 < absence of a pulse or ground potential, for q: 1 <-> positive voltage, 0' > ground potential, then the behavior table is Table IV p q rl r2 0 0 0 0 1 0 0 1 1 1 1 o which is the same as that for the net below, a double-and with polarizer (see Vol. I). P, rl r2 q Fig. D

17. it should be noted that a relay circuit realizing a conjunction under a given set of 0,1 conventions may realize it under one or more other O,1 conventions as well because of the physical nature of the relay and particularly because of the coilo For example, some of the conventions for which the circuits of Fig. A will realize a conjunction are: el l 1 t- pulse, 0,-, absence of a pulse, iq: 1 - t, voltage, 0 4 - 0 voltage; ~p: 1 c > pulse, 0 ~ > absence of a pulse, ~(q: 1 t- - voltage, 0 > 0 voltage; Ip: 1 -~ + voltage, 0 O voltage, =q: 1i ~- + voltage, 0 O 0 voltage; (p: =1< — - voltage, 0 < - 0 voltage, [q: l*-1 - voltage, 0 O voltage. This is usually true of realizations using other components. However, the change of the 0,1 convention will in many cases alter the logical function which the circuit realizes.

18. ColnjLcCtions may also be realized by crystal rectifiers 1ie. if the C,i co.nvenstion is 1 P — high voltage, 0 t lovw voltage, thlen the behavior of" thle foliio l circuit is tt is t of an n-input conjunction. For n = 5, its f-unction is given by Table II above. +/ -.'V... N- r P1 P2' Pn The output, r, has high voltage if and only if P1 "~P have high voltage. Coil njlctions many, of course, be realized by tube circuits. Because the operation of tubes as used inI computers seems to be most naturally described by the stroke function, and because the stroke function is a "iogically-suLfiicient primitive'", the conjunction may be realized by a small tube circuit. Because of tnle relationship of tubes and stroke functions, the discussion of the realization of conjunxctions by tubes is included vawith the discussion of the stroke fmnlctions in Subsection 2o3o

19. 2.2. Disjunction ("or'" Elements. In some cases a disjunction may be realized simply by joining the two or more wires which form its input set. If this is possible, it is the cheapest foiim of' realization. Often, however, it is impossible to realize disjunction without using diodes, for example, to prevent "sneak circuits" and some realizations of this kind are discussed later in this subsection. Disjunctions, like conjunctions, may be realized directly by Burroughs pulse control units. For example, the Type 1202 A Coincidence Detector which, with the 0,1 convention specified in the last section, represents a conjunction canl with the opposite convention, 1' -23 volts, O -> 0 volts, represent a disjunction. Its behavior table, then, is Table V P1 P2 P3- r 00000 0 1 0 O 0 10 0 1 0 0 0 1 1 1 00 0 1 0 0 1 0 1 all 1 1 1 1 1 1])lsi This is the table for a 5-input disjunctiono

20. The Type 1601 A and Type 1602 A Mixers are also physical realizations of disjunction for if L > presence of a pulse, 0 < absence of a pulse, then their behavior is represented by Table V (for the 4-input 1601 A delete column p5 and the bottom sixteen rows). Disjunctions may be realized by relay circuits. Consider the following with the convention, 1 -, + voltage, 0 O0 voltage, defined in the previous subsection for the relay of Fig. A. ql q2 q3 + + t The behavior of this relay circuit may be described by columns Pi, P2, p3, and r in the first eight rows of Table V and clearly is disjunctive. Crystal rectifiers may also be used to realize disjunctions. Consider P''' Pn

21. If at least one of the Pi is at high voltage, then r will be at high voltage (because the rectifying properties of crystal prevents the flow to any pj which might be at low voltage), otherwise, r will be at low voltage. Thus, if 1': high voltage, O - 4 low voltage, tile behavior of this net can be described, for n - 5, by Table V. Another realization of a disjunction -- and a very economical one -- is by means of a Bell A.M. A. ring-transformer such as is represented below.. The ring is the core of the transformer, the input wires Pi which are led through the ring represent primary windings, and the winding r on the right is the output or secondary winding. P2 r Pn

( IP (A) - (B) Relay arid Tube Realization of Negation q _ — p r (C) Tube Realization of Disjunctive Stroke p + q = r (D) Tube Realization of Conjunctive Stroke q - V — r (E) Tube Realization of a Conjunction q ( _; __ ) p F > - _ vr _ _ r b > r Tube Realization of a Disjunction _______ _ Fig. 2*.See bibliography, item 2, for further details.-Ed.

23~ If a high voltage is applied to one or more of the Pi, current will flow in that primary and a potential will be induced in r, otherwise not. Using the customary conventions, the behavior of this disjunction is again represented, for n = 5, by Table V. As in the case of conjunction, disjunction may be realized by tubes. A discussion of this kind of realization is postponed until Subsection 2.3. 2.3. Other Elements Conjunction and disjunction are the two logical elements most widely employed in the networks of this report. Several others, however, should be briefly considered. Negation, which is required for polarizing nets, may be realized, for example, by the relay circuit of Fig. 2(A) (cf. also Fig. B, p. 14) or the triode circuit of Fig. 2(B). The output voltage of the triode will be high if the voltage applied to the control grid is low and vice versa. If then the 0,1 convention is 1 t- highl voltage, O c - low voltage, the behavior table of this circuit

24. P R r 0 1 is that of negation, 1 0. In practice negations are often unnecessary because the input is in polar pair form. The stroke functions may be realized easily by tubes. The circuit of Fig. 2(C) is a realization of the disjunctive stroke. The twin triode with a common plate resistor will have a high output voltage if and only if both control grids (p and q) are low, i.e., its behavior table is O O i O 1 O 1 O 0 1 1 O0 Clearly, this is the table of ~(p v q), the disjunctive stroke. Fig. 2(D) is a pentode realizing the conjunctive stroke. Its output will be high at all times except when the input voltages applied to the grids, p and q, are both high0 Thus, it has the following table. ~P q =r 00 1 0 1 1 t 0 1 1 1 O This is the table for ~'(p-q), the conjunctive

25. stroke. Since the two stroke elements are represented by the following logical nets, (conjunctive stroke), (disjunctive stroke), and since conjunctions, disjunctions, and negations are realizable in relay nets, it is clear that these stroke elements can be realized in relay circuits (i.e., substitute the relay circuit for the corresponding logical element). Conversely, the following logical nets (see Vol. I, Subsection 3.2), conj unction dis junction are realized as in Fig. 2(E) and Fig. 2(F)' by substituting tube stroke and negation circuits for the corresponding logical elements. The remainder of this section is devoted to two circuits (for the MS and for an encoding net) which might appear more closely related to the

260 code converters of Section 3 than to the primitive elements of Section 2o These two realizations are exceptional, however, in consisting basically of a rotary selector switch which, though it does not correspond directly to any of the primitive logical elements, does clearly have the primitive attributes of being a relatively indivisible, "atomic" piece of equipment and of having an internal structure which does not seem to be amenable to any obvious analysis in terms of the standard logical primitives.* Thus, inclusion of these two circuits here confines to Section 2 the introducing of all the types of equipment to be considered and allows Section 3 to focus more sharply on the techniques for combining these types of equipment to effect code conversions. This point might warrant further study -Edo

27. Fig. 3 shows a rotary selector circuit which realizes an Mb. One arc of contacts is assigned to each input set Ij (these sets are defined by the M6) and one additional arc is assigned to the output. Each arc has as many contacts as the net has outputs which, since anl IS effects a complete J decoding, must be equal to 7T N(IJ) (in the example, 4x3 - 12). In operation the wipers, being rigidly joined together, will sweep from one row of contacts (one contact from each arc) to the next physically adjacent row. Each (kth) row is connected through a relay buffer to a unique output wk and the jth input contact of this row is connected to that wire of Ij which must be activated in order to activate wk. The circuit joining the wipers is a relay conjunction: its inputs being connected successively, as the wiper sweeps, to each of the possible input combinations (elements of the Cartesian Product of the Ij) and its output, at each step, being connected to the corresponding circuit output. If we take 1 < - + voltage, 0 O0 voltage, as the 0,1 convention, the operation of the circuit is

28. W2 W3 o6 — I2 Al 2Output 7 10 I1 12 13 14 21 22 23 Rotary Selector Switch as an AS For I1, 12,.o., IJ number of arcs J; J number of contacts per arc - 7N(lj)o 1 Fig. 3

29. described by the following table (where the blank spaces represent zeros). Ill 11 2 113 114 121 1'22 123 WV W21j W W~ 5 W1 W71 81 W91 YU(1 WOl q2 1 1 1 1 I1 1 1- _.......... 1 _ _. i i __ 1 1 (under appropriate operatio) is a realization of an MS............_1 1........1. 1 1 I I I I II II )1 __ 1 _........ i [I 1 I I I~I II __... i i s ince this is a tabl e for an aS with input sets'1 and 1, it is clear that this circuit (under appropriate operation) is a realization of an MS. Fig. 4 is a circuit realizing an encoding switch. M+l arcs are needed, one for each of the M bit positions in the range code (i.e., the code into which we are translating) and one for the input. Some of the ii() contacts of an arc are connected to the appropriate output in such a way as to effect a disjunction. Under operation as an encoding circuit, exactly one of the Wi will

30. Output - -W ~ W1 W "2 1W3 4 / 2 0~_ 0 W5 0 W3 Rotary Selector Switch as al Encoding Circuit Fig. 4

31. carry positive voltage, the others will be at ground potential. If Wi is positive and the wipers are in contact with the ith contact of each1 arc, then the Wj which are connected to the ith contact of the jth arc will be positive. Using the 0,1 convention, 1 <- + voltage, 0 E 0 voltage, the operation of this circuit can easily be seen to be equivalent to that of the following logical net of which it is a realiW1 W214 zation. t t o The principal objection to t-e us- of the rotary selector'is its low speed of oper...tion. it is, nevertheless, an interesting device.

32. 3. Code Converters for Transliterative Functions. In this section circuits are constructed for logical nets which realize (for definition, see Vol. 1, p. 26) transliterative functions. Transliterative functions are, roughly speaking, single-valued functions which map a set of sequences of 0 s and l's, all of the same length, onto another set of sequences of O's and 11s, also all of the same length. For our purposes transliterative functions may be divided into three classes: decoding functions (Subsection 3.1), encoding functions (Subsection 3.2), and arbitrary transliterative functions (Subsection 3.3). The technique of circuit construction which will be used (and which is assumed to yield a circuit with the desired behavior) consists, first, of drawing a logical net to effect thie desired transliteration, and, second, of replacing each logical element by a realization of' that element. Different physical circuits may be obtained by replacing a given logical element of the net by different physical realizations of that element.

33. The realizations of the logical elements must be 1"compatiblet"(e.g., the 0,1 conventions must not conflict, no significant timing discontinuities may arise). In many cases the resulting circuit may be simplified; usually this possibility arises because of the special properties of the physical elements involved. A few examples of such simplifications are given though no generally applicable theory has been formulated and some of the circuits presented undoubtedly could have been further simplified. The circuit designer is interested primarily, of course, in constructing a circuit which will perform some given function, i.e., will have a certain specified "behavior" under certain specified operating or input conditions. Within the limitations imposed by behavior requirements, he will be further guided by such considerations as: minimality, reducing the number of component parts and, hence, the cost of the circuit; parallel loadinr, the number of t"driven't units to which a "driver" can be connected in parallel (e.g., tubes

34. per flipflop, contacts per relay coil); and serial loading, the number of units which can be safely connected in series (e.g., crystal rectifiers which attenuate the signal). The network theory of Vol. I deals very directly with the behavior problem and, by means of indices, also sheds some light on such subsidiary problems as thosee mentioned above. There are, of course, many design factors which cannot be taken into account at the abstract level, and those that are can be treated in ornly a very general way as a means of rather rough comparison of broad classes of realizations. In presenting circuit realizations of logical nets, therefore, we will also attempt to translate the indices associated with these nets into measures of physical characteristics of the circuit wherever resulting figures appear to have practical significance. The physical behavior of a circuit can be determined very easily from the state of the corresponding net. To calculate the state of a net, given the state (O or 1) of all inputs,

35. proceed as follows: (1) let N be the given net and label the inputs of N with O's and l'ts in the desired fashion; (2) repeat as many times as possible the following operations, (a) find an unlabeled wire BC whose origin B is the terminus of a wire AB with label Q (o 0 or 1) and assign label cx to BC, (b) find a logical element all of whose input wires, wl,oo.,wn, are labeled, and assign to its output the label =- O-1,>~..n, nowhere cti is the label of Wi and-L is the logical function (e.g., conjunction, disjunction, etc.) associated with the element. The states of the corresponding circuit wires are then determined by the 0,1 convention~ 3o1 Decoding Functionso A decoding function is a transliterative function, each range sequence of which contains a single lo Such functions can be translated into logical nets which are exponential switches, trees, or balanced MS netso In this subsection many different physical realizations of these nets are constructed and examined. The circuits are drawn so

36. as to emphasize the logical structure, sometimes at a sacrifice of some of the conventional engineering details. For example, in Fig~ 5 only enough wires and labels are presented to establish the pattern of interconnection; also, the "remoteconnection' device is used, i.e., two wires with the same label are to be considered connected. A relay realization of a 4-input-pair exponential switch is shown in Fig. 5. Fig. 5(A) is the logical net and Figo 5(B) is its realization.* The 0,1 convention is 1 - + voltage, O >-open circuit,** The element input count, which is 48 in this case, is the number of relay make-contacts (also, in the diagram, the number of coils). The parallel loading of Pi, which is 8, is the number of contacts operated by Pio. The serial load clearly has little significance hereo One obvious way that this circuit can be simplified is, for each Pi, to replace all eight relays that it drives by a single relay unit consisting of a coil connected to Pi and *Note that this realization is effected by the purely mechanical procedure of replacing each 4-input conjunction element in the net of Fig~ 5(A) by its relay realization as defined in Subsection 2.1o - Edo "**Other conventions are possible, - Ed

37. "" +;'I-'+ - PlP2 P3 P PIP2 P3,r-P P2 - 1;-P 9III.~p4 9 9 P1 -- ~P2 )~ t- Exponential Switch pDo Relay Realization P3 - P- -4- - 4U' -i,~,._... Pi P3' mp4 + P3 Pl P1 P2 P2 P3 P3 P4 P4 (A) (B) Fig. 5

38. eight associated make-contacts. In the original circuit, if the inputs are not polar pairs, a polarizing net is needed. In this case the polarizing net and the conjunctions can easily be combined. All that is necessary is to replace every make-contact operated by Pi by a break-contact operated by Pi. In this way only wires Pi will be required. In Fig. 6(A) a 3-input-pair folded tree without key is given. Fig. 6(B) is a realization of the conjunction net in terms of relay circuits introduced in Subsection 2.1 of the type P r. q' The type of relay conjunction used in the exponential switch example may, of' course, be used here.* A more efficient realization could also be produced by substituting relay double-ands (Subsection 2.1) for the vertices of Fig. 6(A). The 0,1 convention *That is, impress a constant voltage on the wire P and supply a second coil for the P-input. This realization is obviously wasteful of equipment.-Ed.

9'sTj (q) Td Td Td11- i d Zd ad fa d d I ZI td~d.J 7 All, ( - X Cd Td d IId ___ta

40. used here is 1 -< + voltage, O * > 0 voltage. The parallel load of Pi, i = 2, 3, is the number of make-contacts controlled by Pi. A similar fact holds for Pi. The serial load of Pl and Pl is the number of stages (bays) through which the signal must pass. Finally, the element input count is twice the number of contacts. Clearly, the practical interpretation of these indices will vary with the form of the realization. If the inputs are Pi, P2, and p3 (i.e., are not in polarized form), then replace every makecontact controlled by a relay connected to Pi by a break-contact and coil operated by Pi. Then the set of contacts operated by relays controlled by Pi may be replaced by a unit consisting of a single coil and a set of relay transfer contacts. A break-contact operated by a relay coil controlled by Pl (with its contact connected to a positive voltage) is needed to give P1- If, in addition, p1 is given by a make-contact (although this is not necessary unless the tree is to be operated dynamically), the resulting network is the usual relay tree. See Fig. 1(D).

41. In Fig. 1(C) the logical tree of Fig. 1(B) is realized by pulse control units. The 0,1 convention is for Pi: l- > -23 volts, 0* -0 volts, for the others: 1 t ~ pulse, 0 - no pulse. Here the parallel load may be interpreted to mean the number of 1201-A's driven by a single flipflop, and this, according to the specification, has a maximum of 6. This means that, if we do not wish to provide extra flipflops, we are limited to trees (folded) with a maximum of four input pairs. For this case the best possible load distribution (LD) is 1P1- 4P2 4 5P3 +5P4. If five input pairs are required, the best LD is 1P1+ 7P2+7P3-+8P4+ 8P5,* and additional flipflops are required. What the best possible LD's are when additional flipflops or relay coils are needed has not been investigated. Trees may be realized by crystal rectifiers or tubes by substituting the desired circuit for thile logical conjunctions and defining the appropriate *This is the "best balanced" LD. However, 1Pl+ 5P2+ 5P3 4-10P lOP5 might be better for this purpose since it requires only one flipflop for each of P1, P2, P3 and two each for P4, P5, and all flipflops except that for P1 can be loaded equally.Ed.

42. 0,1 conventions. Fig. 7(A) shows a balanced MS net with four input pairs, and Fig. 7(B) is its crystal realization. Here, 1 v > high voltage, 0 4-' low voltage. The element input count is the number of crystals required and so is a direct measure of the cost. The parallel loading coefficients of the input wires do not have much significance for balanced kS nets since they have a maximurm value of 4. Although the parallel loading coefficient is an adequate loading index for trees and exponential switches, it is not for the balanced MS net, for in these nets the parallel loading coefficient of conjunctions (i.e., the number of logical elements to which the output is connected) in the interior of the net may be large. For example, in the diagram below (p. 48) which represents a balanced MS net (each Mi being an MS) with five input pairs, the conjunctions of M3 have a parallel load of 8. This load is

43. P1 P2 Pl P3P4 P3P4 P3P4 P3P4 t _ t tt I T t P1 P1 P2 P2 P3 P3 P4 P4 (A) 4-Input-Pair Balanced MS Net Fig. 7

44. L~~ IttiyI *1- It 4t -.. - P2 1 2 ~N~ I LFig. 7L Cs....... a o'- d, 2~_' ~ ~ ~ (B

45. i+M1 13 o IT _ i_ I202I A I 12 1202A P! Pl, P2 P2_'_:' 2A 10 111202A 1 202A 1202A 1202A102 4202A 1202 1202 202A P1 P1 P2 P2 p33 P4 + 4 (C) Fig. 7 Pulse Control Unit Realization of Logical Net of Flg.7(A)

(V)L -*2T So 5 MaN'[FoT JO TT0Tqo-TzT-[Tal8 X'eTGa L * TT (a)'t7 d Pd ded Ed w-1 1w-4- ~ T — JII _ ~ ~, j Ii'., ~~~~~~~~d~T _______________________~ ~~_, Twj'[

13 OUTPUT RELAY CO1LS 2R1 15 14 13 12 P1 5 3 2 7 t T3R1 l_''4R2 __ _ _ _ _ _ _ _ _ _ _ p3 > 3R 4R P4 __ Relay Multi-tree Decoder Realizing the Logical Net of Fig. 7(A) (E) Fig. 7

48. the largest in the net and is the same as the maximum coefficient of the "best" LD for the corresponding folded tree. However, as the number of input pairs increases, the parallel loading characteristic as compared with those of the folded tree improves. -p-p 32 p 1M2 Fg 173 P1 P2 P3 P4 P5 Fig. 7(C) is the pulse control unit realization. Here the element input count is twice the number of pulse control units required. The serial loading coefficient is the number of pulse control units driven in series. If a static circuit is desired, 1202-A's are used as indicated in the figure, and the 0,1 convention is 1 -0 volts, 0 <O -23 volts.

49. A pulse output may be achieved by replacing the 1202-A's in M1 and M3 by 1201-A s and by connecting the input labeled + in M1 to a pulse source. This, of course, corresponds to a multiple 0,1 convention where for certain wires the 0,1 convention indicated above holds and where for other wires the following convention holds: 1 e presence of a pulse, 0(- absence of a pulse. Two different types of relay realization are shown in Fig. 7(D) and Fig. 7(E). They suggest the variety of forms which relay realizations can take and illustrate some of the characteristics of indices. The 0,1 convention adopted for Fig. 7(D) is 1 < e + voltage, 0~ - 0 voltage, because the outputs of the relays of Ml must operate the coils of M3. The circuit presented here can obviously be simplified. In M1 and M2 only two coils each with two make-contacts are needed and in M3 four coils each with four contacts are required. Clearly here the element input count of 24 is the number of contacts, and the parallel load of an input to an MS is either (1) the number

50. of contacts to which it is connected, or (2) the number of coils in that Mb. Thus, there is a sort of tdual"t significance to the parallel load coefficient here. This "duality" holds generally for all MS with two input nets where the conjunctions are realized as in this example. It is of some interest to compare relay trees and relay balanced MS nets at this point. While the tree is the minimal relay contact net (see Bibliography, item 4, p. 113) producing a complete decoding, the balanced MS net (not a relay contact net) for four or more input pairs has a smaller &eIement input count. In terms of the example, this means that the number of contacts in the circuits of Fig. 7(D) is smaller than that for the corresponding tree. However, it is worth pointing out that the number of coils required for a tree is minimal. Four are required for a 4-input-pair tree as compared to the eight required for the 4-input-pair balanced MS net. Fig. 7(E) is another type of relay realization, and one employing a multiple 0,1 convention of

51. greater complexity. An adequate multiple 0,1 convention can be roughly summarized as follows: in1 M1' >) + voltage, Al0 0 voltage. In M2 for coil inputs it. a-s + voltage, 9 i —to 0 voltage; for other inputs $1.- >- voltage, -O 0 voltage. In M3 for coils rectifier side'1 4- + voltage, (0 -— 0 O voltage, other side S- -> - voltage, I0 - 0 voltage; for output con- (l f * + voltage, tacts (not l t-i O0 voltage, shown) or 1 ---- pulse, O; absence of a pulse. This circuit differs in other ways from that of Fig. 7(D). Its inputs are not polar pairs, and the consequent modifications of the exponential switch have been made. The make-contacts of the relays of M3 are not shown. They may be connected to a pulse source or to a positive voltage source

52. to provide either a dynamic or static output. The use of the relays in M3 illustrates still another way in which conjunction may be realized by a relay. This is shown in the diagram below where both ql and q2 must be in the 1 state (opposite 0,1 convention applying to these two) if the coil is to operate and r be in the 1 state. 4t ql q2 3.2. Encodin Fun ctions. An encoding function is a transliterative function each domain sequence of which contains exactly a single 1. If we choose as our convention that 1 i ) positive potential, 0 4O- ground potential, then this means that in normal operation only one input wire at a time will be positively charged. On the other hand, if operated dynamically, i.e., if 1 - presence

53. of a pulse, 0 - absence of a pulse, then there will be a pulse on only one input at a time. The technique given in Vol. I requires a knowledge of the encoding function Te which is to be realized. For the purposes of our example, Te is given by the following table (the blank spaces representing zeros) which essentially maps the ten decimal digits onto their excess 3 representation. The corresponding logical net is given in Fig.8 (A). The convention that two wires with the same label are to be considered connected is again used. Te W1 W2 W3 4 W W6 W7 W W10 W1 W2 W3W4 1 9 1 1 l........ 1 1.... Fig. 8(B) and (C) give the crystal rectifier realization. Fig. 8(B) is drawn so as to emphasize the correspondence between circuit and net, and Fig. 8(C) is the same circuit in more conventional

54. wgi \ w_> 9gS /WI 4,t,_> X fEX W3 —> W6 W7 W8W9 w10 W4 W2-'~; Ww W5,-W2 W3 W4 W5 Wo w4 W4 7" W2 W3 W4 W5W W7 w5 ti VIO W9 > Wj w w 3 W32W3WW5 6W7W W W (A) (B) (C) Encoding Switch and Realizations'Fig. 8

(V)8 *3'T J: Jo N e 0o uoTeszTTleaJ A'el (ca) oTM 6 9M A LM 9M AM?M A zM TM 6 SM-i 1). K 4 iv j__t4 9 ~! t """""""" F - J

Wlo9 w8 w7 I-..w core 4 w6 W5 -, - -- w -2W2 1l Core 3 Bell A.M.A. Transformer Realization of Net of FigeS(A) (E) Fig. 8

57. form. The 0,1 convention used is 1 - > high voltage, 0 < -> low voltage. A relay realization is given in Fig. 8(D). The 0,1 convention used is l1 - + voltage, 0 ~ ~ 0 voltage. Here the circuit may be simplified by replacing all coils controlled by Wj by a single coil controlled by Wj and a set of makecontacts. The element input count for the crystal realization is the number of crystals required; for the relay realization, the number of contacts. The parallel load of input wire Wj is the number of crystals operated in parallel by Wj. In the simplified relay circuit, it is the number of contacts operated by the coil controlled by Wj. The serial loading coefficient is ideal as it is in the case of the exponential switch. In the relay circuit we have shown each contactor connected to a source of positive voltage. This was done in view of the convention that i represented positive voltage and 0 represented ground potential. A pulse output may be achieved by connecting the wires labeled + to a pulse source.

58. This requires a multiple 0,1 convention. Fig. 8(E) is a realization of the encoding switch in terms of the Bell A.M.A. transformers. 3.3. Arbitrary Transliterative Functions. Any transliterative function can be realized according to Technique 3 of Vol. I by first decoding and then encoding. In the section on decoding circuits, only complete decoding circuits were considered. However, any arbitrary decoding function can be realized in physical equipment by a complete decoding circuit with the unnecessary parts deleted. For our purposes then, the circuits described in Subsections 3.1 and 3.2 or the simplification of these circuits may be taken as components from which to construct circuits for any given transliterative function. On the other hand, it is sometimes possible to construct a single circuit which will realize the given function "directly" and which is, in a sense, simpler than the circuit constructed by first decoding and then encoding. Very little theory has

59. been developed to cover this direct procedure. In this subsection we will consider two examples of circuits constructed by the decoding-encoding technique and a single example of a circuit realizing a transliterative function directly. In all cases the 0,1 convention will be 1 + voltage, 0 - O0 voltage. In the case of decoding nets, we were not primarily concerned with the actual correspondences produced by a switch.* Now, however, it will be necessary to consider these correspondences in detail because (1) two circuits are to be connected, the second of which, the encoding circuit, requires specification of the function it realizes, and (2) more generally, it will be desirable to eliminate equipment required only for correspondences with which we are not concerned. At the beginning of Section 3 a method was given for determining the state of every wire of the net. This can be directly translated into a description of the states of the corresponding wires of the circuit * That is, with precisely which output wire is activated for a given input state, so long as the required complete function is produced.-Ed.

60. by means of the 0,1 convention. This information may also be determined from the circuit by assigning states to the inputs and using electrical properties of the circuit element to determine the states of the other wires. This data yields the necessary correspondences. Let the outputs of a decoding switch be labeled W. and assign to each input character d that J Wj which is in the 1 state when d is represented on the inputs. Similarly, let the inputs of al encoding switch be labeled Wi and assign to each Wi that output character which appears in the output when Wi is in the 1 state. For example, consider the stepping switch 1S and the stepping switch encoding circuit described in Subsection 2.3 and diagramed in Figs. 3 and 4, respectively. The MS correspondence is given in Table VI below, the encoding correspondence in Table VIi. These tables together with the given transliterative function determine at once the way that

61. the wires of the two switches must be connected to yield the complete circuit. Table VI Table VII ll 112113114 121122123 WIs Wts W1 W2W3W 1 1 W 1 1 1 W 1 1 1~ l i I ~'11 1 ~ t I12 I I I J1 V I I W1 i1 I 1 1 WI I.1...... I I w w r-vI JI.... l.... J I~ v!H w 1LL 1 W I HnX 111 the 1 and clmhW W 1 transiterative 1 W10 Wi0 1 1 __ W11 Wi1 1 11 For example, let the transliterative function be given by joining Tables VI awnd VII and eliminating the W and W columns. This transliterative function can be realized by taking the two circuits of Figs. 3 and 4 and connecting Wj to Wj. The resulting circuit will realize the given transliterative function. In operation (though the control

62. circuits are not shown) the WA stepping switch will step until it reaches the position determined by the states of the input wires and then the encoding switch will step until it reaches the corresponding position. This circuit may, of course, be simplified and its operation materially speeded up by (1) using a single stepping switch with N+ M arcs (N being the number of input sets and M the number of outputs), and (2) with the contacts so connected that each row of contacts (one from each arc and touched simultaneously by the wiper) can be divided into two parts, one corresponding to an input character and the other to its image under the given transliterative function. This is illustrated in Fig. 9 for this example. As a second example of the decoding-encoding technique, we construct a circuit realizing the transliterative function in Table VIII. Table VIII 000 0011 0101 1000 0001 0100 0110 y 1001 0010 1 01010 > 1010 0011 - 0110 1000 -- 1011 0100. —- 0111 1001 1100

63. Output Decoding-Encoding by means of a Stepping Switch Fig. 9 Fig. 9

64. The relay tree of Fig. 10(A) is a realization of a 4-input-pair tree together with polarizer. The binary number labeling its output wires designates the input character for which that output is in the 1 state. Clearly not all the outputs are required and the heavy dotted lines indicate the portions of the circuit which may be eliminated. Further simplification may well be possible. The encoding switch required is described in Table IX where the Wi are the inputs and where the character corresponding to Wi is the one appearing on the outputs when Wi is in the 1 state. Table IX W1-.... 0011 W6 - 1000 W2:> 0100 W7 > 1001 W3 -*> 0101 W -- 1010 W4 > 0110 W9 1011 W > 0111 O10 W 1100 Fig. 10(B) is a crystal rectifier circuit realizing the required encoding function. The circuit for this given transliterative function is completed by connecting the Wi and Wi. The

OT':TJ ae a;', X:'e"e'lF (:) (') TZ;ldt~TT 47 T d'd dd -~~~~ f MI~~~~~~~~~~~~~~ Li TM 0000' TM TOOO0 Z&Tiooo _TO M I_ IbI 00TT TT! 9&TOTT 9-~ _____ LtI OTTT T' I01 ~, ~F7,:"'" TO'OT v'L_~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'1, I O T J T I~ ~ ~ ~ ~ ________________ I OTTTT'Ti..............L~~'~

66. logical net for this transliterative function is given in Fig. 11. As a final example of circuits realizing transliterative functions, consider the relay circuit of Fig. 12. It realizes the same transliterative function (Table IX) as the circuit of Fig. 10. It does so directly, however, i.e., without first decoding and then encoding. Such direct transliterations usually take advantage of the incompleteness of the decoding and the special characteristics of the function to be realized (i.e., the specific nature of the correspondence it defines). Fig. 13 is the logical net describing the circuit of Fig. 12 (r stands for the reading input). The circuit may be checked by assigning Ots and l's to the inputs and calculating the output states to see whether it actually realizes the given function. If variables Pi are assigned to the inputs in an appropriate fashion* well-formed formulas may be associated with every wire of the net describing If u and v are two input wires whose states are assigned independently, then the associated variables may be denoted Pi and pj when i # j. If, on the other hand, u and v are considered a polar pair and Pi is assigned to one of them, then ~pi must be assigned to the other.

11 ~ ~z.M IIIA TqeIl Jo uo!%otrnM az.FsaeF!stni e% ao$ %o0 MaN tI!F3o 5 'M.,,.r ~ Jm II fXIIIL~~~~~~~~~~~~~~ L1- — I<L-C1__!-, — a E 41 1 1 it~~~~i ore~M I STY I ~ mI 9-,, *L9 I~~~~~~,, i_ _,, k~' ~9

68. i~IR Jb + 3R1 T-' -2RI 4. ~ 4R3 _ -R3..3R4 b4 n OR ZC 3R 2R R Direct Relay Realization of the Transliterative Function of Table VIII Fig. 12

69. r b1 _'p2 ( p3vp4)v' P2Pl p3 P3 b2 =" ~P2' (P3vP4)v ~P4'~4P3'P 2 P4 P P2 /P3i b3 - (4P4.'P3)vP 4'P 3 P3 b4g P4 Logical Net for the Circuit of Fig. 12 Fig. 13

70. that wire's behavior in terms of logical functions and the input variables. The logical formulas associated with the bi in Fig. 13 are the wellformed formulas describing the behavior of the outputs. It is interesting to compare the two nets (Figs. 11 and 13) in terms of the various indices. Let S1 denote the decoding-encoding net and S2 the direct net. A comparison in terms of the element count and the element input count is given in the following table. Element Count Element Switch Element Count by Types Inut Count S1 28 N4K20D4 Q 2 2 S* 19 K2 D 37 The theory of Vols. I and 111 is concerned largely with nets for complete decoding, and these are constructed primarily of conjunwctions. Because of this, an element count would be of some significance. *These counts can be reduced by better handling of the r-input. In fact, one might question the necessity for including any read-circuits in this comparison.-Ed.

71* In nets composed of different types of logical elements, as are S1 and S2 a breakdown by types is more helpful and this is indicated in the third column of the preceding table. The letters with superscripts denote the type of logical element (iN stands for negation, K for conjunction, and D for disjunction), and the superscript indicates the number of inputs. The subscript indicates the number of that type of element appearing in the net. This yields the expression in the third column which is, in a sense, analogous to chemical formulas. The element input count is given in the first column. It too would be more significant if broken down in an analogous way. For example, in S1 the element input count for the disjunction is that of the encoding switch and is equal to the number of crystal rectifiers. However, in S2 the element input count for the disjunction lacks significance because it is possible to realize them in this case by merely joining wires. This illustrates one significant way of

72. breaking the net up into parts; in the case of S1, the decomposition into element types corresponds to the decomposition of the net into polarizer, decoding net, and encoding net. Many other significant ways of breaking up the net undoubtzdly exist, Iand, for each, values of the different indices may be determined.

73. 4A Code Converters Requiring Memory0 In this concluding section three examples of code conversion requiring memory are described. They illustrate several ways in which circuits for transliterative functions may be combined with other circuits (e.g., memory, sensing, and control circuits) to realize more complicated conversions. As presented, they embody an element of format conversion for the input is in parallel order and the output in serial order. The discussion for each example includes a table defining the function to be realized, a schematic diagram of an appropriate code converter, and a behavior table succinctly describing its behavior. Little detail is included for here we are interested not so much in the circuits as in the broad organization of the components. Nevertheless, a schematic circuit diagram corresponding to a part of the block diagram for Example I is included as an illustration0 It should be mentioned that the only portions of the control which are considered here are those

74. needed for the conversion of one character of the input code into the corresponding character of the output code. The code conversion to be considered first is that of a teletype code into a 4-8 code. This is not a transliterative function for two reasons: (1) the mapping is not single valued, and (2) the image sequences are not all of equal length. This conversion is fully defined in the following function table. Table X Teletype 4 - 8 Teletype 4 - 8 Teletype 4 - 8 A 11000 0000 0000 S 01010 1101 0000 / 11001 1110 lill 1 B 10101 0000 0001 T 00001 1101 0001 11000!1110 0010 C 10110 0000 0010 U 11010 1101 0010 @ 11001 1110 1110 D 01100 0000 1101 V 01111 1101 1101 % 10010 1111 1110 E 01000 0o000 1110 W 10011 1101 1110 01111 1111 1101 F 01110 0000 1111 ll 11101 1101 111 01011 1111 1ll1 G 00111 0001 0000 Y 11001 1110 000 0 01010 1110 1101 H 01001 0001 0001 Z 10001 1110 0001 4 01100 1111 0000 I 10010 0001 0010 0 10110 0011Z 00110 1111 0001 J 11100 0001 1101 1 10111 0100 00101 1111 0010 K 11110 0001 1110 2 10011 0101 - 11111 L 00011 0001 1111 3 00100 0110 S.fis 11011 M 01101 0010 0000 4 01001 0111 N 00110 0010 0001 5 10000 1000 0 00101 0010 0010 6 10101 1001 P 01011 0010 1101 7 00111 1010 Q 10111 0010 1110 8 00011 1011 R 10100 0010 11111 9 11000 1100 *The code referred to here as a'teletype code' is a five channel shift code with the structure of a teletype code but differing to some extent in the specific assignment of characters. -Ed.

75. Fig. 14 contains the block diagram of a code converter realizing this f'unlction. The character to be converted; Qce is read onto the inputs of a decoder; then a conversion signal is applied to the control which puts a signal on one of the pair of wires to the decoder. The wire chosen depends upon the last shift character X read in. Clearly memory is required at this point. 0( is decoded and the output D(X,O() goes to the senser and encoder. It is immediately encoded and transmitted to the register. The senser senses not 0X alone but (X,C() for OZ alone is ambiguous. The "no character" output of the senser has a signal if and only if QC( is a shift character and the "one charactert output has a signal if and only if (X, 0() defines a a number. If the "no character" output carries a signal, then the register is cleared without an output occurring on the register output. If the "one character" output carries a signal, then one character is read out of the register. Finally, if neither carries a signal, two characters are read out of the register in serial order.

76. One Character (Si) No Character (S0) Decoder D( D( Numbers and Punctuation E Cle r II" xCharacter K Character a ~ Read out one word R Rst) ou Converwowor Regiser E Example I Schematic Diagram Fig. 14 Fig. 14

77. The "behavior" of the diagram may be described by menans of C table where the rows correspond to inputs and outputs uld the columns roughly represeilt sucessive points oi' time. The enltries in1 a column may be considered as occurring at approximately the same time, those to the right later, and those the left earlier. 0 and 1 are used to represent the two possible states of the wires but no physical interpretationl is given. The table for Example I is given on the following page. Fig. 15 shows a schematic circuit which includes the decoder, encoder, senser, and a part of the control circuit. The second example of code conversion is from 6 pulse to teletype. Here memory is required for tihe proper insertion of the shift chiaracters. The following incomplete table defines (ini part) the code conversionl functions to be considered (p. 80).

78. Behavior Table - Example I 0 1 2 3 Character Input of Decoder OC Conversion Signal Input Control Output to Decoder (X) (X is first shift character d preceding c ) Decoder to Senser aind Eiicoder D(X,O ) Encoder to negister E(X, ) Case 1: (X,) — a letter i-o Character Wire froim1 Senser 0 One Character Wire from Senser t 0 Control to Register - Read R2 1 out two characters Other Control Outputs C, R1=0 Register Output Es (X, O() Case II: (X, 0) — a figure No Character Wire from Senlser SO O One Charccter Wire from Senser S 1 Control to Register - Read R1 -0 out one character Other Control Outputs C,R2= 0 Register Output ES(X, O) Case II': (X,O() —> Shift character io Ch-aracter Wire froma e-nse r SO = 1 One Character Wire from Senser S1 0- Control to Riegister - clear c - 1 Other Control Outputs R1,R2-O Register Output

Bruned Figure Page See ERI Yile Copy

80so. 6 Pulse Teletype 6 Pulse Teletype A 010000 00011 Z 101010 10001 B 010010 11001 0 000011 10110 C 010011 01110 D 010100 01001 9 001100 11000 E 010101 00001: 110100 01110 F 010110 01101 G 010111 11010 $ 101111 01001 i. / 101110 11101..* @ 101101 11001 *.l, ) o101100 01100 X 101000 11101. 101011 11100 Y 101001 1011uOi Fig. 16 is the schematic diagram of a code coliverter realizing this function. The character to be converted o is read onto the inputs I of the decoder. A conversion signal then decodes 0(, putting DS(OR) on the inputs of the senser and D(04) on those of the encoder. D(Q() is then encoded and transmitted to the regi ster. The letter output of the senser carries a signal if and only if 0( is a letter, and the figure output carries a signal if and only if OC is a figure. The control must remember on which input the preceding signal occurred. If there is a change,

81. D( ) Conversion Signal ( Decoder Encoder DS( ) Senser (Letter) (Figure) (SL)" (SF) Register ES( e out (> Control ~Lea~~tF,, Sh _ (CL Shift Character Figure Source Example I1 Schematic Diagram Fig. 16

82. the appropriate shift character must be inserted. This is done by first putting a shift character in the output and then reading out the register. If there is no change, then the control causes the character to be read out of the register (in serial order) as indicated by thi-e subscript in Es(O(). The behavior table for Example II is given on the following page. Thie final example is a conversion from a 4-8 bit code to a 6 bit code. The fuiction which is to be realized is given in the following table. 4 - 8 6 Pulse 4 - 8 6 Pulse 4 - 8 6 Pulse A 0111 1111 010001 S 1010 1111 100011 1001 1101 101011 B 0111 1110 010010 T 1010 1110 100100 1001 0010 101100 C 0111 1101 010011 U 1010 1101 100i01 0 1001 0001 101101 D 0111 0010 010100 V 1010 0010 100110 1001 0000 101110 E 0111 0001 010101 W 1010 0001 100111 $ 1000 1111 101111 F 0111 0000 010110 X 1010 0000 101000 ace 1000 1110 110000 G 0110 1111 010111 Y 1001 1111 101001 - 1000 1101 110001 H 0110 1110 011000 Z 1001 1110 101010 * 1000 0010 110010 I 0110 1101 011001 0 0100 000011 % 1000 0001 110011 J 0110 0010 011010 1 0011 000100: 000 0000 110100 K 0110 0001 011011 2 0010 000101 L 0110 0000 011100 3 0001 000110 M 0101 1111 011101 4 0000 000111 N 0101 1110 011110 5 1111 001000 0 0101 1101 011111 6 1110 001001 P 0101 0010 100000 7 1101 001010 Q 0101 0001 100001 8 1100 001011 R 0101 0000 100010 9 1011 001100 The schematic diagram for a converter for realizing this function is given in Fig. 17.

83. Behavior Table - Example II O0 1 2 3 4 Character Input of Decoder (I) < Conversion Signal Input Decoder to Encoder D(QC) Decoder to Senser DS(M) Encoder to Register E(0) Case I: If O(= letter and X* = letter Senser Output - letter SL-1 Senser Output - figure SF-O Control to Register - read out R - 1 Other Control Outputs CF,CL-O Register Output ES(o) Case II: If OX figure and X = figure An-llogou to Cas I Case III: If c- letter and X = figure Senser Output - letter SL-1 Senser Output - figure SF=O Control to Shift Source - letter CL —1 Other Control Outputs R,CF=O Shift Source Output, Sh(L) Control to Register - read out R=l Other Control Outputs CFPL= Register Output ES( Case IV: If O- figure and X -- letter An logou$ to Case III X is the preceding character.

84. Conversion D( ) Signal; Decoder Encoder Cx1 DS( ) ).... ~~~~~~( ) Senser s()........ Read out (R) Read in Es Control Clear (C) Register Character II (RI) Example III Schematic Diagram Fig. 17

85. The input character OCl is read onto the I1 input set of the decoder. A conversion pulse then "decodes" O(1 and puts D(0C1) on the inputs of the encoder and DS( O1) on the input of the senser. D(0(1) is encoded and transmitted to the register. In Case I, if Cl1 is a figure, the senser output is unaffected and the control causes the register to read out. In Case II, if K(1 is not a figure, there is an output from the senser which causes the control to clear the register and have ( 2 read onto the 12 input set of the decoder. The next conversion pulse decodes (0(1 UoC2) which is then encoded and transmitted to the register. The control causes the character in the register to be read out and the conversion is complete. Clearly memory is required in this code conversion, (1) for retaining ~<1l while it is being sensed and then for combination with CK 2 if required, and (2) in the control to interpret the signal from the senser, i.e., the second signal from the senser causes the control to make the register read out whereas the first one caused the register to be cleared.

86. Behavior Table - Example III O0 1 2 3 4 5 6 Decoder Input 1 1li I Conversion Signal Input l Decoder to Encoder jD(~l) Decoder to Senser S Encoder to Register E(0( Case I: If tl - fig. Senser to Control ()Control to Register I -read out R=i Other Control Outputs I C=O Register Output ES () Case II: If 0(l $ fig. Senser to Control |(Xl)=l Control to Register - clear C=l Control to Register - read out | R=O Control Output - Character II in R I =l Decoder Input 12 I2 Conversion Signal Input Decoder to Encoder D((lf 0(2) Decoder to Senser DS(oltZ2) Encoder to Register E (l+~C2) Senser to Control S ( 1 I Sl2)-1 Control to Register - read out R=l Control to Register C=O - clear Control Output - Character II in RII=O Register Output I. 1 _ I _ _s (IEtlk2)

87. Bibliography 1. Brown, D.R., and N. Rochester, "Rectifier Networks for Multiposition Switching," Proceedings, 1.R.E., Vol. 37, 1949. 2. Staff of the Computation Laboratory, "Synthesis of Electronic Computing and Control Circuits," Annals, Computation Laboratory of Harvard University, Vol. 27, Cambridge, 1951. 3. Specification for Pulse-Control Equipment, April, 1951, Burroughs Corporation Research Center, Paoli, Pennsylvania. 4. Keister, W., A. E. Ritchie, and S. H. Washburn, The Design of Switching Circuits, New York, 1951.

88. Corrigenda for Volumes I and III, LANGUAGE CONVERSION FOR DIGITAL COMPUTERS Volume I: p. 10, last line of Def.l., should read "see Figure 3a or 5bt" p. 10, the following to be added as a footnote to the Corollary to Def. 1. "The associative property of Cartesian Conunction wcs established somewhat inaccurately, as was pointed out by L. C. Robbins, Jr., Burroughs Corporation Research Center. However, both with regard to Cartesian Product and Cartesian Conjunction, a "tquasi-associativity"t actually obtains, in the sense that an element, (xl,x2), X3, of the Cartesian Product (SlxS2)xS3 can be identified with the element (xl,x2,x3) of (SlxS2xS3) or xl,(x2,x3) of Slx(S2xS3). It is recognized that there are other respects in which this discussion is not fully rigorous, but it is felt that such a presentation is adequate for present purposes." p. 19, the second line of 2)a), following "of an MS" should read "not belonging to the partially completed net and with input" p. 21, line 8, following "into two such which differ" should read l"as to the number of P's by at most one. The" p. 21, second paragraph, line 2 should read "to build it. An..t p. 21, fifth paragraph, third line, following "the Element Input Count is" should read k-l (i+2k-i) "IC - 2.' 2. i —0

89. p. 22, last line of second paragraph, following "upon which" should read "none of the subsequent theory will depend." p. 24, line 2 of second paragraph, following "Figure 7e shows", should read "a Stroke Tree of 2 Bays (3 in-" p. 25, line 6 of footnote, following "for reasons which," should read "it is felt,..." p. 39,.line 2 of sixth paragraph should begin 112,k-2(i4 2k-i) where the number..." i-O p. 47, line 2 of fifth paragraph, following "for n - 6," should read "for d+ F - (64-2)/(6-1) - 121 —2/5;" p. 49, line 1 of Step Three (A), following "If a1 2" should read "then bi =.... and ci = [. 1-i 2 2 Volune III: p. 37, line 6 up from bottom, should begin with the expression k k "(k - 3)al14 ai; (k - 3)a2 4- 4ai;... p. 39, line 6 of Proof of Lemma 1, should read "tion when b - bi or b3;..."

UNIVERSITY OF MICHIGAN 3 9015 02653 5172