System and method for compressive sensing

The present invention provides a system for use with an input signal and a clock signal. The system includes a physical random interval generator, a sampling analog-to-digital converter (ADC), a timing signal generator and a reconstructor. The physical random interval generator can generate a random output signal. The ADC can output a sampled output signal based on the input signal and the random output signal. The timing signal generator can output a timing signal based on the clock signal and the random output signal. The reconstructor can reconstruct an information signal based on the sampled output signal and the timing signal.

BACKGROUND

Reception and reconstruction of analog signals are performed in a wide variety of applications, including wireless communication systems, spectrum management applications, radar systems, medical imaging systems and many others. In many of these applications, an information-carrying analog signal is sampled, i.e., converted into digital samples. The information is then reconstructed by processing the digital samples.

The minimum sampling rate needed for perfect reconstruction of an arbitrary sampling method is known. Further, various methods for signal sampling and reconstruction are known in the art. Some sampling and reconstruction methods refer to bandpass or band-limited signals, and in particular to multi-band signals, i.e., signals that are confined to a finite set of spectral bands. Additionally known are methods for periodic non-uniform sampling of multi-band signals and methods for sampling and reconstruction of multi-band signals.

Various applications, particularly in the field of secure communications, require the production of truly random numbers at a high bit-rate. Most current random number generators (RNGs) typically employ complicated, yet ultimately deterministic, calculations, generating numbers that are, at best, pseudo-random. Other methods employ the inherent, and essential, randomness of quantum processes, since, in accordance with the laws of physics, there is no way, even in theory, to find a pattern within random numbers generated from quantum measurement. Such methods include radioactive decay (see, for example, U.S. Pat. No. 6,445,217, to Figotin, et al., issued Jun. 1, 2004) or outputs of a beam splitter to establish random numbers from the path of a photon (U.S. Pat. No. 6,309,139, to Dultz et al., issued Aug. 19, 2003). A further method uses thermodynamic processes such as diode current fluctuations or Johnson noise measured on the voltage across a resistor (see, for example, U.S. Pat. No. 6,271,263, to Nagai, issued May 27, 2003).

Compressive sensing is a promising new field that has unlocked novel devices such as the single pixel camera. Many demonstrations of compressive sensing involve a high speed clock somewhere in the signal chain, diminishing the advantages of slow and brief sampling that compressive sensing offers.

Compressive sensing is a technique for finding sparse solutions to underdetermined linear systems. An underdetermined system of linear equations has more unknowns than equations and generally has an infinite number of solutions. However, if there is a unique sparse solution to the underdetermined system, then the compressed Sensing framework allows the recovery of that solution. In electrical engineering, particularly in signal processing, compressed sensing is the process of acquiring and reconstructing a signal that is supposed to be sparse or compressible.

Sampling is the process of converting a signal (for example, a function of continuous time or space) into a numeric sequence (a function of discrete time or space). The Nyquist theorem states:If a function x(t) contains no frequencies higher than B hertz, it is completely determined by giving its ordinates at a series of points spaced 1/(2B) seconds apart.

In essence, the theorem shows that a band-limited analog signal that has been sampled can be perfectly reconstructed from an infinite sequence of samples if the sampling rate exceeds 2B samples per second, where B is the highest frequency in the original signal. If a signal contains a component at exactly B hertz, then samples spaced at exactly 1/(2B) seconds do not completely determine the signal

By extending the all-or-nothing conditional of the Nyquist theorem, compressive sensing promises to open up entire new realms of sensing techniques. In the areas of communications and RF signal detection, compressive sensing can potentially enable the capture and reconstruction of signals over large bandwidth with small, low-power hardware and extremely small numbers of samples.

Initial demonstrations of compressive RF sampling consisted of capturing high-bandwidth sparse signals with fast digitizers, which handily satisfy the Nyquist condition, followed by post-selecting a random subset of samples. Hypothetically, were one to only have access to that limited, random subset, one could successfully reconstruct the signal with high probability. Of course, the initial investment in performing high-speed digital sampling of the signal negates the need for the compressive alternative.

