LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 5io.e>4 co|p.2 Digitized by the Internet Archive in 2013 http://archive.org/details/designofdigitalc287fink /JO j&$ort No. 287 V ) DESIGN OF DIGITAL COMPUTER CIRCUITS USING A BASIC LOGIC CELL May 2k, 1968 by Harvey Allen Finkelstein LIBRARY OEIHB 9 1972 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN; DEPARTMENT OF COMPUTER flHMH* UNIVERSITY OF ILLINOIS • URBANA, ILLINOIS Report No. 287 DESIGN OF DIGITAL COMPUTER CIRCUITS USING A BASIC LOGIC CELL* by Harvey Allen Finkelstein May 2k, 1968 Department of Computer Science University of Illinois Urbana, Illinois 6l801 ^Submitted in partial fulfillment of the requirements for the Degree of Master of Science in Electrical Engineering. ■ ACKNOWLEDGEMENT The author wishes to express his gratitude and to thank his advisor Professor Sylvian R. Ray, Myrna Selivonchick for typing the manuscript, John Otten for preparing the diagrams, and the Digital Computer Laboratory for the reproduction of this thesis, all of whose assistance in the preparation of this paper has been greatly appreciated. 111 IV TABLE OF CONTENTS Page ACKNOWLEDGEMENT iii LI ST OF TABLES v LI ST OF FIGURES vi 1. INTRODUCTION 1 2 . CUTPOINT CELL 3 2.1 Cell Design 3 2.2 Coding 3 2 . 3 Logi c Implementation 3 2 .h Advantages and Disadvantages 3 3- SQUARE CELL 6 3-1 Cell Design 6 3.2 Coding 6 3 « 3 Logic Implementation 10 3 . h Advantages and Di sadvantages 20 k. HEXAGONAL CELL 22 k.l Cell Design 22 k,2 Coding 22 U.3 Logic Implementation 25 k.h Advantages and Disadvantages 25 5 • EXAMPLES OF THE USE OF CELLULAR LOGI C 30 6 . SUMMARY AND CONCLUSIONS 52 REFERENCES 55 APPENDI X A 56 APPENDIX B 57 LIST OF TABLES Page 1. Outpoint Cell Coding k 2. Square Cell Controls 8 3- Hexagonal Cell Controls 2k LIST OF FIGURES VI Figure 1. Square Cell Block Diagram 2. Square Cell Input-Output Decision Logic 3. Square Cell Function or Complement Decision Logic k. Square Cell Basic Functions Generation 5. Square Cell Right Output Function Selection 6. Square Cell Left Output Function Selection 7 • Square Cell Bottom Output Special Functions Generation and Selection 8. Square Cell Bottom Output Basic Functions Selection 9. Square Cell Flip-Flop Logic 10. Address Logic 11. Address Logic Flip-Flop 12. Hexagonal Cell Block Diagram 13* Hexagonal Cell Function or Complement Decision Logic 1^. Hexagonal Cell Function Generation and Selection Part a 15* Hexagonal Cell Function Generation and Selection Part b 16. Hexagonal Cell Flip-Flop Logic 17* Square Cell Register and Counter Page 7 11 12 13 Ik 15 16 17 18 19 21 23 26 27 28 29 31 VI 1 Figure Page 18. Hexagonal Cell Register and Counter 32 19. Cutpoint Cell Four Stage Shift Register 33 20. Square Cell Three Variable Decoder 3^ 21. Hexagonal Cell Three Variable Decoder 35 22. Cutpoint Cell Three Variable Decoder 36 23. Square Cell Nines Complement Circuit 37 2k. Hexagonal Cell Nines Complement Circuit 38 25. Cutpoint Cell Nines Complement Circuit 39 26. Square Cell Translator From Binary-Coded Decimal to Two-Out-of-Five kO 27 . Hexagonal Cell Translator From Binary-Coded Decimal to Two-Out-of-Five kl 28. Cutpoint Cell Translator From Binary-Coded Decimal to Two-Out-of-Five k2 29. Square Cell Example A ^3 30. Hexagonal Cell Example A kk 31. Cutpoint Cell Example A ^5 32. Square Cell Example B k6 33. Hexagonal Cell Example B kj 3b. Cutpoint Cell Example B k8 35- Square Cell Example C k9 36. Hexagonal Cell Example C 50 37- Cutpoint Cell Example C 51 1. INTRODUCTION At present, many digital circuits are built using modules containing two or three NAND gates, NOR gates, or a single flip-flop. The result is that a great many of these modules are usually required to obtain a desired logical function. If these various gates could be combined into a single module or cell capable of performing a large number of operations, dimensional requirements of circuits in- corporating these cells would be reduced. Size limitation is extreme- ly important, for example, in digital circuits required in rockets, missiles, and satellites. Therefore, if this multipurpose cell could be designed and constructed at a reasonable cost, a new method of log- ic design could result. To achieve the objective of a universal logic cell, a meth- od termed cutpoint logic had been devised. A cutpoint cellular array is a two-dimensional rectangular arrangement of square cells, each of which has binary inputs on the top and left edges and outputs on the bottom and right edges. Each cell is interconnected with neighboring cells, and it is specialized by a set of binary constants that are termed cutpoints.* Although this cellular arrangement represents a step forward in obtaining a reduction in the size of digital circuits, it will be shown in this paper to have several disadvantages. There- fore, two new types of universal cells, the square cell and the hexag- onal cell, have been designed to eliminate the failings of the cut- point cell. *Minnick, R.C., "Cutpoint Cellular Logic", IEEE Transactions on Elec- tronic Computers, December I96U. The square cell has one fixed input, one fixed output, and two lines that could be programmed either way. The hexagonal cell has three fixed inputs and three fixed outputs. While the cut- point cell can output only functions of two variables, the other two cells yield many of the functions of three variables. In this thesis, it is suggested that the various cells be programmed by placing an address register in each cell. Microwelding or separate lines could be employed but it will take more extensive examples to justify their use. The addressing will be most efficient if done by a computer. At this time, however, an algorithm to pro- gram the hexagonal or square cell has not been found and program- ming must be done by hand. The individual cells consist of integrated chips containing NAND and NOR gates and inverters. The number of gates placed on a chip has been limited to 200 which is about the range of our present technology. Finally, the proposed saving in space and cost requirements are illustrated by various examples of cellular networks. A summa- tion of the number of cells used in applying each of the three meth- ods to specific examples shows that 50$, more cells are needed in the cutpoint cases. Thus, this thesis will attempt to open up a new area in the design of digital computer circuits. By expanding on these methods, cells of different shapes or designs using layers of cells could prove to be even more practical. The final result of the work in this area should be most interesting. 2. CUTPOINT CELL 2.1 Cell Design The cutpoint cell is a square shaped cell employing two in- puts and two outputs. The right output line is tied directly to the left input line. The bottom output yields one of eight functions of two variables or a flip-flop output function. 2.2 Coding The cell coding and functions performed, determined by a four bit code, are shown in Table 1. No method of addressing each cell other than with k switches is given in Mr. Minnick's article. A scheme, however, consisting of a h bit register plus the appropriate addressing logic could be used. This is the same method suggested for the hexagonal and square cells and can be found by referring to Sections 3*1 and 3«3« 2.3 Logic Implementation Two different designs for a cutpoint cell, a resistor-tran- sistor realization and a diode-transistor realization, are given in Mr. Minnick's paper. Hardware design for the cutpoint cell will not be discussed since the cutpoint cell will be shown to be inferior, in a sense to be discussed in the following pages, to the other cells. 2.1+ Advantages and Disadvantages The obvious advantage of designs utilizing cutpoint cells, as well as the hexagonal and square cells to be discussed in the re- maining sections, is that many functions are formed in one module. In the cutpoint cell, 8 functions of two variables and a flip-flop function can be performed without using a large number of individual TABLE 1: CUTPOINT CELL CODING* 1 i y 2 x + y 3 "xy h x + y 5 xy 6 x © y 7 13 »=S, y=R *Minnick, R.C., loc. cit., p. 688. NAND and NOR gates and inverters. The advantage the cutpoint cell has over the square and hexagon is that an algorithm exists to pro- gram the required function. This is done by forming each component of the function in an individual column and then gathering up the parts in the last row. The main disadvantage of the cutpoint cell stems from the large number of cells needed in the programming scheme. Most arrays designed to yield a specific function have as many columns as terms in the function and have one more row than the number of input vari- ables used. Thus, a function f = *1 x 3 x h + *1 *2 x 5 + x l x 5 + *2 X 6 < " 2 ' 1 ^ would be made up in a Ux7 array. Mr. Minnick states that "the synthe- sis of an arbitrary n~variable combinational switching function is shown to require a cutpoint array n+1 cells high and no more than cells wide."* Simplifying the function usually does not work in the cutpoint case since input variables are usually restricted to a single individual row and cannot be added in a subsequent row. An- other shortcoming of this cellular method is that it needs two cells just to form all of the functions of two variables whereas all of the functions of three variables are performed by two hexagonal or square cells. *Minnick, R.C., loc. cit. 3. SQUARE CELL 3.1 Cell Design A block diagram of a square cell is illustrated in Figure 1. The upper righthand corner shows the address elements, a register con- trol and a 16 bit shift register that sets the cell to the function desired. The number next to the individual blocks indicate which bits control that block and the path that the inputs fo]_Low through the cell are shown by the directed lines. Further explanation of this block diagram follows in the next section on coding. 3.2 Coding The coding of the square cell is shown in Table 2. The first decision is whether the input T. is complemented or not and setting q accordingly. Control bits q~ and q^ determine whether the sides are inputs and/or outputs and if the sides are not both outputs, the input ( s) is either complemented or left alone. Once these preliminaries are completed, the desired output functions are formed. If L is an output, the desired result is obtained by set- ting q^, q ft and ^ to the proper values. There are 7 possible output functions on this line of which one combination q^: 1, q^i 1, and q c ^: is set aside to provide more combinations of three inputs on output line B . There are two sets of output functions available on the B o o line. The B functions are similiar to the functions provided on the R and L lines while the A functions are different functions of three o o variables. The functions (L+L~) (T+T) (R+R) + (L+L) (f+T) (R+R) (3.1) L(T©R) + L(T+T) (R+R) (3.2) and L(T@R) +L(T+T) (R+R) (3-3) < cc o < Q O o CO CO o UJ cc < o UJ or z> o 8 TABLE 2: SQUARE CELL CONTROLS V 1 Ti Ti V i Ri Ro %'' 1 Li Lo %'' 1 ¥ 1 Li Li V 1 ¥ 1 Ri Ri FUNCTIONS GENERATE % : ¥ V Y ° 1 Lo: 1 (T+f)©(R+R) 1 (T+T)+(R+R) 1 1 (T+t)(R+R") 1 1 1 R+R 1 1 USE q±k q 15 q^ 1 1 1 T+T \k' 1 V 1 q l6 : 1 FUNCTIONS GENERATED B q n : q !2 : 1 q io : Bo: 1 (T+T)«(L+L)©(R+R) 1 (t+t)+(l+l)+(r+r) 1 1 (t+t)(l+l)(r+r) 1 1 1 R+R 1 1 Li+Li 1 1 1 T+T TABLE 2: cont'd FUNCTIONS GENERATED B V q 3 : 1 1 1 1 V 1 1 ' 1 1 q-. Ro: 1 1 (T+f)»(L+L) (t+t)+(l+l) 1 (T+T) (L+L) 1 (T+f)©(L+L) L+L 1 T+T q 13 : 1 L+L: 1 1 T+T: 1 1 Bo: Ro: 1 1 OUTPUT IS THE SAME AS PREVIOUS OUTPUT V 1 q 8 : 1 V q io : q n : q 12 : FUNCTIONS GENERATED A q lV V q l6 : _ (L+L)(T+f)(R+R) BO ' +(L+L)(T+T)(R+R) 1 (R+R)(T+T)+(L+L) 1 [(L+L)+(T+f)] (R+R) 1 1 [(R+R)+(T+T)] (L+L) 1 L(T9R)+L(T+T)(R+R) 1 1 l(tW)+l(t+t)(r+r) 1 1 [(R+R)©(T+T)] (L+L) 1 1 1 1 10 are included since three cells would otherwise be needed to form these functions. Each of the 256 functions of three variables can be placed in one of 22 different categories of similar functions as listed in Appendix B. Therefore, the remaining function was chosen from the classes of functions of three variables with the most mem- bers. If R is an output, the R functions are formed using control bits q , q, and q . Finally, if the cell is to be used as a flip- flop, q is set as a "1", and the left input is the flip-flop set, the top input is the trigger and B and R are the outputs. 3.3 Logic Implementation Square cells are designed with the NAND and NOR gates and inverters of Appendix A built onto a single chip or cell. Figure 2 illustrates the decision logic used to set inputs and outputs while Figure 3 shows the logic used to complement the input variables. The three basic functions, the "AND", the "OR", and the "EXCIUSLVE-OR", are formed in Figure k. Figure 5 contains the right output function selection logic while Figure 6 is for the left output. The special functions are shown in Figure 7 and. their selection logic is pictured in Figure 8. Since there is also a flip-flop in each cell, Figure 9 was included. Finally, there is a need to program the individual cell. Since these cells must be identical, this addressing is accomplished by means of a 16 bit shift register shown in Figure 10. Three of the h lines attached to each cell are common to every other cell. The fourth, Inhibit, is used to differentiate between cells. A computer is assumed as the source of the 16 bit groups that control each cell's specific function. As each cell's turn to be programmed occurs, the computer would lift the level on the Inhibit line from Ov. to +kv. // o o o o CO o UJ I- z> Q. h- z> o I H Z> Q. UJ u UJ or < Z> O cvi UJ q: z> o IZ N — ro CO" O" Ch ±L> _> 4 la: O o * o K _i z o e> J3 /4 ro «■ cr cr «4> •4 + ■4>i ro c\J I-J •-c > & ro o IE O r- O y CO Z o r- o z 3 3 Q. r- O CD uj o cr < O CO IT) LU tr. 3 CD Icr /s lor + •— C — c ICE + o UJ _l UJ CO O I- a. h- z> o LxJ UJ o UJ a: < Z> O CO to Ld q: => U. 16 yi>** z o o UJ CO O z < O to z o I- o z ID U- < o UJ a to 3 a D o o < O CO 17 o _J UJ co CO z o H O z U. o CO < GO 3 0. I- 3 O o go UJ or < 3 O CO 00 UJ or 3 /s q 7 Li+Li t B, ▼ R„ ▼ q 13 FIGURE 9. SQUARE CELL FLIP-FLOP LOGIC 19 o o CO CO LU or Q Q < Ld a: CD 20 and the 16 bits would be shifted in by the continuously running trig- ger. The Clear line sets the shift register of Figure 11 back to all zeros. Of course, it is not essential that the square cell, as well as the hexagonal cell to be discussed in the next section, have the internal programming depicted in the above paragraph. This was only one of several possible methods. Another is that a register be employed outside the cells in a separate unit. In fact, individual lines to each cell could even replace the registers. Actually, the number of cells used in the computer elements would probably dictate the choice of the type of cell programming. 2>»k Advantages and Disadvantages The advantage of the square cell over the cutpoint cell is that many more functions can be formed in one cell. Only 8 of the l6 functions of two variables can be performed using a cutpoint cell while with one square cell, 152 of the 256 functions of three vari- ables can be constructed. Appendix B gives a listing of the func- tions that can be made with one cell and those that take two cells. Included in those that need only one cell are, of course, all of the functions of two variables. Thus, the many more functions that this cell provides results in fewer cells used in digital circuits. The saving in the number of cells used is obtained by sim- plifying the function involved. This, however, yields no simple scheme to program the cells. For a programmer, though, the job of setting up the cell pattern and programming them does not appear to be too difficult. Also, further investigation could probably yield a method in which a computer would be utilized to determine the individ- ual cell settings. 21 FLIP-FLOP CLEAR DATA g ▼ OUT TRIGGER ^ g FIGURE II. ADDRESS LOGIC FLIP-FLOP- 22 k. HEXAGONAL CELL k.l Cell Design The hexagonal cell's block diagram is shown in Figure 12. The address elements are the same as for the square cell and can be found by referring back to Figures 1, 10 and 11. There are three fixed inputs and three fixed outputs associated with this type of cell. One of the outputs is the same or the complement of one of the inputs while both the D and E output circuits are identical. k.2 Coding The coding for the hexagonal cell is listed in Table 3» The first decision is whether or not to complement the in- puts and then setting bits q , q_ and q„ accordingly. In forming the functions involved, anywhere from none to all of the inputs may be needed, q. , q and q^ are used to inhibit the inputs used for the D output while q ~, q.^ and q ip are used for the E output. Cell func- tions are selected using bits 7 to 9 for the D output and 13 to 15 for the E output. The functions (A+A) (B+B) (C+C) + (A+A) (B+B) (C+C) (k.l) A( Wc) + A( B+B) ( C+C) ( k .2 ) and A(B*C) +A(B+B) (C+C) (+.3) which are the same as functions 3»lj 3«2 and 3«3, are included to avoid the necessity of using three cells to obtain these functions. The fourth function ((A+A) + (B+B)) (C+C) (+.+) was picked since it is the representative function of one of the Z3 < < O o _l UJ o o < X LxJ X CM UJ a: => u. 2k TABLE 3: HEXAGONAL CELL CONTROLS V ° 1 A A ^2 : 1 B B q 3 : 1 c c D OUTPUTS E OUTPUTS v ° A INPUT INHIBITED q io : q 5 : % : B C it it II II *LL ! V o V "6 = V 1 q io : 1 *11 : q l2 : q 13 : 1 0^ q 8 : 1 V 1 • + q 13 : q li+ : o 1 q 15 : 1 1 1 9 1 1 1 ( A+A) ( B+B) ( C+C) +( A+A) ( B+B) ( C+C) 1 1 1 1 1 [ ( A+A) +( B+B) ] (C+C) a(b©c)+a(b+b)(c+c) 1 1 1 1 1 1 1 a(b@c)+a(b+b)(c+c) 1 1 1 *L6 : 1 FLIP' -FLOP V ] A+A B+B C+C E D 1 1 d 1 1 d 1 1 d I OUTPUTS SAME AS q 9 : 1 d i PREVIOUS OUTPUTS 1 1 1 1 1 1 1 1 1 /outputs same as (previous outputs 25 classes with the maximum number of members {2k). The flip-flop is a Set-Reset flip-flop and is controlled by cu and q-./-« When this type of operation is desired, D and E are the outputs while A is the set, C is the reset, and B is the trigger. k.3 Logic Implementation The implementation of- the hexagonal cell is similar to that of the square cell. The function or complement decision logic is shown in Figure 13 while the D functions are formed and generated in Figures Ik and 15. The E functions are formed in exactly the same way except that the control bits are different. A Set-Reset flip- flop is included and illustrated in Figure 16. Finally, the address logic used is the same as that for the square cell and can be found by referring back to Figures 10 and 11. k.k Advantages and Disadvantages As for the square cell, the hexagonal cell can also produce all 256 functions of three variables using two cells. Of these, only 92 can be formed with one cell and would therefore indicate that a square cell would be the better cell. As the examples of Chapter 5 illustrate, however, the hexagonal cell usage results in the minimum number of cells. This is due to the fact that there are always three outputs and three inputs with the hexagonal cell. Thus, hexagonal cells, not requiring an input/output decision, have a more logical coding scheme and are easier to program. The hexagon, as well as the square, have the disadvantage that if a variable is used in both output functions, either the vari- able or the complement is used but not both. This can be corrected in many instances by complementing the input of the adjoining cell rather than adding additional gates in each cell. 26 o o CO o LlJ Q h- Z UJ LlI _J Q. O o cr o g O z LlI O O CD < X UJ X ro LlI a: => o 27 28 23 FLIP-FLOP A + A q 9 B + B C+C q 16 ~?n? 16 FIGURE 16. HEXAGONAL CELL FLIP-FLOP LOGIC 30 5- EXAMPLES OF THE USE OF CELLULAR LOGIC Since each of the three cells discussed in this thesis con- tain a flip-flop, binary counters and shift registers can be made by the proper combination of cells. Figures 17 and 18 show that the square method and the hexagon method use the same number of cells for a shift register while in Figure 19, the cutpoint method requires four times the number of cells.' Another common digital circuit is a three— variable decoder. iigures 20, 21 and 22, which are examples of this type of circuit, show that there are twice as many square cells and three times as many cutpoint cells used than hexagonal cells. Figure 23 shows a nines complement circuit and the individ- ual cell coding for the square cell method. Figures 2k and 25 are the hexagonal and cutpoint methods respectively. A translator from binary-coded decimal to two-out-of-five circuit is shown in the next three figures (26, 27 and 28). As usual, the hexagonal array requires the least number of cells. Further examples of using cellular logic to form functions that are used in digital work are shown in Figures 29 through 37 • As before, the cutpoint arrays use the most cells in every case while the hexagonal method uses the least. 31 4 STAGE SHIFT REGISTER 1 0-7 BINARY COUNTER FIGURE 17. SQUARE CELL REGISTER AND COUNTER 4 STAGE SHIFT REGISTER 0-7 BINARY COUNTER 3Z A — » FIGURE 18. HEXAGONAL CELL REGISTER AND COUNTER. 33 T fc Yi 1 1 v 5 ^ 5 fc 5 ^ 5 h. P p p p ir v 1 v 13 b 13 t 13 t 13 ^ P p p p v v ^ r v 5 fc 5 b 5 h 5 b, T4-P P p p p ir v 1 f 1 r 13 h 13 h 13 t 13 fc, P p p p lx 2 X. x 6 lx. ▼ © FIGURE 19. OUTPOINT CELL FOUR STAGE SHIFT REGISTER. *Minnick,R.C., "Outpoint Cellular Logic," p.696 34 CM x — ► X CM X fc X ix" CM — ►x fO X X CM —►ix x° —►ix ro X x~ CM — ►x IX |X~ CM ->x ro IX IX _3 "^ IX IX CM X w lx"t *t CM X w X CM IX a: UJ X| *t o o o UJ a CM X W Ix CM IX UJ _j IX [ *t m < CM x — ► < > X CM X w UJ X| ix n ! UJ CM ^ X w IX CM X w -1 _l UJ |x t Ix°f o CM x — ► fc UJ < x~ CM IX w 3 O C/> x~T *t CM fc o CVJ X w CM IX w UJ a: 3 ix~[ D?t U- CM X w —w X X 35 IX IX or LlI Q o o LJ Q LJ IX 00 < or < > LJ LlI q: X IX LJ O IX O < X Ll X LJ or => O 36 X lx + IX~ > sr k, CO fc, lO |X~ p w k J i M IX +_ X J L ro fc, CO k. m ix" p p i L •i L CM X + lx" < L ro w *- h in X p p i l i L N i L *t fe *- X + X fc in X p p l i i i CM i i *- w CO IX + ix - h ro |X~ P p i i i i N i i ro fc CO IX + x~ h, ro |X~ p p t i i i CM i i. ro O CD O LlI cL X Q CM IX ~ •» 10 X Ld o _l o> CD < o or < 3 IX - > "a> IX LlI O X LlI tr "c I o h- _l _J 3 o X Ld X IO O O IX r- a: 2 ~ ^mm .^ o o 0_ c r- c _ 3 ^ IX O X * K> IX CO CO LU or e> X Ll X 37 1/=X, ^3 SX 3® X 2 X 5 ^'Vs'W ^ =X P X 5 \C0DE CELbv 1 2 3 4 5 6 7 8 9 10 II 12 13 14-16 1 1 1 1 d d 1 1 1 1 1 2 1 1 1 d d 1 1 1 3 1 1 d d 1 1 1 1 4 1 1 1 1 1 d d 1 5 1 1 d d 1 d d 1 1 6 1 1 1 d d 1 1 1 1 1 1 FIGURE 23. SQUARE CELL NINES COMPLEMENT CIRCUIT 38 IX X II 3 O O UJ UJ -J a. o o 0) UJ -J < o < X UJ X UJ a: O 1 X A — >- 1 1 39 X 2 — M X 3 — » x, — ► T i/, = x,©x 5 T i/ 3 = x 3 ©x 2 x 5 -► LT=X 2 T i^=x 2 x 3 (x 4 ©x 5 ) FIGURE 25. OUTPOINT CELL NINES COMPLEMENT CIRCUIT* *.. Minnick.R.C , Cutpoint Cellular Logic, p.695. 40 IX lx~ IX + IX X $ X II IX IX IX IX + ix" |X + CM Ix + IX IX IX CM X X II IO IX + CM IX X II * X JX IO IX IX X IX X X IX X IX + IX UJ > U- I o I o o UJ Q Q UJ o O O I >- < GQ O or or o < _i CO < or \- UJ o UJ or < z> o CO CD CO UJ or =) CD 4/ X IX e X m X + X IX IX IX" + IX + ix" If X IX + IX x" UJ > u. I U- o o I o 5 < 2 o uj Q Q UJ Q O O I >- cr < CD 2 o tr li- ce o (- < _i CO z < cr UJ a o < x UJ X N-' CVJ UJ tr 4Z w, • x 3 [x l +(x^»)^)| w 2 -x ( (x 2 + x s ) w,- x 2 w 4 ■ Xjix, +5^RX, x 2 x 4 vyx 4 +x J (x | © x 2 9x 4 ) y * y 4 ' L r \ 7 1 7 \ I 3 fe *4 *' V. 1 3 { r 7 1 r r 1 r 1 X 3 y ( r 1 r 5 ] r 4 1 i r 1 1 r x 2 y ' k r 1 i r p } > h 1 - r i p 1 ( r ft. A i < r ' r fe < r 2 1 r i \ r 5 ' r i r } r i r 5 w \ i r i ' r I 1 1 r 4 r 4 — 1 r 4 r w J r 7 p ( r < r J r 1 r \ r w, w, w, w 4 w 5 '2 "3 FIGURE 28. OUTPOINT CELL TRANSLATOR FROM BINARY-CODED DECIMAL TO TWO-OUT-OF-FIVE * * Minnick.R.C. ."Cutpoint Cellular Logic," p.696 43 IX + X IX + ► If) (£ if) * o fO o o O o o o PJ o o o o TJ TJ r o - - o T3 TJ o o - o - "D TJ TJ TJ CJ o - — TJ TJ TJ — — o — TJ TJ TJ O o - - tj TJ TJ /-l /_! / W / ° - CM rO i X,® r *2 i *3 r Y k 5 h 1 fc. 3 h X 4 P p P P i x,x r 5*4 i x ( € * 2 i X 3 F *4 '«" 4 (x,®x 2 wx 3 +x 4 ) x 3+ x 4 3 1 r 1 ' i F FIGURE. 34 OUTPOINT CELL EXAMPLE B 49 CM X x- €) IX IO X + ,x~ K m IX IX* '*L IX + x~ * CM IX in X II ■6 X IX~ x + IX IX" > l>T IX~ IX -f x" x" x~ ♦ X* ,x~ 1 I 1 I J L * X h w P CM X X CM IX X* eg IX + X 1 r IO V x V X CM CM X X P P IO X CM X IO + X lx" IO X n IX x n * X CM IX n X 1 ' N CM IX i r IX _ X X *- w P p i k i k m IX M IX X m IX IX* + IO IX * IX CM IX IX in IX IX Ik IX fc P p i i i i i k * * IX — IX |x CM IX lx~ IX CM IX IX M IX IX h fe p p o UJ _J 0. < X UJ UJ o UJ cr < 3 O CO ID ro ui or 3 O T T f x 50 IX + X X IX x - +m IX •x* eg IX lx~ > r> IX CVI ix_ IX +« UJ _1 0_ < UJ o o < X UJ to ro UJ q: =5 u. T = Xj X^Xg + Xg X^ Xg+ X. X2 X» X- + X. X 2^4 ^5 "*" ^1 ^2 ^3^3 51 x, — ► 00000 11 L _i I x, — > x, — >> x |+ x 2 V X 2 x,+x 2 X 4 — ► x,+x 2 +x 3 x,+x 2 X| x 2 x 3 x.— * X 2 X 4 x 2 x 3 *2*4*9 FIGURE 37. OUTPOINT CELL EXAMPLE C 52 6. SUMMARY AMD CONCLUSION Three types of cells, cutpoint , hexagonal, and square, were discussed in this thesis. Each of these designs were proposed to replace the large number of individual integrated chips that are in use today. The cutpoint cell is the most primitive cell. Only half of the functions of two variables and a flip-flop function are obtain- able from this cell. This results in cellular arrays for a n-vari- p able function as large as n+1 by 2 ' cells. At present, though, this is the easiest module to program. The square cell is the next step in refining this logical design technique. One fixed input, one fixed output, and two vari- able lines are employed in producing many of the functions of three variables. As a result, $6% less square cells than cutpoint cells are used in typical examples. Since no algorithm exists at present, programming these cells must be done by hand. Research into these progr a mming requirements, however, may uncover a suitable computer al- gorithm. Also, new minimization techniques may reduce the number of cells needed to produce various functions and thus make programming easier. The final step in the production of a new logic element is the hexagonal cell. Although this cell produces less functions than the square cell, its three fixed inputs and three fixed outputs yield arrays with 66f less cells than cutpoint arrays and lOf less cells than square cell arrays. Once again, an algorithm for a computer is needed to eliminate programming by hand. 53 A further improvement can be made in both the square and hexagonal cells by increasing the logic in each cell. At present around 200 gates are used in the design of the logic. Since this large number of logic elements appears to be the maximum that can be put on a chip at present, perhaps future innovation could increase this number. With the increased number of gates, however, goes an in- crease in the control bits, tending to complicate the program and pre- venting any substantial saving. The 16 bits used in the hexagonal and square cells were the minimum number of bits that would yield the necessary basic functions. Although an internal shift register is included in each cell, it is by no means the only possible method. In fact, it might not even be the best way as future research may prove. Other sugges- tions for cell addressing would include external registers, micro- welding, or even 16 individual lines per cell. Finally, it is possible that shapes other than square or hexagonal would be more useful. Another area for investigation would be multilayer designs. In this case, the cells that comprise one lay- er may even be different in shape from those of the adjoining ones. Thus, in this paper it has been shown that a single chip capable of performing various functions can be used as the basis for digital circuits. These cells would eliminate the large number of in- dividual NAND and NOR gates and inverters that are presently encoun- tered in this type of circuitry. As a result, the digital equipment could be smaller in size. Also, after an initial period, the cost per module would approach that of the individual integrated chips and would yield a substantial monetary saving. As a final comment on the advisability of using modular design, Mr. John Holland states: 5^ "If the cost of production is largely set-up cost, it may be possible to produce complicated modules for what it presently costs to produce and assemble a few transistors. Should this happen, average use fac- tor for individual elements is no longer a reasonable measure of over- all machine efficiency."* ^Holland, John H., "Iterative Circuit Computers: Characterization and Resume of Advantages and Disadvantages", in Spandorfer, L. M., Proc. of a Symposium on Microelectronics and Large Systems , p. 176. 55 REFERENCES 1. Minnick, R.C., "Cutpoint Cellular Logic", IEEE Transactions on Electron Computers, EC-13, Vol. 6, pp. 685-698, December 1964. 2. The Staff of the Computation Laboratory, "Synthesis of Electronic Computing and Control Circuits", Harvard University Press, Cambridge, Mass., 1951, PP- 23-27. 3. Holland, John H., "Iterative Circuit Computers: Characterization and Resume of Advantages and Disadvantages", in Spandorfer, L. M., Proc. of a Symposium on Microelectronics and Large Systems, Spartan Books, Washington, D.C., 1965, PP« 175-177 • k. Hohn, Franz E., "Applied Boolean Algebra", Second Edition, The Macmillan Company, New York, 1966. 56 APPENDIX A LOGIC ELEMENTS INVERTER A = +4V, A= OV, B = OV B = + 4V A B NAND GATE A = OV, B=OV, C=+4V A=OV, B=44V, C=+4V A = +4V, B=OV» C=+4V A= + 4V, B= +-4V. C=OV A B 5 NOR GATE A=OV, B=OV, C=+4V A=OV, B=-h4V, C=+4V A=+4V, B=OV, 0+4V A=+4V, B*+4V, C=OV 57 APPENDIX B Number of Cells Used to Form a Function of Three Variables Class Hexagonal Cell Square Cell 1 1 1 .1 1 2 1 1 3 2 1 U 1 1 5 1 1 6 2 2 7 1 1 8 1 1 9 2 2 10 2 "2 11 2 1 12 .1 1 13 1 1 ■ lU 2 1 15. 2 2 16 2 2 17 1 1 18 2 2 19 2 2 20 1 1 21 1 1 58 APPENDIX B Cont'd Summary of the 256 Functions of Three Variables Class Number of Functions 1 1 8 2 k 3 12 k 12 5 8 6 2k 7 2k 8 6 9 8 10 2k 11 2k 12 2 13 6 111 2k 15 2k 16 8 IT 12 18 12 19 k 20 8 21 1 Representative Function xyz xyz + xyz x(y©z) xy x(y®z) + xyz xy + zxy x(y + z) x yz + x(y + z) xy + xz x$yz x©(y»z) x«y x + yz xy + (y*z) yz + (xfyz) x + y x + (y®z) (x$y) + (x$z) x + y + z 1 59 APPENDIX B Cont'd Functions of Three Variables Class 0: Class 1: xyz xyz Class 2: xyz xyz xyz xyz xyz xyz xyz xyz + xyz xyz + xyz xyz + xyz xyz + xyz Class 3: x(y©z) z(x©y) x(y©z) z(x®y) x(y©z) z(xiy) x(y©z) y(x©z) y(x©z) y(x©z) y(x©z) z(x©y) 60 Class h: xy xy xy xy yz yz yz yz xz xz xz xz Class 5 x(y®z x(y©z x(y©z x(y®z x(ylz" x(y®z x(y?z" x(y©z + xyz + xyz + xyz + xyz + xyz + xyz + xyz + xyz 61 Class 6: xy + zxy xy + zxy xy + zxy xy + zxy xy + zxy xy + zxy xy + zxy xy + zxy yz + xyz yz + icyz yz + xyz yz + xyz yz + xyz yz + xyz yz + xyz yz + xyz xz + yxz xz + yxz xz + yxz xz + yxz xz + yxz xz + yxz xz + yxz xz + yxz Class 7: x(y+z) x(y+z) y(x+z) z(x+y) x(y+z) y(x+z) y(x+z) z(x+y) x(y+z) y(x+z) z(x+y) z(x+y) x(y+z) y(x+z) z(x+y) x(y+z) y(x+z) z(x+y) x(y+z) y(x+z) z(x+y) x(y+z) y(x+z) z(x+y) 62 Class 8: Class 9: Class 10: x x y y z z x( y+z ) +yz x(y+z)+yz x(y+z)+yz x(y+z)+yz x( y+z ) +yz x( y+z ) +yz x(y+z)+yz x(y+z)+yz xy + xz xy + xz xy + xz xy + xz xy + xz xy + xz xy + xz xy + xz yz + yx yz + yx yz + yx yz + yx yz + yx yz + yx yz + yx yz + yx zx + zy zx + zy zx + zy zx + zy zx + zy zx + zy zx + zy zx + zy 63 Class 11: x © yz x © yz x © yz x © yz x © yz x © yz x © yz x © yz y © xz y © xz y © xz y © xz y © xz y © xz y © xz y © xz z © xy z © xy z © xy z © xy z © xy z © xy z © xy z © xy Class 12: x©(y©z) x©(y@z) Class 13: x©y x©y y©z y©z x©z x@z 6k Class Ik: Class 15: x + yz x + yz x + yz x + yz x + yz x + yz x + yz x + yz y + xz y + xz y + xz y + xz xy + 1 iy®z) xy + ( 'ySz) xy + ( !y©z) xy + ( !y®z) xy + ( !y®z) xy + 'y@z) xy + ( ,y@z) xy + ( !y®z) yz + ( ,x@z) yz + ( ^xiz) yz + ( x@z) yz + ( ,xlz) yz + ( , x@z) yz + ( ,xiz) yz + [ v x$z) yz + ( v x®z) xz + ( >@y) xz + !x@y) y + xz y + xz y + xz y + xz z + xy z + xy z + xy z + xy z + xy z + xy z + xy z + xy xz + (x©y) xz + (x@y) xz + (x@y) xz + (x©y) xz + (x©y) xz + (xl£y) 65 Class 16: yz f (x$yz) yz f (x©yz) yz f (x©yz) yz f (x©yz) yz • f (x@yz) yz ■ f (x©yz) yz ■ f (x@yz) yz ■ f (x©yz) Class 17: X + y X + y X + y X + y y + z y + z y + z y + z X + z X + z X + z X + z Class 18: X + (y©z) y + (x©z) X + (y£z) y + (x®z) X + (y©z) z + (x©y) X + (y5z) z + (x®y) y + (x©z) z + (x©y) y + (x5z) z + (x®y) 66 Class 19: (x$y)+(x©z) ( x@y) +( x©z) (x©y)+(x®z) ( x®y) +( x@z) Class 20: x+y+z x+y+z x+y+z x+y+z x+y+z x+y+z x+y+z x+y+z Class 21: 1 u v 28 tor* £ &