Patent GB-1157981-A (GB)
Title: Adaptive Predictor
Inventor: ANDREAE JOHN HUGH
IPC: G05B13/02
Filed: 1968-10-23
Abstract: 1,157,981. Adaptive predictor. STANDARD TELEPHONES & CABLES Ltd. 23 Oct., 1968, No. 8162/66. Heading G4R. In an adaptive predictor, a clump store contains a set of clumps each including a set of weights against which an input state signal can be evaluated, a clump selected as giving the best evaluation of an input state signal being used to predict the clump selected for the next input state signal, the success or failure of the prediction controlling the modification of the weights of the two clumps, the modification increasing and decreasing the scopes of the two clumps respectively in the case of success and conversely in the ease of failure and in all cases being stochastic in dependence upon the strengths of the individual weights. In Fig. 2, an input state signal is sampled at 1 to produce a j-bit word F1-Fj which is " applied " to each row of a clump store 2. Each row holds one clump by means of j clump weight storage elements shown as squares, one of which-the rth of clump (row) m-is shown in Fig. 7. The symbol involving a potentiometer is schematic for the circuit of Fig. 8 in which bi-stable 83 is set to A or B according as comparator 82 indicates that the count of a reversible counter (the " weight ") is below or above that of a randomly-driven one-way counter respectively. The weight is given a bit value by the outputs >, < of the highest order stage of the reversible counter, the value being 1 or 0 according as the weight is above or below respectively the half-way point of its possible range. The amount it is above or below the half-way point specifies the strength with which the value 1 or 0 respectively is held. Accordingly if a pulse train is applied to Ymr, the number of pulses emerging at Zmr specifies the strength, since the strength of a given binary value is specified by the fraction of the time that bi-stable 83 is in the corresponding state. Returning to Fig. 2, a clump readpulses generator 3 applies pulse train B1-Bj to respective columns of clump store 2, the trains being interleaved in time. Each clump weight storage element for which the stored weight has a different binary value than the corresponding bit Fr of the sampled input state signal, passes the respective pulse train Br via AND 71 (Fig. 7) to input Ymr. The pulses on outputs Zmr are counted, for each row of clump store 2 separately, in clump selector 4 which indicates the smallest by marking one of lines D1-Dn, thus selecting the clump which is the best fit for the sampled input state signal. (Selector 4 resolves ties according to a fixed priority order.) When the next sampled input state signal is applied at F1-Fj, the new selection is applied to lines D1-Dn and the previous selection transferred to lines L1-Ln (by advancing shift registers holding the selections). The lines L1-Ln, in conjunction with an action signal A1-Ak sampled at 8, select one of n x k stored predictions (of the next selected clump) at 6. This prediction is compared at 5 with the identity of the clump actually selected, as specified by lines D1-Dn recorded at 7. A signal R or W is produced according as the prediction is right or wrong respectively. Weights of the two selected clumps are now updated as follows, by a clump weight modifier 9. Whether the bit value of a stored weight is like or unlike the corresponding bit position of the sampled input state signal is indicated by signals LDmr, UDmr for like and unlike respectively (Fig. 7). In the case of a correct (right) prediction, the weights of the first clump which correspond to unlike bits are weakened and those of the second clump which correspond to like bits are strengthened. In the case of a wrong prediction, interchange " strengthened " and " weakened " in the previous sentence. Strengthening decreases the scope of the clump, viz. the number of possible sampled input state signals which will " belong " to the clump, and weakening increases the scope. The clump weight modifier 9 has a circuit as in Fig. 14 for each clump weight storage element, to produce a " strengthen " STmr or a " weaken " signal WKmr which is used to increment or decrement the reversible counter in Fig 8 depending on whether the weight is currently above or below the half-way point. A, E are timing pulses, a circle is an OR gate, and a semicircle is an AND gate. Each prediction stored at 6 (Fig. 2) has an associated prediction weight store as in Fig. 13. When a stored prediction is selected, the associated prediction weight (in the reversible counter) is incremented or decremented in the cases of right and wrong predictions respectively, with a probability proportional to the complement of the weight and the weight itself respectively, as shown. Each stored prediction weight produces an output at #Wmt (Fig. 13) if it is below half-scale and this will prevent it being decremented further by ensuring that if its associated stored prediction is selected any bit positions in the latter found unequal in the comparison at 5 (Fig. 2) are inverted. Modifications.-A threshold condition may be applied to prevent any clump being selected at 4 if none of them "match" " the sampled input state signal sufficiently well, a "noclump " output being produced. "No-clump " may be used as the target or basis of a prediction. Extraction of a prediction from unit 6 and modification of clump weights may be prevented if the prediction weight is below a threshold. A performance weight storage element may be associated with each clump (a measure of past success) and when no stored clump " matches " the sampled input state signal sufficiently well, the clump with the poorest performance weight is replaced by a new clump modelled on the sampled input state signal. The performance weights may be stored like the prediction weights (Fig. 13) and modified on a stochastic (random) basis dependent on the current value of the weight and the success or failure of the clump in the testing of a stored prediction.