A second generation of compressive RF sensors developed around the concept of random demodulation in which the signal of interest is mixed with a pseudo-random phase sequence and sampled with a lower-speed ADC. While this approach provides power savings with its lack of a high-speed ADC, it still requires high-speed digital hardware to generate the pseudo-random sequences. In this way, it does not fully realize the advantages of compressive sensing for RF signals.

What is needed are improved systems and methods for performing compressive sensing.

BRIEF SUMMARY

The present invention provides a compressive sensing technique for performing reconstruction of signals using a low frequency clock signal as compared to the frequency components of the signals being reconstructed.

In accordance with aspects of the present invention a system is provided for use with an input signal and a clock signal. The system includes a physical random interval generator, a sampling ADC, a timing signal generator and a reconstructor. The physical random interval generator can generate a random output signal. The ADC can output a sampled output signal based on the input signal and the random output signal. The timing signal generator can output a timing signal based on the clock signal and the random output signal. The reconstructor can reconstruct an information signal based on the sampled output signal and the timing signal.

DETAILED DESCRIPTION

In accordance with aspects of the present invention, a compressive sensor system does not require a high-speed clock in the signal chain. By employing a physical source of entropy and applying a sub-clock resolution timing scheme to record randomly-timed digital samples, a compressive sensor is demonstrated enabling reduced signal measurement energy requirements when extrapolated to higher bandwidths.

Most conventional sources of entropy are in fact ‘pseudorandom.’ That is, in lieu of generating true physically random numbers, these sources use computational complexity to generate numerical sequences that approximate random ones. These techniques were developed primarily for Monte Carlo simulations or cryptographic applications, where high-speed digital hardware is cheap and ubiquitous. The demands of compressive sensing are entirely antithetical. Compressive sensing has unique advantages where the hardware itself must be compact and low-power. Thus, computational methods for generating entropy are not ideal. Instead, aspects of the present invention make use of a significant body of existing research on physical sources of entropy, non-limiting examples of which include thermal sources based on noisy resistors, chaotic sources based on optical intensity noise, and quantum random number generators based on the single-photon statistics of severely attenuated lasers.

Most of these sources were originally developed for advanced cryptographic applications where very high-quality random numbers are vital. However, the demands on entropy for compressive sensing are much more relaxed; the random sampling matrix must simply satisfy restricted isometry rather than pass stringent, often poorly defined, tests for cryptographic randomness. Thus, instantiation of any physical source of entropy for compressive sensing in accordance with the present invention can be greatly simplified.

An example embodiment uses the physical hardware of a quantum random number generator. This setup operates by measuring the time between single-photon emissions of a strongly attenuated diode laser using a Geiger-mode avalanche photodiode. The Poisson distribution of photon number for coherent light sources gives rise to an exponential distribution, p(x)=λe−λxfor x≧0, with rate parameter λ, of photon arrival time intervals when the source is strongly attenuated.

For cryptographic applications, where regularly timed and uniformly distributed random numbers are vital, the intervals between photon arrival events must be measured using a high-speed digital counter. Those intervals must then be whitened and buffered to generate cryptographic random sequences. Since interest is in random intervals rather than regularly timed random numbers, the present invention is able to eliminate the timing and buffering stages.

Furthermore, even exponentially distributed sampling time intervals still results in a random sampling matrix that satisfies the Restricted Isometry Property (RIP) required of the compressive sensing sampling matrix, eliminating the need for any pulse-shaping or digital whitening. Note that any physical source of entropy may be used, non-limiting examples of which include a chaotic laser or, most promisingly, a noisy resistor and associated operational amplifier for an all-CMOS system.

