Patent GB-1184652-A (GB)
Title: Stochastic Computing Arrangement.
Inventor: GAINES BRIAN RONALD
IPC: G06F7/70
Filed: 1966-03-07
Abstract: 1,184,652. Stochastic computation. STANDARD TELEPHONES & CABLES Ltd. 3 March, 1967 [7 March, 1966], No. 9871/66. Headings G4A, G4D and G4G. [Also in Divisions G1 and G3] General.-A computer assembly comprises one or more digital computing elements, means for representing input information stochastically by the probability that a level in a clocked sequence of logic levels will be ON, means for applying the so represented information to the computing element(s) performing digital computation, and means for converting the stochastically represented outputs of the computation into analogue or digital information valves. Theory.-Analogue variables are presented as probabilities that a specific binary or multilevel event will occur (or generally the probability that a specific configuration representing one of several possible events will occur), and a quantity or event may be scaled as a probability 1 > P > 0, and represented by a sequence of logic levels or states of the inputs and outputs of the computer elements; which representation, e.g. by the adaptive device of Specification 1,099,574, is stochastic since the event or quantity is defined by the statistical properties of a sequence as to the probability that it represents a given event or quantity. In affine symmetric binary representation, analogue quantity -E <V < + E is represented by the probability that a 2 state device will be ON. At V = 0, p = ¢. In affine symmetricternary representation, the inputs and outputs of the computer elements have three output states "ON", "OFF" and "OPEN" and for - E <V< + E and V>0, the states being permanently on or off for maximum or minimum values of V and randomly fluctuating therebetween (or OPEN) for zero. Thus V = [p (ON) - p (OFF)] E 9/ for a sequence in a ternary device wherein p (on) and p (off) are the relative frequencies of on and off conditions and for 0<V<E. Multilevel logic may also be used, which is affine if a sequence of logic levels represents a quantity which is the weighted sum of the probabilities of the logic levels in the sequence. In asymmetric projective binary representation a quantity V#0 is represented by the probability that a 2 state device is in one of its states, given by wherein A>0 is a scaling factor; Zero being represented by "OFF" and infinity by "ON" and extensible to negative quantities by multiplication by (- 1). In symmetric projective ternary representation, when V#0 and when V < 0 so that for a sequence Definitions.-A stationary sequence has invariable statistics over its length. A statistic of a sequence is an unbiased estimator if its mean value over a set of sequences tends to the quantity. A sequence is Markovian of zero order (non autocorrelated) if the probability of a state therein is unaffected by previous states of the sequence. A sequence is Markovian of order N (autocorrelated to depth N) if probability of a state therein is dependent on preceding N states. A sequence is cross correlated with another if probability of a state is dependent on a concurrent state of the other sequence. A set of sequences is pseudo random if probability of a state in one set is independent of concurrent states in other sets. A sequence is pseudo random to depth N if N pseudo random stochastic sequences may be derived therefrom by delay over zero, one, two, &c. events. Parameters whose probability states represent events or quantities may be intensity, frequency, mark/space ratio, or pulse coding in single or multiple signal channels, and may be mechanical, fluidic, thermal, electronic, &c. In synchronous computation, the states or levels of all devices and their inputs and outputs in the computation change only at given instants initiated by a common clock pulse, and in asynchronous computation their states change at independent instants determinable by the devices themselves. An independent event is one whose probability is unaffected by the probability of other events. A probability function p is such that 0<P<1. Operation.-If two events representing analogue variables V 1 , V 2  have probabilities p 1  and P 2  their joint occurrence has probability p 1  p 2 , representing V 1  V 2  so that output of a binary AND gate is unity when both inputs are unity and zero for any other combination, so that if levels applied to the two inputs are such that the probabilities that the inputs are ON are p 1 , p 2 ; the probability that the output is ON is p 1  p 2  representing V 1  V 2  in affine asymmetric binary representation. The product of multiple quantities is similarly obtained as output and AND gate with multiple inputs. A ternary logic circuit (Fig. 2) comprises NPN and PNP transistors connected with equal resistors so that if ON, OPEN and OFF conditions are represented by -, 0, and + voltages at A, B the outputs are shown in the table, and a logical inverter (Fig. 1, not shown) has output ON for input OFF, output OFF for input ON, output OPEN for input OPEN, so as to define V<SP>1</SP> = E - V for affine asymmetric binary representation, V<SP>1</SP> = - V for affine symmetric binary and ternary, projective symmetric ternary, hyperbolic ternary, and trigonometric 1 binary V<SP>1</SP> = - for projective binary represen- V tation. Fig. 6 shows a multiplication circuit for afline symmetric binary representation. If + denotes OR switching and juxtaposition indicates AND switching, while a superposed bar indicates a Boolean inverse so that a = 0 if and only if a = 1 a = 1 if and only if a = 0, the levels a, b as shown are applied through inverters to AND gate 1 as #a #b and directly to AND gate 2 as a, b, so that output of OR gate 3 is #a #b + ab which represents the scaled products of the variables represented by the sequences of a and b; the multiplier being an equality gate giving ON output if and only if its inputs are identical. For multiplication of further quantities, such multipliers are cascaded. An affine ternary representation multiplier is identical logically with that of Fig. 6 and (Fig. 1, o, p, not shown). For a multiplier in projective binary representation, a cross coupled flip flop FF (Fig. 3) receiving inputs X, Y is clocked to change over to a value dependent on its prior state and preceding inputs X, Y; the output Z from an OR gate energized from two AND gates receiving X, Y and the flip flop outputs being equal to a new input X if the flip flop output Q is ON, and equal to the complemented new input #Y if the Q input is ON. The device realizes the transformation For multiplication in projective binary representation (Fig. 4) a clocked cross coupled flip flop CCFF receives inputs AB, #AB from AND gates respectively energized from inputs A, B; directly and through inverters in synchronous logic, while in asynchronous logic the clock pulses may be obtained from a local oscillator, or triggered from a change of output if the inputs are mutually exclusive. A further delay flip flop in one input acts as correlation isolator (Fig. 7, not shown). For evaluation of squares and higher powers utilizing plural multipliers, input isolators utilizing clock pulse delay flip flops (Figs. 7, 8, not shown) are inserted to avoid autocorrelation of the inputs, whenever identical signals are applied to multiple paths, in stochastic computation. Autocorrelated sequences may be de-correlated (Fig. 21) by introducing random delays whose maximum delay # autocorrelated depth from noise sources changing over triggers at random intervals to randomize the clock pulses of flip flops FF1, FF2 when the noise exceeds a predetermined level. The random states are transferred to flip flops FF3, FF4. Flip flops FF5, FF6, FF7 connected as a shift register to the direct inverted input hold previous input states at unit, two, and three delay intervals respectively, and flip flops FF3, FF4 gate one of these delayed inputs through three input AND gates and a common OR gate to the output line, so that at each clock pulse a random delayed replication of the input appears on the output. In an adder for symmetric and asymmetric binary affine representation (Fig. 9), a first flip flop FF is triggered from a noise source with grounded inputs, and its output is applied to a second flip flop FF emitting an ON level to AND gate 4 and an OFF level to AND gate 5, or vice versa with equal probability, so that the probability p (Z) of output from OR gate 6 is ¢ (PA + PB) from gates 4, 5.   It is shown that the output is 1/k the sum of the inputs for a k input adder, and for 2 inputs a trigger pulse is applied to clock input of a first flip flop when signal from random noise source exceeds a preset threshold, to change its state, since its inputs are in a random condition at the instant of a clock pulse. Random sequences carrying information are generated in a comparator with binary output having a random first input and a fixed or variable second input responsive to input voltage or digital code; the random input containing all levels with equal probability. Fig. 10 shows analogue/stochastic converter generating random sequences comprising a comparator receiving an analogue input and an input from a digital to analogue converter triggered at T by a series of flip flops FF, each in turn triggered on its clock line from a random noise source exceeding a predetermined threshold. The flip flops are in random state so that the D/A converter feeds a random level to the comparator. If at a clock pulse applied to an output flip flop fed from the converter, the analogue input exceeds the random input, the output flip flop is ON and otherwise it is off, so that the output sequence is an affine binary stochastic representation of the analogue input if the D/A conversion is linear. Alternatively (Fig. 11, not shown) for digital input the latter is applied directly to a digital comparator also receiving the random digital output of a series of flip flops