L I B RAR.Y OF THE U N IVLR.SITY Of ILLINOIS 510.84 I«6r no. Z50-256 cop. 2. Digitized by the Internet Archive in 2013 http://archive.org/details/analogcomputatio255afus J'ltpfiJ Report No. 255 fll Cl£J>U ^y ' °*~ ANALOG COMPUTATION WITH RANDOM PULSE SEQUENCES by Chushin Afuso February 1, 1968 DEPARTMENT OF COMPUTER SCIENCE • UNIVERSITY OF ILLINOIS • URBANA, ILLINOIS Report No. 255 ANALOG COMPUTATION WITH RANDOM PULSE SEQUENCES* by Chushin Afuso February 1, 1968 Department of Computer Science University of Illinois Urbana, Illinois 6l801 This work was supported in part by Contract No. US AEC AT(ll-l) lk69 and was submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical Engineering, February, 1968, ANALOG COMPUTATION WITH RANDOM PULSE SEQUENCER Chushin &fuso s Ph.D. Department of Electrical Engineering University of Illinois, 1968 A new scheme of analog computation is proposed, in which the continuous variable is represented by a probability of occurrence of a random pulse. In this scheme, basic algebraic operations (addition, subtraction, multiplication and division) are performed with digital elements. Therefore, the realization of such computing elements is simpler than that of the conventional analog computing elements. Because of the inherent randomness in the information carriers, the accuracy is directly related to the speed, and in fact, the accuracy is increased only by sacrificing the speed. Two types of system are possible depending on the nature of the information carriers: Random Pulse Sequence (RPS) system, and Synchronous Random Pulse Sequence (SRPS) system. The latter is a subclass of the former and the information carriers in the latter are obtained from those in the former by shifting the pulses such that they occur only during the time determined by the clock of the system. In the SRPS system, all operations are performed with digital elements, whereas in the RPS system, supplementary use of conventional analog techniques is necessary to perform the four basic operations. Ill ACKNOWLEDGEMENT The author is very grateful to his advisor, Professor W. J, Poppelbaum for suggesting this problem and for much guidance and encouragement. He is also indebted to Professor Louis van Biljon and Mr. John Esch for their suggestions and proofreading. He -would also like to thank Mrs. J. Hudspath, Mrs. G. Osterberg and Mark Goebel for typing the manuscript and producing the drawings. TABLE OF CONTENTS Page 1. INTRODUCTION 1 2. BASIC COMPUTING ELEMENTS FOR THE RANDOM PULSE SEQUENCE (RPS) SYSTEM 2.1 Definitions for a RPS System 4 2.2 Multiplication and Division 9 2.3 Addition and Subtraction 14 3. GENERATION OF A RANDOM PULSE SEQUENCE 19 3.1 Principle 19 3.2 Relation "between the Average Repetition Rate of the RPS and the Discrimination Level 21 3-3 Experimental Results 24 3.4 Analog Voltage-to-RPS Converter - Input Interface .... 28 3.4.1 Direct Method 29 3.4.2 Feedback Method 32 3.4.3 Comparison of the Methods 32 4. STATISTICAL FLUCTUATION IN A RANDOM PULSE SEQUENCE 35 4.1 Pulse Distribution of a RPS 35 4.2 Averaging - Analog Method 38 5. GENERAL COMPUTING ELEMENT FOR THE RANDOM PULSE SEQUENCE SYSTEM 52 6. INTRODUCTION TO THE SYNCHRONOUS RANDOM PULSE SEQUENCE (SRPS) SYSTEM 55 6.1 Definitions for a SRPS System 56 6.2 Generation of a SRPS 57 7. BASIC COMPUTING ELEMENTS FOR THE SYNCHRONOUS RANDOM PULSE SEQUENCE SYSTEM 60 7.1 Multiplication 60 7.2 Addition 62 7.3 Subtraction 70 7.4 Division 77 7.5 Complementary Relation between Addition and Subtraction 84 8. STATISTICAL FLUCTUATION IN A SYNCHRONOUS RANDOM PULSE SEQUENCE 89 8.1 Pulse Distribution of a SRPS 89 8.2 Squaring by Autocorrelation 92 9. EXPERIMENTAL RESULTS - 95 9.1 Mult ipli oat ion and Division in the RPS System 95 9.2 Basic Computing Elements for the SRPS System 96 9.2.1 Multiplication , 96 9.2.2 Addition, Subtraction, and Division 96 9.2.3 Compound Units for Addition and Subtraction .... 103 9.3 Squaring Unit 106 10. CONCLUSIONS 110 REFERENCES 113 APPENDICES l±k A. TOLERANCE SPREAD OF THE CHARACTERISTICS OF NOISE DIODES . . 115 B. DERIVATION OF EQUATION (7.I6) FROM EQUATION (7. 15) . . . . . 118 VITA „ 123 VI ANALOG COMPUTATION WITH RANDOM PULSE SEQUENCES Chushin Afuso, Ph.D. Department of Electrical Engineering University of Illinois, 1968 A new scheme of analog computation is proposed, in which the continuous variable is represented by a probability of occurrence of a random pulse. In this scheme, basic algebraic operations (addition, subtraction, multiplication and division) are performed with digital elements. Therefore, the realization of such computing elements is simpler than that of the conventional analog computing elements. Because of the inherent randomness in the information carriers, the accuracy is directly related to the speed, and in fact, the accuracy is increased only by sacrificing the speed. Two types of system are possible depending on the nature of the information carriers: Random Pulse Sequence (RPS) system, and Synchronous Random Pulse Sequence (SRPS) system. The latter is a subclass of the former and the information carriers in the latter are obtained from those in the former by shifting the pulses such that they occur only during the time determined by the clock of the system. In the SRPS system, all operations are performed with digital elements, whereas in the RPS system, supplementary use of conventional analog techniques is necessary to perform the four basic operations. Vll This thesis is a feasibility study of such analog computing systems. In particular, a practical way of generating the RPS and the SRPS for a given analog voltage as well as the realization of the basic computing elements are considered. A unity scale factor, being attractive since the need for scaling is eliminated, is discussed. To accomplish the unity scale factor, a temporary storage is needed in each computing element except for the multiplier. A storage of 3 binary stages was found to be adequate for the practical use. The theoretical conclusions were all confirmed by experimental results. 1 . INTRODUCTION Analog multiplication using uncorrelated periodical signals gives rise to reasonably simple circuit realizations and has been known for a long time (3) , (8) . This thesis started out as a feasibility study in the use of random pulse sequences for multiplication and led rapidly to the realization that not only multiplication but all fundamental operations of arithmetic can be considerably simplified by its use. It is the purpose of this thesis to extend the use of Random Pulse Sequences, i.e., sequences of standardized pulses with controlled average repetition rates as analog information carriers to these other mathematical operations, i.e., division, addition, and subtraction ■with digital logic elements. Then, one has an analog computing system in which RPS ' s are information carriers and analog operations are carried out with digital logic elements. Such a computing system is now called a Stochastic Computing System. An attractive feature of such a system is its potential adaptability to large scale integration. This simplicity of the system, however, is gained only by' sacrificing efficiency: In the stochastic computing system, the analog variable value is represented by the average duty-cycle or by the average repetition rate of the information carriers. A long averaging time is thus needed to extract accurate analog information. According to probability theory, the statistical fluctuation is proportional to the reciprocal of the square root of the average number of pulses during the averaging time. For example, to get Vjo accuracy (with respect to the machine variable value) the averaging time must be such that on the average 10,000 pulses are counted •which corresponds to, e,g,, 10MHz average repetition rate and 1 ms averaging time, If 10% accuracy is sufficient, the averaging time can be reduced to one hundredth of 1 ms, i.e., 10 fis . From its low cost and the relation between accuracy and speed, the application area of such a stochastic computing system will be an area where a large number of analog computations are required in parallel with a moderate accuracy. This thesis is a feasibility study of a stochastic computing system. In particular, a practical way of generating RPS's as well as the basic computing elements (multiplier, divider, adder, and subtracter) with unity scale factors, are discussed. One of the applications of the computing elements with unity scale factor will be an array computer (9) using general computing elements which perform any one of the above basic operations depending on a "function signal" from the outside world. Although the unity scale factor may not be necessary, it eliminates the need for scaling, thereby facilitating the use of general computing elements in an array computer which employs a large number of general computing elements , Two types of the system are possible depending on the nature of the information carriers: (l) Random Pulse Sequence (RPS) as mentioned above, or (2) Synchronous Random Pulse Sequence (SRPS) . In a SRPS the instant of occurrence of each pulse is timed by a clock, i.e., if a pulse occurs, it occurs during a clock pulse. Therefore the SRPS is a subclass of the RPS and the computing elements developed for the latter are also applicable to the former. The SRPS system has the advantage over the RPS system in that the form of the pulse sequence is conserved for digital logic operations. This means that repeated operations are possible without renormalizing the pulse sequences. 2. BASIC COMPUTING ELEMENTS FOR THE RANDOM PULSE SEQUENCE (RPS) SYSTEM 2,1 Definitions fcr a RPS System A Random Pulse Sequence (RPS) is defined as follows: It is a sequence of standard pulses each of which has the same height V and the same width T such that the pulse repetition rate changes at random about the average value f . This is shown in Figure 1. If v(t) is a voltage, which is usually the case, the average voltage V averaged over T is defined by ^T „ 1 V = ^ v(t)dt , < V < V Q . (2.1) As the parameter to characterize a RPS, the normalized average voltage or average duty cycle, defined by x=£-=~m [ V-(t)dt ; 0° O y(-M V(t) 1 if a pulse is present / - V n if a pulse is not present ^ ' then x = - X(t)dt ; < x < 1 (2.4) Now, in terms of probability, the average voltage can be expressed by V = V Q P (X(t) = 1} where P t X(t) - 1} = probability that X(t) = 1 or £• - P{X(t) = 1} (2.5) Hence the duty-cycle defined by (2.2) is exactly the same as the probability that X(t) attains "1", x = P{X(t) = 1} (2.6) By noting V = V Q Tf (2.7) x = Tf , for a constant t (2.8) it seems also possible to characterize a RPS in terms of the average repetion rate, f, if the pulse width is constant. In a RPS system, however, the pulse width is not constant after being passed through digital logic elements. This can be seen in Section 2.2. In order for a RPS to be an analog information carrier, the incoming analog variable which is usually in the form of voltage, must be mapped onto the corresponding RPS. For a given analog voltage E, in the range < |e| < V-, assign a RPS whose average duty-cycle x is given "by x=M ( 2 . 9 ) v o The sign has to be conveyed by other means „ For example, a separate wire may be employed to convey the sign. Another way is to use sequences of negative going pulses for negative analog quantities. The latter is actually employed in subtraction discussed in Section 2.3. In the following the principles for realization of four basic algebraic operations will be discussed. Only the case of unity scale factor is considered. Let E, and E p be analog input voltages, and x and x p be the average duty-cycles of the corresponding RPS's, i,e, 5 E, x. = i v o 1, 2 (2.10) 2.2 Multiplication and Division When two RPS's with duty-cycles x and x o are fed into an AND gate as shown in Figure 2, the average duty-cycle of the output of the AND gate is given by 1 r T ?J Q X 3 (t)dt i 3 tx 3 (t) 1} p (x 1 (t) - 1 and X (t) = 1} io X r-t (VI X X Figure 2, Multiplication with an AND Gate, 10 Assuming that the two RPS's are mutually independent (uncorrelated) x 3 = P{X ] _(t) = l}-P(X 2 (t) = 1} = x 1 -x 2 (2.11) Thus an AND gate provides the product of the two inputs in terms of the average duty-cycle. Note that the output sequence of the AND gate is no longer a sequence of standardized pulses, hut the pulse width varies between and t as shown in Figure 3« It is obvious that this principle holds true for any number of inputs provided that all inputs are uncorrelated. In practice, it is the average voltage, V, that is to be measured to read the result of the operation. Therefore the conversion factor between the average duty-cycle (machine variable) and the average voltage is a factor which determines the accuracy. Namely, from (2.5) and (2.6), the accuracy of the pulse height, V , directly determines the accuracy of a RPS system. For the multiplier, another possible source of error would be a finite switching time of the AND gate. If the rise and fall times of the AND gate are not equal, this would produce a positive or negative error at the output of the multiplier depending on which one is longer. 11 CM X ro X ^ O rH O t •-_ t i t s g o .o o u a 1 •H H ft •H -P (1) ■P o CO > 12 If the overlapping duration of the two input pulses is so short that the AND gate is not able to react, this would produce an additional negative error. The error due to a finite switching time of the AND gate would be more remarkable as the pulse width of The original RPS's becomes narrower. This sets the lower limit of the pulse width of the RPS. This comment applies to other switching circuits as well. On the other hand, the upper limit of the pulse width is determined by the dynamic accuracy (this is due to the statistical fluctuation of the measured average value) for a given machine variable. By (2,8), x = fi , and for a given value of x, as T increases, f must decrease accordingly. As it will be discussed in Section U.2, the statistical fluctuation of the measured average is proportional to l//fT, where T is the averaging time. Hence this sets the lower limit of f, thereby the upper limit of T for given values of x and T. Division can be accomplished by using a multiplier together with feedback as shown in Figure U, The divisor sequence X and the output of the quotient sequence generator X~ are applied to an AND gate to form the product x^.x . The average voltage of the dividend sequence X, and that of the AND'ed sequence of X ? and X are compared by a differential amplifier. The output of the differential amplifier controls the average repetition rate of the quotient generator such that 13 .3- 0) b0 •H 11+ Xp x^, - x^ Kence x x Q = -i (2.12) 3 x 2 Here, the output is available in the form of RPS from the local RPS generator. The accuracy, naturally, is dependent on the sensitivity of the differential amplifier and the statistical fluctuation at the averaging units as well as the accuracy of the multiplier. 2,3 Addition and Subtraction A first order approximation of addition is accomplished with an OR gate as shown in Figure 5. The probability that the output has logical "1" is given by P [X.(t) - 1} - P (X 1 (t) ■- 1 or/and X g (t) = 1} = P (x 1 (t) = 1} + p [x 2 (t) = 1} - P [X,(t) = 1 and X Q (t) - 1} IS X X I c\j X + II ro X CD ■8 g -p § •H -P O 8 ■s a (U ■P 03 •H LTN (0 X X bO 16 Hence x. = x 1 + x g - x 1 «x 2 (2.13) Only when the occurence of X (t) =1 and that of X (t) =1 are mutually 1 2 exclusive, x gives the sum x + x . Although the synchronous random pulse sequence system enables us to compensate the term "x-,Xp" in a digital fashion as discussed in Section 7«2, only analog methods are available for the RPS system as shewn in Figure 6. A summing operation takes place at the RC averaging circuit. The analog voltage of the sum is then converted into the corresponding RPS for successive operations. Subtraction is accomplished by inverting the subtrahend sequence (negative going pulse sequence from ground) . Although only the conventional analog technique is used in addition and subtraction, it is important to have a complete set of basic computing elements so that realization of a computing system is possible. ote that the output of the multiplier is acceptable to inputs of the other three basic computing elements as -well as another multiplier, even though the pulse sequence is no longer a RPS strictly. However j repeated use of such a deteriorated carrier is not desirable if the influence of the pulse width on accuracy discussed in the previous section is considered. This problem is naturally solved by supplementing the AKD gate with an averaging unit and a local RPS generator. When the four basic computing elements are accommodated 17 ? CM oc X o +1 Li- r-l ^ X 1— ^ en II ^ ro a. IO o X ce X LJ s CD Q X K)li- X O CM K ^VWr O .9 OJ X o CM I CM 2.J u. -P o £ 2 o o o CO rEi cc -P LJ > r" 2 . -i O ~"" •H ■P O C) o f 1 -J < •p ■9 z CO < <-• II ^ CM <-> 5rl o I •H +5 3 -d Pi __ _ a H _l q-i (T => o _l UJ S 00 o |- CO en 5 h- _l K Li_ O UJ o Z X > ffl O CO CO LU o 1 to < 1 UJ _l < > Q_ X 2 o o X II > 5 Z II 5 cc h- o CO Ll) o b X CO U. 1 LU Q n Q. z •o X o > 21 Typical noise pulses which are obtained by filtering the noise voltage of a semiconductor diode through an RC high pass filter are shown in Figure 8(a) . Amplitudes and spacing change at random in time. Now those pulses whose amplitudes are higher than the discrim- ination level, V ( > 0) , are selected by the amplitude discriminator, and a new sequence of noise pulses is obtained. This is shown in Figure 8(b) . This sequence of pulses with various amplitudes and widths is now shaped with a one -shot multivibrator so that each pulse has the standard size as shown in Figure 8(c) , the amplitude and width being V and T, respectively. 3.2 Relation between the Average Repetition Rate of the RPS and the Discrimination Level The average repetition rate of a RPS is determined by the occurrence of the noise pulses whose amplitudes are higher than the discrimination level, V „. As V is lowered, the number of noise d d pulses selected increases, and therefore the average repetition rate, f, of the generated RPS increases. It is reasonable to assume the amplitude distribution of noise pulses (Figure 8(a)) to be the normal distribution as depicted in Figure 9» By setting the discrimination level at amplitude V , all pulses whose amplitudes are higher than V, are converted to the standardized pulses, (Note, however, that only one standard pulse will be generated for all noise pulses \vhich occur within t) . The v nl (t) v n2 (t) ?.2 i v, I I I (a) NOISE PULSES i I I i i i I I i t (b) NOISE PULSES OBTAINED BY AMPLITUDE DISCRIMINATION OF (a) T (c) A RPS OBTAINED BY STANDARDIZING PULSES OF (b) Figure 8. Process of Generation of RPS Whose Average Repetition Rate Is Controlled by the Amplitude Discrimination Level. 23 f(V d =0) AMPLITUDE OF NOISE PULSE, V n (£(V n )dV n = PROBABILITY THAT THE PULSE AMPLITUDE IS BETWEEN V n AND V n -hdV n ire 9- Assumed Probability Density Function, $(V ), for the Random .Amplitude of Noise Pulses. 2k average repetition rate, f, of such a RPS for a discrimination level, V , is proportional to the integral of (V ^ from V^ to the maximum of V i.e. , n f(V ) = A f **** $(v n )dv ri ■where A is a proportionality factor. Since f (V d = 0) - A f V nmax rr n C and • V rjnax $(V )dV = P(0 < V < V } = I x n' n — n — nmax J .V .'max f(v d ) = f (v d = o) f $(v n )dv n (3a) d Then, for the relation between V, and f, we have an inverted S- shaped curve as shown in Figure 10, 3.3 Experimental Results A silicon noise diode was used as the original noise source. The noise voltage from the .loise diode is a negative saw-tooth wave. This was put through RC high pass filters and amplifiers to produce noise pulses with amplitude large enough to be easily discriminated. For the amplitude discriminator, a differential switching amplifier was used. 25 f(V d = 0) Figure 10- Average Repetition Kate of the KPS as a Function of the Discrimination Level for the Assumed Probability Density Function, c£>(v ). n 26 To measure the average repetition rate of the generated RPS, a D'Arsonval type voltmeter was employed. It can be seen that the average voltage of the RPS is proportional to its average repetition rate, since each pulse is standardized, i.e., v = v rt where V = average voltage of the RPS which can "be read on a D'Arsonval type voltmeter, thus f = -^- (3.2) V By measurements on an oscilloscope 1 = 0,62 ps and V = 16.0 v and f ■ 0.6Z16.0 " l - 01 v **■ (3 - 3 ' The numerical value was checked by triggering the one-shot multivibrator with 250Kiiz periodic pulses. Figure 11 shows the V -V characteristic. The corresponding repetition rate scale is also indicated by using (3-3) . The magnitude of the slope of this curve gives the amplitude probability density function, $ (V n ) , For V { j>10 volt, the slope is practically zero, indicating that there are hardly any pulses higher than 10 volt. 27 * 30N3n03S 3S~ind lAIOQNVd JO 3_LVd N0llll3d3d 39Vd3AV N X 0) t> 0) i-q fl o •H -p cti G "A •H A U T O W 1 •H n TJ > CD P _J <4H LU O > a Ixl o •H -P O g 2 h O 03 f- w < CTJ 2 CO — PL, ^ « cc o o (/) CD bO Q cd P H o > CD bO 03 U CD !> < H H 0) •H fc ^ CD 2 S CO LU < _,> < o — ' >' o •H -P to •H M <1) -P 3 ^ & O -d . 0) H £-1 0) •H > W a> (D ^ O a x- 1 "V o rO •H v ' -p c<$ • #\ G d) •H ■p 6 ctf •H « !h O PI W O •H •H Q -P •H © -P w ft r w bO £ O H H aJ !> 5 C) i-5 -p ^ d Ph o fl •H M -P a aj S ^ •H -p 6 •H U fH O o CH M •H P Ld 31 CO LU CO _l Z> CL LU CO o 2 o M ■p o cu (4 •H Q >> ?H CU -P o Ph i o ■p I 0) bo a -p H O > bO O H PO H bO 32 spreads of the noise diode characteristics and of the non-linear elements producing |E| - V characteristics seem to be the factors ■which determine the accuracy. 3.U.2 Feedback Method In this method the output of a comparator, which compares the average voltage of an RPS and an analog input voltage, controls the discrimination level in such a way as to equalize the two com- pared voltages, A circuit for this method is shown in Fig. lU. The comparator, in this case, consists of a single differential amplifier, The output voltage of the differential amplifier determines the emitter-base voltage of T thereby controlling the collector current. The voltage across the collector load is used as the discrimination level. In practice, the sensitivity of the comparator and the fluctuation at the averaging unit are the determining factors for the accuracy. The time constant of the averaging circuit preceding the comparator sets the upper limit of the rate of change of the input variable . 3.^-3 Comparison of the Methods In order to compare the relative merits of the two methods, consider the following numerical example. For the direct method, from the measured V, -V characteristics of three noise diodes (see d 33 <* — vw <* — vw o £\ -P O £ (L) ,Q Im -P fH 0) f> O O CO « l o -p I 0) hO -P H o > bfl O H 03 H bO •H 3h Appendix A), at V = 8„5v the fractional spread is found to be Af AV _ 0.50 , hof /_ ,v This rather poor accuracy comes from the noise diode itself. To this must te added the further error due to non-linear elements in the IE! - V transformer shown in Figure 12(b). On the other hand, for the d feedback method, a sensitivity of 50 mv may be easily obtained for the differential amplifier shown in Figure 14. Therefore, £g. 2*22 -i.i* (3.7) V 3-50 The average repetition rate corresponding to V = 3.50v is f = 350 kHz (for Vo = lOv and t = -T^fts). For 1 ms time constant of the averaging unite, the fluctuation is about 5 overall accuracy is obtained. In this case the statistical fluctuation at the averaging unit dominates the overall error. This, however, can be reduced to any desired extent by choosing fx (averaging time) large enough. With regard to realization, designing a non-linear |e| - Vd transformer seems complicated, whereas realization of circuits for the feedback method is simple as seen in Figure 14. From the above consideration, it is clear that the feedback method is more attractive than the direct method. 35 k. STATISTICAL FLUCTUATION IN A RANDOM PULSE SEQUENCE In a RPS system information is conveyed by the average duty- cycle which is proportional to the average repetition rate. In practice, however, only measured average values are available. Therefore there will be inherent errors in the system due to the statistical fluctuation of the measured average values, and these limit the dynamic accuracy of the system. According to the law of large numbers of probability theory, (k) the measured average converges to the average of a distribution as the averaging time tends to infinity. This means that if one waits longer one will obtain more accurate average values in the sense that their fluctuation becomes smaller. U.l Pulse Distribution of a RPS The statistical fluctuation for a given averaging time can be estimated if the pulse distribution is known. For a RPS the pulse distribution is approximately described by a Poisson distribution function. It is well known that the number of randomly occuring pulses with infinitesimal pulse width in a given time interval, T, is described by a Poisson distribution function, (11 ) 36 P(N;T) = ^ e" fT (4.1) where P(N;T) = probability of finding N pulses in T, f = average number of pulses per unit time. In the above mathematical model, because of the infinitesimal pulse width, there is no upper limit on the number of pulses that can occur in T. In practice this is not true, since the pulse width is a finite t. Approximation of a RPS by such a mathematical model is good, however, This can be shown as follows: The maximum number of pulses that can occur in T is given by N =^ (4.2) max T Supposing that t=1a.s and T = 1ms, which are reasonable values in practice, then Nmax = 1CP, Now the standard deviation for a Poisson distribution is given by a =/fT n {k.3) For f = 900 kHz (which gives a sufficiently large value of the average duty-cycle, x = f t = 0,9), a = J9OO = 30. The distribution outside (the average + 2 a ) can be neglected by considering the normal distribution which is a good approximation of a Poisson with average larger than 10, (5) For our numerical example, the average = f T = 900 and a = 30, therefore f T + 2 a = 900 .+ 60 <10 . Therefore 37 f STANDARD DEVIATION (T 840 900 960 fT Figure 15. Normal Density Function, (j)(^) 38 practically N max = 10 3 does not affect the Poisson distribution. For smaller values of x = ft the situation becomes more favorable and approximation by a Poisson distribution function is better. The relative value of the statistical fluctuation with respect to the average value is defined by One standard deviation A = Average value (^.*+) For a Poisson distribution A= /S ,_L_ (4.5) If the fluctuation is considered as the dynamic error of the machine variable value, this may be expressed with respect to the full range of the machine variable value -which is unity. The relative fluctuation expressed in this way is obtained by setting x = fT = 1 in the expression of the average value fT. Hence we have, 17" /t t (u - 6) T 4,2 Averaging Analog Method In the RPS system, the machine variable is the average duty-cycle of the RPS which is obtained from the average voltage by normalizing with respect to the pulse height, V . To detect the 39 average voltage an analog method of averaging, i.e., filtering with a conventional low pass filter, is convenient. Since it seems impractical to analyze the case of the sequence of non- standardized pulses (output sequence of the multiplier) , we treat only the case of the sequence of standardized pulses (original RPS) . The latter case, however, reveals sufficient information for practical purposes as seen by the following consideration. The pulse width of the output sequence of the multiplier changes from o to t » whereas that of the original RPS is constant r . Therefore, for the same value of x = P (X(t) = 1), the average repetition rate of the former is higher than that of the latter. To see this more closely, consider a RPS with the pulse width of t/2 and the average repetition rate of 2f which gives the same value of x as the original RPS with repetition rate of f . This sequence ia obtained from the pulse sequence in question (i.e., output sequence of the multiplier) by averaging the randomly varying pulse width, while the reasonable assumption is made that the probability distribution of the pulse width is uniform between and r. Now, for a Poisson distribution, the relative value of the statistical fluctuation with respect to the average value is given 1 A = 7T 0-5> Uo ■where f is the average repetition rate of a RPS and T is the averaging time. For the RPS which is an approximation of the output sequence of the multiplier, f is replaced by 2f, and the fluctuation is reduced to 70$> of (U.5). This means that the fluctuation of the output sequence of the multiplier does not exceed that of the original RPS with the same machine variable value. In the following a simple RC low pass filter acted on by a RPS is discussed as an example of the analog averaging method. The relation between the averaging time and the statistical fluct- uation is derived. In order to estimate the effect of an RC averaging circuit we proceed as follows. A RPS may be regarded as a frequency modulated pulse sequence in which the repetition rate varies in time at random about the average value. The distribution of repetition rate is given by a Poisson distribution. For a sufficiently large number of pulses during the averaging time, the probability' density is given by the normal density function as shown in Figure 16. f« aad f are the practical minimum and maximum repetition rates in the sense that about 70$> of the whole distribution lies in the range (f n, f ) . The lower limit of the voltage fluctuation at the output of the averaging circuit is related to f and the upper limit to f . Therefore the Xj U voltage fluctuation due to the fluctuation of the pulse repetition 1+1 >■ flT fT fuT 68.3% OF WHOLE AREA fT= AVERAGE NUMBER OF PULSES Af-T = STANDARD DEVIATION fl =f-Af. f u = f+Af NUMBER OF PULSES IN T Figure 16. Probability Density of the Number of Pulses in T for the RPS. k2 rate may be calculated from the difference bet-ween the output voltage for a periodic pulse sequence with f and that for a periodic pulse sequence with f . . To make the analysis simple, consider a parallel combin- ation of R and C connected to a RPS current generator as shown in Figure 17 . i(t) =^c v ui i(t) = RPS CURRENT GENERATOR Figure 17 > Simplest RC Averaging Circuit for a Current Source h3 A current source is a good approximation for the case where the out- put is taken from the collector of a non- saturated transistor. For a voltage source a large resistor is to be connected in series with the source and the overall characteristic ■will tend to that of a current source. The equivalent circuit therefore is suitable for most practical cases. First we calculate the ripple for a periodic pulse sequence when applied to the circuit of Figure 17. Assuming that i(t) has the waveform as shown in Figure 18(a), then the output voltage v (t) has the waveform as shown in Figure 18(b), where exponential terms are approximated linearly by assuming t, l/f « CR. The ripple voltage, 6V, can be shown to be 5V = V _ v = (l -/ f ' T ) T V (k 7) max min CR ,2 v ' J f where V Q = I Q R. The practical upper limit of the voltage fluctuation is obtained when a periodic pulse sequence with repetition rate f is applied as the input, and the lower limit is obtained by a periodic pulse sequence with f,. This is shown in Figure 19- Hence we have Fluctuation voltage: AV = V - V„ . (k.S) umax iirmn ' Let V v = average voltage of a periodic pulse sequence with f , kh WAVEFORM OF i(t) 2 S or .*. O 3 ^ o ^ o 3 3 -p -p pi o > t- / t- q •H O k W \ o i l J CD > £H/h 00 H CD > 00 +3 to 0) O d gl W 00 K o E > HSh c I > K > O > 3 > E "> o •H Ti O •H 0) O -P o > Chi O O 5 ON H 3 •H then VTf + J: ^/ fu - T ) T y u 2 CR 2 f ' u 46 V = V + ^ &V (if. 9) umax uav 2 u v "" = Vi|f + i 1 / fu " T ] (^ 10) L u 2 CR 2 J 14. ±u; + T U Similarly V Therefore = VT ff - - 1//f/g ' T l (4 11) £min L j?, 2 CP 2 J ^-»-U - V ■ V **„ - *1 * i (^^ + ^-g.' J , (U.l 2 ) 7~ + T To + T X U I £ For a Poisson distribution, the average number of pulses in T is fT, and the standard deviation of the number of pulses in T its 7fT. Hence, Practical maximum number of pulses in T : f T = fT + /fT = fT(l + -i— ) JfT hi or Practical maximum repetition rate: f = f (1 + — r) u f ■ f(l + -7=. ) (^.13) s/fT Similarly Practical minimum repetition rate: f n = f (l + — r) = f (1 +-7=.) (^• ll +) /fT Since actual counting of pulses does not take place, it is not possible to define a definite value for T. However, for the purpose of estimating the fluctuation, it would seem reasonable to take the value of CR as T, i.e., we set T = CR (U.15) Substitution of (U.13), (h.lk) and (U.15) into (U.12) yields » ° R1 Tf^ CR rtj C8 U8 T 11 Since — « 1 < — — , — — , this equation is simplified tc w t\ TI TI n U I ^■= 2 V f [ 7^ + ?CRf l2-T(f u+ f 4 ))j ■ «V ^= + ^ ] (U ' a6) If the relative fluctuation, A , is defined by A = ii/§^ (4.i 7 ) where V - average voltage of the RPS = V if. Substitution of (U.l6) into (U.17) yields, on tne assumptions: T, ^- ^< CP (1+.19) In (U,l8) , the first term is due to the fluctuation of the repetition rate, and the second term is due to the ripple which was calculated for a single periodic pulse sequence. As CR increases, the second term decreases more rapidly than the first term. Actually for all practical purposes, the second term may be neglected as shown in the following. For example, lt 9 = 0.10 - 10$ v/CRf °'<^< - CJ o ro vP o OJ 1^ o -p CO a o o i Q) S •H EH d) O a o ■H -P O Cti W o •rl -P o H Cm 0) > •H -P cti H 0) « O OJ •H P>H V NOIlVniDDld 3AI1V13U 51 were chosen. The assumptions (U.19) were confirmed to be valid within the plotted range. As the average repetition rate increases, the fluctuation decreases. However, the highest frequency is bound by 1/t . To estimate the lower boundary of the fluctuation for a given t , we set f max = -i/ T . Then the second term of (U . 18) vanishes, and rain *U„ ■ Jh (^21) This lower boundary is also shown in Figure 20. 52 5, GENERAL COMPUTING ELEMENT FOR THE RANDOM FULSE SEQUENCE SYSTEM A general Computing Element is a computing element which performs any one of the basic algebraic operations (multiplication, division, addition and jultraction) depending on a "function signal" from the outsiae. Such a computing element is considered to facilitate feasibility of large scale parallel processors. Furthermore the element is particularly suited for fabrication by integrated circuits, since it neecs only few connections from the outside and many circuits inside. rhe circuits of the general computing element for the FPS is shown in Fig-are 21. The output is always provided by a local RPS generator in the form of RPS. G^, Gp : . , . ,jj are diode gates whose input impedances are practically infinite when they are CFF. For multiplication, only G, , Co and G^ are ON (gate control voltage = v) and the rest of the gates are OFF (gate control voltage = V Q if the pulse heignt of the RPS is V ) . x^ and Xn are ANDed with D. and D , and the average voltage of the inversion of the product is compared with the average voltage of the inversion of the local RPS generator. The RPS generator is controlled by the comparator output 53 I IT ^-r^h iHr^- RPS OUT x 3 ; x 3 =f(«„x 2 ) NO: NOISE DIOOE PM i m Figure 21. General Computing Element for the RPS System. 54 such that the inputs to the comparator have the same average value. For division, x-^/x^ (assuming x^ < x 2 ) only G 2 , Go and Gy are ON. X 2 X ^ ^ s formed with D 2 and Do, and the inverse average voltage of x 2 Xo is compared with that of x-j_ and the RPS generator is adjusted so that x 2 Xo = x-j_„ The output, Xo, thus gives X]_/x p . For addition, only G-j_, G^ and G/- are ON. Since Go and Gy are OFF, the AND gate formed with D-j_, D 2 and Do gives x-, itself. At the collector circuit of T^ and T„ the analog sum is formed and the RPS generator is adjusted so that Xo = x, + x 2 . For subtraction, x-^ - x_, assuming x-^ >x 2 , only G-. , Gk and G- are ON, The situation is the same as that of addition except that x 2 is fed through Tc and Tg. Analog inversion takes place at T^ and hence x^. = x-^ - x 2 . Since the RPS generator employs 6 transistors and one diode, the wl ole unit employs 13 transistors and 36 diodes. In order for the element to be able to handle negative inputs and output, additional sign carrying wires and sign detector circuits are needed. 55 6. INTRODUCTION TO THE SYNCHRONOUS RANDOM PULSE SEQUENCE (SRPS) SYSTEM In a RPS system the average duty-cycle is the machine variable. In practice the average voltage, V, is obtained and then this is normalized with respect to the pulse height, V , to get the average duty-cycle. Hence the accuracy of the pulse height directly affects the accuracy of computations. Since averaging takes place for each basic computing operation (not necessarily for multipli- cation) , circuits in each computing element must be carefully designed. This will ensure an accurate value for V and thus also & o for the average duty-cycle. This requirement of analog precision is undesirable, especially for integrated circuits. To eliminate this difficulty, we introduce Synchronous Random Palse Sequences (SRPS) , in which standardized pulses occur in fixed time slots determined by a clock of the system with a probability of occurrence equal to the machine variable value. The main advantage of Guch a system is that logical AND or OR operations on SRPS's lead to another SRPS without any further renormalization, and averaging is not necessary at each algebraic operation. This means subsequent operations can be applied directly, and all the operations can be done by digital elements. Also the average repetition rate may be a convenient parameter characterizing SRPS's, 56 and actually the average repetition rate normalized with respect to the clock frequency of the system is chosen as the machine variable, 6.1 Definitions for a SRPS System A Synchronous Random Pulse Sequence (SRPS) is a sequence of standardized pulses, each of which has the same height and the same width such that the pulse repetition rate changes at random about the average value f and the instant of occurrence of each pulse is controlled by a central clock for the whole system . Only the last criterion differentiates this system from the RPS system. It is clear that the SRPS is a subclass of the RPS. Vr ft (t)f Of- I I CLOCK PERIOD Figure 22. A Synchronous Random Pulse Sequence 57 The probability of occurrence of a pulse in a time slot represents the machine variable. If f Q is the clock "requency and f the average repetition rate of a SRPS, the machine variable is given by u = P (v(t) has a pulse in a time slot} f- (6.D Since x = f t from (2.8), u is related to x by u = t±=) x (6.2) For an analog input voltage E, u is given by, using (6.2) and (2.9) 1 Ie| u = V v o (6.3) Again the sign has to be conveyed by another means. 6.2. Generation of a SRPS The schematic diagram of a SRPS generator is shown in Figure 23. The set and re sat signals and the output are shown in Figure 2h. The reset signals, R, and R , are obtained from the clock of the system. The input interface problem is again solved by feedback, and the circuit shown in Figure ik is acceptable if the one-shot multi- vibrator is replaced by a pair of flip-flops shown ir. Figure 23. 58 co o_ cr CO z> Q_ \- Z> O o w CM o — O ♦ " esiT CO [ OJ CM 3 > 3 II o + CM + II 3 3 30 O O CM 13 CM o 3 CM u. tx QUU u. tx — Ld O 2 i, 5 O Li. •H CM Q Q A A O «H .J _J _l (X _l < Ld r- < H- 2 »- O 3 o Ld O Ld f- O h- Ld Ld Q Q «H CM O Q •z. Q_ £ 3 O Q CM Q CM 3 «H 3 CM 3 + H m o •H -P •H OJ CD u •H 61+ and ends at the preceding cycle of the (k + l) th coincidence. This is sho-wn in Figure 27. In order for the kth order compensation to be effective, it is necessary (hut not sufficient!) that the 1st blank occurs before the (k + l) th coincidence in each range element of the ORed sequence. In reality, the counter of capacity of k pulses is not always able to accept k pulses in every range element, since there are pulses in the counter which have been carried over from the preceding range element. This storage action considerably complicates a detailed analysis. Since the primary interest here is to estimate the accuracy, one may proceed with the assumption that the counter is always able to accept k pulses and obtain a rough estimate for design purposes. P {The kth order compensation is effective for a given range element of (n + l) cycles! = P {The (k + l) th coincidence occurs at the (n + l) th cycle after the 1st coincidence and at least one blank occurs before the (n + I) th cycle for the ORed sequence] = P {The (k + l) th coincidence occurs at the (n + l)th cycle after the 1st coincidence } . P {At least one blank occurs before the (n + l)th cycle after the 1st coincidence assuming that the (k + l) th coincidence occurs at the (n + l) th cycled (7.3) 65 LU X ~ ~ o S^ co m W Z uj ^ uj o ^ a. rr ^ "^ o Z o o < a: UJ > iua tru. < u. UJ UJ cr UJ X h- o o cr UJ O cr o o UJ 2 u Ul Z Q UJ z 3 a UJ o CO o UJ o z UJ Q 05 UJ o z UJ Q O o o CM Z> Ul o z Ul 3 o UJ CO