One significant challenge in constructing a compressive sensor in accordance with the present invention is selecting a proper ADC architecture to accept randomly timed trigger pulses. Most ADC architectures are designed around specific timing requirements; sigma-delta ADCs, for example, generate pulse sequences at various densities in order to encode analog voltages, a process that relies entirely on a regular clock reference. The only architecture that can support direct, un-timed conversion of analog signals into the digital domain is the flash architecture. Flash ADCs are essentially banks of comparators and a resistor ladder. The comparators output a parallel ‘thermometer’ code of 2Nbits, where N is the number of bits of the ADC. This thermometer code is then converted via simple logic to a denser format such as binary-coded decimal or Gray codes and buffered using a latch that normally accepts the clock input.

Flash ADCs are typically not used except in the highest-speed, lowest-resolution applications, since they are the most power-inefficient and complex architecture available; each additional bit of resolution requires a doubling of the number of comparators, leading to significant problems with propagation delay and power consumption within the device for resolutions above 6 or 7 bits.

Additionally, flash ADCs often include one or more sample-and-hold amplifiers in front of the resistor ladder. These circuits maintain the same voltage at each node of the ladder over a time period long enough to allow the signal to propagate to the last comparator. This ensures that all comparators operate on the same input signal uncorrupted by propagation delays across the comparator chain. The time constant of the sample and hold circuit is entirely dependent on assumptions about the clock frequency; at higher bandwidths, when there is no deterministic clock frequency, the sample-and-hold circuitry can wreak havoc on the measurement. Thus, for this architecture to be scalable to higher bandwidths, it is important that a flash ADC is selected that does not have sample-and-hold included. Of course, this typically limits the ADCs to 6 bits of resolution or less for off-the-shelf components, since architectures with more than 6 bits that lack sample-and-hold circuitry often suffer from insurmountable propagation delays.

A challenge in implementing a compressive sensor with a physically random clock in accordance with aspects of the present invention is estimating the time intervals between sampling pulses. Typically, one would achieve this using a high-speed digital counter with a time resolution a number of times finer than the fastest frequency component one would want to sense. However, it is goal of the present invention to avoid high-speed clocks entirely in order to reap the maximum benefit from compressive sensing techniques, and using a digital counter with such fine time resolution would employ an oscillator that could easily satisfy the Nyquist condition were it used to clock a high-speed ADC. Instead, the present invention employs a low-speed clock, a counter-accumulator, and a linear ramp generating circuit to provide time interval estimates. In addition to a flash ADC to sample the signal of interest, the present invention employs a second flash ADC to sample the ramp voltage and capture the counter-accumulator value at the same time as it samples the signal of interest. By comparing the successive sample values on the timing channel, one can use the ramp properties and the counter value to estimate the elapsed time between successive samples.

The obvious limitation in timing resolution of this scheme lies in the limited resolution of the ADC, combined with the ramp rate, which itself must be tailored to the statistics of the random interval generator.

Example systems and methods of compressive sensing in accordance with aspects of the present invention will now be described with reference toFIGS. 1-8.

FIG. 1is an illustration for an example compressive sensor100, in accordance with an aspect of the present invention.

Compressive sensor100includes a sampling ADC102, a physical random interval generator104, a timing signal generator106, and a compressive reconstructor108. Each of the elements of compressive sensor100are illustrated as individual devices, however, in some embodiments of the present invention, at least two of sampling ADC102, physical random interval generator104, timing signal generator106, and compressive reconstructor108may be combined as a unitary device. Further, in some embodiments, at least one of sampling ADC102, physical random interval generator104, timing signal generator106, and compressive reconstructor108may be contained as a utility, program, or subprogram, in any desired tangible computer readable storage medium. In addition, the operations may be embodied by computer programs, which can exist in a variety of forms both active and inactive. For example, they may exist as software program(s) comprised of program instructions in source code, object code, executable code or other formats. Any of the above may be embodied on a tangible computer readable storage medium, which include storage devices. Exemplary tangible computer readable storage media include conventional computer system RAM, ROM, EPROM, EEPROM, and magnetic or optical disks or tapes. Concrete examples of the foregoing include distribution of the programs on a CD ROM or via Internet download. It is therefore to be understood that any electronic device capable of executing the above-described functions may perform those functions enumerated above. When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or a combination of hardwired and wireless) to a computer, the computer properly views the connection as a tangible computer-readable storage medium. Thus, any such connection is properly termed a tangible computer-readable storage medium. Combinations of the above should also be included within the scope of computer-readable storage media.

