# Patent

## Title
Energy-efficient time-stampless adaptive nonuniform sampling

## Abstract

Described herein is a sampling system and related sampling scheme. The system and sampling scheme is based upon a framework for adaptive non-uniform sampling schemes. In the system and schemes described herein, time intervals between samples can be computed by using a function of previously taken samples. Therefore, keeping sampling times (time-stamps), except initialization times, is not necessary. One aim of this sampling framework is to provide a balance between reconstruction distortion and average sampling rate. The function by which sampling time intervals can be computed is called the sampling function. The sampling scheme described herein can be applied appropriately on different signal models such as deterministic or stochastic, and continuous or discrete signals. For each different signal model, sampling functions can be derived.

## Background
CROSS REFERENCE TO RELATED APPLICATIONS
This application claims the benefit of U.S. Provisional Application No. 61/504,440, which is hereby incorporated by reference in its entirety.


GOVERNMENT RIGHTS
This invention was made with government support under Contract No. FA9550-09-1-0196 awarded by the Air Force Office of Scientific Research. The government has certain rights in this invention.


FIELD OF THE INVENTION
The concepts described herein relate to sampling and more particularly to adaptive nonuniform sampling schemes.
BACKGROUND OF THE INVENTION
As is known in the art, there is an increasing trend for mobile phones, “smart” phones, sensors and other lightweight and battery-operated devices to increasingly affect the everyday life of human's. Such devices have already started to become more and more intelligent, equipped with a wide range of features.
The majority of these devices, however, are resource constrained. For example, the devices are typically powered by batteries, or even by energy scavenging, and thus the devices typically have strict power budgets. Thus, reducing power consumption of such devices is beneficial for battery lifetime.
One problem, however, is that many applications require such devices to continuously measure different quantities such as voice, acceleration, light or voltage levels. After processing these quantities and extracting required features, the devices then typically communicate information to humans or to other devices. A concern in all of these applications is the large amount of power which is consumed to continuously sample, process and transmit information.
As is also known, a significant challenge is posed by sampling a signal while at the same time trying to satisfy sampling rate and reconstruction error requirements. This is particularly true in certain applications within the signal processing domain. It should be appreciated that in many applications, energy consumed during a sampling process can be a significant part of a system's energy consumption.
A variety of sampling techniques are known. Sampling techniques which follow a Nyquist sampling theorem utilize an appropriate uniform sampling setup for band-limited deterministic signals. One problem with such an approach, however, is that some samples may be redundant because the maximum bandwidth of the signal may not be a good measure of signal variations at different times. Redundant samples result in extra power consumption in the sampling procedure as well as in processes which follow the sampling. For example, if it is necessary, to transmit samples to another location, having a relatively large number of additional samples results in higher transmission energy and/or in extra energy spent for compressing the samples.
As a way to more efficiently sample a signal, adaptive nonuniform sampling schemes have been proposed. Such adaptive nonuniform sampling schemes result in reduced power consumption since the number of redundant samples is decreased or, in some cases, even eliminated.
Several non-uniform adaptive sampling schemes are known. For instance, a non-uniform sampling scheme based upon level-crossings with iterative decoding has been proposed as has an approach based upon level crossings with a filtering technique which adapts the sampling rate and filter order by analyzing the input signal variations. Also, two adaptive sampling schemes for band-limited deterministic signals have also been proposed. One scheme is based upon linear time-varying low pass filters and another scheme is based upon time-warping of band-limited signals.
Such non-uniform sampling schemes give rise to at least two problems which make it difficult to apply these schemes in practical applications. First, non-uniform sampling schemes are designed for specific signal models (i.e., they are not generic). This is because it is difficult to determine the next sampling time step at each time (i.e. rate control). Second, it is necessary to keep (e.g. store) or transmit sampling times since they are required in the reconstruction process.
For a discrete stochastic signal, one sampling scheme samples uniformly at a fixed high sampling rate (e.g. using an analog to digital converter (ADC)). Source coding is then used to compress these samples approximately to their entropy rate before transmission. While this technique is theoretically optimal, in practice this technique has some inefficiencies in terms of extra sampling and processing power required. Moreover, to achieve desired performance levels, long blocks of samples are necessary to be able to use source coding efficiently. This is particularly true if statistical properties of the signal vary slowly in time. This block-based approach may lead to a large delay on the reconstruction side.
It would therefore, be desirable, to provide an adaptive, nonuniform sampling technique which is generic (i.e. can be used in a wide variety of applications) and which does not need to store or transmit sampling times.
SUMMARY OF THE INVENTION
It has, in accordance with the concepts, systems and techniques described herein, been recognized that a smart sampling scheme should take samples as needed for a particular application (i.e., the technique should utilize innovative samples). This approach leads to an adaptive sampling scheme which inherently is nonuniform.
With this understanding, a general technique for efficiently sampling signals in an adaptive way is provided. The technique reduces (or in some cases, even minimizes) a required sampling rate and therefore the energy consumed during a sampling process. Thus, the technique described herein can greatly improve the energy consumption of a device.
The adaptive nonuniform sampling framework described herein has two characteristics. First, the adaptive nonuniform sampling framework takes samples only when they are innovative for the considered application. This reduces the number of required measurements. Second, unlike traditional nonuniform sampling procedures, sampling times need not be transmitted since the receiver can recover them within the context of the framework. This saves transmission rate and power. This technique (or sampling framework) is referred to herein as Time-Stampless Adaptive Nonuniform Sampling (TANS) or Energy-Efficient TANS (ETANS). TANS can be used in a wide variety of applications including but not limited to modem systems to provide significant rate and power benefits.
One key idea of the TANS technique described herein is that time intervals between samples can be computed by using a function of previously taken samples. Therefore, keeping sampling times (time-stamps), except initialization times, is not necessary. The aim of this sampling framework is to have a balance between the reconstruction distortion and the average sampling rate. The function by which sampling time intervals can be computed is referred to as a sampling function.
This sampling structure can be applied appropriately on different signal models such as deterministic or stochastic, and continuous or discrete signals, and for each, a different sampling function can be derived.
In contrast to schemes which take samples of discrete stochastic signals uniformly at a fixed high rate using an ADC, the techniques described herein takes samples when they are innovative. Since the power consumed during the sampling process depends linearly on the sampling frequency, the time-stampless, adaptive, nonuniform sampling techniques described herein are more efficient in terms of power and processing time, than prior art techniques which uniformly sample at a fixed high rate using an ADC.
Furthermore, in contrast to block-based approaches which may lead to a large delay on the reconstruction side, the techniques described herein correspond to substantially real-time delay-free compression schemes. These schemes adaptively compress the signal by using local properties of the signal causally which results in reduced power consumption.
In one embodiment, a sampling family which can be applied on both deterministic and stochastic signals, satisfying sampling and reconstruction requirements is described. This sampling family is a class of locally adaptive sampling (LAS) schemes. In this sampling family, time intervals between samples are computed via a sampling function which is based upon previously taken samples. Hence, although it is a non-uniform sampling scheme, it is not necessary to keep sampling times. Thus, in accordance with the present concepts, system and techniques described herein, described herein is a real-time compression scheme which adaptively compresses a signal by using its local properties causally.
In one embodiment, the aim of LAS is to have the average sampling rate and the reconstruction error satisfy some requirements. Four different schemes of LAS are described herein with two schemes being designed for deterministic signals and two schemes being designed for stochastic signals.
In the schemes designed for deterministic signals, a Taylor Series Expansion (TSE) sampling function is derived. In one embodiment, the TSE assumes only that the third derivative of the signal is bounded, but requires no other specific knowledge of the signal. Then, a Discrete Time-Valued (DTV) sampling function is proposed, where the sampling time intervals are chosen from a lattice.
In the schemes designed for stochastic signals, two sampling methods based upon linear prediction filters are described. A first sampling method is a Generalized Linear Prediction (GLP) sampling function, and a second sampling function is a Linear Prediction sampling function with Side Information (LPSI). In the GLP method, one only assumes the signal is locally stationary. However, LPSI is specifically designed for a known signal model.
With this particular arrangement, an adaptive, nonuniform sampling framework which can be used on both deterministic and stochastic signals is provided. By taking samples only when they are innovative for the considered application, the number of required measurements is reduced. Also, since the receiver can recover the sample times, and a continuous stream of sampling times need not be transmitted. This saves transmission rate and power.
It should be noted that in conventional nonuniform sampling procedures, sampling times must be transmitted to the receiver which impacts the system transmission rate and also utilizes power.
It should be appreciated that sampling functions can use either fixed or variable window sizes. Alternatively still, a combination of both fixed and variable window sizes can be used. In systems which utilize a variable window size, the system dynamically learns to adjust the window (e.g. the number of samples) for a particular signal. In a fixed window system, the number of samples to use in a window is selected based upon the needs of the particular application. For applications which require a high degree of accuracy, a relatively large number of samples in each window is required (i.e. need a large M). Some factors to consider in selecting number of samples to use in a window include buffer size since the larger the value of M, the larger the buffer which will be needed. It should also be appreciated that the higher the value of M, the more complicated the implementation. Thus, a trade-off must be made between the number of samples needed, the power consumption, and the ability to predict the future of the next window with a desired level of accuracy.
For stochastic signals the sampling function prediction can be based upon a plurality of different methods such as a greedy Method or a Dynamic Programming Based Method. For deterministic signals, a Taylor Series Expansion or a Discrete-Time Valued Method can be used. In operation, the future of the signals is predicted, then depending upon the allowed distortion (or other error value or metric), the next sample is taken.
Thus, the general framework described herein provides at least two advantages: (1) the system is adaptive—i.e. it is possible to change time intervals based upon variations (ideally this is inherently in the design of the sampling function which is chosen); and (2) the system is time-stamp-less—i.e. there is no need to store or transmit sampling times after the first M sampling times because those times after the first M sampling times can be computed using the sampling function.
Schemes of TANS may be categorized into parametric and non-parametric methods. In parametric methods, the signal model is known a priori and the sampling function is designed for that model. In non-parametric schemes, the signal model is not known (or is known partially) and the sampling function learns the necessary characteristics of the signal by using the taken samples.
It should be appreciated that in the case of stochastic signals, there are primarily two general techniques for designing a sampling function: (1) a greedy sampling Function; (2) dynamic programming based methods; (or approximate dynamic programming based methods).
In the greedy approach, the system takes the next sample to minimize the sum of reconstruction costs and a sampling rate penalty.
Dynamic programming based methods are similar to the greedy method, but they also consider quality (Q) of the next sampling prediction or state. Thus, in the DP approach, the concept is trade-off between a present state and a future state (e.g. allow lower performance in a present state to improve a future state).
In accordance with one aspect of the concepts described herein, a method of designing a sampling function includes (a) obtaining an initial number of samples; (b) predicting a future sample upon the initial number of samples; (c) computing an error value of the predicted future sample; (d) comparing the error value to a threshold value (e.g. allowed distortion); (e) in response to the error value exceeding the threshold value, taking a sample; and (f) in response to the error value not exceed the threshold value increasing the sampling time and computing a new predicted future sample.
With this particular arrangement, a technique for adaptive, time-stamp-less sampling is provided. The technique is adaptive since it is possible to change time intervals based upon signal variations. In some embodiments, this characteristic is a result of a design of a selected sampling function. The technique is time-stamp-less since there is no need to store or transmit sampling times after the first M sampling times because those times after the first M sampling times can be computed using the sampling function.
In accordance with a further aspect of the concepts described herein, a method of sampling includes (a) obtaining samples of a signal; and (b) computing a next sample time only as a function of the previously taken samples.
With this particular arrangement, an adaptive and time-stampless sampling technique is provided. In one embodiment, computing a next sample time as a function of previously taken samples is performed by computing a next sample time as a function of only a predetermined number of previously taken samples (e.g. M previously taken samples).
In accordance with a still further aspect of the concepts described herein, a sampling method includes (a) obtaining M samples of a signal; and (b) computing a next sample time as a function of only M previously taken samples of the signal wherein the sampling is adaptive and self-synchronizing. The method further includes (c) recovering sampling times using only the sample values and the first M sample times taken of the signal.
In accordance with yet a further aspect of the concepts, systems, and techniques described herein, a sampling system and method in which time intervals between samples are computed as a function of previously taken samples is described. With this technique, sample intervals are computed via a sampling function corresponding to a time-stampless adaptive nonuniform sampling technique.
In accordance with a further aspect of the concepts, system and techniques described herein, a locally adaptive sampling (LAS) system and method designed for deterministic signals is described. In one embodiment, the system and method utilize a Taylor series expansion (TSE) sampling function. In one embodiment, the TSE only assumes the third derivative of the signal is banded (but requires no other specific knowledge of the signal)
In accordance with a still further aspect of the concepts, systems and techniques described herein, locally adaptive sampling (LAS) system and method for deterministic signals which utilizes a discrete time-valued (DIV) sampling function is described. In one embodiment, the LAS system and method utilize sampling time intervals are chosen from a lattice.
In accordance with a still further aspect of the concepts, systems and techniques a locally adaptive sampling (LAS) system and method for stochastic signals comprise a sampling method based upon a linear prediction filter which utilizes a linear prediction (LP) sampling function with side information (LPSI). This technique is specifically designed for a known signal model.
In one embodiment, a locally adaptive sampling (LAS) system and method utilizes sampling time intervals which are discrete values.
In one embodiment, a locally adaptive sampling (LAS) system and method for discrete stochastic signals utilizes a sampling function based upon a generalized linear prediction (GAP) filter. In one embodiment, this technique assumes that the signal is locally stationary.
In accordance with a still further aspect of the concepts, systems and techniques, a method for providing an appropriate sampling function for a time-stampless adaptive nonuniform sampling (TANS) system and method is described. Factors to consider in providing a sampling function include, but are not limited to: the particular application (e.g. the characteristics of the signals involved), the signal model, the reconstruction method and sampling requirements (e.g. sampling rate, distortion requirements, etc.).