CO £3 r— i ^8^ ^9 O + is— ' — i ' — .-*£ e± c I z O I < Ul o ' + -J cr ui o ui < ui Q 1 w UJ o CO Ul _l O > -p O CQ •H ra >> H a5 o CD H ft •H O PI •H fH ft 0) ■P P{ •H O co ra CD O Pi k - l- 2. Now it can "be shown that 00 2 (r+k-l)(r+k-2). . . (r+l) a r = fo" 1 ? : , k > 2, |a|<| r=0 (1-a)' Hence, P {The kth order compensation is effective for a coincident pulse 68 W U 1 U 2 [ l-(l-u 1 u 2 )(u 1+ u 2 -u 1 u 2 ) ] " (u l U 2 } [^(VWa) ] (7.7) and the amount of compensation is uu V2 r U 1 U 2 ( VV U 1 U 2 ) Jl 1 2 u 1 +u 2 4u 1 u 2 L l- (l-u 1 u 2 ) ( u 1 +u 2 " u i u 2^ ■ (u i U 2 )k+1 [1 " (VV U l U 2 )k "^ (7 ' 8) Although k > 2 was assumed in the course of deviation of (7.8), this is also valid for k' = 1. The proof can be carried out easily by substituting k = 1 in (7.6). The second and the third terms of (7.8) represent the error, and therefore the error £V with respect to the full range of the machine variable value, 1, is 6 - - U 1 U 2 U l U 2 ( y U 2- U l U 2 } k \ " U i + ^2" U 1 U 2 U-u-jUg) (u^u -UjUg) - (u x u 2 ) ■ [1 - ( u 1 +u 2 " u 1 u 2 ) " J> 69 k = 1, 2, ..., (7.9) which is always negative. With regard to k, the number of pulses which can be accepted to the counter in every range element, we have the following consideration. If both input sequences, U-. and Up, have low average repet- ition rates, coincidence occurs rarely. The counter is often empty and can accept as many pulses as the counter capacity in every range element, i.e., k «£_ k . As the average repetition rates of both input sequences increase, coincidence occurs more frequently. The counter is required to store more pulses for a longer time and this tends to decrease the number of pulses acceptable to the counter in every range element. Now, from Figure 27 it is clear that each range element has at least one blank and therefore at least one stored pulse in the counter is cleared after being used for compensation. This assures one vacancy in the counter for the subsequent range element, i.e., k : > 1. From the above argument it can be concluded that k is a function of u-^ and ^, and takes values between 1 and the counter capacity, k , i.e. , 70 1 < k(u 1? u 2 ) < k c (7.10) As iLUp-^ 0, k — > k and as u, and u ? — > 1, k — > 1. To estimate the accuracy it would seem reasonable to set k(u 1 , u 2 ) = -|— (7.11) as the average value. In practice, the counter is made of a binary counter, and the counter capacity is given by k = 2 -1, where m is the number of binary stages and takes 1,2,.... Since increase of m by 1 practically doubles k , it is clear that fine adjustment of k is not necessary for c design purposes. This justifies the crude setting of k by (7«ll) « In terms of the number of binary stages, m, of the counter, we set as the average value of k, k = 2 m ~ 1 ( 7 .i2) 7° 3 Subtraction For subtraction we wish to form a SRPS with machine variable Uo given by Uo = uj_ - u 2 , assijming u, ^Up In the sub tractor by deletion method, the resultant sequence is formed from the minuend sequence by deleting pulses each of which corresponds to every pulse 71 of the subtrahend sequence. When pulses of the two sequences coincide, deleting pulses of the minuend sequence can be accomplished by the use of an AND gate. On the other hand, when pulses of the two sequences do do not coincide, a storage unit is needed to store the pulses of the subtrahend sequence temporarily until the pulses of the minuend sequence appear. The schematic diagram of the subtractor is shown in Figure 2.8, First, coincident pulses of the two sequences are deleted. Then the sequences obtained in this way are applied to an up-down counter with additional gates for further deletion of the pulses of the minuend sequence. Only when there is no stored pulse of the subtrahend sequence in the counter, the output of B. is logical "0" and the pulses of the difference sequence appears at the output. D2 prevents overflowing of the counter. The size of the counter determines the accuracy of the unit. To estimate the accuracy, a binomial distribution is assumed for the pulse distribution as before. For theoretical analysis, a range element is defined as shown in Figure 29. It has n blanks following a pulse of the minuend sequence and has one pulse at the end, where n = 0,1,2.. .. To make the analysis simple, it is assumed that the counter is able to accept k pulses of the subtrahend sequence in every range 72 CM Q Q ii A (/> (/) O i— i _l _l _l _l < < K H O Q< O UJ 1- Ul UJ UJ LlI Q Q i— i o CNJ Q o Q 2 Q_ £ 3 O Q LU u. (/) C/) e uj 3 3 O O O O UJ lu o o ■I ii rH CM Q O CO ViJ CM + Q cvj CM Z3 OJ CO s •H -P O cS CO 0O •H 73 Ul U; A RANGE ELEMENT (n-Hl) CYCLES n BLANKS <~ 2 n n+1 AT MOST k PULSES ARE EFFECTIVE FOR SUBTRACTION a. , \ Figure 29. Illustration of the Minuend and Subtrahend Sequences Showing a Range Element. 7U element. This again is not strictly true because of storage action of the counter as "before. Let r "be the number of pulses of the subtrahend sequence in a range element, then, if r ^ k all r pulses are effective in deleting a pulse of the minuend sequence. If r>k only k pulses out of r are effective. Hence we have, P { A pulse of the minuend sequence is deleted, given a range element of the minuend sequence of n blanks } k , , n+1 , _ /n+l N r,. N n+l-r . „ /n+l N r ,-, Nn+l-r /r , ,„v = z r ( r W 2 (1-u ) + k Z ( )u: (1-u ) (7.13) r=l r=k+l Also P { A range element of the minuend sequence with n blanks occurs } = V 1 " u l) (7.14) For sach such a range element one pulse of the minuend sequence is deleted with the probability determined by (7.13) and (7.1*0 . Therefore the effective subtrahend Ug^. is s n+l N r /, N n+l-r u^ = u x n 2 Q u 1 (l~u 1 ) n [^ r ( n r ) u * (i _ ^ 75 * k "z C 1 ; 1 ) u\ (l-u,) n+1 - r J (7.15) r=k+l » 2 (VVD , k . 'V'-tJOT"'^ 1 ' 2 - (7 - l6) Derivation of (7.16) from (7.15) is found in Appendix B. The second term of (7.16) represents the error. The error with respect to the full range of the machine variable value is u (l/u -1) U - U 2 Wl/ Ul -1) J . k = X > 2 > ••• (7.17) k 2 ' 1 which is always positive. The pulses of the minuend sequence which coincide with those of the subtrahend sequence are deleted with the use of AND gates and are not fed into the counter. Since the calculation was carried out as if all deleting processes took place in the counter, this additional deletion of the pulses of the minuend sequence should be taken into account. However, it can be shown numerically that the correction due to this effect is negligible for k ^* 2 and is appreciable only for k = 1. Since the resultant error for k = 1 is still too large for practical use, the result will simply be indicated. 76 2, - u (l/u -l) U (l-U / ) ^ S n = . t 1 - 7 1 (7.18) l+u 2 (l/u 1 -l) l+u 2 (l/ Ul -l) As in the case of addition, a "brief discussion on the choice of the average value of k will be given. If \x » u , it rarely happens that the instantaneous number of pulses of the subtrahend sequence, U , exceeds that of the minuend sequence, UL , and therefore the counter is practically empty all the time. This means that the counter is able to accept as many pulses as the counter capacity in each range element, i.e., k <^k . If u ^u , the instantaneous number of pulses of U frequently exceeds that of IL. . The counter is required to store more pulses for a longer time. Thus the apparent counter capacity is smaller than k . Nov, from Figure 29 it is clear that there is always one pulse of the minuend sequence at the last cycle in each range element, and this pulse clears one pulse of the subtrahend sequence stored in the counter. This assures one vacancy for the subsequent range element. Therefore k > 1. Since this is the same situation as in the case of addition, one again sets, as the average value of k k = ^r 1 (7.11) 77 or, in terms of the number of binary stages, m, of the counter k = 2 111 - 1 (7.12) So far U]_ ^ Up has been assumed. If u, u 2? the up-down counter is not full on the average. On the other hand, if u, u 2 and u-^u^ 7.*+ Division For division, it is wished to generate a SRPS with machine variable u-, = u-j_/up, assuming u-j_ <> u 2* Since Up = ^2.l^o> ^ e avera S e period of the divisor sequence expressed in terms of the clock period 78 is given by l/urj. If the number of pulse s, given by the average period of the divisor sequence divided by the clock: period, i.e,, l/u p , are generated for every pulse of the dividend sequence, the sequence generated in this way has as its average repetition rate f o = f-j_(l/u p ) „ In terms of the machine variable: 3 f V U 2 U 2 Thus the sequence gives the quotient u^/i^. Correspondence of the dividend, divisor and quotient sequences are shown in Figure 30, In this figure, a favorable situation is depicted, i.e,, the instantaneous period of the dividend sequence is longer than that of the divisor sequence. This is not always so, even though u- < u^j because of the Inherent randomness of pulse occurrence. Since we wish to generate a group of pulses for every pulse of the dividend sequence, a storage unit is needed to store the pulses of the dividend sequence temporarily in case that the instantaneous periods of the divisor sequence exceed those of the dividend sequence. The schematic diagram of the divider is shown in Figure 31 « The size of the counter determines the fraction of the number of pulses of the dividend sequence which are effective for division operation and therefore it determines the accuracy of the divider unit* 79 It If 3 •H tQ •H > CM Z> ro 3 8o z> . ■o + 30 O OJ 3 II ro 3 O O Q_ U CO q: uj z> o o UJ X Q CO OJ o £L Q OJ Z> CM Z> OJ 3 r _i 3 U_ CO a: z> o U UJ X U- H u. CM o : O ii h 11 it l-H OJ Q Q CO CO O r-H _l _) _l _J < < h- \- o cc CJ UJ UJ 1- -z. Z> UJ UJ UJ Q Q •— i o OJ o o O z: Q. o C\J 3 I w ro 3 O •H W •H •H Q H ro faD •H M OJ => Z> 81 When the number of pulses of the dividend sequence exceeds that of the divisor sequence instantaneously, they are stored in the counter. An error arises whenever pulses of the dividend sequence are discarded because of the finite counter capacity. To estimate the error, we need to estimate the fraction of the number of discarded pulses of the dividend sequence. This is exactly the same situation as in subtraction discussed in the previous section. The correspondence of the dividend and divisor sequences is shown in Figure 32, which is the same as in Figure 29 except that the two variables now have the opposite relation u., < u 2 , i.e., the dividend and the divisor correspond to the subtrahend and the minuend, respectively. The similarity of the situation can be also seen by comparing the inputs to the up-down counters of both cases in terms of the Boolean expression. For sub t rati on UP: U-l U 2 D 2 , DOWN : U x U 2 D x and for division UP : U-l U 2 D" 2 , DOWN : U, U g D x If U-i and U 2 ars interchanged in one case, one has the other. The effective dividend is given by njU/ug-l) \ =U 1 [1 " ( l+uJl/ V l) ] ] > k - X ' 2 ' ••" 82 Ul Ur r AT MOST k PULSES ARE EFFECTIVE FOR DIVISION A "N -I h n BLANK \ H n. +- 1 1 2 n n+1 A RANGE ELEMENT (n + 1) CYCLE Figure 32. Correspondence of the Dividend and Divisor Sequences and a Range Element. 83 which is obtained from (7.1&) "by interchanging u, and Ug. The error of the divider with respect to the full range of the machine variable value, 1, is u u (1/u -1) which is always negative. The pulses of the dividend sequence which coincide with those of the divisor sequence are effective for division without being stored in the counter. This introduces the same effect as in the case of subtraction. Hence, for k = 1, the error is estimated more closely by, u^(l/u 2 -l) u 2 (l-u z /2) l d ± = ' UgU+UjU/Ug-l)} [1 " 1+UjU/Ug-l) 1 (T * 20) which is obtained from (?.l8) by interchanging u, and u , and dividing the result by ^. As the average value of k, we again choose k ■ 2"" 1 (7.12) Having established the four basic computing elements for the SRPS system, the General Computing Element can be realized without any problem. In this case the temporary storage can be used in common for the three basic operations. 8U 7.5 Complementary Relation between Addition and Subtraction There are alternative ways of addition and subtraction using the sub tractor and the adder, respectively, together with logical inverters . Their operations are based on the basic principle of probability theory that' the logical inversion of sequence U with machine variable u gives sequence U with machine variable 1 - u. The schematic diagram of the adder and sub tractor by this method is shown in Figure 33. For the sake of convenience, units will be called compound adder and compound subtractor, and the units discussed in Sections 7o2 and 7«3j intrinsic adder and intrinsic subtractor, respectively. It can also be shown that the output pulse sequences of the compound units are identical with the outputs pulse sequences of the corresponding intrinsic units in terms of a Boolean expression . This means that the corresponding units give the same results not only in terms of the machine variable value (average quantity) but also in the instantaneous occurrence of pulses. Hence, the pulse distributions of the both cases, are identical. In the compound adder, using the intrinsic subtractor, U, is applied to the minuend t3rminal of the intrinsic subtractor. As the output of the compound adder the output of the intrinsic subtractor is inverted. Taking these into account, the Boolean expressions of the UP and DOWN inputs and of the output of the compound Ps CM CM 3 I CM 3 fO O CO cr UJ IE UJ > Q < cr o h- O < cr m CO o CO z CT < z CO g o Q < ± 3 1 — - w CO cr UJ \- cr UJ > Q Z < cr UJ Q Q < y CO z cr < z CO Z5 < cr h- CD Z> CO o •H o ctj -P ■s O •H +3 •H d d < o w -P •H s d o o o m oo CD 3 bO •H 86 adder are: UP: U 1 U 2 D 2 , DOWN: ^U^ OUTPUT: U x V U 2 v D x = ^ V U g V U 1 U 2 D 1 which are identical with the corresponding expressions of the intrinsic adder shown in Fig. 26. In the compound sub tractor using the intrinsic adder, U, is applied to the addend terminal and the output of the intrinsic adder is inverted to obtain the output of the compound unit. Therefore the Boolean expressions of the UP and DOWN inputs and of the output of the compound unit are: UP: U-^D^ DOWN: U-JJ^ OUTPUT: U X V U g V U-jU^ = UJJ D which are identidcal with the corresponding expressions of the o (l) intrinsic subtractor shown in Figure 28. The author is indebted to John Esch, Department of Computer Science, University of Illinois, for this proof. 87 The accuracy of the compound units is estimated from that of the intrinsic units. For addition by the compound adder, the intrinsic subtractor gives (l-u-^ - u + S s (JL-.u^u ), where £^ (l-u-^ u ) is obtained k k from (7.17) and (7.I8) by replacing u_ by 1-u-^. The output of the compound adder is u + u - £ (l - tu, u ). , Hence, the error of the compound adder with respect to the full range of the machine variable value is, £ = -f (1-u u ) = - u [ - x f ] , k = 2, 3, ..., \ s k 1 2 2 1_U 1 +U 1 U 2 ^u 2 (1-u ) 2 (l-u /2) [1 " • -, „ T„ „ ~ h for k = 1 (7.21) l-u 1+ u 1 u 2 l-u 1 +u 1 u 2 For subtraction by the compound subtractor, the intrinsic adder gives 1 - ^ + u g + £ (l-i^, u 2 ) 3 where £ (l-^, u 2 ) is obtained from (7.9) by replacing u-, by 1 - u-j_„ The output of the compound subtractor is tt. - u - C (l-u_ , u„). Hence, the error 1 2 a, 1 2 of the compound subtractor with repsect to the full range of the machine variable value is 88 = -\ (1 -v V (1WU 1 )U 2 a - U l )u 2 (l "V U I U 2 ) ,k 1 " U 1 +U 1 U 2 1_ (l-u 2 +u 1 u 2 ) (l-u^u^) + [(l-u 1 )u 2 ] K+ - I [l-(l-u 1+ u 1 u 2 ) K X ], k = 1, 2 ; (7.22) 89 8. STATISTICAL FLUCTUATION IN A SYNCHRONOUS RANDOM RJLSE SEQUENCE 8.1 Pulse Distribution of a SRPS For a SRPS j the pulse distribution is described by a binomial distribution function, if the occurrence of a pulse in a time slot is independent of any previous occurrence. If there is any storage action in the process of generating a SRPS or in the course of algebraic operations with SRPS's, the pulse distribution is not strictly described by a binomial distribution functicn„ To observe independence between different time slots, a test by autocorrelation is convenient. The autocorrelation function of U(t) , which is the binary representation of a SRPS, is defined "oj NT Q cpUT ) = lim ~~ / U(t)u(t h 4T )dt, I = 1. 2, ... (8.1) N->oo / where T = l/f Q = clock period of the system. The argument of the autocorrelation function, £T .., is chosen discrete for our present purpose. In (8.1), the integral and NT Q are proportional to the number of pulses generated by U(t)tl(t + IT ) and the number of clock pulses during the sampling time, NT Q , respectively, with the same proportionality factor. Therefore cp(iT n ) gives the probability of occurrence of a pulse in a time slot of a SRPS given by U(t)U(t + i'2 ) 90 i.e. , cpUT Q ) = P{U(t)u(t + jJT Q ) = 1} (8.2) If there is no storage action, u(t + #T ) is independent of U(t) , "but has the same probability of occurrence of a pulse in a time slot, and (8.2) is equal to FtU(t) = 1} • P{U(t -r ; T Q ) = 1 ) (8.3^ 2 = u (5=12 If this is not valid, U(t + £'£ ) is not independent of U(t) , and therefore the pulse distribution is not exactly described "by a binomial distribution function. If a binomial distribution is assumed for the pulse distribution of a SRPS, the standard diviation for a given averaging time T - nT Q is given by a =J nu(l - u) (8.4) The relative fluctuation with respect to the average, nu, is A -kfi - L (8 ' 5) 91 For example, for u = 0.5 and n = 10^ £ = 3.2$. if the clock frequency of the system is 1 MHz, the averaging time corresponding to n = 1CP is 1 ms. If u « 1, since n - T/T and u = f/f Q = fT Q , (8.5) reads y/fT which is identical with (^.5), the relative fluctuation with respect to the average value for a Poisson distribution. The fluctuation with respect to the full range of the machine variable value, 1, is obtained by setting u = 1 in the expression of the average value nu. Hence we have, A , .fihsl = ua (8.6) For example, for the same numerical values in the above example, A ' =1.6$>. A' is defined so that there is the common scale for the static errors of the computing elements which were discussed in Section 7 and the dynamic errors in the system which are due to the statistical fluctuations „ From (8.5) and (8.6), it is clear that the dynamic accuracy is related to the averaging time in the same way as in the previously treated RPS system. Since the analog variable is represented by the relative average repetition rate with respect to the clock frequency in the 92 SRPS system, a digital counter as well as an analog averaging unit can "be used as the averaging unit. One of the advantages of the digital method is that the measured values are independent of the pulse shape, ■whereas this is not so in the analog method. 8.2 Squaring by Autocorrelation In the previous section, it was shown that the square of a machine variable was obtained by autocorrelation, if the pulse distribution of the SRPS was a binomial distribution. This suggests a squaring unit in a SRPS system. Realization of such a squaring unit is rather simple, once a delay unit is available. A delay unit which delays the incoming SRPS by one clock cycle is shown in Figure %k. The first JK-f lip-flop is provided to stretch the pulse width of the incoming SRPS up to the full clock period, T Q . The output sequence obtained at Qo also has the pulse width of T , and if pulses occur successively, they are no longer separate pulses but a long pulse of the width of a multiple of T . To obtain a longer delay nT Q , n such units must be connected in cascade. The squaring unit in this scheme is shown in Figure 35. It is clear that higher order powers can be obtained by a repeated use of this scheme. o UJ 5 CO _IQ_ OCO rO O 93 "\ O CJ CO cj cj CJ >8§ UJ •H bO * CD O ^ •H H Ul Ul H O >> 2 Q O o M o o H O y O •H o o _i o o CJ en Q_ or en 9^ +3 •H 8 w a •H •H ?6 = 95 9. EXPERIMEFx n AL RESULTS 9.1 Multiplication and Division in the RPS System In the experiments, the pulse height V Q = 10.0 v and T - 1.0 JJ s. The average voltage was measured with a digital voltmer (lOv full range and 1 mv minimum reading) . The time-constant of the RC averaging unit preceding the voltmeter was as large as 2 seconds to measure the static accuracy. The static accuracy of the multiplier under this condition was within + 0.5$ of the full range of the machine variable value, 1. For example, for x, = x ? = 0.500, the output of the multiplier was 0.250 + 0.00 5. High speed switching diodes and transistors (the total of the rise and fall times less than 10 ns) were used. To see the error due to the switching time, the pulse width was changed between 0.5 and l//s while the machine variable value x was kept constant. There was no appreciable errsr due to this effect. The experimental circuit for the divider was the same as the divider part of the general computing element shown in Figure 20 except for the function selecting gates. Yne time constant of the RC averaging circuit preceding the differential amplifier was chosen as 30 ms. The overall accuracy was observed to be + 1.0$ of the full range of the machine variable. For example, for Xn = 0.250 and X p = 0.500, the output of the divider was (x^/xg) , = 0.500 + 0.01. 96 9.2 Basic Computing Elements for the SRPS System In the experiments the clock frequency of the system was 1 MHz. The highest average repetition rate of SRPS's was about 989kHz and this in terms of the machine variable is 0.< 9.2.1 Multiplication With regard to multiplication, there is no error if two sequences are independent. Conversely, the result of multiplication may be used to test independence of two sequences. The results of the experiments show no appreciable error, and hence the two sequences are taken to be practically independent. 9.2.2 Addition, Subtraction and Division In order to see the variation of accuracy due to the capacity of the counter, the number of stages of the binary counter was varied. Experimental results are compared with the theoretical estimates where k is calculated from (7.12). Therefore k = 1, 2 and h correspond to 1, 2 and 3 stages of the binary counter, respectively. The average repetition rates of the SRPS's were measured with a counter to obtain the machine variable values. The sampling time (averaging time) was 1 second and for this the maximum statistical fluctuation in the whole range of the machine variable value was + 0.05% of the full range, 1. Therefore the measurements give practically the static characteristics of the computing elements. 97 For addition, the worst case occurs "when u + u = 1. The error under this condition is plotted in Figure 36(a) . The theoretical estimates were obtained from (7.17) . The experimental results agree fairly well with the theoretical estimates for k = 1 and 2. For the case of a 3-stage binary counter the experimental results do not fit the theoretical curve for k = U, but does fit the one for k = 3- This suggests that for the worst case, "k = number of the stages of the binary counter" would be a better choice than (7.12) . However, (7.12) seems still reasonable in the whole range of u + u as shown in Figure 36(b). A slight deviation of the experimental results from the theoretical curve for the fixed k seems to be due to the following reasons. The first source of discrepancy may be the choice of k. In Section 7.2 it was shown that k was a function of u and u , whereas it was set by k «= constant = 2 to simplify the analysis. The second source of discrepancy may be due to the fact that the pulse distribution is not strictly binomial. The experi- mental results of the squaring unit show that the pulses of the SRPS generator tend to be distributed uniformly (i.e., tend to be periodic) for u>0,U, Since this tendency eliminates the crowded occurrence of pulses, this tends to decrease overloading of the counter. Therefore this tendency is favorable for any one of the algebraic operations : THEORETICAL VALUES 0,x : EXPERIMENTAL VALUES UJ CO < o co cc o UJ X o I t 0.2 0.4 0.6 0.8 1.0 u« (a) Static Error of the Adder Under the Worst Case Condition; 1^+11=1. % 3 r u. (b) Static Error of the Adder with a 3-Binary Stage Counter. Figure 36. Static Characteristics of the Adder. 99 which employ the counter as a temporary storage. This accounts for the fact that the measured errors are smaller than the estimated ones. For the case of a 3-stage binary counter, the error is less than Vfo of the full range if u-, + Up<0.95. The error exceeds 1% only within the last 5''j& near the full range. This is shown in Figure 36(h) . Therefore 3 binary stages provide adequate storage capacity in practice. For subtraction, the worst case occurs when u, = u p . The error under this condition is plotted in Figure 37v?<) . The theoretical estimates for k = 1 given by (7.18) yield a symmetric curve with respect to r.T_ = Up = 0.5. The experimental values agree with the theoretical ones fairly well. Cn the other hand, (7.17), which is to be used for k _£ 2, dcec not yield symmetrical curves whereas the experimental results are symmetric. To remedy the discrepancy, (7.17) is plotted only for ) _S v -i = ^2 S^'^i anc ^ ^ or 0.5^'u-|_ = Up _5 1, the mirror images of the curves for (0, 0.5) with respect to u, = Up = 0.5 are plotted. There is a good reason for such a modification, as noted below. In the subtracter, the coincident pulses of the two operand sequences are deleted before they are applied to the counter where a further deletion takes place. The sequences which are applied to the counter have the logical expressions U^l^ and U-j_ T Jp, and the machine variables Ut - uvug and Up - u-]_Up, respectively. Under the worst case condition, u-^ = Uo = u, both sequences have the machine variable value u(i-u) , This is invariant for the replacement of u by 1-u. This means that the inputs having the machine variable values u and 1-u produce 100 % 15 UJ if) < o (/> (Z o UJ X CO 10 - 5 - 0.2 : THEORETICAL VALUES ©,x EXPERIMENTAL VALUES 0.4 0.6 lh= U 1 -u 2 0.8 1.0 (a) Static Error of the Subtractor under the Worst Case Condition; u =u , 7c CO w 1 o U!=0.3 U 1 =0.5 • © U!=0.7 ©U^O.9 0.2 0.4 0.6 0.8 1.0 u- (b) Static Error of the Subtractor with a^-Binary Stage Counter. Figure 37. Static Characteristics of the Subtractor. 101 the same conditions for the counter ar.d produce the same amount of error. This justifies the above modification. It seems that the inadequacy of (7.1?) is the result of neglecting the functional dependence of k on u . and Up. As in the case of the adder, the experimental results for the 3-stage binary counter in the worst case agree with the theoretical curve for k = 3? rather than the one for k = k. However, k = 2 m seems still good in the whole range. To show this, the errors for the case of the 3-stage binary counter were plotted as functions of u<2 while u-, was kept constant. The error exceeds 1$ only within the last 5$ of the full range. Again the 3-stage binary counter is adequate in practice. For division the worst case occurs when u-j_ = Up. The error under this condition is plotted in Figure 33(a) . The experimental results agree well with the theoretical estimates, except for the case of k = k. Again the case of the 3-stage binary counter fits the theoretical curve for k = 3. In Figure 3&(b) , the error for the case of the 3-stage binary counter is shown as a function of the dividend, u-j_, while the divisor, U2j is kept constant as a parameter. The error exceeds 2.5$ only within the last 5$ of the full range. As the divisor decreases the maximum error increases to as large as 10$ which is k times larger than those for the adder and sub tractor. UJ CO < CO §♦ UJ X % 50 40 - 30 20 - ^ 10 i 0.2 102 : THEORETICAL VALUES © , x : EXPERIMENTAL VALUES 0.4 0.6 Ul =U 2 0.8 1.0 (a) Static Error of the Divider under the Worst Case Condition; u, /u % 10 - G = 1. i 0.2 I =0.4 o U 2 =0.6 0.4 0.6 0.8 1.0 U (b) Static Error of the Divider with a 3-Binary Stage Counter. Figure 38. Static Characteristics of the Divider. 103 9.2.3 Compound Units for Addition and Subtraction The errors under the worst case condition for the compound adder and the compound subtractor are shown in Figure 39(a) anu (b) , respectively. The symmetry of the theoretical curves for the compound adder were obtained by the same procedure as for the intrinsic subtractor. The experimental values agree -with the theoretical ones well except for the case of k = U. Comparison between Figure 39(a) and Figure 36 ( a) shows that the intrinsic adder and the compound adder have the same characteristics, as expected. On the other hand, the theore- tical estimates for both cases do not agree very well. This is due to the difference between the mathematical procedures to estimate the errors for both cases. The same comment applies to the relation between : compound subtractor and the intrinsic subtractor. Now, comparing the characteristics of the intrinsic units and these of the compound units under the worst case conditions, one comes to the following conclusion: The theory developed for the intrinsic adder describes the symmetry property of the adder and subtractor very well. On the other hand, the theory developed for the intrinsic subtractor is inadequate for describing the symmetry of the character- istics of both units, except for the case of k = 1. 104 THEORETICAL VALUES 7c © , x : EXPERIMENTAL VALUES 0.2 0.4 0.6 0.8 1.0 Figure 39(a) • Static Error of the Compound Adder under the Worst Case Condition; u.. + u = 1, 105 LlI < o co O Ld X u; % 15 10 - 5 - k = l 0.2 0.4 0.6 0.8 1.0 u l =u 2 Figure 39(b). Static Error of the Compound Subtractor under the Worst Case Condition; u, = u . io6 9.3 Squaring Unit The experimental results of the squaring unit are interesting not only to confirm the analysis of the squaring unit itself but also to oh serve characteristics of the pulse distribution of the incoming SRPS. The delay unit in the squaring unit gives a delay of one clock period. The averaging time was 1 second and the clock frequency was 1 MHz as before. The error of the squaring unit, esq, is defined by /Output of the. _ -Theoretical value r squaring unit' * of square ' /q ,\ Full range of the machine variable value, 1. Figure ^o(a) shows the experimental results when the input is a SRPS generator. Generator #1 and #2 were able to generate only up to 0.5 and 0.6, respectively. The circuits of the generators #1 and #z are the same, whereas the circuits of generator #3 is different from the others. In generator #3 ? the noise voltage from the noise diode is amplified in both current and voltage so that even originally low noise pulses are able to trigger the flip-flop in the SRPS generator. Therefore higher average repetition rates were obtained. The difference in the circuits seems responsible not only for the highest variable value obtained but also for the pulse distribution of the generated SRPS. In both respects, generator #3 is superior to the others. % 10? x : GENERATOR #1 d : ,. #2 2 x X INPUT- D D X 0.4 0.6 0.8 1.0 U A o 0.2 y 9 o -2- □ o o o -4 X □ -6- □ (a) Errors of the Squaring Unit When the Input is the SRPS Generator, la \ 10 8- 6 4 2 ■ o : ADDER x : DIVIDER 0.2 0.4 0-6 (b) Errors of the Squaring Unit When the Input Is Adder or Divider 0.8 1.0 INPUT — ► the Output of the % 2] v> r\ -2\ o _GL 0.4 0.2 0.6 0.8 INPUT- 1.0 (c) Errors of the Squaring Unit When the Input Is the Output of the Subtract or. Figure ^0. Static Characteristics of the Squaring is: (a) SRPS Generator, (b) Output (c) Output of the Subtractor. Unit When the Input of the Adder or Divider, 108 The negative value of Ssq shews the phenomenon that pulses do not occur successively, i.e., the tendency to be periodic. This is favorable for any one of the basic operations which employs a temporary storage as mentioned in Section 9»2.2. All three generators have this tendency beyond O.U. Figure Uo(b) and (c) show the case in which the output of the basic computing units are applied to the squaring unite The numerical values on the abscissa show the net input to the squaring unit, i.e., they do not include the errors due to the computing units preceding the squaring unit. Figure Ho(b) shows the results when the output of the adder or the divider is applied to the squaring unit. The values of the two inputs to the adder were chosen to be equal, i.e., u = u . Under this condition, coincidence occurs most frequently for a given output u, + u . For the inputs to the divider, the divisor, u , was kept constant at 0.5 while the dividend, u , was varied so that the output of the divider gave the desired values for the input of the squaring unit. In addition, each coincident pulse is inserted into the first blank slot after the coincidence, and this enhances the probab- ility that the output sequence will have successive pulses. The positive error at the output of the squaring unit for the case of the adder, indicates this effect. 109 In division, a group of pulses are generated for each pulse of the dividend sequence and this again produces the positive error at the output of the squaring unit. It is apparent that the output of the divider is unsuitable for direct input to the squaring unit. Figure 4CHc) shows the case of the subtracter. In this case the minuend, u^, was kept constant at 0.9 while the subtrahend, Ug, was varied so that the actual output of the subtractor gave the desired values for the input of the squaring unit. Both positive and negative errors were observed. It should be able to obtain a squaring unit with a higher acjuracy if a delaying unit with a longer delay, dependent on the pulse distribution of the incoming SRPS, is employed. The length of the delay is naturally limited by the cost of the delay unit. 110 10. CONCLUSIONS From the theory for the basic analog computing systems of the RPS's and of the SRPS's and from the corresponding experimental results, it can he concluded that such computing systems are indeed feasible. The treatment of the "basic computing elements have been confined to the case of unity scale factor. Since no scaling is needed for each basic computation, it will facilitate the realization of systems of such computing elements. In particular, is this true for the General Computing Element. In the RPS system, the static accuracy is primarily determined by the analog precision of the pulse height. In the SRPS system, this requirement of analog precision is eliminated. For multiplication, there is no static error due to the multiplier itself. For the other three basic operations (addition, subtraction and division) , the capacity of the temporary storage of the computing elements determines the static accuracy. Equations (7-9) t (7.12), (7.17) and (7.19) are to be used to determine the number of binary stages of the temporary storage for a desired static accuracy. For 3 binary stages lf accuracy with respect to the full range of the variable value is obtained for most values of the machine variable. Ill Note that only for multiplication the inputs have to be 2orrelated, in both the RPS and SRPS systems. In the RPS system s a new RPS is generated for each operation 5 and therefore there is no correlation between the pulse distribution of the output and those of the inputs. This is desirable when a group of operations are performed in which identical variables appear more than once. On the other hand, in the SRPS system, the pulse distribution of the output is correlated with those of the inputs „ When a group of operations is performed and if identical variables are applied more than once, one must be careful to avoid multiplication of correlated sequences. The dynamic error of the system is due to the statistical fluctuation of the measured average values. As it was mentioned in Sec 8, about lc5io fluctuation with respect to the full range of the machine variable value is obtained for an averaging time of l s 000 clock periods. This corresponds to the averaging time of 1 ms if the clock frequency of the system is 1 MHz. It seems that a 10 MHz system will be realized without too much difficulty. In this case, the averaging time 1 be reduced to 100 Ass to obtain the same dynamic accuracy „ To accomplish a 10 MHz system, the generator needs improvement to generate zf higher repetition rates. It is clear that realization of the computing elements in the stochastic 2omputing system is simpler than that in the conventional 112 analog computing system. Since they can be fabricated in the form of Integrated Circuits s their low cost are evident. However 9 since a high accuracy is attained only by sacrificing the speed, an attractive application area will be an area where a large number of computing elements with a moderate accuracy are required in parallel operations. 113 REFERENCES 1. Afuso, C, and Esch, J., "Quarterly Technical Progress Reports", Department of Computer Science, University of Illinois, starting January, 19&5 to September, 1966. 2. Afuso, C, and Esch, J., "Quarterly Technical Progress Reports", Department of Computer Science, University of Illinois, starting October, I966 to September, 1967. 3. Chance, B., et al., Waveforms , McGraw-Hill, I9U9. h. Feller, W., An Introduction to Probability Theory and Its Appli - cations , Volume 1, Wiley, 1967= 5. Fry, T. C, Probability and Its Engineering Uses , Second Edition, Van Nostrand, 1965. 6. Gaines, B. R., "Techniques of Identification "with the Stochastic Computer", IFAC Symposium, 1967? Prague. 7. Gilstrap, L. 0., et al., "Study of Large Neuromime Networks", Adaptronics Interim Engineering, Report Number 1 to the Air Force Avionics Laboratory, USAF, Wright-Patterson A.F.B., Ohio, August, I966. 8. Petrovic, R., and Siljak, D., "Multiplication by Means of Co- incidence", 3rd International Analog Computation Meetings (ACTES Proceedings), 1962. 9. Poppelbaum, W. J., et al., "Stochastic Computing Elements and Systems", Fall Joint Computer Conference, Anaheim, California, 1967. 10, Ribeiro, S. T., "Random-Pulse Machines", IEEE Transactions on Electronic Computers, Volume EC-16, Number 3 5 June, 19&7 • 11. Rice, 3. 0., "Mathematical Analysis of Random Noise", Bell System Technical Journal, Volumes 23 and 2k. Ilk APPENDICES 115 A. TOLERANCE SPREAD OF THE CHARACTERISTICS OF NOISE DIODES (CLEVITE CND-012) Figure 1+1 shows the tolerance spread of the V -V character- istics of noise diodes (Cievite CND-012) . Although four samples were tested originally, one was discarded because its characteristic deviated too much from those of the other three. For the generated RPS: Pulse height V = 10 volt Pulse width t = l/(s Hence the average repetition rate f = rr^~ = 100 V kHz V The diode amplitude discriminator circuit is also shown in Figure kl. The original noise voltage appears across the 100 k resistor. An emitter follower is provided for current amplification in order to obtain enough power to trigger the one-shot multivibrator, The noise voltage is a negative saw tooth wave superposed on 10 volt dc. Therefore decreasing V from 10 volt decreases the average > 5 116 o X u $ UJ > g 5 CC o to o 10 m ^ ro a; i i o a> -p •H > a; H O w cu t3 o •H « a; w •H o 82; <^ o CO o •H -P W •H cy -p o a3 O CU +3 2 (l-a) K 120 Hence 1 2 ^(VV 1 ) k-2 AU 2/ ^ a " U 2 ( i + u 2 (l/u r l) ] [ l+u 2 (l/ V l) ] Let l+u (l/u r l) =a ' l + u 2 (l/u r l) = P then 2 k-2 A Up = /-u - u a p k k-1 = A U . - u a 2 a k ' 3 - u p aS k " 2 Tt-2 2 ° k-2 u^a' (1 + p + . .. + p ) (B.l) - ~^* \- X Now u = (u - u ) + (u - u )+...+ (u - u ) + u \ \ Tt-1 Tc-1 k-2 2 ^1 1 = Au + Au + . .. + A U + u (B.2) ^k Tt-1 ^2 *1 121 Substitution of (B.l) into (B.2) yields u =u - u a (1 + p 2 + ... + p k ~ 2 ) k 1 * 2 2 k- ~\ + u - u a (1 + p + p + . . . + p J ) l + X ku - u a 2 [(k-l)+(k-2)p+...+2p k ~ 3 +p k ~ 2 ] 1 ku - u a 2 [k(l+p+_.+p k ~ 2 ) 1 - {l+2p-3p 2 +...^(k-l)p k " 2 }] k-1 v "i 2 r . 1-p 1-R k ~! k" 1 ! ku - u a [k p - - p + y— p ] 2 1 2 J -" P (1-p) 2 1_P ku 2 x - XT" [k " p " Up ] 122 But u„ =u 2 Z (l-u.) n [l-(l-u p ) n+1 ] *1 n=0 U 2 (B.3) l+u 2 (l/u 1 -l) = u 2 « 1-p = a 1 R k_1 u = ii a[k-k+p + ±£ 2. 2 a k u 2 [l-(l-a)p " ] u 2 (l-p k ) u 2 ( 1 /u 1 -l) k ujl - { rr } }, k > 2 l+UgC^U^l) Combining this with (b-3) j we have u 2 (" /u^-l) u 9 = uj>{ 1 } ], k= 1,2,3,..- (7.16) ^k d l+u 2 ( J / Ul -l) VITA Chushin Afuso was born on December ;i. ' ,. i i Jnawa, Japan. He received his Bachelor of Engineering from Yokohama Na- tional University, Japan, in 1956. He taught at Okinawa Technical High School, Japan, for two years and then joined the staff of the Department of Electrical Engineering at the University of the Ryukyus in Japan. In 1959 he came to the University of Illinois to do graduate work. In i960 he obtained a research assistantship from the Digital Computer Laboratory at the University of Illinois and joined the Circuits Research Group. After receiving his M.S. in i960, he went back to Japan and rejoined the staff of the Department of Electrical Engineering at the University of the Ryukyus . In I96U he returned to the Digital Computer Laboratory at the University of Illinois as a Research Assistant to continue his graduate work where he has stayed until the present time. He is a member of the Institute of Electronics and Com- munication Engineers of Japan. •* \