Sampling method, reconstruction method, and device for sampling and/or reconstructing signals

0001The present invention relates to a sampling method, a reconstruction method and related devices for sampling and/or reconstructing signals.

0002With the increasing use of digital devices in all scientific and technical fields, the need for reliable acquisition devices equally increases. The role of these devices is to acquire the analog signals or waveforms of the continuous-time world and convert them in time-discrete digital signals which can then be processed by said digital devices, for instance to perform some computational operations such as processing, decoding or reconstructing the analog waveform. Such acquisition devices are used in many areas of science and technology, including for example scientific measurements, medical and biological signal processing, telecommunication technology, etc.

0003The acquisition devices sample the analog waveform at uniform sampling intervals and with a regular sampling frequency, thus generating a set of sampled values of the sampled signal. It is critical in most sampling schemes to use the smallest set of representative samples needed to fully represent and eventually allow the faithful reconstruction of the analog waveform. In other words, the smallest sampling frequency still allowing a faithful representation of the first signal is the goal.

0004The sampling and reconstruction methods currently used in common acquisition devices are based on the sampling theorem of Whittaker, Kotelnikov and Shannon.

0005This theorem states that a signal, for example a received signal y(t), bandlimited to the frequency band [−ω_m, ω_m] can be completely represented by samples y_s[n] spaced by an uniform sampling interval T if the sampling rate 2π/T is at least twice the bandwidth ω_m.

0006This sampling scheme is represented on <figref idref="DRAWINGS">FIG. 1</figref>. The lowest sampling frequency 2ω_mgiven by this theorem is commonly referred to as the Nyquist rate or Shannon frequency. In other words, the minimal sampling frequency directly depends on the bandwidth of the analog signal y(t) to sample and/or reconstruct.

0007The reconstruction method related to this sampling theorem allows a perfect reconstruction of a signal y(t) by superposing regularly spaced sinc functions regularly delayed by the value of one sampling interval T and weighted by the successive sampled values y_s[n] of the sampled signal. This well-known reconstruction scheme is illustrated on <figref idref="DRAWINGS">FIG. 2</figref>, where the bloc <b>1</b> illustrates the sinc reconstruction filter.

0008If the signal y(t) to sample and/or reconstruct is a non-bandlimited signal, or if its bandwidth is too high to sample it at an acceptable sampling frequency, one usually filters it with a lowpass filter, is thus generating a bandlimited lowpass version of the signal. This lowpass version of the signal can then be sampled and reconstructed with the above-described sampling and reconstruction schemes. The lowpass filtering can be performed by a dedicated lowpass filter circuit, by the transfer function of a transfer channel over which the signal y(t) has been transmitted, and/or by the transfer function of a measuring device or demodulating circuit used for acquiring this signal.

0009Therefore, when sampling and reconstructing a non-bandlimited signal y(t) or a bandlimited signal having a frequency spectrum with non-zero Fourier coefficients for frequencies higher than half of the sampling frequency 2ω_m, current sampling and reconstruction methods imply a distortion of the reconstructed signal with respect to the sampled signal.

0010In order to avoid the above mentioned problem, one usually uses a higher sampling frequency, thus allowing perfect reconstruction of a broader range of signals and minimizing distortion for non-bandlimited signals or wideband signals. A high sampling frequency however requires fast, expensive and power-consuming A/D converters, fast digital circuits and a waste of storage place for storing the digitized signal.

0011Furthermore, there are wide classes of very common signals, including stream of Dirac pulses, bilevel signals, piecewise polynomial signals, etc., which are not bandlimited and which therefore cannot be sampled and faithfully reconstructed by the known methods, even by increasing the sampling rate.

0012An aim of the present invention is to find a sampling method and a related reconstruction method for sampling at least some classes of non-bandlimited signals and for allowing an exact reconstruction of these signals from the samples generated with said sampling method.

0013Another aim of the present invention is to find a sampling method and a related reconstruction method for sampling at least some classes of bandlimited signals with a sampling frequency lower than the frequency given by the Shannon theorem and still allowing an exact reconstruction of these signals.

0014Another aim of the present invention is to find an improved method for sampling and faithfully reconstructing signals with a finite rate of innovation which can only be seen through an imperfect measuring device, a transfer channel and/or a modulating system having not necessarily a bandlimited transfer characteristic.

0015These aims are achieved with a sampling method and a reconstruction method including the features of the corresponding independent claim.

0016In particular, these aims are achieved with a new sampling method for sampling and faithfully reconstructing signals having a finite rate of innovation, i.e. having, over a finite time interval, a finite number 2K of degrees of freedom. In particular, the invention concerns the sampling and reconstruction of signals which can be completely represented by the superposition of a finite number K of known functions delayed by arbitrary shifts (t_n, t_k) and weighted by arbitrary amplitude coefficients c_n, c_k.

0017The Shannon theorem indicates that bandwidth limited signals can be exactly specified by sampling values y_s[n] taken at uniform sampling intervals if the sampling rate is at least twice the bandwidth. The invention is based on the finding that a larger class of signals, i.e. signals having a finite number 2K of degrees of freedom over a finite time interval, can be exactly specified by a finite set of shifts and associated weights. It can be shown that, in many common cases, the minimal number of values 2K, or even 2K+1, is much lower than the number of samples required for faithfully reconstructing a signal with the existing reconstruction methods.

0018As an example, in the case of a CDMA communication system, each symbol (information bit) of each signal sent by each user is modulated with a coding sequence (signature) which can for example be 1023 chips long. In this case, the chip rate of the transmitted signal is thus 1023 times higher than its symbol rate. Modulating a signal with the coding sequence thus expands the signal's bandwidth by the value of the spreading factor, here 1023. Sampling and reconstructing a received CDMA signal with the conventional sampling and reconstruction methods thus requires a very fast and therefore complex and expensive analog sampling device. As the number of degrees of freedom in each received signature is at most two (shift and weight of the signature), the method of the invention can be used for sampling the received signal at a much lower rate whilst still allowing a faithful reconstruction of the sequence of symbols sent.

0019It is important to understand that, in the sampling method of the invention, the signal (or a filtered version of the signal) is still sampled at uniform sampling intervals, using for example common regularly clocked sampling devices. It is only for the reconstruction of the signal from the set of sampled values that a set of shifted values is computed. In most cases, those shifted values do not correspond to samples of the signal to reconstruct.

0020The inventive sampling method first convolves the signal x(t) with a sampling kernel and then samples the convolved signal at regular sampling intervals, both the sampling kernel and the sampling frequency being chosen such that the sampled values completely specify the first signal, thus allowing a perfect reconstruction of said first signal. The sampling frequency used for the inventive sampling method can be lower than the frequency given by the Shannon theorem, but is greater than or equal to the rate of innovation of the signal to reconstruct.

0021The inventive reconstruction method reconstructs a first signal x(t) from a set of sampled values taken from this signal x(t) or from a second related signal y(t) regularly sampled at a sub-Nyquist rate by retrieving from the regularly spaced sampled values a set of shifts and weights with which the first signal can be completely specified and reconstructed.

0022In particular, the inventive reconstruction method can be used for reconstructing, from a set of at least 2K sampled values, any signal which can be represented by the superposition of K known functions delayed by arbitrary shifts and weighted by arbitrary amplitude coefficients (weights). A preferred embodiment of the inventive reconstruction method comprises the steps of first solving a structured linear system for retrieving said arbitrary shifts and then retrieving the arbitrary weights using the previously retrieved arbitrary shifts.

0023Note that for some applications it may be sufficient to retrieve the shifts and that the weights are only needed if a complete reconstruction of the signal is needed. This is for instance the case during an estimation session in a CDMA decoder, when one wants to estimate the relative delays (shifts) occurred by the different users' signals along different propagation paths.