BRIEF DESCRIPTION OF THE DRAWINGS
The foregoing features of this invention, as well as the invention itself, may be more fully understood from the following description of the drawings in which:
FIG. 1 is a plot of an amplitude of a continuous signal vs. time;
FIG. 2 is a block diagram of a system for sampling and transmitting data;
FIG. 3 is a flow diagram of a fixed window process for time-stampless adaptive nonuniform sampling (TANS);
FIG. 4 is a flow diagram of a process for time-stampless adaptive nonuniform sampling;
FIG. 5 is a flow diagram of a process for time-stampless adaptive nonuniform sampling;
FIG. 6 is a flow diagram of a process for designing a sampling function;
FIG. 7 is a plot of signal amplitude vs. time;
FIG. 8 is a plot of an EKG signal;
FIG. 8A is a plot of a reconstructed EKG signal using TANS; and
FIG. 8B is a plot of a reconstructed EKG signal using uniform sampling.



DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS
Before describing a system and process for a process for time-stampless adaptive nonuniform sampling (TANS), some introductory concepts and terminology are explained.
A deterministic signal is a signal which can be described by analytical expressions for all times (past, present, future). Thus, deterministic signals are predictable for arbitrary times and can be reproduced identically arbitrarily often.
A stochastic signal may be an analog or continuous parameter signals or may be made up of a plurality of discrete values (a so-called discrete stochastic signal) which is often represented as X(n) where n takes on a plurality of discrete values.
It should be appreciated that the systems and processes described herein for time-stampless adaptive nonuniform sampling can be applied to either deterministic or stochastic signals which are either continuous or discrete. Accordingly reference to or exemplary embodiments described herein which use continuous parameter signals should not be construed as limiting. Rather such examples are provided only to promote clarity in the text and to promote clarity of the broad concepts described herein related to the adaptive, nonuniform sampling framework.
Reference is sometimes made herein to specific applications. For example, energy efficient sampling and communication systems and health care/monitoring systems. It should be appreciated that the systems and processes described herein for time-stampless adaptive nonuniform sampling can be applied to a wide variety of different applications. In a broad sense, sampling can be considered as a query for information. The systems and techniques described herein can be used in any applications where it is necessary to reconstruct some function f(t) that can only be measured remotely. The systems and techniques described herein allow one to obtain a sample of the function f(t) at an arbitrary time when it is queried (e.g. queried over some communication medium). In such an application, a portion of the operational cost (e.g. power) is proportional to the number of samples which are obtained. It should be appreciated that in some applications, this part of the operational cost is dominant. Thus, in such applications, the systems and techniques described herein result in large operational cost benefits (e.g. less power consumption).
Referring now to FIG. 1, a time varying continuous signal 10 has a plurality of samples 12a-12h taken therefrom. A first plurality of samples, here samples 12a-12f, are taken inside a first window 14. In general, the first M samples are taken in the first window 14 at times ti−m+1 through ti. In the particular example of FIG. 1, M=6. Those of ordinary skill in the art will appreciate, however, that fewer or less than six (6) samples may be used. The particular number of samples M to use in any particular application depends upon a variety of factors.
FIG. 1 also illustrates a second window 16 which is the same size as first window 14 in terms of the number of samples. Thus, in this exemplary embodiment, window 16 also includes six (6) samples corresponding to samples 12b-12g. Thus, in this exemplary embodiment a fixed window size is used. It should, however, be appreciated that in other embodiments a variable window size may be used (i.e. the windows need not contain the same number of samples).
In operation, the future of the signals is predicted, then depending upon the allowed distortion (or other error value or metric), the next sample is taken.
With the above arrangement, Ti may be expressed as