Physical random interval generator104generates a random signal112.

Sampling ADC102is arranged to output a digital signal116based on an input signal110and random signal112. In an example embodiment, sampling ADC102is arranged to receive input signal110and random signal112. Alternatively, intermediate circuitry may be included to modify input signal110and/or random signal112somewhat prior to sampling ADC102. Non-limiting examples of intermediate circuitry include matching networks, amplifiers, filters, resistors, etc.

Timing signal generator106is arranged to output a random timing signal118and a counter signal420. Counter signal420is based on a clock signal114, whereas random timing signal418is based on clock signal114and random signal112. In an example embodiment, timing signal generator106is arranged to receive clock signal114and random signal112. Alternatively, intermediate circuitry may be included to modify clock signal114and/or random signal112somewhat prior to timing signal generator106.

Compressive reconstructor108is arranged to output a reconstructed signal122based on digital signal116, random timing signal118and counter signal120. In an example embodiment, compressive reconstructor108is arranged to receive digital signal116, random timing signal118and counter signal120. Alternatively, intermediate circuitry may be included to modify digital signal116, random timing signal118and/or counter signal120somewhat prior to compressive reconstructor108.

Compressive sensor100, as a whole, receives and processes a received input signal for reconstruction of an uncompressed signal.

In operation, sampling ADC102receives compressed input signal110and randomly converts the analog signal to a digital or discrete signal. Furthermore, sampling ADC102performs the random conversion based upon a random signal received from physical random interval generator104.

Timing signal generator106receives clock signal114with a frequency of operation lower than the frequency components associated with input signal110. Compressive reconstructor108receives the randomly converted signal from sampling ADC102via digital signal116, receives a digital ramp signal randomly sampled from timing signal generator106via random timing signal418and receives an incrementing count signal from timing signal generator106via counter signal420to perform reconstruction of the signal received via digital signal116for delivery via reconstructed signal122.

Compressive sensor100will be now described in further detail with reference toFIG. 2.

FIG. 2is an illustration for an example compressive sensor system200, in accordance with an aspect of the present invention.

Compressive sensor system200includes compressive sensor100and a clock generator201. Each of the elements of compressive sensor system200are illustrated as individual devices, however, in some embodiments of the present invention, compressive sensor100and clock generator201may be combined as a unitary device.

Clock generator201generates clock signal114. Sampling ADC102includes a plurality of resistors with a sampling denoted as a resistor202, a plurality of comparators with a sampling denoted as a comparator204, a conversion logic portion206and a latch208.

Resistor202provides voltage drop. Comparator204compares the voltage potential of an input signal to a known voltage potential. Conversion logic portion206receives of information for determining a digital representation associated with a received analog signal. Latch208preserves an input based upon a latching input signal. As a non-limiting example, latch208may retain on its output signal a rendition of its input signal at the rising edge of a latch signal.

Sampling ADC102additionally includes banks of comparators and a resistor ladder. The comparators output a parallel ‘thermometer’ code of 2Nbits, where N is the number of bits of resolution of the sampling ADC102. This thermometer code is then converted via simple logic to a denser format such as binary-coded decimal or Gray codes and buffered using a latch that normally accepts the clock input. Additional bits of resolution for sampling ADC102require a doubling of the number of comparators.

Additionally, for some sampling ADCs, sample-and-hold amplifiers may be included prior to the resistor ladder. The sample-and-hold amplifiers maintain the same voltage at the nodes of the resistor ladder over a time period sufficient enough to allow the signal to propagate to the last comparator. The configuration with sample-and-hold amplifiers enables the comparators to operate on the same input signal uncorrupted by propagation delays across the comparator chain.

The time constant of the sample and hold circuit is entirely dependent on assumptions about the clock frequency; at higher bandwidths, when there is no deterministic clock frequency, the sample-and-hold circuitry can pose problems for realizing an accurate measurement.