0024The lowest sampling frequency required in the method of the invention directly depends on the rate of innovation of the signal to sample and/or reconstruct, and not on its bandwidth as in prior art methods. More precisely, the sampling frequency required by the sampling method of the invention must be greater than or equal to the rate of innovation of the signal to sample. A minimal sampling frequency can thus be determined for any signal with a finite rate of innovation, including for some non-bandlimited signals.

0025In the specification and in the claims, the rate of innovation ρof a signal is defined as the number of degrees of freedom of the signal within a time period. For example, a signal x(t) made of K weighted Dirac pulses, even if clearly not bandlimited, can be fully specified by the K occurrence times (shifts) t_kand by the K amplitudes (weights) c_kof the Diracs. The signal can be written as

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mrow><mi>δ</mi><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0001.tif" />

0026The degree of freedom of this signal is 2K. Its rate of innovation ρ is thus finite and equal to 2K/τ, where τ is the time interval in which these K Dirac pulses occurred.

0027If the Dirac pulse function δ(t) is replaced by any other known function γ(t), the number of degrees of freedom of the signal obviously always stays 2K, that is K occurrence times, or shifts, t_kand K amplitudes, or weights, c_k.

0028Considering the more general case of an unlimited time-continuous signal, for example a sequence of regularly spaced Dirac pulses with a space T between the pulses, the signal can be represented as

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mrow><msub><mi>c</mi><mi>n</mi></msub><mo></mo><mrow><mi>δ</mi><mo></mo><mrow><mo>(</mo><mfrac><mrow><mi>t</mi><mo>-</mo><mrow><mi>n</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>T</mi></mrow></mrow><mi>T</mi></mfrac><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0002.tif" />

0029where the degrees of freedom of the signal are the coefficients c_n. The number of degrees of freedom per time interval T is therefore equal to one. The rate of innovation of this signal is thus ρ=1/T. Such a signal could for example be a Pulse Amplitude Modulated (PAM) signal where the coefficients c_nrepresent the value of the information data to be transmitted.

0030Again, replacing the Dirac pulse function δ(t) by any other known function γ(t) doesn't change the rate of innovation of the signal. The signal

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mrow><msub><mi>c</mi><mi>n</mi></msub><mo></mo><mrow><mi>γ</mi><mo></mo><mrow><mo>(</mo><mfrac><mrow><mi>t</mi><mo>-</mo><mrow><mi>n</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>T</mi></mrow></mrow><mi>T</mi></mfrac><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0003.tif" />

0031thus also has a rate of innovation ρ=1/T. There are many examples of such signals, for example when γ(t) is a scaling function in a wavelet multi-resolution framework, or in approximation theory using uniform splines.

0032If the superposed copies of the function γ(t) are shifted by arbitrary shifts t_n, the signal can be written as

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mrow><msub><mi>c</mi><mi>n</mi></msub><mo></mo><mrow><mi>γ</mi><mo></mo><mrow><mo>(</mo><mfrac><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>n</mi></msub></mrow><mi>T</mi></mfrac><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0004.tif" />

0033Assuming that the function γ(t) is known, the degrees of freedom of the signals over a time interval T are the weights c_nand the shifts t_n. Thus the rate of innovation is ρ=2/T.

0034A signal could also be represented as a superposition of a determined set of functions {γ_r(t)}_{r=0, . . . , R}, instead of the unique function γ(t). It can thus be written as

0000<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>r</mi><mo>=</mo><mn>0</mn></mrow><mi>R</mi></munderover><mo></mo><mrow><msub><mi>c</mi><mi>nr</mi></msub><mo></mo><mrow><msub><mi>γ</mi><mi>r</mi></msub><mo></mo><mrow><mo>(</mo><mfrac><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>n</mi></msub></mrow><mi>T</mi></mfrac><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0005.tif" />

0035For example, γ_rcould be a Dirac, a differentiated Dirac, a polynomial function, etc. Likewise, a multi-user CDMA signal x(t) is the sum of a plurality of weighted and shifted known signatures γ_rof the users.

0036Again, assuming that the functions γ_r(t) are known, the degrees of freedom of the signal x(t) are the coefficients c_nrand the time instants t_n. With the introduction of a counting function c_x(t_a,t_b) which counts the number of degrees of freedom in the signal x(t) over a time interval [t_a,t_b], the rate of innovation ρ can be defined as

0000<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mrow><mi>ρ</mi><mo>=</mo><mrow><munder><mi>lim</mi><mrow><mi>τ</mi><mo>→</mo><mi>∞</mi></mrow></munder><mo></mo><mrow><mfrac><mn>1</mn><mi>τ</mi></mfrac><mo></mo><mrow><msub><mi>c</mi><mi>x</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mrow><mo>-</mo><mfrac><mi>τ</mi><mn>2</mn></mfrac></mrow><mo>,</mo><mfrac><mi>τ</mi><mn>2</mn></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0006.tif" />

0037Signals with a finite rate of innovation ρ can be completely determined and faithfully reconstructed with a set of at least ρ/2 weights (c_n, c_nr, c_k) and ρ/2 shifts (t_n, t_k) per unit of time and with the knowledge of the functions γ_r(t) which only depend on the class of the signal to reconstruct (stream of pulses, piecewise polynomials, etc.).

0038The rate of innovation ρ can also be defined locally with respect to a moving window of size τ. Given a window of time τ, the local rate of innovation ρ_τ(t) at time t is

0000<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mrow><mrow><msub><mi>ρ</mi><mi>t</mi></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mi>τ</mi></mfrac><mo></mo><mrow><mrow><msub><mi>C</mi><mi>x</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mrow><mi>t</mi><mo>-</mo><mrow><mi>τ</mi><mo>/</mo><mn>2</mn></mrow></mrow><mo>,</mo><mrow><mi>t</mi><mo>+</mo><mrow><mi>τ</mi><mo>/</mo><mn>2</mn></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0007.tif" />

0039In this case, as the rate of innovation ρ_τ of the signal determines the lowest required sampling frequency needed for sampling the signal with the inventive sampling method, it is necessary to determine the maximal local rate of innovation ρ_max(τ)

0000<br />ρ_max=max ρ_τ(<i>t</i>).

0040Applications of the new sampling and reconstruction methods can be found in many technical fields, including signal processing, communication systems and biological systems. The sampling and reconstruction methods can for instance be used for sampling and reconstructing wideband communication signals, such as CDMA signals, or ultra-wideband communication signals, such as PPM signals and time-modulated ultra-wideband signals, among others.

0041Various embodiments of the new sampling method and of the related reconstruction method applied to different classes of signals with finite rate of innovation are explained in the specification. The one skilled in the art will understand however that the invention is not limited to the specific examples given and that advantageous technical effects can be obtained by sampling and reconstructing other kinds of signals with a finite rate of innovation.

0042The invention will be better understood with the help of the figures in which:

0043<figref idref="DRAWINGS">FIG. 1</figref> diagrammatically illustrates a sampling device and method using the already known Shannon theorem.

0044<figref idref="DRAWINGS">FIG. 2</figref> diagrammatically illustrates a reconstructing device and method using the already known Shannon theorem.

0045<figref idref="DRAWINGS">FIG. 3</figref> illustrates a communication system in which the sampling and reconstruction method of the invention can be used for sampling the signal y(t) and reconstructing any of the signals x_i(t).

0046<figref idref="DRAWINGS">FIG. 4</figref> illustrates a sampling device according to the invention.

0047<figref idref="DRAWINGS">FIG. 5</figref> shows one period τ of a periodic stream of Diracs x(t).

0048<figref idref="DRAWINGS">FIG. 6</figref> shows the Fourier transformation of a periodic stream of Diracs.

0049<figref idref="DRAWINGS">FIG. 7</figref> shows the Fourier transformation of a bandlimited periodic stream of Diracs.

0050<figref idref="DRAWINGS">FIG. 8</figref> shows the Fourier transformation of a sampled bandlimited, periodic stream of Diracs.

0051<figref idref="DRAWINGS">FIG. 9</figref> shows an example of bilevel signal.

0052<figref idref="DRAWINGS">FIG. 10</figref> shows a box spline φ₀(t/T).

0053<figref idref="DRAWINGS">FIG. 11</figref> shows a hat spline φ₁(t/T).

0054<figref idref="DRAWINGS">FIG. 12</figref> illustrates a two-dimensional picture signal with a 0/1 transition given by an arbitrary function.

0055<figref idref="DRAWINGS">FIG. 13</figref> illustrates a two-dimensional picture signal with a 0/1 transition given by a smooth, for example a bandlimited, function.

0056<figref idref="DRAWINGS">FIG. 14</figref> illustrates a two-dimensional picture signal with a 0/1 transition given by a piecewise polynomial function.

0057<figref idref="DRAWINGS">FIG. 3</figref> diagrammatically illustrates a communication system in which the sampling and reconstruction method of the invention can be used. The system comprises a signal x₁(t) which is modulated by a modulating device <b>3</b> having a known transfer function φ₁(t). The resulting modulated signal x₂(t) is transmitted over a transmission channel <b>5</b> with a transfer function φ₂(t). Noise may be added to the signal x₃(t). The transmitted signal x₃(t) is acquired or measured by a measuring device <b>7</b> with a transfer function φ₃(t). The measured signal x₄(t) is demodulated by a demodulating device <b>9</b> with a known transfer function φ₄(t). The demodulated signal x₅(t) is filtered by a filter <b>11</b> with a known transfer function φ₅(t), for instance a lowpass filter in the sampler. In the following, the combination of transfer functions φ_i(t) by which the sampled signal y(t) is related to the signal x_i(t) one wishes to reconstruct will be designated by φ(t), and the reconstructed signal will be designated x(t). The filtered signal x₆(t)=y(t) is sampled at uniform sampling intervals by a sampling device <b>13</b> working at a sub-Nyquist rate, generating a set of sampled values y_s[n]. This set of sampled values can be stored, processed, transmitted, etc., and used by a reconstruction device <b>15</b> for reconstructing the signal y(t) or, if the transfer functions φ_i(t) are known or at least if they have themselves a finite rate of innovation, any of the signals x_i(t). Depending on the application, one may wish to reconstruct the sampled signal y(t) or any signal x_i(t) related to the sampled signal y(t) by a known transfer function, or at least by a transfer function which has itself a finite rate of innovation.

0058<figref idref="DRAWINGS">FIG. 4</figref> illustrates a sampling device <b>13</b> with a filter <b>11</b> able to carry out the sampling method of the invention. The aim of the sampling device is to generate a set of sampled values y_s[n] from the signal y(t) having a known finite rate of innovation ρ, where this set of value y_s[n] must completely specify the signal to reconstruct x(t).

0059According to the sampling method of the invention, the signal to sample x(t) is first filtered with a lowpass filter, for example with the lowpass filter <b>11</b> or with a combination of the elements <b>3</b>-<b>11</b> in the system of <figref idref="DRAWINGS">FIG. 3</figref>, having an impulse response φ(t), for instance φ₅(t). Advantageously, the impulse response φ₅(t) of the lowpass filter has a bandwidth of ρ/2.

0060Calling x(t) the signal to reconstruct, its filtered version is

0000<br /><i>y</i>(<i>t</i>)=<i>x</i>(<i>t</i>)* <o ostyle="single">φ</o>(<i>t</i>)

0000<br />where

0000<br /><o ostyle="single">φ</o>(<i>t</i>)=φ(−<i>t</i>)

0061is the convolution kernel (transfer function of the filter <b>3</b>-<b>11</b>). Then, uniform sampling of y(t) with a sampling interval T leads to samples y_s[n] given by:

0000<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><mi>y</mi><mo>,</mo><mrow><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mo>〈</mo><mrow><mrow><mi>ϕ</mi><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mrow><mi>n</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>T</mi></mrow></mrow><mo>)</mo></mrow></mrow><mo>,</mo><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow><mo>〉</mo></mrow><mo>=</mo><mrow><msubsup><mo>∫</mo><mrow><mo>-</mo><mi>∞</mi></mrow><mi>∞</mi></msubsup><mo></mo><mstyle><mspace width="0.2em" height="0.2ex" /></mstyle><mo></mo><mrow><mrow><mi>ϕ</mi><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mrow><mi>n</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>T</mi></mrow></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><mo></mo><mi>t</mi></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0008.tif" />

0062By choosing a sampling frequency f=1/T greater or equal to the rate of innovation of the signal x(t) to reconstruct, we will show that the samples y_s[n] allow for a faithful reconstruction or decoding of the signal x(t), as will be illustrated by the not-limiting following examples.

0063Periodic Signals with Finite Rate of Innovation

0064In an embodiment, the new sampling and reconstruction methods are applied to the sampling and/or reconstruction of a periodic first signal x(t) with finite rate of innovation ρ over its period τ. As examples, we will consider streams of weighted Diracs and periodic piecewise polynomials. Although the demonstration will be made using continuous-time periodic signals, similar results could be achieved with discrete-time periodic signals.

0065A periodic stream of K Diracs at locations t_k, weighted by weights c_kand with a period τ, can be written as

0000<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mo>∑</mo><mi>n</mi></munder><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mi>δ</mi><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mrow><mo>(</mo><mrow><msub><mi>t</mi><mi>k</mi></msub><mo>+</mo><mrow><mi>n</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>τ</mi></mrow></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0009.tif" />

0066One period τ of a stream of Diracs x(t) is shown on <figref idref="DRAWINGS">FIG. 5</figref>. Each period of x(t) can thus be represented by the superposition of K Diracs delayed by shifts t_kand weighted by weights c_k. This signal x(t) can thus be fully determined by knowing the values of the K amplitudes and the K shifts of the K Diracs. It has therefore 2K degrees of freedom per period τ and its rate of innovation ρ is equal to 2K/τ. However, the bandwidth of x(t) is clearly not limited, so that x(t) cannot be sampled and faithfully reconstructed with existing methods.

0067According to the sampling method of the invention, this first signal x(t) is first convolved by a filter <b>3</b>-<b>11</b> with a sampling function φ(t), for instance the sinc sampling kernel of bandwidth

0000<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><mrow><mrow><mo>[</mo><mrow><mfrac><mrow><mo>-</mo><mi>K</mi></mrow><mi>τ</mi></mfrac><mo>,</mo><mfrac><mi>K</mi><mi>τ</mi></mfrac></mrow><mo>]</mo></mrow><mo>,</mo></mrow></math></maths><img file="US2010042374A1_D0010.tif" />

0000and then sampled at a sampling frequency f=1/T greater than

0000<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><mrow><mfrac><mrow><mn>2</mn><mo></mo><mi>K</mi></mrow><mi>τ</mi></mfrac><mo>.</mo></mrow></math></maths><img file="US2010042374A1_D0011.tif" />

0068The Fourier series coefficients X[m] of the signal x(t) are given by

0000<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mi>τ</mi></mfrac><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><msup><mi></mi><mrow><mrow><mo>-</mo><mi></mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mfrac><mrow><mn>2</mn><mo></mo><mi>π</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>mt</mi><mi>k</mi></msub></mrow><mi>τ</mi></mfrac></mrow></msup></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Figure</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>6</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2010042374A1_D0012.tif" />

0069The filtered signal y(t), resulting from the convolution of the first signal x(t) with the sinc sampling kernel of bandwidth

0000<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mrow><mo>[</mo><mrow><mfrac><mrow><mo>-</mo><mi>K</mi></mrow><mi>τ</mi></mfrac><mo>,</mo><mfrac><mi>K</mi><mi>τ</mi></mfrac></mrow><mo>]</mo></mrow></math></maths><img file="US2010042374A1_D0013.tif" />

0000is a lowpass approximation of the first signal x(t) given by

0000<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mrow><mrow><mi>y</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mrow><mo>-</mo><mi>K</mi></mrow></mrow><mi>K</mi></munderover><mo></mo><mrow><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow><mo></mo><msup><mi></mi><mrow><mi></mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mfrac><mrow><mn>2</mn><mo></mo><mi>π</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>m</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>t</mi></mrow><mi>τ</mi></mfrac></mrow></msup></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0014.tif" />

0070<figref idref="DRAWINGS">FIG. 7</figref> shows the Fourier series Y[m] coefficients of y(t).

0071Sampling one period τ of the filtered signal y(t) at multiples of T, we obtain M=τ/T sampled values y_s[n]. In a preferred embodiment, T is a divider of τ.

0000<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>y</mi><mi>s</mi></msub><mo></mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>y</mi><mo></mo><mrow><mo>(</mo><mi>nT</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mrow><mo>-</mo><mi>K</mi></mrow></mrow><mi>K</mi></munderover><mo></mo><mrow><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow><mo></mo><msup><mi></mi><mrow><mi></mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mfrac><mrow><mn>2</mn><mo></mo><mi>π</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>mnT</mi></mrow><mi>τ</mi></mfrac></mrow></msup></mrow></mrow><mo>=</mo><mrow><mo><</mo><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow><mo>,</mo><mrow><mrow><mrow><mi>ϕ</mi><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mi>nT</mi></mrow><mo>)</mo></mrow></mrow><mo>></mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><mi>where</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>n</mi></mrow></mrow><mo>∈</mo><mrow><mrow><mo>[</mo><mrow><mn>0</mn><mo>,</mo><mrow><mrow><mi>τ</mi><mo>/</mo><mi>T</mi></mrow><mo>-</mo><mn>1</mn></mrow></mrow><mo>]</mo></mrow><mo>.</mo></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0015.tif" />

0072y(nT) is periodic with a period τ/T. <figref idref="DRAWINGS">FIG. 8</figref> shows the Fourier series coefficients Y_s[m] of y_s[n]. The Fourier coefficients Y_s[m] can be computed from the set of N sampled values y(nT) of the filtered signal y(t) by using for instance the well-known Fast Fourier Transform (FFT) method.

0073It can be shown that if the number τ/T of samples per period is greater than or equal to 2K+1, the samples y_s[n] are a sufficient representation of x(t).

0074The following method can be used for reconstructing the signal x(t) from the coefficients Y_s[m]. The Fourier coefficients X[m], computed from the samples y_s[n] with a known method, are a linear combination of K complex exponentials:

0000<maths id="MATH-US-00016" num="00016"><math overflow="scroll"><mrow><msubsup><mi>u</mi><mi>k</mi><mi>m</mi></msubsup><mo>=</mo><msup><mi></mi><mrow><mrow><mo>-</mo><mi></mi></mrow><mo></mo><mfrac><mrow><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><mn>2</mn><mo></mo><mi>π</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>m</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>t</mi><mi>k</mi></msub></mrow></mrow><mi>τ</mi></mfrac></mrow></msup></mrow></math></maths><img file="US2010042374A1_D0016.tif" />

0075The shifts t_kof the K Diracs can be determined from the samples using for instance an annihilating filter. A filter (1-z⁻¹u_k) is called an annihilating filter for u_k^mif

0000<br />(<i>l−z</i>⁻¹<i>u</i>_k)<i>u</i>_k^m=0

0076In order to find the shifts t_k, an annihilating filter H(z) has to be determined whose coefficients are (1, H[1], H[2], . . . , H[K]) or

0000<maths id="MATH-US-00017" num="00017"><math overflow="scroll"><mrow><mrow><mi>H</mi><mo></mo><mrow><mo>(</mo><mi>z</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mn>1</mn><mo>+</mo><mrow><mrow><mi>H</mi><mo></mo><mrow><mo>[</mo><mn>1</mn><mo>]</mo></mrow></mrow><mo></mo><msup><mi>z</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup></mrow><mo>+</mo><mrow><mrow><mi>H</mi><mo></mo><mrow><mo>[</mo><mn>2</mn><mo>]</mo></mrow></mrow><mo></mo><msup><mi>z</mi><mrow><mo>-</mo><mn>2</mn></mrow></msup></mrow><mo>+</mo><mi>…</mi><mo>+</mo><mrow><mrow><mi>H</mi><mo></mo><mrow><mo>[</mo><mi>K</mi><mo>]</mo></mrow></mrow><mo></mo><msup><mi>z</mi><mrow><mo>-</mo><mi>K</mi></mrow></msup></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><mrow><mi>H</mi><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow><mo></mo><msup><mi>z</mi><mrow><mo>-</mo><mi>m</mi></mrow></msup></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0017.tif" />

0077and which annihilates each exponential u_k^m. It can be shown that the K shifts of the Diracs {t₀, t₁, . . . , t_k−1} are given by, or at least can be retrieved from the zeros of the filter H(z).

0078The filter H(z) can be found by solving the following structured linear equation system for H:

0000<maths id="MATH-US-00018" num="00018"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow></mtd><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>]</mo></mrow></mrow></mtd><mtd><mi>…</mi></mtd><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mrow><mo>-</mo><mrow><mo>(</mo><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>1</mn><mo>]</mo></mrow></mrow></mtd><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow></mtd><mtd><mi>…</mi></mtd><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mrow><mo>-</mo><mrow><mo>(</mo><mrow><mi>K</mi><mo>-</mo><mn>2</mn></mrow><mo>)</mo></mrow></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow><mo>]</mo></mrow></mrow></mtd><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mrow><mi>K</mi><mo>-</mo><mn>2</mn></mrow><mo>]</mo></mrow></mrow></mtd><mtd><mi>…</mi></mtd><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow></mtd></mtr></mtable><mo>]</mo></mrow><mo></mo><mrow><mrow><mo>·</mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>H</mi><mo></mo><mrow><mo>[</mo><mn>1</mn><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>H</mi><mo></mo><mrow><mo>[</mo><mn>2</mn><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mrow><mi>H</mi><mo></mo><mrow><mo>[</mo><mi>K</mi><mo>]</mo></mrow></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mo>-</mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>1</mn><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>2</mn><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mi>K</mi><mo>]</mo></mrow></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0018.tif" />

0079Because the matrix is a Toeplitz system, fast algorithms are available for finding the solution. This system has a unique solution if the first matrix is invertible, which is the case if all K Diracs in x(t) are distinct, that is if t_k≠t_l, ∀k≠l.

0080Given the coefficients 1, H[1], H[2], . . . , H[K] the filter H(z) can be factored into its roots

0000<maths id="MATH-US-00019" num="00019"><math overflow="scroll"><mrow><mrow><mi>H</mi><mo></mo><mrow><mo>(</mo><mi>z</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∏</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mrow><msub><mi>u</mi><mi>k</mi></msub><mo></mo><msup><mi>z</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup></mrow></mrow><mo>)</mo></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0019.tif" />

0081which leads to the K shifts t_kusing the above given relation between u_kand t_k.

0082Given the shifts t_k, the K values of the weights c_kcan be found by solving

0000<maths id="MATH-US-00020" num="00020"><math overflow="scroll"><mrow><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mi>τ</mi></mfrac><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><msup><mi></mi><mrow><mrow><mo>-</mo><mi></mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mfrac><mrow><mn>2</mn><mo></mo><mi>π</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>m</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>t</mi><mi>k</mi></msub></mrow><mi>τ</mi></mfrac></mrow></msup></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0020.tif" />

0083which leads to the following Vandermonde system

0000<maths id="MATH-US-00021" num="00021"><math overflow="scroll"><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mn>1</mn><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow><mo>]</mo></mrow></mrow></mtd></mtr></mtable><mo>]</mo></mrow><mo>=</mo><mrow><mrow><mfrac><mn>1</mn><mi>τ</mi></mfrac><mo></mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mi>…</mi></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><msub><mi>u</mi><mn>0</mn></msub></mtd><mtd><msub><mi>u</mi><mn>1</mn></msub></mtd><mtd><mi>…</mi></mtd><mtd><msub><mi>u</mi><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><msubsup><mi>u</mi><mn>0</mn><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mtd><mtd><msubsup><mi>u</mi><mn>1</mn><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mtd><mtd><mi>…</mi></mtd><mtd><msubsup><mi>u</mi><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>·</mo><mrow><mo>[</mo><mtable><mtr><mtd><msub><mi>c</mi><mn>0</mn></msub></mtd></mtr><mtr><mtd><msub><mi>c</mi><mn>1</mn></msub></mtd></mtr><mtr><mtd><mi>⋮</mi></mtd></mtr><mtr><mtd><msub><mi>c</mi><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msub></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0021.tif" />

0084which again has a unique solution when the K shifts t_kare distinct, t_k≠t_l, ∀k≠l. Because the matrix is a K×K Vandermonde equation system, known fast solution methods are available.

0085This result can easily be extended to a periodic stream of differentiated Diracs:

0000<maths id="MATH-US-00022" num="00022"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>r</mi><mo>=</mo><mn>0</mn></mrow><mrow><msub><mi>R</mi><mi>n</mi></msub><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>nr</mi></msub><mo></mo><mrow><msup><mi>δ</mi><mrow><mo>(</mo><mi>r</mi><mo>)</mo></mrow></msup><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>n</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0022.tif" />

0086with the periodicity conditions t_n+K=t_n+τ and c_n+K,r=c_nrfor all n.

0087This first signal x(t) is entirely determined by the K shifts t_kand the K′ weights c_nr, where

0000<maths id="MATH-US-00023" num="00023"><math overflow="scroll"><mrow><msup><mi>K</mi><mi>′</mi></msup><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>R</mi><mi>k</mi></msub><mo>.</mo></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0023.tif" />

0088which makes at most K+K′ degrees of freedom per period τ. The rate of innovation ρ is thus

0000<maths id="MATH-US-00024" num="00024"><math overflow="scroll"><mrow><mi>ρ</mi><mo>=</mo><mrow><mfrac><mrow><mi>K</mi><mo>+</mo><msup><mi>K</mi><mi>′</mi></msup></mrow><mi>τ</mi></mfrac><mo>.</mo></mrow></mrow></math></maths><img file="US2010042374A1_D0024.tif" />

0089Applying the new sampling method as in the previous examples, this signal is first convolved with a sampling kernel of a bandwidth B greater than or equal to the rate of innovation ρ of said first signal x(t), then sampled at a frequency greater than or equal to the maximum between B and ρ. Note that even sampling at a frequency ρ when the bandwidth B is greater than the rate of innovation ρ leads to a limited number of solutions among which the good solution may often be guessed.

0090The so generated sampled values y(nT) will then be sufficient to recover the spectral values X[m] using similar steps of the variant embodiment of the reconstruction method used in the case where x(t) is a periodic stream of weighted Diracs, leading then similarly to the recovery of the shifts t_kand the K′ weights c_nr.

0091We will now extend this result to signals x(t) belonging to the class of periodic piecewise polynomial signals of period τ, containing in each period K pieces of maximum degree R. If we differentiate a periodic piecewise polynomial x(t) R+1 times, we obtain a stream of K weighted and shifted Diracs or derivative of Diracs:

0000<maths id="MATH-US-00025" num="00025"><math overflow="scroll"><mrow><mrow><msup><mi>x</mi><mrow><mo>(</mo><mrow><mi>R</mi><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></msup><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mrow><mo>-</mo><mi>∞</mi></mrow></mrow><mi>∞</mi></munderover><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>r</mi><mo>=</mo><mn>0</mn></mrow><mrow><msub><mi>R</mi><mi>n</mi></msub><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>nr</mi></msub><mo></mo><mrow><msup><mi>δ</mi><mrow><mo>(</mo><mi>r</mi><mo>)</mo></mrow></msup><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>n</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0025.tif" />

0092Periodic piecewise polynomials signals x(t) are thus entirely determined by K shifts t_kand K′=(R+1)K weights. The rate of innovation ρ is

0000<maths id="MATH-US-00026" num="00026"><math overflow="scroll"><mrow><mi>ρ</mi><mo>=</mo><mrow><mfrac><mrow><mrow><mo>(</mo><mrow><mi>R</mi><mo>+</mo><mn>2</mn></mrow><mo>)</mo></mrow><mo></mo><mi>K</mi></mrow><mi>τ</mi></mfrac><mo>.</mo></mrow></mrow></math></maths><img file="US2010042374A1_D0026.tif" />

0093The Fourier coefficients of the derivative operator is defined by D[m]=i2πm and therefore the Fourier coefficients X^(R+1)[m] of the differentiated signal x^(R+1)(t) are equal to

0000<br /><i>X</i>^(R+1)<i>[m</i>]=(<i>i</i>2<i>πm/τ</i>)^R+1<i>X[m]</i>

0094with the periodicity conditions t_n+K=t_n+τ and c_n+K,r=c_nrfor all n.

0095This first signal x(t) is entirely determined by the K shifts t_kand the K′=(R+1)K weights. The rate of innovation ρ is thus

0000<maths id="MATH-US-00027" num="00027"><math overflow="scroll"><mrow><mi>ρ</mi><mo>=</mo><mrow><mfrac><mrow><mrow><mo>(</mo><mrow><mi>R</mi><mo>+</mo><mn>2</mn></mrow><mo>)</mo></mrow><mo></mo><mi>K</mi></mrow><mi>τ</mi></mfrac><mo>.</mo></mrow></mrow></math></maths><img file="US2010042374A1_D0027.tif" />

0096Applying the new sampling method as in the previous example, x(t) is first convolved with a kernel φ(t) of a bandwidth B greater than or equal to the rate of innovation ρ of said first signal x(t), for example with the differentiated sinc sampling kernel, or with another differentiated kernel.

0097We can then take τ/T samples regularly spaced apart in order to get a set of values y_s[n] from which the periodic piecewise polynomial signal of degree R x(t) can be faithfully reconstituted using the previously described annihilating filter method.

0098A similar reconstruction method can be applied for sampling and reconstructing periodic non-uniform splines of degree R, i.e. signals whose (R+1)th derivative is a periodic stream of K weighted and shifted Diracs. Likewise, a similar reconstruction method can be applied for periodic filtered piecewise polynomial signals.

0099Furthermore, this sampling and reconstruction method can be applied to piecewise bandlimited signals, i.e. to signals which are bandlimited except for jumps or discontinuities. Piecewise bandlimited signals can be seen as the sum of bandlimited signals with a stream of Diracs and/or with a piecewise polynomial signal:

0100x(t)=x_BL(t)+x_PP(t) where x_BL(t) is a L-Bandlimited signal and x_PP(t) is a piecewise polynomial signal.

0101The Fourier coefficients X[m] are defined by

0000<maths id="MATH-US-00028" num="00028"><math overflow="scroll"><mrow><mrow><mi>X</mi><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mo>{</mo><mrow><mtable><mtr><mtd><mrow><mrow><msub><mi>X</mi><mi>BL</mi></msub><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow><mo>+</mo><mrow><msub><mi>X</mi><mi>pp</mi></msub><mo></mo><mrow><mi>p</mi><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow></mrow></mrow></mtd><mtd><mi>if</mi></mtd></mtr><mtr><mtd><mrow><msub><mi>X</mi><mi>pp</mi></msub><mo></mo><mrow><mo>[</mo><mi>m</mi><mo>]</mo></mrow></mrow></mtd><mtd><mi>if</mi></mtd></mtr></mtable><mo></mo><mtable><mtr><mtd><mrow><mi>m</mi><mo>∈</mo><mrow><mo>[</mo><mrow><mrow><mo>-</mo><mi>L</mi></mrow><mo>,</mo><mi>L</mi></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>m</mi><mo>∉</mo><mrow><mo>[</mo><mrow><mrow><mo>-</mo><mi>L</mi></mrow><mo>,</mo><mi>L</mi></mrow><mo>]</mo></mrow></mrow></mtd></mtr></mtable></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0028.tif" />

0102The Fourier coefficients of the signal x(t) outside of the band [−L,L] are exactly equal to the Fourier coefficients of the piecewise polynomial. Therefore it is sufficient to take at least 2K(R+1) Fourier coefficients outside of the band [−L,L] to retrieve the signal x_PP(t). The Fourier coefficients of the bandlimited signal are then obtained by subtracting X_PP[m] from X[m] for mε[−L,L].

0103As a piecewise polynomial signal has 2K(R+1) and the bandlimited signal 2L+1 degrees of freedom, we can sample the signal x(t) using a periodized differentiated sinc sampling kernel bandlimited to 2L+4K(R+1)+1, because of symmetry constraints.

0104Finite Length Signals with Finite Rate of Innovation

0105A finite length signal with finite rate of innovation ρ clearly has a finite number of degrees of freedom. We will illustrate with several examples that those signals can be uniquely specified with a finite set of samples, and that the minimal number of samples in the set only depends on the number of degrees of freedom of the signal, but not on its bandwidth.

0106Consider first a continuous time signal x(t) with a finite number of weighted Diracs:

0000<maths id="MATH-US-00029" num="00029"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mi>δ</mi><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><msub><mi>t</mi><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0029.tif" />

0107x(t) clearly has 2K degrees of freedom, K from the weights c_kand K from the shifts t_kof the Diracs. We will see that N samples, N being greater than 2K, preferably greater than 2K+1, will be sufficient to recover the signal x(t), and describe an appropriate reconstruction method. Similar to the previous cases, the reconstruction method will require solving two systems of linear equations: one for the shifts of the Diracs and one for the weights of the Diracs.

0108In a first embodiment, the signal x(t) is filtered with a sinc kernel φ(t), as an example of infinite length sampling kernel. Sampled values y_s[n] of x(t) are obtained by filtering x(t) with the sinc(t/T) sampling kernel:

0000<br /><i>y</i>_s<i>[n]=<x</i>(<i>t</i>), <i>sinc</i>(<i>t/T−n</i>)>, <i>n=</i>0, . . . , <i>N−</i>1

0109By developing the inner product one shows that:

0000<maths id="MATH-US-00030" num="00030"><math overflow="scroll"><mrow><mrow><msub><mi>y</mi><mi>s</mi></msub><mo></mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mfrac><msup><mrow><mo>(</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow><mi>n</mi></msup><mi>π</mi></mfrac><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mrow><mi>sin</mi><mo></mo><mrow><mo>(</mo><mrow><mi>π</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><msub><mi>t</mi><mi>k</mi></msub><mo>/</mo><mi>T</mi></mrow></mrow><mo>)</mo></mrow></mrow><mo>·</mo><mfrac><mn>1</mn><mrow><mo>(</mo><mrow><mrow><msub><mi>t</mi><mi>k</mi></msub><mo>/</mo><mi>T</mi></mrow><mo>-</mo><mi>n</mi></mrow><mo>)</mo></mrow></mfrac></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0030.tif" />

0110This leads to:

0000<maths id="MATH-US-00031" num="00031"><math overflow="scroll"><mrow><msub><mi>Y</mi><mi>n</mi></msub><mo>=</mo><mrow><mrow><msup><mrow><mo>(</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow><mi>n</mi></msup><mo></mo><mrow><mi>P</mi><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>y</mi><mi>s</mi></msub><mo></mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mi>π</mi></mfrac><mo></mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><mrow><mi>sin</mi><mo></mo><mrow><mo>(</mo><mrow><mi>π</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mrow><msub><mi>t</mi><mi>k</mi></msub><mo>/</mo><mi>T</mi></mrow></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>P</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0031.tif" />

0111where

0000<maths id="MATH-US-00032" num="00032"><math overflow="scroll"><mrow><mrow><mi>P</mi><mo></mo><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><msub><mi>p</mi><mi>k</mi></msub><mo></mo><msup><mi>u</mi><mi>k</mi></msup></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0032.tif" />

0000has zeros at locations t_l/T for l=0, . . . , K−1

0112The right-hand side of this expression is a polynomial of degree K−1 in the variable n, thus applying K finite differences makes the left-hand side vanish, that is

0000<maths id="MATH-US-00033" num="00033"><math overflow="scroll"><mrow><mrow><mrow><msup><mi>Δ</mi><mi>k</mi></msup><mo></mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow><mi>n</mi></msup><mo></mo><mrow><mi>P</mi><mo></mo><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>y</mi><mi>x</mi></msub><mo></mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mn>0</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>for</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>n</mi></mrow><mo>=</mo><mi>K</mi></mrow></mrow><mo>,</mo><mi>…</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><mrow><mrow><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow><mo></mo><mstyle><mtext></mtext></mstyle><mo>⇔</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><msub><mi>p</mi><mi>k</mi></msub><mo></mo><mrow><msup><mi>Δ</mi><mi>k</mi></msup><mo></mo><mrow><mo>(</mo><mrow><msup><mrow><mo>(</mo><mrow><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow><mi>n</mi></msup><mo></mo><msup><mi>n</mi><mi>k</mi></msup><mo></mo><mrow><msub><mi>y</mi><mi>x</mi></msub><mo></mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>=</mo><mn>0</mn></mrow></mrow></math></maths><img file="US2010042374A1_D0033.tif" />

0113The p_kcan be retrieved by solving this system. With the p_k, the K roots of the polynomial P(u) can be retrieved, and thus the shifts t_k=Tu_k. Once the shifts t_khave been retrieved, the weights c_kcan be found with the above described method, i.e. by solving a linear system of equations.

0114The above method for reconstructing a signal which has been filtered by a sinc transfer function is easy to carry out and elegant. However, in the real world, many signals are measured by a measuring device <b>7</b> respectively transmitted over a channel <b>5</b> having a transfer function which can be more precisely approximated by a Gaussian transfer function φ_σ(t). It can be shown that similar to the sinc sampling kernel, 2K sample values y_s[n] obtained by filtering the signal with a Gaussian kernel φ₉₄(t) are sufficient to represent the signal x(t).

0115This can be demonstrated by computing the sample values

0000<maths id="MATH-US-00034" num="00034"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>y</mi><mi>s</mi></msub><mo></mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mo><</mo><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>,</mo><mrow><msup><mi></mi><mrow><mrow><mrow><mo>-</mo><msup><mrow><mo>(</mo><mrow><mrow><mi>t</mi><mo>/</mo><mi>T</mi></mrow><mo>-</mo><mi>n</mi></mrow><mo>)</mo></mrow><mn>2</mn></msup></mrow><mo>/</mo><mn>2</mn></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>σ</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mn>2</mn></mrow></msup><mo>>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>c</mi><mi>k</mi></msub><mo></mo><msup><mi></mi><mrow><mrow><mrow><mo>-</mo><msup><mrow><mo>(</mo><mrow><mrow><msub><mi>t</mi><mi>k</mi></msub><mo>/</mo><mi>T</mi></mrow><mo>-</mo><mi>n</mi></mrow><mo>)</mo></mrow><mn>2</mn></msup></mrow><mo>/</mo><mn>2</mn></mrow><mo></mo><msup><mi>σ</mi><mn>2</mn></msup></mrow></msup></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0034.tif" />

0116By expanding and regrouping the terms so as to have variables that depend solely on n and solely on k, we obtain:

0000<maths id="MATH-US-00035" num="00035"><math overflow="scroll"><mrow><msub><mi>Y</mi><mi>n</mi></msub><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>a</mi><mi>k</mi></msub><mo></mo><msubsup><mi>u</mi><mi>k</mi><mi>n</mi></msubsup></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0035.tif" />

0117where we have Y_n=eⁿ^{<sup2>2</sup2>}^/2σ^{<sup2>2 </sup2>}y_s[n], a_k=c_ke^−t^{<sub2>k</sub2>}^{<sup2>2</sup2>}^{/2 σ}^{<sup2>2</sup2>}^T^{<sup2>2 </sup2>}and u_k=e^t^{<sub2>k</sub2>}^/σ^{<sup2>2</sup2>}^T. Y_nis a linear combination of real exponentials. Thus the annihilating filter method can be used to find the K values u_kand a_k. This means that the values u_kcan be solved by finding the roots of an annihilating filter chosen such that

0000<maths id="MATH-US-00036" num="00036"><math overflow="scroll"><mrow><mrow><mrow><mi>h</mi><mo>*</mo><mi>Y</mi></mrow><mo>=</mo><mrow><mrow><mn>0</mn><mo></mo><mstyle><mtext></mtext></mstyle><mo>⇔</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mi>K</mi></munderover><mo></mo><mrow><msub><mi>h</mi><mi>k</mi></msub><mo></mo><msub><mi>Y</mi><mrow><mi>a</mi><mo>-</mo><mi>k</mi></mrow></msub></mrow></mrow></mrow><mo>=</mo><mn>0</mn></mrow></mrow><mo>,</mo><mrow><mi>n</mi><mo>=</mo><mi>K</mi></mrow><mo>,</mo><mi>…</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>,</mo><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow></mrow></math></maths><img file="US2010042374A1_D0036.tif" />

0118From the u_k, the shifts t_kcan be retrieved using t_k=σ²T ln u_k. Once the shifts t_kare obtained then we solve for a_ka Vandermonde equation system. The weights c_kare simply given by c_k=a_ke^t^{<sub2>k</sub2>}^{<sup2>2</sup2>}^2σ^{<sup2>2</sup2>}^T^{<sup2>2 </sup2>}

0119Infinite Length Signals with Local Finite Rate of Innovation

0120In this section, we will describe a sampling and local reconstruction method for sampling and reconstructing infinite length signals x(t) with a finite local rate of innovation ρ_τ(t) with respect to a moving window of size τ. We will in particular describe bilevel signals, and explain local reconstruction methods using sampling kernels with a compact support. Those results could be generalized to other 8-splines of different degree d.

0121Bilevel signals x(t) are infinite length continuous-time signals which take on two values, 0 and 1, with a known initial condition, for example x(0)=1. These signals are completely represented by their transition values (shifts) t_k. Suppose the signal x(t) has a finite local rate of innovation ρ as described above. This is the case of most signals produced by electronic digital circuits, where the rate of innovation is usually limited by the clocking of the integrated circuit generating the signal. Examples of common bilevel signals with a finite local rate of innovation include amplitude or modulation pulses or PAM, PPM signals among others. An example of bilevel signal is shown on <figref idref="DRAWINGS">FIG. 9</figref>.

0122If a bilevel signal is sampled with a box spline φ₀(t/T) shown on <figref idref="DRAWINGS">FIG. 10</figref>, then the sample values y_s[n] are given by the inner product between the bilevel signal and the box function:

0000<maths id="MATH-US-00037" num="00037"><math overflow="scroll"><mrow><mrow><mrow><msub><mi>y</mi><mi>s</mi></msub><mo></mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>=</mo><mrow><mo><</mo><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow></mrow></mrow><mo>,</mo><mrow><mrow><msub><mi>ϕ</mi><mn>0</mn></msub><mo></mo><mrow><mo>(</mo><mrow><mrow><mi>t</mi><mo>/</mo><mi>T</mi></mrow><mo>-</mo><mi>n</mi></mrow><mo>)</mo></mrow></mrow><mo>>=</mo><mrow><msubsup><mo>∫</mo><mrow><mo>-</mo><mi>∞</mi></mrow><mi>∞</mi></msubsup><mo></mo><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>ϕ</mi><mn>0</mn></msub><mo></mo><mrow><mo>(</mo><mrow><mrow><mi>t</mi><mo>/</mo><mi>T</mi></mrow><mo>-</mo><mi>n</mi></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><mo></mo><mi>t</mi></mrow></mrow></mrow></mrow></mrow></math></maths><img file="US2010042374A1_D0037.tif" />

0123The sample value y_s[n] simply corresponds to the area occupied by the signal x(t) in the interval [nT, (n+1)T]. Thus, if there is at most one transition per box, then we can recover the transition from the sample. The non-bandwidth limited signal x(t) is thus uniquely determined from the finite set of samples y_s[n].

0124However, if the bilevel signal x(t) is shifted by an unknown shift, then there may be two transitions in an interval of length T and one box function will not be sufficient to recover the transitions. To sample this signal, one can use a sampling kernel φ(t/T) with a larger support and with added information. For example, the hat spline function defined by

0000<maths id="MATH-US-00038" num="00038"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>ϕ</mi><mn>1</mn></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>1</mn><mo>-</mo><mrow><mo></mo><mi>t</mi><mo></mo></mrow></mrow></mtd><mtd><mrow><mrow><mi>if</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mrow><mo></mo><mi>t</mi><mo></mo></mrow></mrow><mo>&lt;</mo><mn>1</mn></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mi>else</mi></mtd></mtr></mtable></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Fig</mi><mo>.</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>11</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2010042374A1_D0038.tif" />

0125leads to two sample values in each interval [nT, (n+1)T] with which the maximum two transitions time t_k(shifts) in the intervals can be uniquely retrieved.

0126In fact, if there are at most 2 transitions in the interval [n,n+2], then the possible configurations are

0127(0,0), (0,1), (0,2), (1,0), (1,1), (2,0)

0128where the first and second component indicate the number of transitions in the intervals [n, n+1] and [n+1, n+2] respectively.

0129Since the hat sampling kernel is of degree one, we obtain for each configuration a quadratic system of equations with variables t₀, t₁:

0000<maths id="MATH-US-00039" num="00039"><math overflow="scroll"><mrow><msub><mi>y</mi><mi>n</mi></msub><mo>=</mo><mrow><mrow><msubsup><mo>∫</mo><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mo></mo><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mi>t</mi><mo>-</mo><mi>n</mi></mrow><mo>)</mo></mrow><mo></mo><mrow><mo></mo><mi>t</mi></mrow></mrow></mrow><mo>+</mo><mrow><msubsup><mo>∫</mo><mi>n</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msubsup><mo></mo><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mi>n</mi></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mo></mo><mrow><mo></mo><mi>t</mi></mrow></mrow></mrow></mrow></mrow></math></maths><maths id="MATH-US-00039-2" num="00039.2"><math overflow="scroll"><mrow><msub><mi>y</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><mrow><msubsup><mo>∫</mo><mi>n</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msubsup><mo></mo><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mi>t</mi><mo>-</mo><mrow><mo>(</mo><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mo></mo><mrow><mo></mo><mi>t</mi></mrow></mrow></mrow><mo>+</mo><mrow><msubsup><mo>∫</mo><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow></msubsup><mo></mo><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>-</mo><mrow><mo>(</mo><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mo></mo><mrow><mo></mo><mi>t</mi></mrow></mrow></mrow></mrow></mrow></math></maths>

0130It can easily be shown that this system of equation admits one solution and that this solution is unique.

0131Similarly, infinite length piecewise polynomial signals with a local finite rate of innovation can be sampled and reconstructed with a box sampling kernel. Consider an infinite length piecewise polynomial signal x(t) where each piece is a polynomial of degree R and defined over an interval [t_k−1,t_k], that is,

0000<maths id="MATH-US-00040" num="00040"><math overflow="scroll"><mrow><mrow><mi>x</mi><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mrow><msub><mi>x</mi><mn>0</mn></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mi>R</mi></munderover><mo></mo><mrow><msub><mi>c</mi><mrow><mn>0</mn><mo></mo><mi>m</mi></mrow></msub><mo></mo><msup><mi>t</mi><mi>m</mi></msup></mrow></mrow></mrow></mtd><mtd><mrow><mi>t</mi><mo>∈</mo><mrow><mo>[</mo><mrow><mn>0</mn><mo>,</mo><msub><mi>t</mi><mn>0</mn></msub></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>x</mi><mn>1</mn></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mi>R</mi></munderover><mo></mo><mrow><msub><mi>c</mi><mrow><mn>1</mn><mo></mo><mi>m</mi></mrow></msub><mo></mo><msup><mi>t</mi><mi>m</mi></msup></mrow></mrow></mrow></mtd><mtd><mrow><mi>t</mi><mo>∈</mo><mrow><mo>[</mo><mrow><msub><mi>t</mi><mn>0</mn></msub><mo>,</mo><msub><mi>t</mi><mn>1</mn></msub></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>…</mi></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>x</mi><mi>K</mi></msub><mo></mo><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mi>R</mi></munderover><mo></mo><mrow><msub><mi>c</mi><mi>Km</mi></msub><mo></mo><mi>t</mi></mrow></mrow></mrow></mtd><mtd><mrow><mi>t</mi><mo>∈</mo><mrow><mo>[</mo><mrow><msub><mi>t</mi><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>t</mi><mi>K</mi></msub></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mi>…</mi></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable></mrow></mrow></math></maths><img file="US2010042374A1_D0039.tif" />

0132Each polynomial piece x_k(t) contains R+1 unknown coefficients c_km. The transition values are easily obtained once the pieces x_k−1(t) and x_k(t) are determined, thus there are 2(R+1)+1 degrees of freedom. If there is one transition in an interval of length T then the maximal local rate of innovation is ρ_m(T)=(2(R+1)+1)/T. Therefore, in order to recover the polynomial pieces and the transition we need to have at least 2(R+1)+1 samples per interval T. This can be achieved for example by sampling with the following box sampling kernel:

0000<maths id="MATH-US-00041" num="00041"><math overflow="scroll"><mrow><msub><mi>ϕ</mi><mn>0</mn></msub><mo></mo><mrow><mo>(</mo><mrow><mi>t</mi><mo>/</mo><mfrac><mi>T</mi><mrow><mrow><mn>2</mn><mo></mo><mrow><mo>(</mo><mrow><mi>R</mi><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mn>1</mn></mrow></mfrac></mrow><mo>)</mo></mrow></mrow></math></maths><img file="US2010042374A1_D0040.tif" />

0133For example, if the signal x(t) to reconstruct is a piecewise linear signal (R=1) with maximal one transition in each interval T, then we need at least 5 samples per interval.

0134We can generalize this case by noting that the Rth derivative of a piecewise polynomial of degree R is a piecewise constant signal which can be sampled and reconstructed using the same method.

0135Multidimensional Signals

0136The sampling and reconstruction method of the invention is not restricted to one-dimensional signals, but can also be used with multidimensional signals. For example, an interesting case appears with two-dimensional images, where bilevel and multi-level signals are quite common. Furthermore, many two-dimensional picture signals have a finite length and can only be seen through an optical system with a transfer function which is at least approximately Gaussian.

0137Consider the cases shown on <figref idref="DRAWINGS">FIGS. 12</figref>, <b>13</b> and <b>14</b>:

0138<figref idref="DRAWINGS">FIG. 12</figref>: unit square with a 0/1 transition given by an arbitrary function.

0139<figref idref="DRAWINGS">FIG. 13</figref>: unit square, with a 0/1 transition given by a smooth, for example bandlimited, function.

0140<figref idref="DRAWINGS">FIG. 14</figref>: unit square, with a 0/1 transition given by a piecewise polynomial function.

0141The sampling and reconstruction method developed in the previous sections can be applied on a set of lines, for example on a square grid, through the square. Obviously, a perfect reconstruction of the boundaries shown on <figref idref="DRAWINGS">FIGS. 13 and 14</figref> is possible, but a priori not for the case illustrated on <figref idref="DRAWINGS">FIG. 12</figref>. Depending on the a-priori known class of function to which the boundary function belongs, a different sampling kernel φ(t) will be used for sampling lines through the image and to allow a perfect reconstruction of the image if the sampling is fine enough. For instance, if the image is piecewise polynomial with boundaries that are either bandlimited or piecewise polynomial, then separable one-dimensional sampling using spline kernels is possible that allows, with the above described method, a perfect reconstruction of the boundary and thus of the bilevel image, if the sampling is fine enough, i.e. if the sampling rate is higher than the rate of innovation of the boundary function.

0142Instead of scanning a picture along lines with a one-dimensional sampling kernel, one can scan it with a two-dimensional sampling kernel. Indeed, this is exactly what a scanner or a digital camera does: the image is first filtered by the optical system which has a two-dimensional φ(x,y) transfer function and then sampled at regular intervals by the matrix sensor. In fact, the above-described methods can also be applied to two-dimensional signals which need to be filtered by a two-dimensional sampling kernel and sampled by a two-dimensional sampling system with a sampling rate at least equal to the two-dimensional rate of innovation.

0143The newly defined class of signals with finite rate of innovation ρ includes a broad variety of signals of which the examples discussed above are only a subset. The new sampling method can however be applied to many signals x(t) with a finite rate of innovation ρ, regularly sampled so as to generate a set of sampled values y(nT) at a sampling frequency f=1/T greater than said rate of innovation ρ, said sampled values y(nT) representing entirely the first signal x(t). Depending on the form of the resulting equation system which only depends on the class of signal to reconstruct, there can be an easy solution method for retrieving the shifts and weights.

0144In the above-described embodiments, the new sampling and reconstruction methods are applied to sample and/or reconstruct a noiseless first signal x(t). The one skilled in the art will however recognize that in applications with noisy conditions, the same methods can be used with a higher sampling frequency, thus providing a higher number of sampled values x(nT). The corresponding equation systems described above can then be solved using well-known spectral estimation techniques, such as for example the singular value decomposition (SVD) method, in order to overcome the uncertainty induced by the noise.

0145In the above described embodiments, the sampled signal y_s[n] is used for reconstructing the signal y(t) before sampling, or at least a signal x(t) related to y(t) by a transfer function φ(t). The one skilled in the art will understand however that the sample values y_s[n], or even the sets of shifts t_kand weights c_kretrieved from those sample values, can be stored, transmitted and processed. In particular, a set of values y_s[n] obtained by sampling a first signal y₁(t) at a sub-Nyquist rate can be added to a second set of values y_s2[n] obtained by sampling a second signal y₂(t) at a sub-Nyquist rate. The rate of innovation ρ_sof the signal y_s(t)=y₁(t)+y₂(t) is obviously the sum of the rates of innovation ρ₁, ρ₂of the summed signals y₁(t) and y₂(t). Therefore, for the sum of the sampled values to be a sufficient representation of y_s(t), the number of samples of the signal y_s(t) in a time interval must be greater than the sum of the number of degrees of freedom of the two added signals in this time interval. Therefore, if one wishes to perform some processing operations on the set of sampled values, one may increase the sampling rate in order to have a sufficient number of samples in the processed signal.

0146The sampling method and the reconstruction method of the invention can be performed by hardware circuits or systems and/or by a computer program product, including memories in which a software or a firmware has been stored and a computer program product directly loadable into the internal memory of a digital processing system and comprising software code portions for performing the above described methods. Accordingly, the invention also relates to a circuit, to a system and to a computer program product adapted to carry out the above described methods, and to a processing circuit or program for processing sets of values obtained by sampling a signal with the above described method.