Ti=f(X(ti), . . . Ti+1)=f(X(Ti+1), . . . X(Ti−m+2), ti+1, . . . ti−m+2)

In this example, a sampling function with order M may be represented as f(.). It should be noted the sampling function is a function of previously taken samples as opposed to being a function of the entire signal. By not depending upon the entire signal, if the signal has a low signal variation, then the sampling time is increased (i.e. the time between samples is increased). On the other hand, if the signal has a high signal variation, then the sample time is decreased (i.e. the time between samples is decreased). It should also be noted that it is not necessary to keep sampling times.
Designing appropriate sampling functions depends upon a variety of factors including, but not limited to the application, the signal model, the reconstruction method, other reconstruction requirements, the sampling rate, the allowed distortion level, etc. . . . .
For example, in a medical application such as a continuous health monitoring application, such as monitoring an EKG signal, the EKG signal is known to contain both low and high frequency components. In this case, a generic sampling function (as opposed to an application specific sampling function) can be used. In one embodiment, a generic sampling function can be derived by using a Fourier Transform and the Cauchy-Schwarz inequality:




  
    T
    i
  
  =
  
    
      (
      
        
          p
          c
        
        ⁢
        
          1
          
            
              w
              ⁡
              
                (
                
                  t
                  i
                
                )
              
            
            2
          
        
      
      )
    
    
      1
      ⁢
      
        /
      
      ⁢
      3
    
  




where





  
    w
    ⁡
    
      (
      ti
      )
    
  
  =
  
    
    
      
        
          X
          
            (
            
              t
              i
            
            )
          
        
        -
        
          X
          
            (
            
              t
              
                i
                -
                1
              
            
            )
          
        
      
      
        
          t
          i
        
        -
        
          t
          
            i
            -
            1
          
        
      
    
    
  




where

w(ti) is an approximation of the signal slope at time ti;
c is a sampling parameter; and
p is the signal power.
It should be noted that the higher the derivative at time ti, the higher the signal variations at this time and thus, the smaller the sampling step size.
An example of a sampling function with discrete steps is




  
    T
    i
  
  =
  
    {
    
      
        
          
            
              
                
                  T
                  
                    i
                    -
                    1
                  
                
                +
              
              ∈
              
                
                  w
                  ⁡
                  
                    (
                    ti
                    )
                  
                
                <
                th
              
            
            ,
          
        
      
      
        
          
            
              
                T
                
                  i
                  -
                  1
                
              
              ⁢
              th
            
            ,
            
              ≤
              
                w
                ⁡
                
                  (
                  ti
                  )
                
              
              ≤
              
                th
                2
              
            
          
        
      
      
        
          
            
              
                T
                
                  i
                  -
                  1
                
              
              -
            
            ⁢
            
              ∈
              ′
            
            ⁢
            
              
                w
                ⁡
                
                  (
                  ti
                  )
                
              
              ≥
              
                th
                2
              
            
          
        
      
    
    }
  




in which





  
    w
    ⁡
    
      (
      ti
      )
    
  
  =
  
    
      
      
        
          
            
              X
              ti
            
            -
            
              t
              
                i
                -
                1
              
            
          
          
            T
            
              i
              -
              1
            
          
        
        -
        
          
            
              X
              
                (
                
                  ti
                  -
                  1
                
                )
              
            
            -
            
              X
              
                (
                
                  ti
                  -
                  2
                
                )
              
            
          
          
            T
            
              i
              -
              2
            
          
        
      
      
    
    
      
        (
        
          
            T
            
              i
              -
              1
            
          
          +
          
            T
            
              i
              -
              2
            
          
        
        )
      
      /
      2
    
  