In order to support scalability to higher bandwidths, a sampling ADC is configured such that it does not include a sample-and-hold. For conventional technology, using a sampling ADC without a sample-and-hold typically limits the sampling ADC to 6 bits of resolution or less for off-the-shelf components, since architectures with more than 6 bits that lack sample-and-hold circuitry often suffer from propagation delays which may result in unwanted results.

In operation, input signal110is received by comparator204. Comparator compares the received signal with a known voltage supplied via a signal212received from resistor202. If the voltage of the received signal is greater than the voltage received by signal212, then comparator transmits a logic 1 to its output. If the voltage of the received signal is less than the voltage received by signal212, then comparator transmits a logic 0 to its output. Conversion logic portion206receives the output information provided by the multiplicity of comparators (e.g. comparator204) and based upon the various inputs generates a digital output representing the received analog signal. The digital output representing the received analog signal is received by latch208via a signal216. Latch208presents the information received by its inputs to its output via digital signal116upon receiving a signal to latch via random signal112. Latch208maintains information at its output until instructed to transition to a new output value via random signal112.

Physical random interval generator104includes a laser driver222, a diode laser224, an attenuator226and a detector228. Non-limiting examples for other configurations for physical random interval generator104include a chaotic laser and a noisy resistor with an associated operational amplifier and comparator. Furthermore, any known physical source of entropy may be used for physical random interval generator104.

Laser driver222provides electrical power. Diode laser224generates laser beam. Attenuator226attenuates the laser beam created by diode laser224. Detector228detects and communicates receipt of a photon. As a non-limiting example, detector228may be a Geiger-mode avalanche photodiode.

Diode laser224receives a power supply signal230from laser driver222. Attenuator226receives a signal232from diode laser224. Detector228receives a signal234from attenuator226and provides a random signal to random signal112.

Physical random interval generator104measures the time between single-photon emissions of diode laser224attenuated by attenuator226and using detector228for detecting single-photon emissions.

The Poisson distribution of photon number for coherent light sources gives rise to an exponential distribution, p(x)=λ exp(−λx) for x≧0, with rate parameter λ, of photon arrival time intervals when source of emission from diode laser224is attenuated by attenuator226. Furthermore, exponentially distributed sampling time intervals may result in a random sampling matrix satisfying the Restricted Isometry Property (RIP) needed for the compressive sensing sampling matrix, enabling configuration without the need for pulse-shaping or digital whitening. In linear algebra, the RIP characterizes matrices that are nearly orthonormal, at least when operating on sparse vectors.

Timing signal generator106includes a ramp generator236, a counter238and a sampling ADC240.

Timing signal generator106generates a timing signal and a random output signal. Ramp generator236receives a clock signal and generates a ramp signal. Counter238increments a count value when signaled and maintains and provides count value.

A sampling ADC205receives an analog ramp signal and converts analog ramp signal to a digital or discrete ramp signal. Sampling ADC205has a similar configuration to sampling ADC102described previously.

Ramp generator receives clock signal114from clock generator201. Sampling ADC205is arranged to receive a signal from ramp generator236via a signal242. Counter238is arranged to receive a signal from ramp generator236via a signal244.

Compressive reconstructor108is arranged to receive a signal from latch208via digital signal116, to receive a signal from sampling ADC240via random timing signal118and to receive a signal from counter238via counter signal120.

Compressive reconstructor108provides reconstructed signal122to sources located external to compressive sensor system200.

In operation, sampling ADC102receives compressed input signal110and randomly converts the analog signal to a digital or discrete signal. Furthermore, sampling ADC102performs the random conversion based upon a random signal received from detector228. Timing signal generator106receives a clock signal from clock generator201via clock signal114with a frequency of operation lower than the frequency components associated with the received analog signal. Compressive reconstructor108receives the randomly converted signal from latch208via digital signal116, receives a digital ramp signal randomly sampled from timing signal generator106via random timing signal118and receives an incrementing count signal from counter238of timing signal generator106via counter signal120to perform reconstruction of the signal received via digital signal116for delivery via reconstructed signal122.

