Digitized by the Internet Archive in 2013 http://archive.org/details/burstlogicdesign895tiet CENTRAL CIRCULATION BOOKSTACKS The person charging this material is re- sponsible for its renewal or its return to the library from which it was borrowed on or before the Latest Date stamped below. You may be charged a minimum fee of $75.00 for each lost book. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. TO RENEW CALL TELEPHONE CENTER, 333-8400 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN JUN 1 8 1996 SEP 2 3 m JUN 3 1997 When renewing by phone, write new due date below previous due date. L162 ^ UIUCDCS-R-77-895 ^/auL UILU-ENG 77 171*9 BURSTLOGIC: DESIGN AND ANALYSIS OF LOGIC CIRCUITRY TO PERFORM ARITHMETIC ON DATA IN THE BURST FORMAT By LEON CLEMENS TIETZ May, 1977 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS i UIUCDCS-R-77-895 BURSTLOGIC: DESIGN AND ANALYSIS OF LOGIC CIRCUITRY TO PERFORM ARITHMETIC ON DATA ON THE BURST FORMAT By Leon Clemens Tietz May, 1977 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 1977 BURSTLOGIC: DESIGN AND ANALYSIS OF LOGIC CIRCUITRY TO PERFORM ARITHMETIC ON DATA IN THE BURST FORMAT Leon Clemens Tietz, Ph.D. Department of Computer Science University of Illinois at Urbana-Champaign, 1977 The goal of this research was to develop designs for arithmetic processors with input and output data both in the Burst format. An ad- ditional requirement was that these designs be constructive from readily available logic circuits such as TTL SSI and MSI and be competitive on both a cost and performance basis with the Block Sum Register (BSR) techniques first proposed for Burst Processing. The result is a family of arithmetic processors based on a design for adding Bursts known as the Perverted Adder (PA). The PA is a full adder and a flip-flop connected with the sum output of the full adder fed back to the carry input via the flip-flop. This simple circuit performs Burst addition. However, the output Bursts are uncompacted, i.e. the ones are no longer adjacent to one another, whereas BSR de- signs output compacted Bursts. Designs for a multiplier and divider use a tree of perverted adders to perform the requisite additions in parallel. Several modifications of this basic PA tree are also presented. They permit a reduction in the amount of hardware and a natural extension to Burst lengths other than the integer powers of two that are so natural for PA tree design. Several designs are also presented for performing arithmetic on signed Bursts. Designs employing both the sign and magnitude and a biased Burst technique are illustrated. The designs for unsigned Bursts and some of those for signed Bursts use no registers to assemble Bursts before or after the processor. This design feature makes these truly on-line processors and gives them better high frequency response for a given clock rate than the other logic designs which have been proposed. A PA CPU has been constructed to demonstrate Burst multiplication and division using PA techniques. The design of the CPU is basically a PA divider with modifications to permit the circuit to function as a multiplier. The design is based on an 8-bit-per-Burst format and displays the output in the form of the number of "1" bits in either 8 or 64 time slots at the user's option. A comparison to other Burst processor designs shows that the PA designs are less hardware intensive and are generally faster than the other designs. m ACKNOWLEDGMENT I am deeply indebted for the generous assistance given me during the preparation of this thesis. I wish to thank Frank Serio and Stan Zundo for their assistance in the preparation of the hardware needed for this thesis. Many thanks to Marty Blakey for preparing the drawings and to Nadine Luc for typing the manuscript. Their long hours are greatly appreciated. To my advisor, Professor Poppelbaum, go special thanks for his ideas, guidance and encouragement. Last but not least, thanks to my mother and father for their encourage- ment and to my wife, Addie, for her patience and understanding. iv TABLE OF CONTENTS Page 1 INTRODUCTION 1 1.1 An Explanation of Burst Processing 1 1.2 Burst Encoding Methods 2 1.3 Definitions 5 2 PERVERTED ADDER CIRCUITS 8 2.1 Introduction 8 2.2 Logic Description of the PA 8 2.3 Design and Operational Principles of a PA Multiplier ... 10 2.4 Design and Operational Principles of a PA Divider 13 2.5 Use of PA Circuits in Signed Arithmetic Processors .... 16 2.5.1 Sign and Magnitude PA Adder/Subtractor 17 2.5.2 Biased Representation PA Multiplier 19 2.5.3 Representation Converters 20 2.6 Modified PA Trees 22 2.7 Multi-input Pa Adders 28 3 A BURST CPU TO DEMONSTRATE PAs 29 3.1 Clock and Control Circuits 29 3.2 Burst Generators 32 3.3 The CPU 35 3.3.1 Shift Register and Combinational Logic 35 3.3.2 PA Tree 37 V Page 3.4 Display Circuitry 40 3.5 Discussion of Operation 40 4 CIRCUIT DESCRIPTIONS, EVALUATIONS AND COMPARISONS ....... 43 4.1 BSR Circuits 43 4.2 PA Circuits 45 4.3 Other Logic Design Approaches to Bursts 46 4.3.1 BURSTCALC 48 4.3.2 LOCOBURST 49 4.4 Weighted Binary 53 4.5 Other Arithmetic Processors 55 4.6 Summary 55 5 CONCLUSIONS 59 REFERENCES 61 APPENDIX A: ICs Used in the CPU 62 APPENDIX B: Edge Connector Pin Assignments 64 VITA 65 1 INTRODUCTION 1.1 An Explanation of Burst Processing Burst processing was first proposed in 1974 by Professor W. J. Poppelbaum (1) as a PCM transmission and processing system that com- bined the advantages of both stochastics and weighted binary methods. The unit of information in Burst processing is the Burst which con- sists of a predetermined number of "bits". These bits are all of equal weight as opposed to weighted binary where bit position deter- mines a weighting factor. The equal weighting of the bits in a Burst causes Burst process- ing to have high noise tolerance without a need for sophisticated error correcting codes and the complex hardware associated with such devices. This noise tolerance does not come cheaply. A ten bit Burst is able to represent 11 different values. Only about 3-1/2 bits of weighted binary are necessary for the same precision. Another advantage is that there is no need for synchronization. Because e\tery bit has the same weight you can start anywhere. Because Bursts are a deterministic representation of values, they do not suffer from the severe problems of attaining accuracy that stochastic methods do. In Burst processing the accuracy is di- rectly proportional to the length of the bit stream, or number of Bursts being observed. In stochastics the accuracy goes up only as the square root of the length of the bit stream. 1 The first method for performing arithmetic on Bursts involved a Block Sum Register (BSR). A BSR is a shift register with each bit position of the register controlling a current source (see Figure 1). As the data in Burst format passes through the BSR it produces an output signal proportional to the number of one bits in the register. BSRs perform arithmetic in a quasi -analog fashion and re-encode the result- ant data to Burst format for retransmission. Applications of Burst processing have been demonstrated by the Information Engineering Laboratory, under the direction of Professor Poppelbaum. (2) Many current projects are using Perverted Adder (PA) techniques as developed in this thesis rather than BSRs or other logic approaches to performing arithmetic. Comparisons of the various methods are found in chapter 4. 1.2 Burst Encoding Methods Before data can be transmitted or processed in the Burst format it is necessary to encode it in that form. The simplest form of encoder is the ramp encoder. A staircase waveform is generated and con- stantly compared to the analog input. If the analog signal is greater than the staircase, the encoder transmits a one. If it is lower, a zero is transmitted. Figure 2 depicts this encoding process. This simple encoder is incapable of generating a Burst sequence with a long term accuracy greater than that available from a single Burst (e.g. one part in ten). (A CD O >|o: x OH I 00 c 2 ° < ■o« o c o c o o d31SI03d ldlHS o 00 2 >- < Q- z o z < h- => J- Ol o O O) Q. •r- (J C •r— $- Q. i- cu -o o (J c O) «3 CM ro tr o u. Z5 O rO rO ro rO ro rO a- 4-> (/> S- 13 CO 4- o a> Q. E f8 X cu E fO T3 s- aj "O O o o QJ J- QJ C s- QJ CO QJ S- 3 • © was developed. All the ones in a single Burst are adjacent. In this representation the beginning of a Burst can easily be defined as the first one of the adjacent group. Uncompacted Bursts have ones scattered throughout the Burst and thus lose the sense of a "burst" of ones. Better frequency response is attainable with uncompacted Bursts, but some of the cheap error correcting methods (3) possible with compacted Bursts are lost. A Super Burst is a group of n Bursts each n bits long. If a Burst then can have a precision of p, a Super Burst can have a precision of 2 p . The vernier encoder of section 1.2 is designed to produce Super Bursts. The Bursts that have been described thus far are capable of representing only positive numbers. They will be referred to as unsigned Bursts . Most Burst applications have used unsigned Bursts. Representation of negative numbers has been accomplished in two ways. The sign and magnitude representation uses an additional signal to represent the sign of the number, the magnitude is the same form as an unsigned Burst. A biased Burst represents signed numbers by assigning the value of zero to a half filled Burst; less than half is negative, more than half is positive. Designs employing both representations are presented in chapter 2. 2 PERVERTED ADDER CIRCUITS 2.1 Introduction A new family of circuits has been designed to perform arithmetic on data in the Burst format. This family is the result of a search for a logic design that is competitive with the Block Sum Register (BSR) arithmetic elements that were first proposed for Burst arith- metic. This family of circuits is based on a simple circuit building block which has been called the Perverted Adder (PA). The name was chosen because of the unconventional use of a full adder in the circuit. It should be noted that logically simpler realizations of a PA than the one shown here are possible. However, their realiza- tion with conventional SSI and MSI chips yields a higher chip count than the circuit described here. 2.2 Logic Description of the PA The function of the PA is to accept input in Burst format on two input lines and to produce as an output the sum, also in Burst format. This sum must necessarily be scaled by a factor of two to prevent overflow. Table 1 is a state table (4) which describes the PA. Notice that there are two inputs "X-," , and "X-", two in- ternal states, and one output. Table 1: State table for the Perverted Adder (PA) (PS = Present State; NS = Next State) NS,Z PS x^ 2 = 00 01 11 10 A B A,0 B,0 B,0 A.l A.l B.,1 B,0 A.l The machine is in state "A" when an even number of pulses have arrived on the two inputs and in state "B" after an odd number of pulses. An output "1" is generated whenever the machine goes from state "B" to state "A" or when two ones appear at the inputs simul- » taneously. The combinational equations describing this machine are: Z = x ] x 2 + x^ + x 2 y (1) Y = x^y + x^ 2 y + x^ 2 y + x-,x 2 y (2) 7" is the output and "Y" is fed back to the delay element yielding 10 when the flip-flop passes the signal. Except for an interchange of the left hand sides, the above equations are just those of a conventional serial adder. Figure 4 shows the logic of a full adder, the full adder and a D flip-flop connected as a Perverted Adder and the symbol used to repre- sent the PA. This PA circuit is all that is required to add two unsigned Bursts or two Bursts with biased Burst representation. To subtract biased Bursts an inverter is inserted in the input lead of the subtrahend. The output is always a properly scaled, uncompacted Burst. Uncompacted Bursts are completely acceptable as input. 2.3 Design and Operational Principles of a PA Multiplier A multiplier has been designed in which the multiplier, multiplicand and the product are all in Burst format. It will be helpful to refer to Figure 5 during the discussion of the operation of the PA multiplier. The multiplicand ("B" in Figure 5) flows through the shift register at the top of the diagram. The shift register is exactly the length of one Burst, and so, like a BSR, always contains as many ones as the value of the number being represented. Notice that the multiplier ("A" in Figure 5) is ANDed with a clock signal and the output of this AND gate is used to clock the Perverted Adders. The top row of PAs will produce a scaled sum of the contents of the shift register. This sum will appear in paral- 11 INPUTS V V v W W CARRY D SUM X, X: CLOCK ► BURST SUM ► BURST SUM Figure 4. Logic diagram of a Full Adder (top), Full Adder and Flip-flop connected as a PA (lower left), Symbol for PA (lower right) 12 B SHIFT REGISTER I , 1 CLOCK Figure 5. Circuit for the PA multiplier. 13 lei on the four outputs from the top row. These four lines are Inputs to the second row of PAs and the outputs of these go to the Inputs of the final PA. The actual addition takes place only when a one is present on A to produce the clocking signal. The result is that B will be added into the PA tree A times and the output will be the scaled sum of these additions. Each level of the PA tree causes a scaling by a factor of 2, hence the factor of 8 for the multiplier in Figure 5. The delay through this circuit is dependent on the Burst sum propo- gation. Recalling that this is actually the carry output as the full adder is normally used and that that output is often faster than the production of the sum, propagation speed through the tree is quite good. Speeds of 5 to 8 MHz are possible with conventional TTL ICs. 2.4 Design and Operational Principles of a PA Divider A PA divider can be constructed by adding only a few components to the multiplier. Recall from the discussion of the PA multiplier that the PA tree produces one output pulse (on the average) for eyery 8 ones added into the top row of PAs. If one were to "load" the tree with 8-n ones, then just n more ones would produce a one at the output. This would, in effect, be performing division by n on the input stream supplying the additional pulses. If eyery time the output of the tree produces a one, we load the tree again, we are performing a continuous division by n. The number of ones needed to load the tree (8-n) is easily generated by inverting the divisor and passing 14 it into a shift register. An example should serve to clarify this division algorithm. Assume we wish to calculate A/B in an 8 bit-per-Burst system. A can be any number, B will be assumed to be 3. Passing B through an inverter produces Bursts with 5 ones. Begin by adding the 5 ones (in parallel) into the PA tree. Begin to add A into the tree, one bit at a time, into one input to the top row of the PA tree. After three ones (on the average) from A are added into the tree, a one will be output. At this time we again add 5 ones (the inverted B) into the tree and proceed adding more bits from A. A divider of this type needs a two phase clock. During one clock phase the inverted divisor is added into the tree (when needed), and during the other phase the dividend is added into one input of one PA in the top row. The PA tree must be clocked on both phases. It is possible, at the expense of some hardware to build a divider using a single phase clock. This divider runs at speeds comparable to the multiplier as it is necessary to wait for only one ripple through the tree each cycle instead of two. This can be performed in either of two ways. The inverted divisor can be staticized (i.e., held without shifting for 8 clock cycles) in a register in such a way that the one bits in that register do not interfere with the input of the dividend. It may also be accomplished by moving the one bits (specifically the one that falls on the input lead reserved for the dividend) as necessary with combinational logic. This latter approach is used in the circuits in Chapter 3 and is illustrated in Figure 6. The combinational logic shown in Figure 6 implements the following equations: 15 B H> B, i — r SHIFT REGISTER J L B B- B, B. B, B B, COMBINATIONAL LOGIC ^ c 4 C 7 W V V V V V CLOCK Figure 6. Circuit for the PA divider. 16 C ] = B ] B 2 B 3 B 4 B 5 B 6 B 7 B g (3) C 2 - B 1 + B 2 (4) C 3 = Bl B 2 + B 3 (5) C 4 = B ] B 2 B 3 + B 4 (6) C 5 = B ] B 2 B 3 B 4 + B 5 (7) C 6 = B l B 2 B 3 B 4 B 5 + B 6 (8 > C 7 = B-| B 2 B 3 B 4 B 5 B g + B ? (9) C 8 = B l B 2 B 3 B 4 B 5 B 6 B 7 + B 8 (10) The quotient in this divider is not scaled, therefore overflow occurs only upon division by numbers smaller than 1. Division of any number by ' zero yields Bursts completely filled with ones. 2.5 Use of PA Circuits in Signed Arithmetic Processors Addition and subtraction of biased Bursts were covered in section 2.2 and proved to be trivial to implement. Multiplication and division of sign 17 and magnitude Bursts is also very simple. The only additional circuitry needed is an exclusive or gate to process the sign information. The imple- mentation of a sign and magnitude adder or subtractor and of a biased PA multiplier are described in this section. The most economical way to per- form division on biased Bursts appears to involve conversion to sign and magnitude and back again. In each of these circuits it is necessary to staticize Bursts in registers. In each case the data is delayed for a total of only one or two Burst periods. 2.5.1 Sign and Magnitude PA Adder/Subtractor A possible design for a Sign & Magnitude (S&M) PA Adder is shown in Figure 7. The principle components are two PAs and an n+1 bit bi-directional shift register. Not shown are an n bit parallel load shift register and the clocking circuitry to gate the result from one register to the other and to clear the bi-directional shift register after every Burst. This design is capable of accepting compacted or uncompacted Bursts and transmits compacted Bursts. The 4 inputs to this adder (2 Bursts and two signs) are duplicated above each of the PAs in Figure 7. The gating between the input and the PAs causes the left PA to add only positive numbers, the PA on the right adds only negative numbers. The outputs of the PAs are used to control the shifting of the bi-directional shift register. The shift register is end connected via inverters. This ensures that the number of ones in the register corresponds to the magnitude regardless of the arrival times of positive or negative addend or augend. The left most bit of the re- 18 SIGN SIGN A A B B W A Kj CLOCK > — SIGN SR CLOCK OUT A SIGN SIGN A A B B vv SHIFT + LEFT 1 r BI-DIRECTIONAL SHIFT REQISTER 3! SHIFT RIGHT ▼ ▼ ▼ T * * MAGNITUDE OUT (8) 7. Figure 7. A design for a sign and magnitude adder. 19 gister always contains the sign bit according to the convention of a one for negative. The eight output bits are gated out in parallel, one of these bits being generated by the OR of the two end bits. 2.5.2 Biased Representation PA Multiplier By adding additional circuitry to the PA multiplier of Figure 5 it is possible to multiply biased Bursts directly with PAs. A mathematical explanation of the principles of operation of this circuit will simplify understanding its functioning. A biased Burst representation of n time slots per Burst will contain the number of ones specified by the following equations: A = a + n/2 (11) B = b + n/2 (12) The capital letters represent the number of "1" bits in the Burst. The lower case letters are the numeric value represented and n/2 is the biasing term. The product of two biased Bursts should then be 2ab + n/2 IT (13) Where "a" and "b" have been multiplied, scaled and biased. In terms of 20 the number of bits in the incoming Bursts the multiplication function be- comes : 2AB - A - B + n. (14) n The PA multiplier of Figure 5 performs the AB/n part of this function, Remembering that an output pulse from the PA multiplier is possible only when A has a "1", the function then becomes AB - A* - B + n (15) n where A* represents the A pulses that do not produce a product pulse from the PA multiplier. Looking farther we see that -B + n is just B, so we have AB - A* + B (16) n This function is realized by the circuit in Figure 8. Not shown in Figure 8 are a register to collect B~ left packed and a register to accept and serially transmit the data as well as the necessary clocking circuitry. 2.5.3 Representation Converters No biased representation divider has been designed. The only reasonable approach would be to convert to sign and magnitude and back again. Repre- sentation converters are not yery complex, but will involve running the bit rate for the biased representation at twice that of the sign and magnitude 21 l = RIGHT 0=LEFT SHIFT L/R Figure 8. A multiplier for biased Bursts, 22 representation in order to prevent loss of information. A sign and magnitude to biased converter is shown in Figure 9 and a converter from biased to sign and magnitude in Figure 10. 2.6 Modified PA Trees Several changes to the basic PA tree design are possible to adapt the circuit better to certain applications. If lower speeds can be tolerated in order to save hardware the circuit principle illustrated 1n Figure 11 can be used. An additional advantage is that the random noise caused by stored bits in the tree is decreased. This circuit uses only one flip-flop per level in the tree. This scheme requires carry ripples through the tree to proceed across and down. The optimum method of carry handling is to ripple toward the center of the tree and down. All PA trees described so far have scaled by an integer power of 2. It is possible to use this type of tree with noninteger power of two length Bursts, but dynamic range of number representation is lost. For example, ten bit Bursts scaled by a normal 4 level tree, cause a reduction of 37% of the dynamic range. Two such stages cause a loss of 61%. The method shown in Figure 12 illustrates a technique to adjust the scaling to precisely the value needed to preserve dynamic range. Figure 12 illustrates the tech nique for 10 bit Bursts but the generalization to any number is straight forward. To modify the tree to scale by the desired factor, the smallest tree is constructed which is capable of handling the desired number of inputs. The 23 00 o a: UJ i- — o UJ X CO o o _l o CO ■M to s. 3 CO ■o CD CO re .S o re E "O E re E D) •r— CO LU m O or CO z e> o < CO 2 E s- E o o o. z 24 x<-> COW UJ CO o o a:-" coo _i tc < LU Z H. O U> o LU O LU o '1 X 00 CO ^ H- to rar IO o -\ CO > QC < a. Q_ O O CU l i— c o •r" -M fO -M C a> to aj s_ Q. a> s- aj "O CJ +■> C cn -o •r- CU oo to 00 CU CD -C o +J o fO o -a c 0. C7) ° o to +J s- =J CO -o cu to CU CU -Q N to fO cu E E O -M O 'r- cu 91 -M +-> •r- IO .a -r- en 4_> CU .c s- O) •i- i- t- CU CU o -C r— +J CU CU 4-> s o +-> o 4- "O CU CU CU -C +J cu CU -o c s- cu ■a > -a <: CL CU ■M C to 1) c: o o +J ■a 0) cn -a cu 00 "O CU +J N ^~ »i — ZJ r— 00 •i — CU C -C •I— +J y en cu -Q • cn c c u +■> 00 •!— +-> .c 3 to CL +J S- =j o ol- io (-> to c cu cn •r- cu -c o rhi- CU i— •M • (TJ tO • r— C •r- "O CU o cn cu «— •■- CU $- f— -M J- fO fO fO cu s- c S- f— fO T- CU O Q.J3 Q- E Q. 00 C O 3 -i- t- O -O T- E o J- s- cu +J J- cu > c o u 25 to >>r: E 0) -a -c a) Q. C CO 4-> S- tO O O -C r— 10 0J O _C +-> +■> «4- O o s- cu -c E a o CD en c a. •i- o to r- • ca> OVi- to CD "O O) s- +■» a> c o s- +-> to r— TO Q- 0) Q. C7> •r- O) -C 26 -* fc. 5|2 i o li. < ft. o i < 0. ^ to It 3 to W / n 0) s- to Ol 2 w~ "s to x: 1 4- +-> < Q_ 01 1 1 1 SHIFT REGISTER 1 1 1 +j + a. < ft. <- o u. -J u. o a *- < ft. 1 01 s- u o -M [ -► 0. used ble. «- -> iques possi 2 < ft. *. c ^ O t~ k 2 «- a> +■> J- 01 h u a; A p < Q_ T3 •!- p 01 ^ s 1 (0 * • >> t CD Si > > Figure Scalir 27 unused inputs (regardless of their position in the tree) are feedback points to preload the tree in a manner similar to that described in section 2.4 for the PA divider. Table 2 shows various comparisons for performance for the techniques pre- sented in this section for various Burst lengths. Hardware complexity and delay times are given for normal PA trees as well as non-power-of-two trees and for both techniques of 1 storage element per level. Table 2: Comparisons of PA Trees Bits per Burst 8 10 12 16 20 Hardware Complexity Full Adders 7 11 12 15 21 Flip Flops Normal 7 11 12 15 21 Modified 3 4 4 4 5 Delays (ripples) Normal 3 4 4 4 5 Carry to End 6 8 9 11 14 Carry to Center 5 6 7 8 10 28 2.7 Mul ti -input PA Adders Burst addition as defined with automatic scaling is not associative; i .e. (A + B) + C ¥> A + (B + C) . (17) After calculation the left side will be A + B + C 4 4 2 (18) The right side will be A + B + C 2 4 5" (19) If it is desired to generate A + B + C 3 3 3 (20) this can be accomplished by a PA tree with feedback. Using a four input tree A,B and C are connected to three inputs and feedback is supplied to the fourth. This scheme can be generalized to any number of inputs. 3 A BURST CPU TO DEMONSTRATE PAs A Burst CPU capable of multiplying or dividing two 8-bit Bursts has been constructed. The input Bursts have each bit position de- termined by a front panel switch. The output is displayed on a pair of seven segment LED readouts. The counter which drives the read- outs is selectable between 8 and 64 clock cycles for the display. The clock may be external or internally derived by dividing the power- line frequency by 1, 2, 4, 8, or 16. The remainder of this chapter is devoted to a more detailed description of this CPU. Figure 13 is a photograph of this CPU which is complete on two circuit boards plus the front panel components. Figure 14 is a block diagram of the CPU and should be referenced to determine how the blocks of circuitry to be discussed relate to each other. Consult Appendices A and B for lists of ICs and board pin connections respectively. 3.1 Clock and Control Circuits The clock and control signal generation circuits occupy part of board 1 and can be seen in the schematic diagram at Figure 15. A.C. ripple from the power supply is directed to a one-shot multi- vibrator. The resulting TTL compatible signal is fed to the selector switch and to a 74163 4-bit binary counter, the outputs of which are additional clock signals which may be selected by SI. The external clock input is also shown. This clock signal is used in the Burst 29 30 C3 O CO 4- O o JZ Q. CO CD a> 31 HO UJ — ujO V) 0- UJ Si >- < -J o. 4 * CO o i / ^ or 5 UJ ^ ^ 2 ik z K p 3 O U. o o 4 ^ J k -1 3 in UJ Of < 3 CD H K X O -J S o|=^ 5 o -J UJ m o _ »- I => O 0- 1- ^ or en uj u a: < UJ 1- < " * <(=£> or z o (0 _) * 2 w as e> a. u u t u_ < 2 O UJ ■ H | * i r * 1- OT O O 52 ! J X o o X CO O o CO ( J or o UJ -1 r u 1 Q Z UJ -1 UJ _i t- fcj UJ z o , < or ^ or O < co > < UJ K J w o S2 5 o co o Q c_> i- c o E cu cu o to =D CO CU -C 4-> O E *o J- O) o o CQ CU s- en 32 generator, (see Figure 17) as well as in one of the NORs of IC 16. One of the by-products of Burst generation is the signal labeled "A", shown as an input to the clock section in Figure 15. The timing diagram of Figure 16, illustrates the relationship between the selected clock (system clock on Figure 16) and signal "A". This signal is used to drive a 7473 flip-flop and a 74163 4-bit counter. The feedback from Q D to the CLR input causes the 74163 to divide by 9. These two signals are used to gate the counter for display of 8 or 64 clock cycles respec- tively. The selection is made by either grounding or applying 5 volts to the display select input. This is done by a front panel switch. The output of the AOI (IC 20) is the same as the signal labeled "wait light" on Figure 16 for the selection of the signal from the 7473. If the 74163 was selected the signal would remain low for 64 clock cycles and high for 8 cycles. The output of the AOI is used to derive the remaining control signals. NORing it with the system clock produces the CPU clock. This signal is out of phase with the system clock and is inhibited when the display is in its update cycle (see Figure 16). "C" and "F" are signals similar to "A" but of different phases. In conjunction with the output of the AOI these generate the STROBE and CLEAR signals for the counter. The "wait light" is driven by an open collector inverter. 3.2 Burst Generators The input Bursts to the CPU are generated by the circuit of Figure 17. The heart of the Burst generator is the shift register and the NAND 33 o o _i o or O UJ I- O £ CD o <^0 J?*? o X UJ s &$$ 9 o CO en CO ■«-> U s- o c o •I— 4-> to s- OJ c O) C7> c •i— O s- +-> c o CJ -o c rU o o (J 0) 4-> a •r- -o ■M S- (0 cu •i- .c 34 L d GO f^- (O . m . =d a. «- ° o 1-1 o K) o _J 1- 00 <* (M => CO co UJ CO o cc co < UJ »- IU- 7 U- o§ o i H (VJ 03 — 00 UJ UJ > — CD O < 00 Z X o 1- _ CO t- * cc _l o o -J 13 CO 3 CO UJ o t- cc 3 r> 3 Q_ 0. 0. o z o 35 gate in the center of the diagram. These are connected to cause the shift register to always contain one zero and seven ones. The circuit is self-starting in less than 8 cycles. The outputs of Q», Q c and Q F are used by the clock and control circuits. Using the eight signals Q. to Q H any number of Burst generators can be driven. Each Burst generator (both are shown) consists of 8 switches, 8 2-input OR gates an 8-input NAND and a D flip-flop. These Burst generators generate uncompacted Bursts. 3.3 The CPU The actual arithmetic functions of multiplication and division are performed by the circuitry on board 2. This will be illustrated and discussed in two parts: 1) the shift register and combinational logic section and 2) the PA tree. The design is basically the PA divider discussed in section 2.4. This has been augmented with a few gates to change easily between the two functions. The switching is performed by a front panel switch which supplies either 5 volts or ground to the gates. During multiplication the circuit is operated with the divider's combinational logic in place and functioning. This logic is two levels deep and does not seriously degrade the multiplier. 3.3.1 Shift Register and Combinational Logic The CPU clock signal shown in Figure 17 is used to clock the shift 36 10 to Q) c_> <_> I— I CD O 00 0£ ZD ca S- o «♦- «/) CO s- ca -o CD +J - Q. § u c ai +■> f0 i- oj c o 4-> ■»-> o c_> i— TD S- J- O 3 CD •i- C U- O 37 register through which the B Burst will flow (see Figure 18). This Burst enters the register through an XOR gate which serves to pass or to invert the B Burst depending on the mode select input (inversion is necessary for division). Other functions of the mode select are to inhibit the A Burst from being fed directly into the first PA's input, and to inhibit feedback from the output of the PA tree. To clarify the diagram of Figure 18 connections between the shift regis- ter and the combinational logic are lettered. The use of these letters is local to this one diagram and is unrelated to similar letters in the Burst generator for example. Signals L & M are identical. Two gates were used to prevent the fanout problems of driving 14 inputs in the combinational logic section. The outputs of the combinational logic are labeled C, to C g . The corresponding inputs are labeled similarly on the PA tree diagram (Figure 19). 3.3.2 PA Tree The PA tree occupies the second half of board 2. Complete PAs are used rather than the circuits with less than one flip-flop per full adder shown in section 2.6. The mode select permits the flip-flops to be clocked by the A Burst or by the CPU clock. The circuit description and operation are exactly those of the designs in Chapter 2. The final flip-flop is needed to hold the last result for feedback and to accurately toggle the counter. Note that 38 -Ah 1) a. o t— I CJ3 O CO CD .c c o +■> o O) l/> o o c o 'I— +J CD s- JSZ CM (/) TJ (D S- .c « h- o CO . c CO o r ~ 3 (A CD S- (1) .c +■* «} +■> CD •♦-> O o o _l h- oo or Z3 CO 4- O C O •r- 4-> O CD (•> CD CD S- +-> o r-* CD - CM N ft £ CM S <" -<-i < 0. v 1 Q CO o f"l H- <^-| o *<_j • o >*— 1 z VwJ o o cs % Ul o ^*— 1 z CM cu c \_i >- UJ 10 > < us Q O < t* — L Q z o 1— 1 o CJJ o _J 1— to cc ZD CO -> >- o * s # £ o» ^n < -J Q. s 1 c o o O Q H- ^^"— 1 CO O +J — <-J u H 10 o Q Q # \ 9 s~~\ Z UJ >> ^ — 1 c O ro K> C_? •o ^~\ 2 >UJ 4-> •r- ^ — 1 CJ m a m U <^n CO z UJ > •r— a V_J fO en H o < .£> — •P" U- \- * * CO * UJ u to o O CO O ? o K ° UJ K _1 o QL Z _l o co _j o 42 unit is performing display update. This "wait light", so called because the CPU must wait for the output to be performed, serves several purposes. When the output is not changing, it assures the user that the unit actually is computing. It is also useful when experimenting with fractional input Burst patterns, such as representing 3-1/2 by 3 4 3 4. The switches that control the input Bursts can be safely reset during the time that the light is on. If these switches are changed at other times the results are unpre- dictable. The slower clock speeds are useful for this type of experi- mentation. The display format of the unit is a decimal number, not octal as might be guessed from the 8-bit input Bursts. The interpretation of the result must also take into account the fact that multiplication is scaled to prevent overflow in the 8-bit output Burst. Division is not scaled, hence overflow occurs only upon devision by zero. Division by one yields precisely the numerator. Caution must be exercised when interpreting the display with fast external clocks as changing displays are easily mis- read because of the inability of the eye to perceive the changes. Because it is inherent in the design of a PA tree to have some data stored and to not be able to define precisely when that data will come out, a given setting of the front panel switches may not always yield the same result (although the average will always be correct). It is possible, for example, to generate a value of 2-2/3 with 2 3 3 2 3 3 one time and with 2 2 4 2 2 4 the next. 4 CIRCUIT DESCRIPTIONS, EVALUATIONS AND COMPARISONS The PA circuits described in chapter 2 have been presented as a viable method of performing arithmetic in low precision, real time applications. This chapter will present comparisons to other Burst designs and to the more conventional methods of weighted binary and the Digital Differential Analyzer (DDA). These comparisons will in- clude design and operational descriptions and present data on hardware complexity/cost, aesthetics, speed of operation, noise immunity, and trade-offs between these and other design parameters. 4.1 BSR Circuits The BSR was used in the ramp and vernier encoders presented in chapter 1. The operating principle of the BSR is that it is a current source or sink whose strength is proportional to the number of ones in the shift register. Addition is performed by current summing and re-encoding the result with a ramp or vernier encoder (see Figure 21). Two multiplier designs are possible. A simple design uses one BSR to control the voltage source of the second. This scheme is a complete multiplier when the output of the second BSR is re-encoded. If higher precision is needed and is available, as when the inputs come from a vernier encoder, a time slip cascade multiplier is possible. (1) This design requires an entire 10 block segment of input to be trapped and be available for processing. Selection of bits is made by the same 43 44 03 + < Hi co CD Hi a: ! < ■►-aaaHi h- o CO i- Q -a -o go CO C\J S- cr> W\A-o > GD 45 vernier encoder that is encoding the result. The BSR approach is conceptually very simple, and has good possi- bilities for IC versions of entire Burst processors. The design of BSRs from discrete components is more difficult and is probably the reason for I EL projects using PA designs instead of BSRs. BSR designs are quick to respond to input changes and have a uni- versal building block (the BSR) much as PA designs do. The outputs are always compacted Bursts while the inputs may or may not be compacted. BSR designs are well adapted to designing digital filters. It is possible to vary the weights of the individual bits in the BSR so that the optimum n bit approximation to a given window (e.g. Hamming) is achieved. This can be done more accurately with BSRs than with any other method described in this chapter. An approximation of the hardware complexity using 3 gate equiva- lents per flip-flop and 1 gate equivalent for each current source yields a complexity of about 160 gates for the adder and multiplier and 240 gates for the divider. As with all Burst methods there is no need for synchronization and noise immunity is high. Comparison charts are available in section 6 of this chapter. 4.2 PA Circuits A thorough description of the PA arithmetic circuits will not be repeated here, but rather, unique characteristics and comparisons will be discussed. The comparisons will be made both on the basis of 46 compacted and uncompacted Bursts; i.e., results will be given with and without a compactor running after the PA circuitry. The PA adder is the simplest Burst adder with or without the com- pactor. The circuit is approximately 6 gate equivalents compared to 160 for BSRs. The complexity is about the same as the sampler adder (see 4.3.1), but that circuit has a significant drawback. One problem with PA circuits, especially the multipliers and dividers is the storage of data in the PA tree. For circuits with complete PA, as in the CPU of chapter 3, 1/2 bit per level in the tree can be stored. In the tree with one flip-flop per level slightly less than one bit is stored. This storage can cause a somewhat higher deviation of the output from the expected value than BSR circuits. Computer simulations and experience with the CPU have shown that this deviation is a very complex function of the inputs and the condition of the tree prior to the operation. For applications which may be sensi- tive to such deviations longer averaging at the output completely elimi- nates this phenomenon at the expense of some high frequency response. The complexity of the PA multiplier and divider are lower than any other Burst method (uncompacted Bursts) and for the low cost de- signs with one flip-flop per level, the complexity is the same as weight- ed binary of the same precision (16 bit PA tree compared to 4 bit binary), and is capable of comparable speeds. 4.3 Other Logic Design Approaches to Bursts Logic design approaches to Burst arithmetic other than the PA 48 approach have been made. BURSTCALC has been constructed to demonstrate some of these ideas. The concept design for a low cost Burst CPU (LOCOBURST) was presented by Dr. Poppelbaum in March, 1976. Both of these approaches are now described. 4.3.1 BURSTCALC BURSTCALC (5) contains a Burst adder, subtractor and multiplier/di- vider. The principle of operation of the adder is known as the selector adder. The two input Bursts are alternately sampled to determine the next output pulse. In an effort to eliminate problems of correlations between this sampling scheme and the input Bursts, the sampler changes phase ewery Burst. This scheme solves the problem for constant Bursts, but any scheme which discards data (this discards half) can have errors due to correlations between the discard pattern and the data. The subtractor uses a shift register to obtain the value of one Burst. It then shifts in the opposite direction to perform the sub- traction of the other Burst. Underflow is handled by changing the sign and shifting data back into the register after the sign change. If two such units are used and are one Burst length out of phase no data is lost. The multiplier/divider uses the carousel register scheme shown in Figure 22. Multiplication requires a super Burst to complete the cal- culation. In each Burst of the multiplier a different bit position is 49 checked. If the position so checked contains a one, the multiplicand is added into a reconstruction register. During one super Burst every bit position in the multiplier is checked, so the reconstruction registers will contain the product. This must be reformated to be trans- mitted as a super Burst. It is imperative that the inputs be compacted Bursts and that the amount of deviation of Burst sizes be minimal if correlation problems are again to be ignored. Note that nine out of ten data bits of the multiplier are discarded. This multiplier is also relatively slow to respond to changes in the inputs. An advantage which this multiplier shares with the PA multiplier is that most of the multiplier circuitry can be used in the divider. The divider works on a system of comparing the length of the Burst in the divisor register with the length of the dividend Burst assembled in another register. When the two lengths are equal, the dividend is cleared and a one is added to the reconstruction register. The input Bursts must be compacted and the division should be quite constant. If uncompacted Bursts are satisfactory as output, the reconstruction circuitry can be eliminated. This divider responds quickly to changes of input if used without the reconstructor. Note that a noise pulse can confuse this divider as the leading and trail- ing edges of the Burst control the operation of the divider as they circulate in the registers. 4.3.2 LOCOBURST The ideas and goals of LOCOBURST are very different from the 50 other Burst designs discussed. It is intended to be a Burst CPU rather than just a single adder, etc. The heart of this design is the compactor/repeater shown in Figure 23. Half of this circuit is accepting bits and forming a compacted Burst while the other half is circulating and transmitting its contents. This same Burst will circulate and be transmitted until the other Burst is ready. The time for this to happen can vary from a Burst or two to ten or more depending on the function being performed and the numbers involved. A \/ery distinct advantage that this circuit has compared to the others is that it eliminates the persistant Burst problem of sum of products not equaling product of sums and sum of quotients not equaling quotient of sums. This is accomplished by performing an averaging before performing the arithmetic. The addition scheme is essentially the same as the selector adder of BURSTCALC. The compactor/repeater is involved in the role of com- pacting these results. There are several clocking type signals involv- ed, including the selector signal for the adder and a vernier type signal which is low for 9 clock cycles, then high for two cycles. Figure 24 shows the entire L0C0BURST arithmetic unit. The selector signal is labeled "s" and the vernier signal "e" in this figure. 51 O 00 QC ID CO o o o T3 ea o. S- s- o (J Q. E o o CO C\J 0) S- 3 52 s- o to CO a; o o i- Q. to a: ZD ca o o o a> CVJ 3 l3>tP T *-■ Ul •r- h- 3 = o2 tn QC Ul u. Q. +J U. o u. K CO *~ UJ 3 CD 3 E UJ D ti- ll. z Q CO C =3 < o Z CD K < u JD 0- 0. 1- < UJ fc o or UJ a -J a. _l -J a. _l (0 i- O <4- F 3 3 a 3 3 C O O < 2 2 to 0J "O h p M 4 ^ ^ r^ ^ ^ ^ > P 4 M 4 +-> ^ ^ ^ ^ < ^ fc P 4 4 * 4 LO ^ % ^ CM ^ fc ai S. w M * ^ en % ^ ^ A u_ ^ T 0. 55 in place of the adder. 4.5 Other Arithmetic Processors The comparison of Bursts to such techniques as the Digital Differential Analyzer (DDA) (6) and the Binary Rate Multiplier (BRM)(7) have been attempted, but because of the specialized uses of these circuits a direct comparison is not possible. The principal function of the DDA and BRM is as an integrator. When these devices are used for simple multiplication or addition, hardware is being under-utilized. To attempt to use Burst hardware to perform integration is difficult because the dynamic range of number representation with Bursts is in- sufficient. 4.6 Summary This section consists of a series of tables that compare various features of adders, multipliers and dividers for the various process- ing techniques discussed. 56 CO C o CO •T— i- s- a; XI -o a» -Q > c O o o N 31 0) c CD C7) s- o $- s: CD -a r— t- CO o CD Q. 0) c fi •r— > >> CM > oo o LD o o to CO ^. a: -a <£> ^- c e CD a> #i -C (J t/1 "O ^~ >> >> r— +-> O CO a o 4- to T3 T3 "O Q. C d) CD E CD 4-> >> +J O a. -C i~ O o CD CD (O UD O CO o o <: »o ■o •r- C C\J a> c c ^ Q. CD CD -t- >> E .£> >> 3 CQ +->- — O o c 3 E •!■■ X CD X +J +j a> lO Q. to a> c c to 3 -Q +-> E +J r- a> o *>.•— >> Q. CO O to Q_r— •r— -* (O +J 4-> >> s- a s- E (J c •r^ 3 TCJ 3 3 o > -a (O o en £1 O E 03 CD CQ o •«- cd--^ N f«- r— *r- 3 S- 3 CD —J •r- >, o to E "O to -l-> fd +-> 3 2 •^ s- CD oo h- O (O i— f— ■»-> 3 Q. -o JD A3 s- to s- 2 .c to •i- S- O) »o to C 3 fO O -O -!-> U N O <1J U -M to a. 0) t— i o ^ ■ — J- (O O IE c: o at c •r— E A-> A3 C7> i— s: >> CD a. o O O O nr — C_)> — CO Z 00 o ■z. <_) Z CM CO «3" 57 co e o CO s- fC CL E o o i- cu a. 4-> ST — ■l-J CO o o S 00 LO o o CO o «3- o r^ • E E (1) E A 4-> (— CO >> CO CO 1- •» i- -Q CM <+_ r— >> CM r~ 3 2: < 4-> ' Q_ CO o ^ u #1 CO «3" O O CO O CO 5 LO E E cu E A ■M O >> CM •r— i— J3 00 , — r— o CO O O CO O CO 3 r>» E E cu E #1 <*- >> CM CU CO i- «r- -a c a) i— cu •r- 4-> a. o CO O CO co CO ^— 0) 4-> CO t- co E CD CD Ql r<3 M- +-> r— >> >> >> CO +J C7)i— o a> 3 o aQis: E i_ (U • •r— cu n~ • Q. o LO O O co CO CM CT> •1— CO ^~ E E CU CU a 4J t— >> >> t— ^J- CU OC r— «s- cu CO 3 S- co s: .E +-> •r— 3 -o cu +J 4-> a. cu -E -a u > ■a Q. •!■■ +J -E S- m CO co CO o < cu E •i— CD ro o a> O r— -Q •!- E r— >> >» o o CU 1 t2CQ >> -M — - •r— CO a. E O u E 3 cu >> fO E cu s- cu Q. X -4-> +-> co CU CO a. CU E E co 3 +-> -O +J o i— CU O %^ r— >> Q. CO co t-~ Q-r— •r- -^. ra 4-> ■M i_ >> s- c»- E «3 -M O E •r— 3 =3 3 1 o > -a fO o on E O CQ £ CO a. O '!- cu^ N f>« r— *r m 3 •r— 3 a) _i 1- >> O co C -a -t-> co +-> r— cu cr Q-H- E S- £ cu •i— +-> Z3 il- S- CU CO l— O (O r— r— •p- +j -Q 3 Q. ro J- CO fO O u I Q. +-> CU 2 CU ^«i * -E co •i- S- CU (_> N a cu O 4-> CO Q. CD i— I— < O o S- fO o :r e a CD E *r- E 4-> fO O) r- 2! >> cu Q. O o o o ac^— c_> — • CO z CO O 2: o z 1 CM CO «3- 58 co e o CO "r— s- O 00 CO o o CO o 'St- •r- I— c E cu E at -Q >> ro O CM t— r~ r— O «3- o O CO o CO 3 CvJ e E cu E n CO M- r— >> CM J- ai ■a •r— > •r— 1 Q -M ct CO Q- O O ^T «tf" cn o O co O n s r-^ • c E cu E 00 o CD >> «t • — CNJ +J •r- .a CO CU CO ^-» cu ^— CO en o O CO O CO s- s 00 e E cu E n u «f- >> CO cu -a -o cu cu Q. co C7> s- E CU S- O •>-+-> 0) E +J CO TD o CO o CO cu CO f— fO •r— •r— CO c CU E CU +J +-> Crt > ■ — >> o >> CO O CU «r- CO CC OC Q • CU • s_ 0) ^r CU TD o Lf> o O CO co C\J «*• cu •r— <3- T— E E cu cu A $- or > C\] >> >> r— ^. +-> CO •<- +j CQ Q •r- s -a cu -M a co D_ CU -E +J E -a -a o_ •r— a> cu E 4-> >> LO CO co co o -e s- r— a» cu E z: o u CU •r- C75 (O r— >> >> A3 > -O •■- E Q. cu cu 1 > •f— CO O u E 3 >> E ai Q- X +J +J CO CU co Q. a> e E CO 3 +J -O. +-> O t— CU O ^r— >> Q. CO CO r^ O-i— •i— -Z fD +J +J i~ >> S- M- E «3 4-> O E •r— =3 3 *o 3 1 o > "O <0 O 05 E o CQ E CQ CL C_> -r- > O CO g -o +J CO +-> ^~ a> cr O-h- E S- £ cu •r— +-> 3 M- s- a; co h- o ro r— i— •r- +■> _Q 3 Q. U N (j a> CJ +-> CO a. cu f— 1— t O O %- ta O 31 E O CU E •r— E 4J — s: >> cu O- O o o O zn — O — ' en z: CO C_) z o Z OJ CO «^- 5 CONCLUSIONS The PA has been shown to be a very competitive (in many respects the best) way to perform arithmetic on data in the Burst format. Even with the large amount of redundancy compared to weighted binary the PA circuits compare favorably in both complexity and speed of operation with weighted binary circuits. The major advantages over other logic design approaches to Burst processing are the ability to use the data on line and to respond very quickly to changes in that data. An additional advantage is that the PA designs do not ignore any of the incoming data making the assumption that the ignored data is identical to the last data received. As with all Burst designs other than LOCOBURST, there is the per- sistent problem that the sum of products does not equal the product of sums. If the rate of change of the input is small, this is not a serious problem. The PA designs presented are easy to construct because only readily available parts are needed and the parts count is quite low. Since the entire calculation is done with logic the parts matching and adjustment problems of the BSR are eliminated. PA designs ushered in the concept of the uncompacted Burst, princi- pally because this design was capable of accepting as well as producing data in that format. Uncompacted Bursts have both advantages and dis- advantages. The uncompacted format allows the processor to respond to input changes more quickly and is generally cheaper. The principle dis- 59 60 advantage is the loss of the ability to do some error correction before the data is processed (majority function decoding, etc.). Both sign and magnitude and a biased representation of signal num- bers have been investigated. Generalized arithmetic in either system nearly doubles the complexity of the hardware, however, many applications (those requiring only addition/subtraction or only multiplication/divi- sion) can be handled with little or no increase in hardware complexity. The utility of the PA designs has been verified by the students of the Information Engineering Laboratory (IEL) who have chosen or adopted PA designs for projects which required Burst arithmetic processing. These projects provide excellent evidence that this search for a better approach to Burst arithmetic processing has been successful. REFERENCES 1. Poppelbaum, W. J., Appendix I to "A Practicability Program in Stochastic Processing", proposal for the Office of Naval Re- search, Department of Computer Science, University of Illinois, March 1974. 2. Annual Progress Report, UIUCDCS-APR-76, Department of Computer Science, University of Illinois, April 1976, pp 1-98. 3. Taylor, G. L. , "An Analysis of Burst Encoding Methods and Trans- mission Properties", M.S. Thesis, UIUCDCS-R-75-770, Department of Computer Science, University of Illinois, December 1975. 4. Kohavi, Z. , Switching and Finite Automata Theory , McGraw-Hill, New York, 1970, pp 241-263. 5. Bracha, E., "BURSTCALC ( A BURST CALCulator)" , M.S. Thesis, UIUCDCS-R-75-769, Department of Computer Science, University of Illinois, October 1975. 6. Sizer, T.R.H., The Digital Differential Analyser , Chapman and Hall, London, 1968. 7. Newman, W.M. and R.F. Sproull, Principles of Interactive Computer Graphics , McGraw-Hill, New York, 1973, pp 41-48. 61 62 Appendix A: ICs Used in the CPU Board 1 Position # Type Description 1 7432 Quad 2-input OR 2 7432 Quad 2-input OR 3 7430 8-input NAND 4 5 6 7430 8-input NAND 74121 Monostable Flip-flop 7 74163 4-bit Counter 8 7474 Dual D Flip-flop 9 74164 8-bit Parallel-out SR 10 7430 8-input NAND 11 7432 Quad 2-input OR 12 7432 Quad 2-input OR 13 7446 7-segment Decoder/ Driver 14 7475 4-bit Latch 15 7490 Decade Counter 16 7402 Quad 2-input NOR 17 7404 Hex inverter 18 74163 4-bit Counter 19 7473 Dual J-K Flip-flop 20 7451 Dual 2-wide 2-input AOI 21 7405 Open-collector Hex Inverter 22 7490 Decade Counter 23 7475 4-bit Latch 24 7446 7-segment Decoder/Driver 63 Board 2 Position # Type 1 7486 2 7430 3 74164 4 7430 5 7430 6 7430 7 7400 8 7400 9 7420 10 7430 11 7400 12 7400 13 7400 14 7474 15 74H183 16 7474 17 74H183 18 19 20 74H183 21 7474 22 74H183 23 7474 24 7402 Description Quad 2-input XOR 8- input NAND 8-bit Parallel-out SR 8-input NAND 8-input NAND 8-input NAND Quad 2-input NAND Quad 2-input NAND Dual 4-input NAND 8-input NAND Quad 2-input NAND Quad 2-input NAND Quad 2-input NAND Dual D Flip-flop Dual Full Adder Dual D Flip-flop Dual Full Adder Dual Full Adder Dual D Flip-flop Dual Full Adder Dual D Flip-flop Quad 2-input NOR 64 Appendix B: Edge Connector Pin Assignments Board 1 Pin # 1-8 9-16 17 18 19 20 30 31 32 33 34 35 60 61 64 65-71 72-78 79 80 Pin # 1 2 3 4 78 79 80 Board 2 Description Switches for "A" Burst Switches for "B" Burst Master clock from selector Display format switch DATA from CPU board Clock to CPU A.C. ripple from power supply Clock 1 to selector Clock 2 to selector Clock 3 to selector Clock 4 to selector Clock 5 to selector B Burst to CPU A Burst to CPU Wait Light Seven segment units display Seven segment tens display Ground cc (+5 volts) Description CPU clock in Mode select switch Burst A in Burst B in DATA result out Ground V (+5 volts) cc VITA Leon Clemens Tietz was born February 28, 1948 in New Prague, Minnesota. He graduated from New Prague High School in 1966, and entered Mankato State College, Mankato, Minnesota. In 1970 he graduated Cum Laude with a B.A. in Physics, and in 1972 he entered the University of Illinois to pursue a Ph.D. in Computer Science. While attending the University of Ilinois he was employed by the U.S. Army Construction Engineering Research Laboratory (CERL), Champaign, Illinois as a graduate research assistant. He is currently a permanent employee with the same organization. He has co-authored several published reports while employed by CERL. He is a member of the Association for Computing Machinery and the Institute of Electrical and Electronics Engineers. He is a member of Sigma Zeta and an associate member of Sigma Xi honorary frater- nities. 65 SECURITY CLASSIFICATION OF THIS PACE (Whan Data Entarad) REPORT DOCUMENTATION PAGE READ INSTRUCTIONS BEFORE COMPLETING FORM I REPORT NUMBER UIUCDCS-R-77-895 2. OOVT ACCESSION NO 3. RECIPIENT'S CATALOG NUMBER 4 TITLE (and Submit) BURSTLOGIC: DESIGN AND ANALYSIS OF LOGIC TO PERFORM ARITHMETIC ON DATA IN THE BURST FORMAT B. TYPE OF REPORT ft PERIOD COVERED Ph.D. Thesis, May, 1977 6. PERFORMINO ORO. REPORT NUMBER UIUCDCS-R-77-8895 a. Contract or grant numbers; 7. AUTHORS.) Leon Clemens Tietz N00014-75-C-0982 » PERFORMING ORGANIZATION NAME AND ADDRESS Department of Computer Science University of Illinois at Urbana-Champaign Urhana. Illinois 6T8Q1 10. PROGRAM ELEMENT, PROJECT. TASK AREA * WORK UNIT NUMBERS II. CONTROLLING OFFICE NAME AND ADDRESS Office of Naval Research Code 437 Arl -inotrm Virginia ???1 7 U MONITORING AGENCY NAME ft AODRESSf' different /rem Controlling Otllca) »2. REPORT DATE May 1977 IS- NUMBER OF PACES 65 IS. SECURITY CLASS, (ol thla tiaport) Release Unlimited 1S«. DECLASSIFICATION/ DOWNGRADING SCHEDULE 16. DISTRIBUTION ST ATEMEN T (ol thla F.aport) Distribution Unlimited 17. DISTRIBUTION STATEMENT (ol tha abatrmcl antarad In Block 20, If dltlarant horn Report) '8 SUPPLEMENTARY NOTES 9 KEY WORDS (Contlnum on ravaraa aid* It nact-aaary and Idantlty by block number; Perverted Adder Burst Processing Burst Arithmetic ' ABSTRACT 'Continue on rararaa aid* II nacaaaary and Idantlty by block manbmr) A family of Processors has been developed to perform arithmetic on data in the Burst Format. The common building block of these circuits is a simple finite state machine called the Perverted Adder (PA) which performs BURST addition. The interconnection of PAs in a tree formation with some additional circuitry produces a Burst multiplier or divider. A PA CPU has been constructed to demonstrate these PA designs. D , ;Sn" M 7, 1473 EDITION OF 1 NOV 68 IS OBSOLETE S/N 0102-014-6601 | SECURITY CLASSIFICATION OF THIS PAGE (Whan Dmtm tntmrmd) LIOCRAPHIC DATA :ET 1. Report No. UIUCDCS-R-77-895 2. 3. Recipient's Accession No. "itle and SubMTTe URSTLOGIC: DESIGN AND ANALYSIS OF LOGIC TO PERFORM 5. Report Date May 1977 RITHMETIC ON DATA IN THE BURST FORMAT 6. uthor(s) eon Clemens Tietz 8. Performing Organization Rept. No - UIUCDCS-77-895 Worming Organization Name and Address epartment of Computer Science 10. Project/Task/Work Unit No. Diversity of Illinois at Urbana-Champaign rbana, Illinois 61801 11. Contract /Grant No. N00014-75-C-0982 Sponsoring Organization Name and Address ffice of Naval Research ode 437 13. Type of Report & Period Covered Ph.D. rlington, Virginia 22217 14. Supplementary Notes Abstracts A family of Processors has been developed to perform arithmetic on data in the urst Format. The common building block of these circuits is a simple finite state achine called the Perverted Adder (PA) which performs BURST addition. The inter- onnection of PAs in a tree formation with some additional circuitry produces a urst multiplier or divider. A PA CPU has been constructed to demonstrate these A designs. Key Words and Document Analysis. 17a. Descriptors arverted Adder jrst Processing -irst Arithmetic Identifiers Open-Ended Terms COSATI Field/Group 'variability Statement 19. Security Class (This Report) yNCI.ASSTFIED 21. No. of Pages 65 ^Lease Unlimited 26. Security Class (This Page UNCLASSIFIED 22. Price " NTIS-3S (10-701 USCOMM-DC 40329-P7 1 BLIOGRAPHIC DATA EET 1. Report No. UIUCDCS-R-77-895 Title and Subtitle BURSTLOGIC: DESIGN AND ANALYSIS OF LOGIC TO PERFORM ARITHMETIC ON DATA IN THE BURST FORMAT 3. Recipient's Accession No. 5. Report Date May 1977 \uthor(s) .eon Clemens Tietz 8. Performing Organization Rept. No ' UIUCDCS-77-895 Performing Organization Name and Address Department of Computer Science Jniversity of Illinois at Urbana-Champaign .'rbana, Illinois 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. N00014-75-C-0982 sponsoring Organization Name and Address Office of Naval Research ode 437 Arlington, Virginia 22217 13. Type of Report & Period Covered Ph.D. 14. Supplementary Notes Abstracts A family of Processors has been developed to perform arithmetic on data in the iurst Format. The common building block of these circuits is a simple finite state lachine called the Perverted Adder (PA) which performs BURST addition. The inter- onnection of PAs in a tree formation with some additional circuitry produces a iurst multiplier or divider. A PA CPU has been constructed to demonstrate these 'A designs. Key Words and Document Analysis. 17o. Descriptors erverted Adder urst Processing urst Arithmetic Identifiers/Open-Ended Terms 3 COSATI Field/Group Availability Statement F lease Unlimited £ M NTIS-3S (10-70) 19. Security Class (This Report) TINTI ASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 65 22. Price USCOMM-DC 40329-P71 LIOGRAPHIC DATA ET 1. Report No. UIUCDCS-R-77-895 2. 3. Recipient's Accession No. tie and Subtitle JRSTLOGIC: DESIGN AND ANALYSIS OF LOGIC TO PERFORM 5- Report Date May 1977 UTHMETIC ON DATA IN THE BURST FORMAT 6. uthor(s) jon Clemens Tietz 8- Performing Organization Rept. No- UIUCDCS-77-895 •rlorming Organization Name and Address jpartment of Computer Science 10. Project/Task/Work Unit No. liversity of Illinois at Urbana-Champaign -bana, Illinois 61801 11. Contract /Grant No. N00014-75-C-0982 >ponsoring Organization Name and Address : fice of Naval Research de 437 13. Type of Report & Period Covered Ph.D. ■lington, Virginia 22217 14. • upplementary Notes abstracts A family of Processors has been developed to perform arithmetic on data in the irst Format. The common building block of these circuits is a simple finite state ichine called the Perverted Adder (PA) which performs BURST addition. The inter- nnection of PAs in a tree formation with some additional circuitry produces a irst multiplier or divider. A PA CPU has been constructed to demonstrate these l designs. Cey Words and Document rverted Adder Analysis. 17a. Descriptors rst Processing rst Arithmetic Identifiers/Open-Ended Terms COSATI Field/Group vailability Statement Lease Unlimited 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 65 22. Price < NTIS-35 ( 10-70) USCOMM-DC 40329-P7I IAN 2 5 »/ i. 2W9