As noted above, the sampling structure described above can be used with both deterministic and stochastic modeling and analysis. For example, Taylor Series Expansions and Discrete-Time Valued methods can be used for deterministic signals while for stochastic signals the prediction can also be based upon a plurality of different methods such as a greedy Method, a Dynamic Programming Based method or a Generalized Linear Prediction method.
It should be appreciated that while the same number of samples are used in windows 14, 16 (i.e. fixed window sizes), variable window sizes can also be used.
In a fixed window system, a number of samples to use in a window are selected based upon the needs of the particular application. For applications which require a high degree of accuracy, a relatively large number of samples in each window is required (i.e. need a large M). Some factors to consider in selecting number of samples to use in a window include buffer size since the larger the value of M, the larger the buffer which will be needed. It should also be appreciated that the higher the value of M, the more complicated the implementation. Thus, a trade-off must be made between the number of samples needed, the power consumption, and the ability to predict the future of the next window with a desired level of accuracy.
In systems which utilize a variable window size, the system dynamically learns how to adjust the window (e.g. the number of samples) for a particular signal.
It should also be appreciated that a combination of both fixed and variable window sizes can be used and that some systems may dynamically change between fixed and variable window sizes.
Thus, the general framework described herein provides at least two advantages: (1) the sampling system is adaptive—i.e. it is possible to change time intervals based upon variations (ideally this is inherently in the design of the sampling function which is chosen); and (2) the sampling system is time-stamp-less—i.e. there is no need to store or transmit sampling times after the first M sampling times because those times after the first M sampling times can be computed using the sampling function.
As mentioned above, in the case of stochastic signals, there are primarily two general techniques for designing a sampling function: (1) a greedy Sampling Function; (2) Dynamic Programming Based Methods; (or approximate dynamic programming based methods). In the greedy approach the system takes the next sample to minimize the sum of reconstruction costs and a sampling rate penalty. Dynamic programming based methods are similar to the greedy method, but they also consider quality (Q) of the next sampling prediction or state. Thus, in the DP approach, the concept is trade-off between a present state and a future state (e.g. allow lower performance in a present state to improve a future state).
Referring now to FIG. 2, a sampling and transmission system includes a processing device 30 which comprises an analog to digital converter (ADC) 32 which samples or converts signals 33 provided thereto into a stream of bits which may be grouped as digital words. Signal 33 may correspond to either deterministic or stochastic signals which are either continuous (analog) or discrete.
ADC 32 operates in accordance with a sampling function which defines a time-stampless, arbitrary and nonuniform sampling rate. The particular sampling function selected for any particular application is selected based upon a variety of factors related to the requirements of the particular application including, but not limited to factors such as the particular application, the signal model, the reconstruction method, other reconstruction requirements, the sampling rate and the allowed distortion level.
At the output of ADC 32, the stream of digital words are coupled to a transmission device 34 and also to a control logic element 36. Control logic element 16 may include a buffer memory element (not shown in FIG. 2) and may be under control of a system controller (not shown in FIG. 2) via control signals on control lines (not shown in FIG. 2). The sampling rate of ADC 32 is under control of control logic element 36 via control signals on control lines 38 (i.e. control logic element 36 implements the sampling function). After a sufficient amount of data has been collected in control logic element 16, the control logic element 16 computes a time at which a sample should be taken by ADC 12.
Significantly, the sampling function is a function of previously taken samples (as opposed to being a function of the entire signal). Furthermore, the sampling function causes the system 30 to take samples only when they are innovative for the particular application (e.g. for the signal being sampled). This results in fewer samples being taken. Since the power consumed by system 30 is largely dependent upon sampling frequency, the technique results in system 30 being more efficient in terms of power and processing time, than prior art techniques.
Also, since the time intervals between samples are computed using a function of previously taken samples, it is not necessary to keep sampling times. This results in further power efficiencies since less it is not necessary to transmit sampling times via transmission device 34.
FIGS. 3-6 are a series of flow diagrams showing exemplary processes to perform time-stampless adaptive nonuniform sampling (TANS). Such a process may be performed, for example, by a processing apparatus which may, for example, be provided as part of a sampling system such as that shown in FIG. 2. The rectangular elements (e.g. block 40 in FIG. 3) in the flow diagram(s) are herein denoted “processing blocks” and represent steps or instructions or groups of instructions. Some of the processing blocks can represent an empirical procedure or a database while others can represent computer software instructions or groups of instructions. The diamond shaped elements in the flow diagrams (e.g. block 50 in FIG. 3) are herein denoted “decision blocks” and represent steps of instructions or groups of instructions which affect the processing of the processing blocks. It should be noted that some of the processes described in the flow diagram may be implemented via computer software while others may be implemented in a different manner e.g. via an empirical procedure.
Alternatively, some of the processing blocks can represent steps performed by functionally equivalent circuits such as a digital signal processor circuit or an application specific integrated circuit (ASIC). The flow diagram does not depict the syntax of any particular programming language. Rather, the flow diagram illustrates the functional information one of ordinary skill in the art requires to perform the steps or to fabricate circuits or to generate computer software to perform the processing required of the particular apparatus. It should be noted that where computer software can be used, many routine program elements, such as initialization of loops and variables and the use of temporary variables are not shown. It will be appreciated by those of ordinary skill in the art that unless otherwise indicated herein, the particular sequence of steps described is illustrative only and can be varied without departing from the spirit of the concepts, systems and techniques described herein.
Referring now to FIG. 3, an exemplary time-stampless adaptive nonuniform sampling (TANS) process for a fixed window system begins in processing block 40 by selecting a number of samples to use in each window (hence the windows are said to be “fixed”). Processing then proceeds to processing block 42 in which at least a first M samples within the first window (e.g. window 14 in FIG. 1) are taken.
Next, as shown in processing block 44, a sampling function is used to compute the next sampling time. This means that a sample should be taken after a specific amount of time (i.e. there is no need to keep checking; it should be noted that FIG. 4 shows a variation of the process in which the process keeps checking to see when it is time to sample). In one embodiment, processing block 44 may be accomplished as described below in conjunction with processing blocks 82, 84 of FIG. 6.
It should be appreciated that the sampling function is known on both the sampling and the reconstruction sides of a system employing the TANS technique. It should also be appreciated that the next sampling time depends upon samples taken before that time. As shown in processing block 46, at the appropriate time, the next sample is taken and the window (e.g. window 14 in FIG. 1) slides.
Decision box 50 implements a loop in which if a decision is made to keep sampling, then processing returns to processing block 44 where the next sampling time is computed using the sampling function. If in decision block 44 a decision is made not to keep sampling, then processing ends.
Referring now to FIG. 4, another exemplary embodiment of a time-stampless adaptive nonuniform sampling process begins in processing block 52 by obtaining a plurality of initialization samples. Processing then proceeds to processing block 54 in which a sample is taken. Next, as shown in processing block 56, a sampling interval is computed using a sampling function. Processing then proceeds to decision block 58 in which a loop Is implemented in which it is determined whether it is time to sample (i.e. the process keeps checking to see when it is time to sample). Once it is time to sample, processing proceeds to processing block 54 where a sample is taken and then processing flows to blocks 56, 58.
Referring now to FIG. 5, another exemplary embodiment of a process for time-stampless adaptive nonuniform sampling begins by obtaining initialization samples and then predicting future samples as shown in processing blocks 60, 62.
Next, as shown in processing block 64, error values of the predicted samples are computed and then as shown in processing block 66, the next sampling time is determined based upon the error values.
Processing then proceeds to processing block 68 in which a next sample is taken at an appropriate time. If the sample taken is a last sample in a given window, then the window “slides” as shown in processing block 70.
Processing then proceeds to decision block 72 where a decision is made as to whether additional samples should be taken. If in decision blocking 72, a decision is made to keep sampling then processing flows to processing block 74 in which future samples are predicted using the new window. The processing in blocks 64-72 is then repeated.
If in decision block 72 a decision is made to not keep sampling then processing ends.
Referring now to FIG. 6, a flow diagram for another exemplary embodiment of a time-stampless adaptive uniform sampling process begins by initializing the system (e.g. by obtaining initialization samples) and predicting future samples as shown in processing blocks 80, 82. The prediction made in block 82 is then compared to a threshold value. The threshold value may correspond, for example, to an allowed distortion value. The threshold value may, of course, be based upon characteristics other than distortion. For example, one may attempt to maintain a certain probability of keeping the approximation error within a specified bound. Those skilled in the art can choose a characteristic appropriate for particular applications. In decision block 86, a decision is made as to whether a distortion threshold is exceeded. If the distortion threshold is exceeded, then a sample is taken and the window slides as shown in processing blocks 88, 90. Processing then returns to processing block 80 and processing blocks 82-90 are repeated.
If in decision bock 86, a decision is made that the predicted values did not exceed the threshold value, then processing flows to processing block 92 where the sampling step is increased and processing returns to processing block 82 and processing blocks 82-86 (and optionally 88, 90) are repeated.
As described hereinabove, a general sampling framework which improves a trade-off between sampling rate and distortion by adapting to local characteristics of a signal being sampled has been described. Significantly, the sampling times are a function (e.g. a causal function) of previous samples, and thus there is no need to stored and/or communicate sampling times. Furthermore, the techniques described herein above can be used with deterministic and stochastic modeling and analysis.
To illustrate the concepts described herein above, next described are three specific methods which can be used in accordance with the general concepts described herein for deterministic and stochastic signals. A Taylor series expansion technique and a Discrete-Time Valued technique are used for deterministic signals and a Generalized Linear Prediction (GLP) technique is used for stochastic signals.
In the examples to be described hereinbelow, the sampling scheme is causal because the next sampling time depends upon samples taken before that time. In general, however, the sampling scheme can be designed to be non-causal. It should also be noted that the reconstruction method can be causal or non-causal. The sampling scheme described herein is an adaptive process, because the sampling function depends upon local characteristics of the signal. Finding an appropriate sampling function of the sampling scheme depends upon sampling requirements such as the sampling rate, the distortion requirement, etc. Table 1 illustrates a taxonomy of proposed sampling functions.