FIG. 2is an illustration for an example compressive sensor system where an analog information signal is digitized and sampled based upon a random signal, an analog ramp signal is digitized and sampled based upon a random signal and the ramp signal increments a counter. Furthermore, digitized and randomly sampled received signal, digitized and randomly sampled ramp signal and counter value are used for performing compressive reconstruction. Furthermore, the frequency for the signal used for random sampling of received signal and ramp signal has a lower frequency component than the frequency components for the received signal.

FIG. 3is a graph300of example waveforms for the operation of compressive sensor system200described with reference toFIG. 2, in accordance with an aspect of the present invention.

Graph300includes an x-axis302with units of microseconds, a first y-axis304with units of Volts, a second y-axis306with units of Volts and a third y-axis308with units of Volts.

A waveform310corresponds to an example of ramping signal242as generated by ramp generator236. A waveform312corresponds to example clock signal114as generated by clock generator201. A waveform314corresponds to counter signal120as generated by counter238. A dotted-line316corresponds to a linear function used to map sampled voltage values, as will be discussed below.

In this example, waveform310is a saw-tooth shape, having falling edges318,320and322and having rising edges324,326and328. Falling edge318falls from time t0to time t1. Rising edge324rises from time t1to time t7. Falling edge320falls from time t7to time t9. Rising edge326rises from time t9to time t14. Falling edge322falls from time t14to time t15. Rising edge328rises from time t15.

In this example, waveform312is a square pulse shape with three pulses330,332and334. Pulse330has a rising edge336at time t1and a falling edge338at time t4. Pulse332has a rising edge340at time t9and a falling edge342at time t12. Pulse334has a rising edge344at time t15and a falling edge346at time t17.

In this example, waveform314is stepped-shaped with three steps350,352and354. Step350rises at time t1. Step352rises at time t9. Step354rises at time t15.

A plurality of voltages are sampled from waveform310at random intervals. These samples include: a voltage value356at time t2; a voltage value358at time t3; a voltage value360at time t5; a voltage value362at time t6; a voltage value364at time t8; a voltage value366at time t10; a voltage value368at time t11; a voltage value370at time t13; and a voltage value372at time t16. These samples correspond to samples of random timing signal118as generated by sampling ADC205. Dotted-line316corresponds to an example linearly increasing function for mapped sampled values, as will be described in greater detail below.

Dotted-line316is a continuation of a line between an initial set of sampled points, in this case, voltage values356,358,360and362. Dotted-line316may be considered a superposition of rising edges324,326and328, wherein falling edges320and322are not included. The processing for generating waveform310is performed by compressive reconstructor108.

For a compressive reconstructor to reconstruct a signal, the detected voltages must be associated with the appropriate sampled times. This can be accomplished by associating increasing sampled voltages, e.g., voltage values360,362,366, and368, with increasing sampled times, respectively, e.g., t5, t6, t10, and t11.

As seen in the figure, voltage values360and362, increase with respective, increasing sampled times and voltage values366and368, additionally increase with respective, increasing sampled times. In this example, voltage value360<voltage value362, voltage value366<voltage value368and voltage value368<voltage value360.

When considering voltage values360,362,366, and368, compressive reconstructor may incorrectly associate voltage values360,362,366, and368with random sampling times t5, t6, t10, and t11. If a compressing reconstructor is presuming an a rising edge, then the sampled voltages would increase. In such a case, a compressing reconstructor mar arrange voltage values360,362,366, and368in a sampled order of voltage values366,368,360and362. By arranging the samples in increasing order, the compressive reconstructor may incorrectly determine that the sampled signal would correspond to: voltage value366sampled at time t5; voltage value368sampled at time t6; voltage value360sampled at time t10; and voltage value362sampled at time t11. Clearly, this is not the order of the sampled voltage values.

