Abstract:
A method and system are described that can predict the future value of a positive signal from prior measured values of the signal. The signal is measured at a prior baseline time, and at times incrementally beyond the baseline time. The post-baseline time increments comprise sets of geometric sequences. The system produces a future estimate of the signal merely by multiplying and dividing prior signal values. By repeated operation, the system can produce an output signal: a continuing stream of periodic signal predictions, which approximates periodic samples of the future signal “pulled back” in time.

Description:
BACKGROUND OF THE INVENTION 
     Human beings have long been interested in predictions of what the future will be. In recent centuries, mathematicians have succeeded in finding methods of prediction for a very limited range of phenomena. If the predicted entity is a measurable quantity, it is possible to estimate the magnitude of the quantity at a future time, given its magnitude at previous times, if the measured quantity changes smoothly, i.e., has no sudden changes. A mathematician would call such a smoothly varying quantity an “analytic” function of the time. 
     Brook Taylor, an English mathematician, was among the first to invent such a method, nearly three centuries ago, in 1715. Taylor&#39;s formula calculates the value of a smoothly-varying quantity ƒ at a future time t from knowledge of the quantity at a previous time t 0 . The formula uses the value of the quantity at time t 0  and its derivatives at t 0 . The need to know the derivatives of the quantity limits the formula&#39;s usefulness. Sometimes it is possible to calculate the analytic form of these derivatives, but this requires knowledge of the analytic form of the quantity itself. In many situations, one does not have this information. 
     There are many other methods for estimating the value of a quantity at a future time from its values at previous times. Some other methods rely on adjusting parameters (i.e., constants) of an analytic expression, which is assumed to accurately characterize the quantity. Such methods include mean-square curve-fitting and the maximum likelihood method, which are described in many textbooks. The parameters to be adjusted might include slope and intercept (in the case of a line), or standard error and central value (in the case of a probability distribution). However, these methods, like Taylor series, assume that one knows the analytic form of the quantity (e.g., a line or bell-shaped curve). They are not useful if the analytic form of the quantity is not known. 
     Recently researchers have learned to use neural networks to predict future signal values. The neural network is “trained” on previous data. Neural networks can sometimes produce reasonable results for non-smooth signals, such as a sawtooth signal. As applied, however, neural networks are often trained to recognize expected patterns in the signal, such as frequency components or wavelet patterns. 
     SUMMARY OF THE INVENTION 
     The present invention is a system and method that can predict an estimate of the future value of a smooth signal from prior values, without any knowledge of the form of the signal. The system measures signal values at a baseline time and at a collection of succeeding times. The baseline time is the time at which the first measurement of the signal is made. The time increments—from the baseline time to each of the succeeding measurement times—form sets of geometric sequences. Although the method requires a large number of signal measurements, the processing that produces the prediction is quite simple. The method calculates the predicted signal value merely by multiplying and dividing the prior measured signal values. By repetition, the method is capable of producing an output signal: a continuing stream of signal predictions, which approximates periodic samples of the future signal “pulled back” in time. 
    
    
     
       DESCRIPTION OF THE DRAWING 
       The present invention will hereafter be described with reference to the accompanying drawings, of which: 
         FIG. 1  is a block diagram of one embodiment of a Signal Prediction System, which is comprised of a Prediction Controller (PC), multiple Geometric Sampling Units (GSUs) and a Prediction Accumulation Multiplier (PAM); 
         FIG. 2  is a description of the method followed by the Prediction Controller; 
         FIG. 3  is a description of the method followed by each Geometric Sampling Unit; 
         FIG. 4  is a description of the method followed by the Prediction Accumulation Multiplier; and 
         FIG. 5  is an example output of the method, calculating the future value of a sinusoidal function. 
     
    
    
     DESCRIPTION OF THE INVENTION 
     The invention is a system and method that predicts an estimate of a future value of a signal from prior measured values of the signal. The times when the signal is measured include a baseline time and a collection of incrementally subsequent times. The baseline time is the time at which the first measurement of the signal is made. The time increments—from the baseline time to each of the succeeding measurement times—form sets of geometric sequences. The predicted future value of the signal is obtained merely by multiplying and dividing the prior measured signal values. 
     The mathematical basis for the method is a theorem in mathematical analysis that was discovered by the inventor. The method applies only to signals that are not negative. However, a bounded signal that takes on negative values can be adapted for the method, by adding to the signal a sufficiently-large positive bias. 
     System Architecture 
     One example embodiment of the system, which we call the Signal Prediction System (SPS) is shown in  FIG. 1 . The architecture of the SPS closely parallels the structure of the method. The SPS  101  comprises a Prediction Controller (PC)  102 , multiple Geometric Sampling Units (GSUs), e.g.  103 , and a Prediction Accumulation Multiplier (PAM)  105 . 
     The PC accepts user input parameters, and distributes to the PAM and to each of a number of GSUs, the parameters they require for the prediction. The system comprises at least one GSU for each geometric sequence of measurement times used by the method. The basic functions of a GSU are to measure the signal values at the baseline time and the subsequent times for one geometric sequence, normalize each value, raise each normalized value to an appropriate power, and report the result or its inverse to the PAM. Each GSU has access to the signal  104  whose future value is to be predicted, and has means to measure the magnitude of the signal. The PAM multiplies the values received from the GSUs, keeping track of when the GSUs have all indicated that they have finished reporting the results of their measurements. When this occurs, the PAM outputs its product, which is the predicted future value of the signal. The process may then be repeated, if the user desires a continuing stream of periodic signal predictions. The number of geometric sequences to be used, the measurement times appropriate to each geometric sequence, and the appropriate exponent to be used in calculating the result of each measurement, are described below. 
     Process of the Prediction Controller 
       FIG. 2  is a flowchart of the method followed by the Prediction Controller. The method uses several parameters input by the user of the SPS, and other parameters calculated therefrom by the PC that are used by the GSUs and the PAM. 
     In step  201 , the PC collects parameters input by the user of the SPS. They include the following:
         M is a positive integer that determines the number of geometric sequences of time increments used in the prediction. The number of geometric sequences used by the method is 2 M −1. Since there is one GSU for each geometric sequence, the SPS must contain at least 2 M −1 GSUs to make the prediction. M is an optional user input. If the user does not provide a value, the PC uses a default value, equal to log 2 (N GSU +1), where N GSU  is the largest integer equal to one less than a power of two, and is also less than or equal to the number of GSUs in the system.   N is a positive integer that determines the number of time increments in each of the geometric sequences.   N cycle  is the number of consecutive signal predictions requested by the user. A negative value for N cycle  is interpreted by the SPS as a request for an unending stream of successive periodic signal predictions.   t 0  is the baseline time of the first signal measurement used in the prediction.   Δs, the sampling interval, is the length of time during which the signal will be sampled for one prediction. The last signal measurement during one cycle is made at time t 0 +Δs.   Δp, the prediction interval, is the length of time between when the last signal measurement is made and the future time for which the value of the signal is being predicted.   ΔT cycle  is the time requested between successive periodic signal predictions.
 