TABLE I





Sampling 




Function
Blind
With Side Information







Deterministic
Taylor Series Expansion (TSE) 
Discrete Time Valued


Stochastic
Generalized Linear Prediction 
Linear Prediction with



(GLP)
Side Information









The aim of the sampling scheme described is to balance between the average sampling rate and the reconstruction distortion.
It should be appreciated that this objective is different from the objectives considered in change point analysis or active learning. In those techniques, the objective is to find points of the signal at which the statistical behaviors of the signal change, by causal or non-causal sampling, respectively.
Referring now to FIG. 7, a continuous signal 110 which may be expressed as X(t) has an ith sample taken at time ti. For deterministic signals, assuming the reconstruction method is line connection, the sampling function can be obtained via a Taylor Series Expansion (TSE). Thus, this method is referred to as the Taylor Series Expansion (TSE) method.
In this example, it is explained how a how a sampling function can be computed for a specific set up. This method (as well as the so-called GLP method to be described below) is referred to as a blind sampling method. Thus, Taylor's theorem is used to derive a suitable sampling function for deterministic signals. It should be appreciated that various instantiations of TANS can be derived by using Taylor's theorem, depending on signals of interest, the allowed complexity of the sampling function f, and the distortion requirement.
In the example below, an explanation is provided as to how a sampling function can be computed for a specific setup where X(t) is a continuous signal.
In this example, the following assumptions are made:
(C1) the order of the sampling function is two. In other words, the sampling function is a function of three previously taken samples which may be expressed as:

Ti=f(Uj=i−m+1i−1{Tj,Δj}).

(C2) The reconstruction method is connecting two adjacent samples by a line (this is referred to as non-causal linear interpolation).

Also, the distortion requirement is assumed to be as follows:
(C3) If {circumflex over (X)}(t) is the reconstructed signal, then |X(t)−{circumflex over (X)}(t)|<D1, for all t, where D1 is a sampling parameter.
(C4) it is assumed that the third derivative of X(t) is bounded by M;
The upper bound on the absolute value of the third derivative is used as a parameter in the sampling function and is also used in the analysis.
In the Taylor Series Expansion method of the locally adaptive sampling technique described herein, if |X′′′(t)| is uniformly bounded by a constant M, under assumptions (c1), (c2), the following sampling function satisfies the sampling requirement (c3).

Ti=arg max T 

s.t. (C1T+C2)T2≦D1  Equation (1)

where C1 and C2 are constants, defined as follows,




  
    
      C
      1
    
    =
    
      M
      3
    
  




  
    
      C
      2
    
    =
    
      
        
          
            
              
              
                
                  Δ
                  ⁢
                  
                    
                  
                  ⁢
                  i
                
                -
                1
              
            
            
              
              
                Ti
                -
                1
              
            
          
          -
          
            
              
                
                  Δ
                  ⁢
                  
                    
                  
                  ⁢
                  i
                
                -
                2
              
              
            
            
              
                Ti
                -
                2
              
              
            
          
        
        
          
            Ti
            -
            1
            +
            Ti
            -
            2
          
          2
        
      
      +
      
        
          
            M
            ⁢
            
              
            
          
          3
        
        ⁢
        
          
            
              
                (
                
                  
                    T
                    
                      i
                      -
                      1
                    
                  
                  +
                  
                    T
                    
                      i
                      -
                      2
                    
                  
                
                )
              
              2
            
            +
            
              
                (
                
                  T
                  
                    i
                    -
                    1
                  
                
                )
              
              2
            
          
          
            T
            
              i
              -
              2
            
          
        
      
    
  



It is insightful to investigate the behavior of Ti, with respect to different involved parameters in Equation (1).