To avoid the above discussed issue, a constantly increasing waveform is simulated, wherein sampled voltage values are mapped to the constantly increasing waveform. In this example, dotted-line316is the simulated constantly increasing waveform, wherein voltage values366,368,370and372are mapped thereto, as voltage values374,376and378(the mapped voltage value corresponding to voltage value372is not shown). With the mapping of voltage values366,368and370to voltage values374,376and378, respectively, the set of voltage values356,358,360,362,374,376and378continuously increase. Accordingly, the increasing sampling times t2, t3, t5, t6, t10, t11and t13may be correctly mapped to the correct voltage values356,358,360,362,374,376and378, respectively.

It should be noted that voltage values374,376and378are not the sampled voltage values. As seen inFIG. 3, voltage values374,376and378are much higher that the actual sampled voltage values, voltage values366,368and370, respectively. Now that the correct sampling times have been associated with voltage values356,358,360,362,374,376and378, the sampling times for voltage values374,376and378are then associated with actually sampled voltage values366,368and370, respectively.

In other words, in accordance with an aspect of the present invention, an initial set if increasing sampled voltage values are used to construct a linearly increasing waveform. Subsequently sampled voltage values are then mapped to the linearly increasing waveform. Once all the sampled values are mapped to the waveform. The increasing sample times are associated with respective increasing mapped voltage values. Once the mapped voltage values are associated with the correct sampling times, the sampling times are associated with the correct original voltage values.

There is another issue that needs to be addressed—sampled voltage values on a falling edge of a signal. For example, sampled voltage value364is sampled on falling edge320of waveform310. These such sampled voltages are ignored.

The process for generating waveform310in accordance with aspects of the present invention involves recording the sampled voltage values {yi} and the corresponding counter values associated with waveform310{Ni}. Furthermore, the process involves determining the maximum voltage achieved for waveform310, ymax=max{yi}. Furthermore, the process involves estimating the slope, noted as m, of the upward ramp for waveform310using the calculated ramp time and the maximum voltage recorded, m=tramp/ymax. Furthermore, negative-transitioning samples are discarded (e.g. voltage value664). Furthermore, compute estimated times based on Equation (1) shown below:
ti=ti-1+m(yi−yi-1+(Ni−Ni-1)*ymax)+(Ni−Ni-1)*tfall(1)

The variable tfallfor Equation (1) represents the fall time for waveform610. As an example, tfallmay be represented by the difference in time between time t9and time t10.

FIG. 4illustrates an example histogram400for measured time estimation error associated with the time estimation as performed per Equation (1), in accordance with an aspect of the present invention.

Histogram400represents the error between estimated time per Equation (1) and the actual measured time for the example compressive sensor system as described with reference toFIG. 2. Histogram400includes an x-axis402with units for number of samples and a y-axis404representing error with units of seconds×10−7.

The wider and more dispersed histogram400, the greater the error associated with estimating the time per Equation (1). Alternatively, the narrower and less dispersed histogram400, the less the error associated with estimating the time per Equation (1).

Histogram400initiates at y-axis404bin sample value of approximately 10 samples at a time of approximately 1.2×10−7seconds. Histogram400presents y-axis404bin sample value of approximately 30 sample at a time of approximately 1.3×10−7seconds. Histogram400presents y-axis404bin sample value of approximately 125 samples at a time of approximately 1.5×10−7seconds. Histogram400presents y-axis404bin sample value of approximately 400 sample at a time of approximately 1.6×10−7seconds. Histogram400presents y-axis404bin sample value of approximately 1100 sample at a time of approximately 1.8×10−7seconds. Histogram400presents y-axis404bin sample value of approximately 1800 sample at a time of approximately 2×10−7seconds. Histogram400presents y-axis404bin sample value of approximately 350 sample at a time of approximately 2.2×10−7seconds.

The statistical one sigma (σ) standard deviation for histogram400is presented as 18.251 ns, representing a maximum frequency which can be reconstructed for this example of approximately 27 MHz as determined by Equation (2) shown below:
fmax=0.5/σ  (2)

The value fmaxrepresents the maximum frequency that can be reconstructed based upon the one sigma (σ) standard deviation of the estimated time error. Attempting to reconstruct signals with a frequency component above fmaxmay not perform well.