From the user input, the PC in step  202  calculates:
   N GSU =2 M −1, the number of GSUs to be used for the requested prediction;   P=1+Δp/Δs, a measure of the power or range of the prediction, used solely to calculate the geometric ratio r;   r=P/(P M −1) 1/M , the common geometric ratio of all the geometric sequences used in the prediction; and   Δt=Δs+Δp, the time between the baseline time t 0  and the time for which the future value of the signal is being predicted.       

     In step  203  the PC sends to each of the N GSU  GSUs participating in the prediction the following parameters: N, N cycle , r, t 0 , Δt, and ΔT cycle . 
     In step  204  the PC generates all of the non-empty subsets of the first M positive integers, including the so-called improper subset containing all M integers; the PC assigns a unique subset to each of N GSU  GSUs; and the PC sends that subset to its GSU. For the k th  GSU, this subset, called its generating set, will be referred to as S k . The post-baseline geometric sequence of times when the GSU measures the signal depends upon its generating set.  FIG. 1  illustrates the case of M=3, in which 7 GSUs are required; each GSU is labeled with its generating set of integers. 
     Finally, the PC sends to the PAM the parameters it requires: N GSU , N cycle , t 0 , Δt, and ΔT cycle . 
     Process of the Geometric Sampling Unit 
       FIG. 3  is a flowchart of the method followed by the k th  Geometric Sampling Unit. 
     In step  301  the GSU receives the parameters sent to it by the PC. In step  302  the GSU receives S k , the unique generating set of integers assigned by the PC to the k th  GSU. 
     In step  303 , the GSU calculates the geometric sequence of time increments Δt k,n  that will be added to t 0  to form its set of measurement times beyond t 0 . The time increments are given by Δt k,n =Q k ·Δt·r n /r N+1 , where Q=Π jεs     k   (r j −1) 1/j , |S k | is the number of integers in the set S k , and the index n runs from 1 to N−|S k |+1. 
     The GSU keeps a count of two things: n cycle  counts how many cycles of measurements have been started, and n counts the number of the time increments used so far by a GSU in each measurement cycle. A cycle is the process for making all of the measurements, and doing all of the calculations, required for a single signal prediction. In step  304 , the GSU initializes n cycle . In step  305 , the GSU increments n cycle  and initializes n. 
     In step  306 , the GSU waits for the current time t to equal time the t 0 , whereupon in step  307  it measures the magnitude of the signal v 0  at the time t 0 . 
     Most of the signal measurements are normalized, by dividing them by v 0 . But the predicted signal value requires one unnormalized factor of v 0  in its numerator. This is accomplished by each GSU in step  308  testing whether its generating set is equal to {1}. Only the unique GSU that passes this test sends the value ƒ=v 0  to the PAM, along with a flag value of zero, in step  309 . A flag value of zero indicates to the PAM that the GSU is not yet done sending all of its signal prediction factors for the current measurement cycle to the PAM. 
     In step  310  the GSU increments n, beginning the process of measuring the signal for the n th  time increment beyond t 0 . In step  311  the GSU waits until the current time t reaches t 0 +Δt k,n , the time associated with the n th  time increment of the k th  geometric sequence; at that time it measures the magnitude of the signal v k,n  in step  312 . In step  313  the GSU tests whether the number of integers in its generating set, |S k |, is odd or even. If it is odd, in step  314  the GSU calculates the next prediction factor ƒ that it will send to the PAM, by calculating the normalized signal value, v k,n /v 0 , and raising it to the power given by the binomial coefficient ( |S     k     |−1   N−n ). If it is even, in step  315  the GSU calculates the next prediction factor ƒ that it will send to the PAM, by calculating the inverse of the normalized signal value, v 0 /v k,n , and raising it to the power given by the binomial coefficient ( |S     k     |−1   N−n ). 
     In step  316  the GSU compares n, the number of post-t 0  measurements that have been made, with the number of such measurements that are to be made in the current measurement cycle, N−|S k |+1. If they are not equal, in step  317  the GSU sends the prediction factor ƒ to the PAM with a flag value of zero; it then loops back to step  310  to begin the next signal measurement of the cycle. If they are equal, in step  318  the GSU sends the prediction factor ƒ to the PAM with a flag value of one, and proceeds to step  319 . A flag value of one indicates to the PAM that the GSU has finished reporting its prediction factors. 
     At step  319  the GSU checks whether the count of completed measurement cycles, n cycle , equals the number to be done, N cycle . If so, the GSU stops. If not, in step  320  the GSU increments t 0  by ΔT cycle , and loops back to step  305  to begin the next measurement cycle. Note that if the user inputs a negative value for N cycle , the GSU will always loop back to step  305 , and the GSU will report a continuing stream of signal prediction factors to the PAM. 
     Process of the Prediction Accumulation Multiplier 
       FIG. 4  is a flowchart of the method followed by the Prediction Accumulation Multiplier. 
     The process of the PAM begins in step  401  when it receives from the PC the parameters N GSU , N cycle , t 0 , Δt, and ΔT cycle . In step  402  the PAM calculates t p =t 0 +Δt, the future time for which the prediction of the signal is to be made. In step  403  the PAM initializes n cycle  to zero, which it increments in step  404 . In step  404  the PAM also initializes n done  to zero; n done  counts the number of GSUs that have finished reporting the results of their measurements to the PAM for the current cycle. 
     In step  404  the PAM also initializes the quantity v p  to unity. The purpose of the PAM is to produce the predicted value of the signal v p  at time t p . The PAM incorporates all of the factors of the predicted signal value, which are sent to it by the GSUs, into the quantity v p —including the single factor of v 0 . The PAM does so by multiplying the current value of v p  serially by each factor received; therefore, the value of v p  is initialized to unity. 
     In step  405  the PAM receives two values, ƒ and a flag value, from a GSU. In step  406  the PAM multiplies the current value of v p  by this factor, thereby incorporating this factor into the prediction. In step  407  the PAM checks whether this factor is the last to be received during this measurement cycle from the GSU that sent it. If the flag value is zero, it is not, and the PAM loops back to step  405  to receive the next factor sent by a GSU. If the flag value is one, this is the last factor to be received from this GSU in the current cycle; and the PAM proceeds to step  408 , in which it increments n done , the count of GSPs that are done with this cycle of measurements. 
     In step  409  the PAM compares the number of GSUs that are done with the number of GSUs participating in the prediction. If they are not equal, the PAM returns to step  405  to receive the next factor sent by a GSU that is not yet done. If all GSUs are finished reporting their measurement factors, in step  410  the PAM outputs two values: v p , the predicted signal value, and the time t p  for which v p  is the predicted value. 
     In step  411  the PAM checks whether the number of cycles completed is equal to the number of cycles to be performed. If so, the PAM stops; if not, it increments both t 0  and t p  by ΔT cycle  in step  412 , before looping back to step  404  to begin the next cycle. If the user has input a negative value for N cycle , the PAM always proceeds from step  411  to step  412 , and will produce a continuing stream of periodic signal predictions and their times. 
     Example Output 
       FIG. 5  is an example of the output of the method. The method was used to calculate the future value of an analytic function, namely ƒ(t)=1+(½)sin(t). The solid line is the function ƒ. The dashed line is the pullback of the function ƒ, namely ƒ(t+p). The dots on the dashed line are predictions of future values of the function ƒ, calculated using the method of the present invention. The dots on the solid line are values of the function itself. Observe that (1) the predicted values of the function do, in fact, lie on the pullback&#39;s dotted line, and (2) the value of the ordinate at these times is equal to the corresponding value of the function itself, a time interval p later. The prediction uses the values M=4, Δs=π/6, Δp=π/12, and N=500. The predictions have a time spacing equal to Δs, as they would have if the method were used on an actual signal to produce a stream of predictions, with sampling interval Δs. The calculations and graphs were produced using Mathematica. 
     Other embodiments of the invention will be apparent from the foregoing description to those of ordinary skill in the art, and such embodiments are likewise to be considered within the scope of the invention as set out in the appended claims.