First, it should be noted that increasing D1 leads to an increase in Ti. Intuitively, the higher the allowed distortion, the lower the sampling rate, and the larger the sampling time intervals.
Also it should be noted that the first term of C2 (i.e. |Δi−1/Ti−1−Δi−2/Ti−2|/((Ti−1+Ti−2)/2) can be viewed as an approximation of the second derivative of the signal X(t) (which may be expressed as |X′′(t)|) at time ti. It should be appreciated that use of a second derivative is but one of many ways to measure a signal. Since the reconstruction method is a first order linear filter, the higher the second derivative, the faster changes of the signal. Therefore, by increasing




  
    
      
        
          
          
            
              Δ
              ⁢
              
                
              
              ⁢
              i
            
            -
            1
          
        
        
          
          
            Ti
            -
            1
          
        
      
      -
      
        
          
            
              Δ
              ⁢
              
                
              
              ⁢
              i
            
            -
            2
          
          
        
        
          
            Ti
            -
            2
          
          
        
      
    
    
      
        Ti
        -
        1
        +
        Ti
        -
        2
      
      2
    
  
  ,
  
    T
    i
  




the value of Ti, should decrease.
While the above has considered deterministic signals, since the proposed sampling method is blind, it renders this method a well-suited choice for uncertain signals. For example, the method may be used when a signal is deterministic over stochastically varying time intervals.
Next described is a family of sampling functions where sampling time intervals are discrete values. Thus, this technique is referred to as a discrete time-valued method.
In this method, the sampling rate is being adapted based upon an estimation of local variations of the signal. This method can be applied to both continuous and discrete signals. In this example, a continuous time version of a signal is considered; however, its discrete time version can be also be derived.
If |X′′′(t)| (i.e. third derivative of X(t)) is uniformly bounded by a constant M, under assumptions C1 and C2 mentioned above, an estimate of local variation of the signal at time ti, by using previously taken samples, can be written as follows:




  
    w
    ⁡
    
      (
      
        t
        i
      
      )
    
  
  ⁢
  
    =
    △
  
  ⁢
  
    
      
        
          
          
            
              Δ
              ⁢
              
                
              
              ⁢
              i
            
            -
            1
          
        
        
          
          
            Ti
            -
            1
          
        
      
      -
      
        
          
            
              Δ
              ⁢
              
                
              
              ⁢
              i
            
            -
            2
          
          
        
        
          
            Ti
            -
            2
          
          
        
      
    
    
      
        Ti
        -
        1
        +
        Ti
        -
        2
      
      2
    
  




The error of this estimation can be bounded as follows:





  
    
    
      
        w
        ⁡
        
          (
          
            t
            i
          
          )
        
      
      -
    
    
  
  ⁢
  
    
      X
      ′′
    
    ⁡
    
      (
      
        t
        i
      
      )
    
  
  ⁢
  
    
    
      ≤
      
        
          M
          3
        
        ⁢
        
          
            
              
                (
                
                  
                    T
                    
                      i
                      -
                      1
                    
                  
                  +
                  
                    T
                    
                      i
                      -
                      2
                    
                  
                
                )
              
              2
            
            +
            
              
                (
                
                  T
                  
                    i
                    -
                    1
                  
                
                )
              
              2
            
          
          
            T
            
              i
              -
              2
            
          
        
      
    
  




Consider the following heuristic sampling function,





  
    T
    i
  
  =
  
    {
    
      
        
          
            f
            ⁢
            
              
            
            ⁢
            1
            ⁢
            
              (
              
                Ti
                -
                1
              
              )
            
          
        
        
          
            
              w
              ⁡
              
                (
                ti
                )
              
            
            ≤
            
              th
              ⁢
              
                
              
              ⁢
              1
              ⁢
              
                
              
              ⁢
              and
              ⁢
              
                
              
              ⁢
              Ti
            
            >
            Tmin
          
        
      
      
        
          
            Ti
            -
            1
          
        
        
          
            
              th
              ⁢
              
                
              
              ⁢
              1
            
            ≤
            
              w
              ⁡
              
                (
                ti
                )
              
            
            <
            
              th
              ⁢
              
                
              
              ⁢
              2
            
          
        
      
      
        
          
            f
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              (
              
                Ti
                -
                1
              
              )
            
          
        
        
          
            
              w
              ⁡
              
                (
                ti
                )
              
            
            ≥
            
              th
              ⁢
              
                
              
              ⁢
              2
              ⁢
              
                
              
              ⁢
              and
              ⁢
              
                
              
              ⁢
              Ti
            
            >
            Tmax
          
        
      
    
  




where

f1(Ti−1)>Ti−1 and

f2(Ti−1)<Ti−1.

    
    
        Tmin and Tmax make sampling time intervals to be bounded.
    
    


Thresholds th1 and th2 depend upon signal characteristics and sampling requirements. If W(ti) is smaller than a threshold, the signal's slope variations are small and, since f1(Ti−1)>Ti−1, the sampling rate can be decreased in this case. An analogous argument can be expressed when w(ti) is greater than a threshold.
An example of the above sampling function with linear increase or decrease of Ti can be expressed as follows,




  
    T
    i
  
  =
  
    {
    
      
        
          
            
              T
              
                i
                -
                1
              
            
            +
            
              ɛ
              1
            
          
        
        
          
            
              w
              ⁡
              
                (
                
                  t
                  i
                
                )
              
            
            ≤
            
              
                th
                1
              
              ⁢
              
                
              
              ⁢
              and
              ⁢
              
                
              
              ⁢
              
                T
                i
              
            
            >
            
              T
              min
            
          
        
      
      
        
          
            T
            
              i
              -
              1
            
          
        
        
          
            
              th
              1
            
            ≤
            
              w
              ⁡
              
                (
                
                  t
                  i
                
                )
              
            
            <
            
              th
              2
            
          
        
      
      
        
          
            
              T
              
                i
                -
                1
              
            
            -
            
              ɛ
              2
            
          
        
        
          
            
              w
              ⁡
              
                (
                
                  t
                  i
                
                )
              
            
            ≥
            
              
                th
                2
              
              ⁢
              
                
              
              ⁢
              and
              ⁢
              
                
              
              ⁢
              
                T
                i
              
            
            <
            
              T
              max
            
          
        
      
    
  




where ∈1 and ∈2 are positive constants. Note that, given Ti−1, there are only three possibilities for Ti, so, the sampling time intervals are discrete.

Next described is a family of sampling functions based upon a generalized linear prediction filter. Thus, this technique is referred to as a generalized linear prediction (GLP) method. This sampling method is for discrete stochastic signals.
In this method, the signal is locally stationary. This family of signals is described in detail below. The reconstruction method and the distortion measure used are as follows:

    (C7) the reconstruction method is using a generalized linear prediction filter; and
    (C8) if {circumflex over (X)}[n] is the reconstructed signal, we want to have E[(X[n]−{circumflex over (X)}[n])2]≦D2, where D2 is a sampling parameter.


A generalized linear prediction filter for stationary signals is next described. Assume X[n] is a stationary signal and further assume there are M samples of X[n] at times n−m1, n−m2, . . . , and n−mM. The aim is to predict linearly X[n] by using these known samples so that the expected mean square error is minimized (MMSE predictor).



  
    
      min
      
        
          w
          
            m
            ⁢
            
              
            
            ⁢
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          w
          mM
        
      
    
    ⁢
    
      
    
    ⁢
    
      E
      ⁡
      
        [
        
          
            
            
              
                X
                ~
              
              ⁡
              
                [
                n
                ]
              
            
            
          
          2
        
        ]
      
    
  




  
    subject
    ⁢
    
      
    
    ⁢
    to
  




  
    
      
        X
        ^
      
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        ∑
        
          k
          =
          1
        
        m
      
      ⁢
      
        
      
      ⁢
      
        
          w
          mk
        
        ⁢
        
          X
          ⁡
          
            [
            
              n
              -
              
                m
                k
              
            
            ]
          
        
      
    
  




  
    
      
        X
        ~
      
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        X
        ⁡
        
          [
          n
          ]
        
      
      -
      
        
          
            X
            ^
          
          ⁡
          
            [
            n
            ]
          
        
        .
      
    
  



A solution of this linear optimization can be called wmi* for 1≦I≦M. One difference of this setup with a traditional linear prediction is to predict X[n] by a set of non-uniform samples. In an optimal scheme, the error term should be orthogonal to all known samples as expressed by Equation (2):

E[X[n−mk]{tilde over (X)}*[n]]=0  Equation (2)

for k=1, . . . , M, where {tilde over (X)}*[n]=X[n]−Σk=1Mwmk*X[n−mk].

An auto-correlation function of X[n] can be written as shown in Equation (3):

r[i]=E[X[n]Xc[n−i]]  Equation (3)

where XC[n] is the conjugate of X[n]. Since this example deals with real signals, without loss of generality conjugation effects are ignored. Hence, by using Equations (2) and (3), the following set of linear equations are found:

r[−mk]=Σi=1Mwmi*r[mi−mk]  Equation (4)

for k=1, . . . , M. This can be expressed in matrix form as shown in Equation (5):

m=[m1, . . . ,mM]T 

Xmn=[X[n−m1], . . . ,X[n−mM]]T 

P=[r[−m1], . . . ,r[−mM]]T 

W*m=[w*m1, . . . ,w*mM]T 

R=E[(Xmn)(Xmn)T].

Thus, linear equations of Equation (4) can be written as a matrix multiplication

p=Rwmi*

For X[n] with zero mean, define,

σX2=E[|X[n]|2]=r[0]

σX2=E[|{tilde over (X)}*[n]|2|

Thus, for generalized liner prediction:

p=Rwmi*

σX2=r[0]−pTwm*

For LAS with a generalized linear prediction filter, and assuming that a signal [n] is a locally stationary signal, locally stationary processes can be used as a tool to model systems where their statistical behavior varies with time. Definitions of a locally stationary process are provided in S. Mallat, G. Papanicolaou, and Z. Zhang, “Adaptive covariance estimation of locally stationary processes,” Annals of Statistics, vol. 26, no. 1, pp. 1-47, 1998 and D. Donoho, S. Mallat, and R. von Sachs, “Estimating covariances of locally stationary processes: rates of convergence of best basis methods,” Statistics, Stanford University, Stanford, Calif., USA, Tech. Rep, 1998.
Intuitively, a locally stationary process is a process where one can approximate its local covariance coefficients within an error. The above-mentioned Mallat Reference approximates the covariance of a locally stationary process by a covariance which is diagonal in basis of cosine packets, while the above-mentioned Donoho reference proposes a method to estimate the covariance from sampled data.
For simplicity, a fixed window size is assumed. It should be appreciated, of course, that this can also vary by time.
A window WL[n] with length L can be defined as follows,




  
    
      W
      L
    
    ⁡
    
      [
      n
      ]
    
  
  =
  
    {
    
      
        
          1
        
        
          
            0
            ≤
            n
            ≤
            
              L
              -
              1
            
          
        
      
      
        
          0
        
        
          otherwise
        
      
    
  




XLni[n] is a truncated version of X[n] which has its samples over ni−L+1≦n≦ni.
That is:

XLni[n]=X[n],WL[n−ni+L−1].

For XLni[n], auto-correlation coefficients can be written as follows,

rnil[k]=E[XLni[n]XLni[n−k]]. 

By using these coefficients, for m=[0, l, . . . , M−l]T, where M<L, matrices can be defined as (XLni)L, PLnii, (wm*)Lni and RLni similarly to Equation (5) above. Since X[n] is assumed to be locally stationary, for any time n0 and any given ∈, there exists an appropriate L such that,

|E[|{tilde over (X)}[ni+1]|2]−rniL[0]+(PniL)T(w*m)niL|<∈,

Where

{tilde over (X)}[ni+1]|=X[ni+1]−((w*m)niL)T(Xnim)L 

L is referred to as a window size of the locally stationary signal and L0 and L1 are defined as the minimum and the maximum allowed window sizes, respectively. The stochastic nature of the signal affects L0 and L1.
Intuitively, since X[n] is locally stationary, its MMSE linear prediction filter with locally estimated autocorrelation coefficients leads to an approximately same error as the one of stationary signals. Now, a setup of LAS by using a MMSE generalized linear prediction filter for locally stationary signals can be introduced. Except being locally stationary, there are no other assumptions on the signal. Hence, this method is referred to as a blind sampling method.
Suppose X[n] is a locally stationary signal with window size L and there are M samples X[ni], X[ni−m2] . . . X[ni−mM]′ where 0<m2<m3< . . . <mM<L. Now, consider a truncated signal XLni[n] as defined above. If only taken samples of this truncated signal are used (i.e. X[n−mi] for 1≦i≦M), the approximations for RLni, PLni and (wm*)Lni.can be computed and are referred to as {circumflex over (R)}Lni, {circumflex over (P)}Lni and (ŵm*)Lni respectively.
If L is sufficiently larger than L0, we will have enough known samples in the truncated signal and these approximations can be close to RLni, PLni and (wm*)Lni. Then, one can linearly predict X[ni+Ni] by using samples X[ni], X[ni−m2]′ . . . , and X[ni−mM]. It is assumed that parameter L1 of the locally stationary signal is sufficiently large.
Hence, by using σX2=r[0]−pTwm* and |E[|{tilde over (X)}[ni+1]|2]−rniL[0]+(PniL)T(w*m)niL|<∈,

|E[|{tilde over (X)}[ni+1]|2]−{tilde over (r)}Lni[0]+({circumflex over (P)}Lni)T(ŵm*)Lni|<∈

where ∈ is a small positive constant and m=[Ni, Ni+m2, . . . , Ni+mM]. The reconstructed signal can be written as,

{circumflex over (X)}[ni+ni]=((ŵm*)Lni)TXmni+Ni.

A sampling function for this scheme chooses the greatest possible Ni to have the expected error less than a threshold value D2. Thus, this sampling function can be written as the following linear optimization setup:

Max Ni 

s.t. {circumflex over (X)}[ni+Ni]=((ŵm*)Lni)TXmni+Ni.

{circumflex over (P)}Lni={circumflex over (R)}Lni(ŵm*)Lni 

{tilde over (r)}Lni[0]−({circumflex over (P)}Lni)T(ŵm*)Lni|<D2 

It should be noted that, if the window size L is sufficiently larger than the minimum allowed window size L0, there are enough known samples in the window, and these approximations would be appropriate. However, if there are not enough known samples in the window, autocorrelation coefficients of the previous window can be used.
Next described is a sampling function based upon linear prediction with side information about the signal. Hence, this method is non-blind. Consider a signal model described as:

X[n]=αθnX[n−1]+Zθn[n]

where θn is the state of a hidden Markov chain (MC) with state transition probability p.

Suppose its parameters (i.e., αθn) are known for every n. Also, assume that the transition probability of the underlying MC, p, is small. These parameters form the side information. For reconstruction, a linear prediction filter is used.
Consider A={(R, MSE)} as a set of achievable rate distortion pairs for this signal model and consider the MSE of the error as a distortion measure. Similarly, As can be defined as As={(Rs, MSEs)}, a set of achievable rate-distortion pairs within state s. The next sample is taken when the prediction error (or, the noise variance) exceeds a threshold value D3.
For the signal model described above (i.e. X[n]=αθnX[n−1]+Zθn[n]), the following rate-distortion pairs are achievable,



  
    
      
        
          A
          =
          
          ⁢
          
            
              {
              
                R
                ,
                MSE
              
              )
            
            ❘
            
              (
              
                R
                ,
                MSE
              
              )
            
          
        
      
    
    
      
        
          
            =
            
            ⁢
            
              
                
                  1
                  2
                
                ⁢
                
                  (
                  
                    
                      1
                      /
                      
                        K
                        0
                      
                    
                    ,
                    
                      MSE
                      0
                    
                  
                  )
                
              
              +
              
                
                  1
                  2
                
                ⁢
                
                  (
                  
                    
                      1
                      /
                      
                        K
                        1
                      
                    
                    ,
                    
                      MSE
                      1
                    
                  
                  )
                
              
            
          
          }
        
      
    
  




  
    where
    ,
    
      

    
    ⁢
    
      
        MSE
        s
      
      =
      
        
          ∑
          
            i
            =
            1
          
          
            Ks
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          
            (
            
              1
              -
              
                α
                s
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  i
                
              
            
            )
          
          /
          
            K
            s
          
        
      
    
  




  and




  
    
      K
      s
    
    =
    
      {
      
        
          
            
              
                
                  log
                  ⁡
                  
                    (
                    
                      1
                      -
                      
                        D
                        3
                      
                    
                    )
                  
                
                /
                2
              
              ⁢
              
                
              
              ⁢
              log
              ⁢
              
                
              
              ⁢
              
                α
                s
              
            
          
          
            
              
                α
                s
              
              ∉
              
                {
                
                  0
                  ,
                  1
                
                }
              
            
          
        
        
          
            1
          
          
            
              
                α
                s
              
              =
              0
            
          
        
        
          
            0
          
          
            
              
                α
                s
              
              =
              1
            
          
        
      
    
  



where 0≦D3≦1 is a sampling parameter and s ∈{0, 1} represents the state of the Markov Chain. By using X[n]=αθnX[n−1]+Zθn[n]) for each state s, results in:




  
    
      
        
          
            X
            ⁡
            
              [
              
                n
                +
                K
              
              ]
            
          
          =
          
          ⁢
          
            
              α
              ⁢
              
                
              
              ⁢
              
                KsX
                ⁡
                
                  [
                  n
                  ]
                
              
            
            +
            
              
                ∑
                
                  i
                  =
                  1
                
                K
              
              ⁢
              
                
              
              ⁢
              
                
                  z
                  ⁡
                  
                    [
                    
                      n
                      +
                      i
                    
                    ]
                  
                
                ⁢
                
                  a
                  j
                  
                    k
                    -
                    i
                  
                
              
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              α
              ⁢
              
                
              
              ⁢
              
                KsX
                ⁡
                
                  [
                  n
                  ]
                
              
            
            +
            
              
                Z
                
                  s
                  ,
                  K
                
              
              .
            
          
        
      
    
  




  
    Hence
    ,
    
      

    
    ⁢
    
      
        σ
        
          Zx
          ,
          K
        
        2
      
      =
      
        1
        -
        
          α
          s
          
            2
            ⁢
            
              
            
            ⁢
            K
          
        
      
    
  



Consider a sample when the prediction error (or, the noise variance) exceeds a threshold value D3. Hence, for αs∉{0, 1} a maximum value of K is chosen to have:

1−αs2K≦D3 

Hence, at state s,

Ks=log(1−D3)/2 log(αs)

when αs∉{0, 1}.

It should be noted that cases when αs=0 or αs=1 are trivial.

Suppose MSEs(l)=E[(X[n+l]−{circumflex over (X)}[n+l])2] at state s.

If samples are taken at times n and n+Ks, then MSEs(0)=MSEs(Ks)=0.

For l∉{0, Ks}, MSEs(l)=σZs,i2=1−σs2l 

Hence, the average MSE at each state s (called MSEs) is:

MSEs=Σi=1Ks−1(1−αs2K)/Ks 

The foregoing description has in some instances been directed to specific embodiments. It will be apparent, however, that variations and modifications may be made to the described embodiments, with the attainment of some or all of their advantages.
For instance, a family of locally adaptive sampling schemes (sometime referred to as LAS) which can be applied on both stochastic signals has been described. In this sampling family, time intervals between samples can be computed by using a function of previously taken samples (referred to herein as a sampling function). Hence, although it is a non-uniform sampling, it is not necessary to keep sampling times. The aim of this sampling scheme is to have the average sampling rate and the reconstruction error satisfy some requirements. Four different schemes of LAS have been described to help explain different properties: Taylor Series Expansion (TSE) and Discrete Time Valued (DTV) methods for deterministic signals; Generalized Linear Prediction (GLP) and Linear Prediction with Side Information (LPSI) methods for stochastic signals. TSE and GLP were referred to as blind methods since they included a general condition on the considered signal (bounded third derivative for TSE, and being locally stationary for GLP). However, DTV and LPSI methods are non-blind, because the sampling scheme is specifically designed for a known signal model.
Accordingly, in view of the description provided hereinabove, it should now be apparent to those of ordinary skill in the art that the systems and processes described herein find use in a wide variety of applications.
Sensing, for example, is a process performed in any system interacting with the real world and one of the main power consumption contributors of low power devices. For this reason, the framework described herein can be applied to a wide variety of different sensing and other systems, enabling the development of new applications in the future.
For example, several research projects refer to continuous health monitoring by using either custom sensors or platforms based on commercial mobile phones, recording ECG signals and other human's vital information. The current approach for the design of these systems is to continuously sample the considered signals at a rate greater than or equal to the maximum rate of happening an event of interest. However, in the approach described herein, the sampling rate is adapted by using previously taken samples as described herein above. Furthermore, it is not necessary to keep sampling times. Hence, the scheme described herein achieves a lower power consumption in the sensing process.
For example, a generic sampling function can be designed by bounding the derivative of the signal by the integral of its Fourier transform and then using the Cauchy-Schwarz inequality as follows:

Ti=[(p/c)(1/(w(ti)2)]1/3 

In which:

p is the signal power;
c is a sampling parameter;
w(ti) is an approximation of a derivative of a signal at time ti where
i.e., w(ti)=abs[(Δi−1)/(Ti−1).
It should be noted that the higher the derivative at time ti, the higher the signal variations at this time, and the smaller the sampling step size. It should also be noted that, this sampling function is not designed specifically for ECG signals. In some simulations on ECG signals, a sampling function designed by using characteristics of ECG signals to provide more gain was used. Simulation results with real ECG signals indicate advantages of the approach described herein, reducing by approximately an order of magnitude the sampling rate compared to uniform sampling.
FIG. 8, for example, illustrates an ECG signal while FIGS. 8A and 8B illustrate two reconstructed ECG signals using the same number of samples (i.e., a down sampling factor of 10). FIG. 8A illustrates a reconstructed ECG signal using the techniques described herein while FIG. 8B illustrates a reconstructed ECG signal by uniform sampling. One can see that, the approach used in FIG. 8A provides a better reconstructed signal given the same sampling rate.
The framework described herein can also be applied to a majority of applications that involve the interaction of smartphones and humans as well as a surrounding environment. For instance, the use of smartphones, equipped with several sensors has been proposed for traffic monitoring, sound sensing, location tracking and many other scenarios. Although most of these proposed ideas seem promising applications in the future, the strict power constraints of portable devices are a main obstacle in their realizations. It is believed that the framework described herein can be an efficient solution in applications requiring continuous sampling and interaction with the real world. This is particularly true in view of data showing that sensors in a modern smartphone can consume approximately up to 60% of the overall power consumption when the phone is in sleep mode.
While exemplary applications of TANS have been describe herein, those of ordinary skill in the art will appreciate that TANS can also be used in a wide variety of other applications.
Accordingly, it is submitted that that the concepts and techniques described herein should not be limited to the described embodiments but rather should be limited only by the spirit and scope of the appended claims.

## Claims

1. A sampling method comprising:
(a) obtaining M samples of a signal using an analog-to-digital converter (ADC);
(b) computing a next sample time as a function of previously obtained samples of the signal wherein the sampling function is adaptive and time-stampless; and
(c) recovering sampling times using sample values and sample times from the M samples obtained from the signal.

2. The method of claim 1 wherein computing a next sample time as a function of previously obtained samples comprises computing a next sample time as a function of only M previously obtained samples.

3. A method of sampling a signal, the method comprising:
(a) obtaining M samples of the signal using an analog-to-digital converter (ADC);
(b) computing a next sample time as a function of only the M previously obtained samples of the signal wherein the sampling is adaptive, nonuniform, and self-synchronizing; and
(c) recovering sampling times using the sample values and the sample times taken of the first M samples of the signal.

4. A method of adaptive, nonuniform sampling, the method comprising:
identifying a sampling function;
obtaining a first set of M samples from a signal using an analog-to-digital converter (ADC), wherein the first set of M samples includes sample times and sample values;
obtaining additional samples from the signal wherein the samples are obtained at time intervals determined by applying the sampling function to one or more of the first set of M samples;
providing to a receiver: (a) the sampling function; (b) the sample times of the first M samples; (c) the values of the additional samples; and
recovering sampling times of the additional samples in the receiver using only the sampling function, the obtained sample values and sample times taken of the first M samples of the signal.

5. The method of claim 4 wherein recovering sampling times in a receiver comprises computing the sampling times via the sampling function.

6. The method of claim 4 wherein the signal being sampled corresponds to a stochastic signal and wherein the stochastic signal is locally stationary and wherein the sampling function is based upon a linear prediction filter which utilizes a General Linear Prediction (GLP) sampling function.

7. The method of claim 4 wherein the signal being sampled corresponds to a stochastic signal having a known signal model and the sampling function is based upon a linear prediction filter which utilizes a linear prediction sampling function with side information (LPSI).

8. A system comprising:
an analog-to-digital converter (ADC) configured to obtain samples of an input signal, one or more of the obtained samples having a sample value and a sample time; and
a control means, coupled to said ADC, said control means for controlling the times at which said ADC samples the input signal, said control means computing a next sample time as a function of previously obtained samples.

9. The system of claim 8 further comprising a transmission system coupled to said ADC and configured to transmit sample values obtained by the ADC.

10. The system of claim 9 further comprising a receiving system configured to receive sample values transmitted by said transmission system, said receiving system comprising means for recovering sample times associated with the received sample values using the sampling function.

11. The system of claim 8 wherein said control means is provided as a digital signal processor.

12. The system of claim 11 wherein said digital signal processor implements a real time compression scheme which adaptively compresses a signal using its local properties causally.

13. The method of claim 1 further comprising:
predicting a future sample based upon at least some of the M samples;
computing an error value of the predicted future sample; and
comparing the error value to a threshold value.

14. The method of claim 13 further comprising:
in response to the error value exceeding the threshold value, obtaining a next sample.

15. The method of claim 14 further comprising:
in response to the error value not exceeding the threshold value, increasing a sampling time and computing a new predicted future sample.

16. The method of claim 13 wherein predicting a future sample based upon at least some of the initial number of samples comprises predicting a future sample based upon all of the initial number of samples.

17. The method of claim 13 wherein the threshold value corresponds to an allowed distortion value.

18. The method of claim 1 wherein obtaining M samples of the signal comprises obtaining a first set of signal samples, the method further comprising:
using first set of signal samples to determine a sampling function to compute time intervals between samples; and
sampling the signal at a time determined by the sampling function.

19. The method of claim 18 wherein the sampling function is based upon a set of the M most recently taken samples.

20. The method of claim 18 wherein the sampling function is selected in accordance with sampling requirements and distortion requirements.

21. The method of claim 18 wherein:
in response to the signal being a stochastic signal, the sampling function is based upon one of: (1) the greedy method; or (2) a dynamic programming technique; and
in response to the signal being a deterministic signal, the sampling function is based upon one of: (1) a Taylor expansion series; (2) a discrete-time valued function.

22. The method of claim 3 further comprising:
predicting a future sample based upon at least some of the M samples;
computing an error value of the predicted future sample; and
comparing the error value to a threshold value.