FIG. 5illustrates an example graph500representing sample values versus time, in accordance with an aspect of the present invention.

Graph500includes an x-axis502with units of seconds×10−5and a y-axis504with units representing a proportional voltage.

The values for y-axis504represent a proportional voltage as depicted by digital signal116as described with reference toFIGS. 1-2. The time values for x-axis502represent the estimated time as calculated by compressive reconstructor as described with reference toFIGS. 1-2and per the previously discussed Equation (1). Two frequency components, 5.5 MHz and 7 MHz, are contained within the presented 128 samples.

FIG. 6illustrates an example graph600representing the reconstruction of the data as discussed with reference toFIG. 5, in accordance with an aspect of the present invention.

Graph600includes an x-axis602with units of Hertz×106and a y-axis604with units of Volts.

A frequency component606is presented with an x-axis frequency of 5.5 MHz and a y-axis voltage of approximately 210 Volts. A frequency component608is presented with an x-axis frequency of 7 MHz and a y-axis voltage of approximately 240 Volts.

Graph600illustrates successful reconstruction of the 5.5 MHz signal and 7 MHz signal associated with the data presented inFIG. 5.

For a conventional reconstruction implementation, reconstruction of a 7 MHz signal would require a sample frequency of at least twice or 14 MHz for success. For this example, the 7 MHz signal was reconstructed using a random sample clock with a frequency of 1 MHz, significantly less than the minimum 14 MHz conventional sample clock.

FIG. 7illustrates an example graph700representing the reconstruction of the data, in accordance with an aspect of the present invention.

Graph700includes an x-axis702with units of Hertz×107and a y-axis704with units of Volts.

The data for reconstruction included a 5 MHz signal and a 25 MHz signal, where the 25 MHz signal was close the fmaxof 27 MHz as calculated by Equation (2). A frequency component706is presented with an x-axis frequency of 5 MHz and a y-axis voltage of approximately 230 Volts. A frequency component708is presented with an x-axis frequency of 25 MHz and a y-axis voltage of approximately 49 Volts. A frequency component710is presented with an x-axis frequency of approximately 26 MHz and a y-axis voltage of approximately 70 Volts.

As may be observed, the 5 MHz signal was successfully reconstructed. The 25 MHz signal was somewhat reconstructed, although with a lower voltage and with an unwanted frequency component at approximately 26 MHz. The poor performance for reconstructing the 25 MHz signal is due to the limitations for the timing estimation as described with reference to Equation (2), as the 25 MHz signal was close to the fmaxof 27 MHz.

FIG. 8illustrates an example method800for performing time estimation, in accordance with an aspect of the present invention.

Method800presents processing as discussed with reference to Equation (1).

Method800starts (S802) with storage of ramp samples, {yi}, and counter values {Ni} (S804). For example, the ramp values associated with random timing signal118as described with reference toFIGS. 1-2and the counter values associated with counter signal120as described with reference toFIGS. 1-2are stored.

The maximum value, ymax, for the stored ramp samples, {yi}, is then determined (S806). For example, the maximum ramp value for rising edge324of waveform310for a voltage value356, voltage value358, voltage value360and voltage value362, as described with reference toFIG. 3would be determined as voltage value362.

The slope, m, of the ramp would then be estimated as m=tramp/ymax(S808). The estimated ramp time, tramp, associated with ramp signal242as digitized by sampling ADC205, as calculated by compressive reconstructor108and as described with reference toFIGS. 1-2, is divided by the previously determined ymax.

Negative-going samples of the stored ramp samples, {yi}, are discarded (S810). As an example, voltage value364of waveform310as described with reference toFIG. 3is discarded, as voltage value364occurs when the ramp signal is decreasing.

Estimated times are then calculated (S812). For example, the calculation as described with reference to Equation (1) is performed.

A compressive sensor system in accordance with the present invention uses a physical random interval generator that enables reconstruction of signals using a clock signal with a lower frequency component than contained within the signals to be reconstructed.