Method and an apparatus for sampling rate conversion

Abstract

A signal conversion from an input signal to an output signal where the filter used is factorized so that the conversion comprises determining 1) only a first factor at each sampling time of the input signal, where this first factor is independent on the sampling times of the output signal, and 2) only a second factor at each sampling time of the output signal, where this second factor is independent of the sampling times of the input signal. This reduces the computational load for this conversion. In addition, for most filters, the factors may be calculated recursively further increasing the computational load and also reducing the storage requirements. This allows for instantaneous changes in the sampling rates or non-uniform sampling rates with low computational requirements and low memory usage.

Claims

1. A method for converting an input signal to an output signal wherein the input signal has an input signal sampling rate that is non-uniform, the input signal representing, at each of a plurality of first points in time, τ, a first value x(τ), such that the input signal includes a plurality of first values x(τ.sub.0) to x(τ.sub.n) corresponding to separate, respective first points in time, τ.sub.0 to τ.sub.n, wherein n is a nonzero integer, the output signal representing, at each of a plurality of second points in time, t, a second value y(t), such that the output signal represents a plurality of second values y(t.sub.0) to y(t.sub.m) corresponding to separate respective second points in time t.sub.0 to t.sub.m, wherein m is a nonzero integer, the method comprising: generating the output signal responsive to the input signal using a controller comprising at least one of a microprocessor, a digital signal processor (DSP), or a field-programmable gate array (FPGA), the plurality of second values y(t.sub.0) to y(t.sub.m) based on, for each given second point in time t.sub.m, determining a corresponding second value y(t.sub.m) based on the controller executing a computer program stored in a storage device to execute the following Equation (1) that is stored in the storage device:
y(t.sub.m)=h.sub.1(t.sub.m)Σ.sub.n=0.sup.n=λ.sup.mx(τ.sub.n)*h.sub.2(τ.sub.n)  (1) wherein, in Equation (1), h.sub.1(t.sub.m) is a first factor that is calculated as a first exponential depending on the second point in time t.sub.m but not depending on any of the first points in time τ.sub.0 to τ.sub.n based on the controller executing the computer program stored in the storage device, h.sub.2(τ.sub.n) is a second factor that is calculated as a second exponential depending on the first point in time τ.sub.n but not depending on any of the second points in time t.sub.0 to t.sub.m based on the controller executing the computer program stored in the storage device, and λ.sub.m is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (2) that is stored in the storage device: $\begin{array}{cc}{\lambda }_m=.Math.m\frac{T_y{\in }_{y,m}}{T_x{\in }_{x,n}}.Math.& \left(2\right)\end{array}$ wherein, in Equation (2), T.sub.x is a constant that is stored in the storage device, T.sub.y is another constant that is stored in the storage device, ϵ.sub.x,n is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (3) that is stored in the storage device: $\begin{array}{cc}{\in }_{x,n}=\frac{{\tau }_n}{n{T}_x},& \left(3\right)\end{array}$  and ϵ.sub.y,m is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (4) that is stored in the storage device: $\begin{array}{cc}{\in }_{y,m}=\frac{t_m}{m{T}_y}.& \left(4\right)\end{array}$

2. The method according to claim 1, wherein the input signal represents the first value x(τ) where not all points in time τ are equidistant in time.

3. The method according to claim 2, wherein the input signal represents the first value x(τ) where x(τ1), x(τ2), x(τ3) and x(τ4) exist, where τ1 and τ2 are neighbouring and τ3 and τ4 are neighbouring, and where |τ2−τ1|>1.001*(|τ4−τ3|).

4. The method according to claim 1, wherein, for each first point in time, the second factor is calculated.

5. The method according to claim 1, wherein, for each second point in time not being identical to a first point in time, the second factor is not calculated.

6. The method according to claim 1, wherein the first factor is calculated for each second point in time.

7. The method according to claim 1, wherein, for each first point in time not being identical to a second point in time, the first factor is not calculated.

8. The method according to claim 1, wherein, in Equation (1), Σ.sub.n=0.sup.n=λ.sup.mx(τ.sub.n)*h.sub.2(τ.sub.n) is a sum of third values each corresponding to different first points in time.

9. The method according to claim 6, wherein, in Equation (1), Σ.sub.n=0.sup.n=λ.sup.mx(τ.sub.n)*h.sub.2(τ.sub.n) is a sum of third values each corresponding to different first points in time, and the different first points in time are a predetermined number of latest first points in time prior to the second point in time for which the second value y(t.sub.m) is determined.

10. The method according to claim 1, wherein h.sub.1(t.sub.m) is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (5) that is stored in the storage device:
h.sub.1(t.sub.m)=a(e.sup.bT.sup.y.sup.ϵ.sup.y,m).sup.m  (5) wherein, in Equation (5), a is a first constant that is stored in the storage device and b is a second constant that is stored in the storage device, and h.sub.2(τ.sub.n) is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (6) that is stored in the storage device:
h.sub.2(τ.sub.n)=c(e.sup.−bT.sup.x.sup.ϵ.sup.x,n).sup.n  (6) wherein, in Equation (6), c is a third constant that is stored in the storage device and b is the second constant that is stored in the storage device.

11. An apparatus for converting an input signal to an output signal wherein the input signal has an input signal sampling rate that is non-uniform, the apparatus comprising: a signal input, a signal output, a controller including at least one of a microprocessor, a digital signal processor (DSP), or a field-programmable gate array (FPGA), the controller being configured to execute a computer program stored in a storage device to: receive the input signal from the signal input, the input signal representing, at each of a plurality of first points in time, τ, a first value x(τ), such that the input signal represents a plurality of first values x(τ.sub.0) to x(τ.sub.n) corresponding to separate, respective first points in time, τ.sub.0 to τ.sub.n, wherein n is a nonzero integer, generate the output signal responsive to the input signal using the controller, the output signal representing, at each of a plurality of second points in time, t, a second value y(t), such that the output signal represents a plurality of second values y(t.sub.0) to y(t.sub.m) corresponding to separate respective second points in time t.sub.0 to t.sub.m, wherein m is a nonzero integer, and transmit the output signal from the signal output, wherein the controller is configured to generate the plurality of second values y(t.sub.0) to y(t.sub.m) based on, for each given second point in time t.sub.m to determining a corresponding second value y(t.sub.m) based on the controller executing the computer program stored in the storage device to execute the following Equation (1) that is stored in the storage device:
y(t.sub.m)=h.sub.1(t.sub.m)Σ.sub.n=0.sup.n=λ.sup.mx(τ.sub.n)*h.sub.2(τ.sub.n)  (1) wherein, in Equation (1), h.sub.2(t.sub.m) is a first factor that is calculated as a first exponential depending on the second point in time t.sub.m but not depending on any of the first points in time τ.sub.0 to τ.sub.m based on the controller executing the computer program stored in the storage device, h.sub.2 (τ.sub.n) is a second factor that is calculated as a second exponential depending on the first point in time τ.sub.n but not depending on any of the second points in time t.sub.0 to t.sub.m based on the controller executing the computer program stored in the storage device, and λ.sub.m is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (2) that is stored in the storage device: $\begin{array}{cc}{\lambda }_m=.Math.m\frac{T_y{\in }_{y,m}}{T_x{\in }_{x,n}}.Math.& \left(2\right)\end{array}$ wherein, in Equation (2), T.sub.x is a constant that is stored in the storage device, T.sub.y is another constant that is stored in the storage device, ϵ.sub.x,n is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (3) that is stored in the storage device: $\begin{array}{cc}{\in }_{x,n}=\frac{{\tau }_n}{n{T}_x},& \left(3\right)\end{array}$  and ϵ.sub.y,m is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (4) that is stored in the storage device: $\begin{array}{cc}{\in }_{y,m}=\frac{t_m}{m{T}_y}.& \left(4\right)\end{array}$

12. The apparatus according to claim 11, wherein the signal input comprises an analogue signal input and a A/D converter.

13. The apparatus according to claim 11, wherein the signal input comprises an element configured to receive data packets and derive from each data packet, a separate first value x(τ) and a separate first point in time, τ.

14. The apparatus according to claim 11, further comprising a clocking element for generating the second points in time.

15. The apparatus according to claim 11, wherein h.sub.1(t.sub.m) is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (5) that is stored in the storage device:
h.sub.1(t.sub.m)=a(e.sup.bT.sup.y.sup.ϵ.sup.y,m).sup.m  (5) wherein, in Equation (5), a is a first constant that is stored in the storage device and b is a second constant that is stored in the storage device, and h.sub.2(τ.sub.n) is calculated based on the controller executing the computer program stored in the storage device to execute the following Equation (6) that is stored in the storage device:
h.sub.2(τ.sub.n)=c(e.sup.−bT.sup.x.sup.ϵ.sup.x,n).sup.n  (6) wherein, in Equation (6), c is a third constant that is stored in the storage device and b is the second constant that is stored in the storage device.

16. A computer program stored on a computer-readable medium for converting an input signal to an output signal wherein the input signal has an input signal sampling rate that is non-uniform, the computer program comprising executable instructions that cause a computer which includes at least one of a microprocessor, a digital signal processor (DSP), or a field-programmable gate array (FPGA) to: receive the input signal representing, at each of a plurality of first points in time, τ, a first value x(τ), such that the input signal represents a plurality of first values x(τ.sub.0) to x(τ.sub.n) corresponding to separate, respective first points in time, τ.sub.0 to τ.sub.n, wherein n is a nonzero integer, generate the output signal responsive to the input signal using the computer, the output signal representing, at each of a plurality of second points in time, t, a second value y(t), such that the output signal represents a plurality of second values y(t.sub.0) to y(t.sub.m) corresponding to separate respective second points in time t.sub.0 to t.sub.m, wherein m is a nonzero integer, and wherein the generating the output signal includes generating the plurality of second values y(t.sub.0) to y(t.sub.m) based on, for each given second point in time t.sub.m, determining a corresponding second value y(t.sub.m) based on the computer executing the computer program stored on the computer-readable medium to execute the following Equation (1) that is stored on the computer-readable medium:
y(t.sub.m)=h.sub.1(t.sub.m)Σ.sub.n=0.sup.n=λ.sup.mx(τ.sub.n)*h.sub.2(τ.sub.n)  (1) wherein, in Equation (1), h.sub.1(t.sub.m) is a first factor that is calculated as a first exponential depending on the second point in time t.sub.m but not depending on any of the first points in time τ.sub.0 to τ.sub.n based on the computer executing the computer program stored on the computer-readable medium, h.sub.2(τ.sub.n) is a second factor that is calculated as a second exponential depending on the first point in time τ.sub.n but not depending on any of the second points in time t.sub.0 to t.sub.m based on the computer executing the computer program stored on the computer-readable medium, and λ.sub.m is calculated based on the computer executing the computer program stored on the computer-readable medium to execute the following Equation (2) that is stored on the computer-readable medium: $\begin{array}{cc}{\lambda }_m=.Math.m\frac{T_y{\in }_{y,m}}{T_x{\in }_{x,n}}.Math.& \left(2\right)\end{array}$ wherein, in Equation (2), T.sub.x is a constant that is stored on the computer-readable medium, T.sub.y is another constant that is stored on the computer-readable medium, ϵ.sub.x,n is calculated based on the computer executing the computer program to execute the following Equation (3) that is stored on the computer-readable medium: $\begin{array}{cc}{\in }_{x,n}=\frac{{\tau }_n}{n{T}_x},& \left(3\right)\end{array}$  and ϵ.sub.y,m is calculated based on the computer executing the computer program to execute the following Equation (4) that is stored on the computer-readable medium: $\begin{array}{cc}{\in }_{y,m}=\frac{t_m}{m{T}_y}.& \left(4\right)\end{array}$

17. The computer program according to claim 16, wherein h.sub.1(t.sub.m) is calculated based on the computer executing the computer program to execute the following Equation (5) that is stored on the computer-readable medium:
h.sub.1(t.sub.m)=a(e.sup.bT.sup.y.sup.ϵ.sup.y,m).sup.m  (5) wherein, in Equation (5), a is a first constant that is stored on the computer-readable medium and b is a second constant that is stored on the computer-readable medium, and h.sub.2(τ.sub.n) is calculated based on the computer executing the computer program to execute the following Equation (6) that is stored on the computer-readable medium:
h.sub.2(τ.sub.n)=c(e.sup.−bT.sup.x.sup.ϵ.sup.x,n).sup.n  (6) wherein, in Equation (6), c is a third constant that is stored on the computer-readable medium and b is the second constant that is stored on the computer-readable medium.

Description

(1) Preferred embodiments of the invention will now be further described with reference to the drawings, in which:

(2) FIG. 1 illustrates a block diagram of the non-uniform sampling rate conversion illustrated as reconstruction and resampling in the continuous-time domain.

(3) FIG. 2 illustrates a block diagram representing the discrete-to-continuous block as a sequence-to-impulses operation followed by a reconstruction filter.

(4) FIG. 3 illustrates a block diagram for time-varying discrete-time system for non-uniform sampling rate conversion.

(5) FIG. 4. Illustrates an interpretation of a non-uniform sampling rate converter by considering samples of the function h(t−τ), i.e. {h(t.sub.m−τ.sub.n)}, for an underlying system given by h(t)=e.sup.−αtu(t).

(6) FIG. 5. Is a block-diagram representation of the time-varying filter h[n, m] for an associated continuous-time first-order system. Both systems are input-output equivalent. The interchange of the last two operations results in the bottom one having a recursive filter parametrized by cy.

(7) FIG. 6. Is a block-diagram representation for non-uniform sampling rate conversion where the underlying continuous-time filter consists of a linear combination of first-order systems.

(8) FIG. 7. Is a block-diagram representation of non-uniform sampling rate conversion for an underlying continuous-time second-order system h(t). The last block takes the imaginary part of the complex input sample.

(9) FIG. 8. Illustrates a structure for real poles with multiplicity.

(10) FIG. 9. Illustrates a structure for several systems with real poles with multiplicity.

(11) While the invention is susceptible to various modifications and alternative forms, specific embodiments have been shown by way of examples in the drawings and will be described in detail herein. It should be understood, however, that the invention is not intended to be limited to the particular forms disclosed. Rather, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

(12) It should be understood that the detailed description and specific examples, while indicating embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.

(13) In general, the present invention relates to a method enabling non-uniform sampling rate conversion of signals. In the following, the invention will primarily be described in relation to an embodiment where the method is described through block diagrams and where the converted signals may be in any suitable form such as acoustic signals, such as audio signals, such as telecommunication signals and the like.

(14) The invention may further enable the conversion of sampling rates of signals arbitrarily while adapting to instantaneous changes in the sampling rate over time. This may be done by accommodating the processing of sequences at non-uniform input and output sampling rates in a computationally efficient manner, requiring low complexity and with low memory requirements.

(15) Sampling rate conversion may be understood by considering the reconstruction of the discrete-time signals involved in the process. In particular, it may be possible to associate a continuous-time signal x.sub.c(t) to a given discrete-time sequence {x.sub.n} at time instants τ.sub.n=nT.sub.xϵ.sub.x,n for some T.sub.x>0 and ϵ.sub.x,n∈ by assuming that x.sub.c(t) may be constructed from the non-uniform samples {x.sub.n} in the following manner:

(16) $\begin{array}{cc}{x}_c\left(t\right)=\underset{n\in \mathbb{Z}}{.Math.}{x}_n{h}_r\left(t-{\tau }_n\right)& \left(1\right)\end{array}$

(17) The continuous-time signal x.sub.c(t) may be resampled, in a controller 10, at time instants t.sub.m=mT.sub.yϵ.sub.y,m for some T.sub.y>0 and ϵ.sub.y,m∈, it may be desirable to perform some processing by means of a filter 105 before—e.g. in order to avoid aliasing—and sample the signal y(t)=(x*h.sub.p)(t) instead, see the block diagram 101 of FIG. 1. Then, non-uniform sampling rate conversion comprises taking the sequence {x.sub.n} and generating the sequence {y.sub.m} for general non-uniform input and output rates. In principle, this process may be carried out in the continuous-time domain by considering it as resampling after reconstruction of x.sub.c(t) from the non-uniform samples {x.sub.n}. This may be carried out by means of a discrete-to-continuous block 103, which takes a sequence of {x.sub.n} as input and outputs a continuous time signal x.sub.c(t). Note that the filter 105 may be an ideal low-pass filter whose cut-off frequency satisfies the considerations about the Nyquist rate relative to x.sub.c(t), the system outputs the non-uniform samples {x(t.sub.m)}. This process is illustrated in 105 in the block diagram 101 of FIG. 1. It may be assumed that the sampling instants form a strictly increasing sequence which is guaranteed if

(18) $\begin{array}{cc}{ϵ}_{.Math.,l+1}>{ϵ}_{.Math.,l}\frac{l}{l+1}& \left(2\right)\end{array}$

(19) for all l∈.

(20) The continuous-to-discrete block 107 takes a continuous-time signal y.sub.c(t) and outputs its samples y.sub.m=y(t.sub.m). The operation of the discrete-to-continuous block 103 may be further split into two parts. FIG. 2 shows its two components in the block diagram of 201. The first block 203 converts the sequence to an impulse train, i.e. it outputs the continuous-time signal x.sub.nδ(t−τ.sub.n). The resulting signal is then passed through a reconstruction filter 205. It may be possible to combine the reconstruction filter 205 and the filter 105 into a single filter h(t)=(h.sub.r*h.sub.p)(t) (herein after denoted as h(⋅)). Then, the signal to be resampled after reconstruction y.sub.c(t)=Σx.sub.nh(t−τ.sub.n) may generate the samples

(21) $\begin{array}{cc}{y}_m=\underset{n\in \mathbb{Z}}{.Math.}{x}_{n}h\left(t_m-{\tau }_n\right)& \left(3\right)\end{array}$

(22) From (3), it may be seen that the entire conversion process may be carried out in the discrete-time domain by considering h.sub.n,m=h(t.sub.m−τ.sub.n) as a time-variant discrete-time system, see the block diagram 301 of FIG. 3.

(23) Note that the coefficients h.sub.n,m correspond to non-uniform samples of h(⋅). In the next sections, it will be shown how the computation of this samples may be done efficiently with low memory and computational requirements when h(⋅) comprises a linear combination of exponentials. Such filters may for instance be Infinite Impulse Response (IIR) filters. An IIR filter may comprise a plurality of filter types such as a Butterworth filter, such as a Chebyshev filter, such as an Elliptic filter (also known as a Cauer filter), such as a Bessel filter.

(24) Uniform sampling rate conversion may be seen as a particular case of the non-uniform case, i.e. ϵ.sub.x,n=ϵ.sub.y,m=1 for all n, m∈. In this setting, the reconstruction filter may be considered as an ideal filter performing bandlimited interpolation given by h.sub.r(t)=sinc(t/T.sub.x). Then, h.sub.p(t) may be taken as an antialiasing filter appropriately chosen according to the new sampling rate. Therefore, it may be common in practice to choose the filter h(t)=(h.sub.r*h.sub.p)(t) as a causal filter approximating an ideal one with cut-off frequency min{π/T.sub.x, π/T.sub.y} rad/s. The uniform samples of the signal y.sub.c(t), denoted by y[m]=y(mT.sub.y), may then be written as

(25) $\begin{array}{cc}y\left[m\right]=\underset{n\in \mathbb{Z}}{.Math.}x\left[n\right]h\left(m{T}_y-n{T}_x\right)& \left(4\right)\end{array}$

(26) for m∈ where x[n] may be the uniform input sequence. The conversion process may also be carried out in the continuous-time domain. Equivalently, it may be performed in the discrete-time domain by considering the time-varying filter h[n, m]=h(mT.sub.y−nT.sub.x). The discrete-time approach may be in general preferable. One of the advantages of the resampling after reconstruction approach in the continuous-time domain may be that it does not make any assumption whatsoever of the relationship between the two sampling rates, i.e. the framework may be valid for any two arbitrary sampling rates.

(27) Similarly to the non-uniform case, each output sample may require knowledge of the samples of the impulse response {h(mT.sub.y−nT.sub.x). This set of samples may, in principle, be different for each output sample and for changes in T.sub.x or T.sub.y when considering non-uniform rates. It is shown that the present invention may compute efficiently, in a recursive manner, and with low memory requirements this new set of samples for each output sampling rate and for instantaneous changes in the sampling rates.

(28) The key aspect of this embodiment is to make non-uniform sampling rate conversion efficient based on a useful decomposition of the impulse response h(⋅). In particular, the approach of the present embodiment may be based on the observation that filters of interest used in practice may be separated in the following manner:
h(t−τ)=h.sub.1(t)h.sub.2(τ)u(t−τ)   (5)

(29) where u(⋅) is defined as u(t)=0 for t<0 and u(t)=1 for t≥0. This separation property satisfied by the impulse response may enable to express the output signal as

(30) $\begin{array}{cc}{y}_m=h_1\left(t_m\right)\underset{n\ge 0}{.Math.}{x}_n{h}_2\left({\tau }_n\right)u\left(t_m-{\tau }_n\right)& \left(6\right)\end{array}$

(31) where it may be assumed that the input signal may be causal, i.e. x.sub.n=0 for n≥0. It should be noted that the summation may be finite since u(t.sub.m−τ.sub.n)≠0 only for t.sub.m>τ.sub.n. Equivalently, it may be further denoted that

(32) $\begin{array}{cc}{\lambda }_{m,n}:=.Math.m\frac{T_y{ϵ}_{y,m}}{T_x{ϵ}_{x,n}}.Math.& \left(7\right)\end{array}$

(33) where └⋅┘ may denote the floor function. Thus, the summation comprises the values of n such that 0≤n≤λ.sub.m,n. It may be clear that there may always exist some integer value λ.sub.m such that
{n∈:0≤n≤λ.sub.m,n}={n∈:n=0, . . . λ.sub.m}   (8)

(34) Then, it may be possible to write

(35) $\begin{array}{cc}{y}_m=h_1\left(t_m\right)\underset{n=0}{\overset{{\lambda }_m}{.Math.}}{x}_n{h}_2\left({\tau }_n\right)& \left(9\right)\end{array}$

(36) The complexity in this expression may reduce to computing the values at the corresponding non-uniform instants of both factors of h(⋅). This factorization may allow separating the output sampling instants into the factor h.sub.1(t.sub.m) and a second factor comprising a summation whose terms may solely depend on the input sampling instants and where the number of terms may be given by a relationship between input and output sampling instants. It will be shown below how this calculation may be done recursively with the added complexity of an exponentiation whenever the corresponding ϵ.sub.⋅,l are not constant.

(37) An example of a relevant class of filters is filters described by linear-constant coefficient differential equations. The particular structure of the impulse response of a linear combination of exponentials may be amenable to computing recursively the filter coefficients and adapting to instantaneous changes in the input and output sampling rates. The general form for an N-th order equation may be given by

(38) $\begin{array}{cc}\underset{k=0}{\overset{N}{.Math.}}{a}_k{y}^{\left(k\right)}\left(t\right)=\underset{l=0}{\overset{M}{.Math.}}{b}_l{x}^{\left(l\right)}\left(t\right)& \left(10\right)\end{array}$

(39) Under certain assumptions, this equation may be interpreted as describing a system with input x.sub.c(t) and output y.sub.c(t). In particular, assuming initial rest—i.e. if x.sub.c(t)=0 for t≤t.sub.o, then y.sub.c(t)=0 for t≤t.sub.o—the input-output relationship may correspond to a causal Linear Time-Invariant (LTI) system. Continuous-time linear filters may usually be described in this manner and analysed in the Laplace transform domain. In particular, they may yield rational transfer functions of the form

(40) $\begin{array}{cc}H\left(s\right)=\frac{Y\left(s\right)}{X\left(s\right)}=A\frac{\underset{k=1}{\overset{M}{.Math.}}\left(s-z_k\right)}{\underset{k=1}{\overset{N}{.Math.}}\left(s-p_k\right)}& \left(11\right)\end{array}$

(41) for A∈

(42) If we assume that the poles are distinct and that N>M, it may be shown by partial fraction expansion that the inverse Laplace transform may correspond to an impulse response of the form

(43) 0$\begin{array}{cc}h\left(t\right)=\underset{k=1}{\overset{N}{.Math.}}{a}_k{e}^{{\alpha }_{k}t}u\left(t\right)=\underset{k=1}{\overset{N}{.Math.}}{h}_k\left(t\right)& \left(12\right)\end{array}$

(44) where α.sub.k∈. Due to the linearity property of the convolution, the output of such a system may be the sum of the outputs for each of the systems h.sub.k(⋅). This may allow performing the convolution in a parallel manner.

(45) In order to illustrate how the computation may be arranged, filter (12) may be taken as an example for one of its components h.sub.k(t)=a.sub.ke.sup.αv.sup.k.sup.tu(t). The output of this signal path of the sampling rate converter may be then be expressed as

(46) $\begin{array}{cc}{y}_m^k={a_k\left(e^{{\alpha }_k{T}_y{ϵ}_{y,m}}\right)}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}{x_n\left(e^{-{\alpha }_k{T}_x{ϵ}_{x,n}}\right)}^n& \left(13\right)\end{array}$

(47) Where ϵ.sub.x,n and ϵ.sub.y,m are seen as deviations from a fixed frequency of the input signal, T.sub.x, and the output signal, T.sub.y, respectively.

(48) If it is assumed that ϵ.sub.x,n=ϵ.sub.y,m=1, it may be straightforward to see how the factor (e.sup.α.sup.k.sup.T.sup.y).sup.m=(e.sup.α.sup.k.sup.T.sup.y).sup.m−1(e.sup.α.sup.k.sup.T.sup.y) may be recursively computed for each output sample from the value in the previous time step. The same applies to the coefficients (e.sup.α.sup.k.sup.T.sup.x).sup.n. However, one of the key benefits of designing a sampling rate converter in this way may be the ability to accommodate non-uniform input and output sampling instants—i.e. adapt to instantaneous changes in the sampling rates—with low computational requirements. These changes may require a computation of the factors (e.sup.α.sup.k.sup.T.sup.y.sup.ϵ.sup.y,m).sup.m and (e.sup.−α.sup.k.sup.T.sup.x.sup.ϵ.sup.x,n).sup.n where the number of terms in the summation may also be updated.

(49) The update of the coefficients in both cases may be carried out in the same manner. Taking the coefficients corresponding to the output sampling rate between time step m−1 and m as an example, and assuming that at this point the value (e.sup.α.sup.k.sup.T.sup.y).sup.m−1 and e.sup.α.sup.k.sup.T.sup.y are kept in memory. Thus, in order to compute (e.sup.α.sup.k.sup.T.sup.y.sup.ϵ.sup.y,m).sup.m, the following may be written
(e.sup.α.sup.k.sup.T.sup.y.sup.ϵ.sup.y,m).sup.m=(e.sup.α.sup.k.sup.T.sup.y.sup.m).sup.ϵ.sup.y,m=(e.sup.α.sup.k.sup.T.sup.ye.sup.α.sup.k.sup.T.sup.y.sup.(m−1)).sup.ϵ.sup.y,m   (14)

(50) Thus, this calculation may firstly require the computation of (e.sup.α.sup.k.sup.T.sup.y).sup.m which may be done recursively followed by the operation of raising this value to the power of ϵ.sub.y,m. The same applies to the coefficients (e.sup.α.sup.k.sup.T.sup.x.sup.ϵ.sup.x,n).sup.n. The added computational complexity on top of the recursion reduces to performing this exponentiation. Another possibility if the non-uniform time instants are given by T+ε may be to compute instead, in addition to (e.sup.α.sup.k.sup.T.sup.y).sup.m, the value e.sup.α.sup.k.sup.εm. This may be, in principle, less computationally efficient as m grows larger. In this case, the computation may be reduced by using the principle of addition-chain exponentiation.

(51) Certain non-uniform input and output sampling instants are particularly amenable to efficient computation. In order to introduce this, note first that the summation in (9) can be computed recursively since for the output sample y.sub.m, we can use the result of the summation calculated to compute y.sub.m−1. Note that, for each m, there exists some n.sub.m such that n.sub.m≤λ.sub.m,n.sub.m and 1+n.sub.m>λ.sub.m,1+n.sub.m. Thus, the additional number of terms in the summation for each output sample m is given by
M.sub.m: =λ.sub.m,n.sub.m−λ.sub.m−1,n.sub.m−1.   (15)

(52) In order to illustrate this recursion, consider the function h(t−τ). We can interpret (1) as a linear combination of its sampled versions along both time axis, each one corresponding to the input or output time variables. FIG. 4 depicts this function for the system in (13) with α.sub.k<0. It shows that, for each m, we have samples of the function h(t.sub.m−τ) at the instants {τ.sub.n}.sub.τ.sub.n.sub.≤t.sub.m. However, due to the separation property, we can arrange the computation as in (9). Thus, the summation performed to obtain y.sub.m−1 can be reused by adding the terms x.sub.nh.sub.2(τ.sub.n) corresponding to t.sub.m−1<τ.sub.n≤t.sub.m. In other words, the number of terms to compute this recursion depends on how many input sampling instants fall between two consecutive output sampling instants. This number is precisely M.sub.m which can be equivalently expressed as M.sub.m=|.sub.m| where .sub.m={τ.sub.n:t.sub.m−1<τ.sub.n≤t.sub.m}. Then, it can be shown that M.sub.m may be relatively small depending on the input and output sampling instants.

(53) We can illustrate this more formally by taking as an example uniform input and output sampling rates. Let us first decompose the ratio of sampling rates as

(54) $\begin{array}{cc}\frac{T_y}{T_x}=l+r& \left(16\right)\end{array}$

(55) where l is a nonnegative integer and 0≤r<1. Then, the additional number of terms in the summation reduces to

(56) $\begin{array}{cc}\begin{array}{c}{M}_n={\lambda }_m-{\lambda }_{m-1}\\ =l+.Math.\mathrm{mr}.Math.-.Math.\left(m-1\right)r.Math.\\ =l+{\Delta }_m\end{array}& \left(17\right)\end{array}$

(57) where Δ.sub.m is binary valued, i.e. Δ.sub.m∈{0,1}. Note that if T.sub.y<T.sub.x, then l=0 and depending on the index m, Δ.sub.m determines if there is an additional term in the summation or not. In other words, when the output rate is faster than the input rate, there is only need to compute at most one term in the summation. Similarly, when both sampling rates are close, we may also have l=1 which reduces the number of terms in the summation significantly.

(58) A particular case involving non-uniform samples that may be specially amenable to efficient computation corresponds to uniform input rate and non-uniform output rate. In practice, this situation can arise when two systems with different clocks operating at uniform nominal rates are interconnected. Then, the output rate is non-uniform relative to the input rate. In other words, the conversion ratio varies with time as a result of this drift. These output samples may then be used for further processing as discussed here or for subsequent non-uniform reconstruction.

(59) In this scenario, the computational efficiency is based on the fact that the exponentiation is performed solely for the factor h.sub.1(t.sub.m). We may have more coefficients to update in the summation, which are determined by [mT.sub.yϵ.sub.y,m/T.sub.x], that would only require multiplications without the need of exponentiations. Thus, the computational complexity of the exponentiation is only connected to the single coefficient h.sub.1(t.sub.m). We will illustrate in detail how this computation can be arranged and show how these properties apply to different systems in the next sections.

(60) In order to avoid cumbersome notation, we denote the non-uniform input sampling instants by nT.sub.x instead of nT.sub.xϵ.sub.x,n, similarly for the output sampling instants. The reader can assume then that T.sub.x can vary from sample to sample as presented in previous sections.

(61) Let us first consider a first-order system with the impulse response
h(t)=e.sup.−αtu(t)   (18)

(62) with α>0 and Laplace transform H(s)=1/(s+α) for Re(s)>−α. Then, the discrete-time varying system takes the form

(63) $\begin{array}{cc}\begin{array}{c}y\left[m\right]=\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]h\left(m{T}_y-n{T}_x\right)\\ =\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]e^{-\alpha \left(m{T}_y-n{T}_x\right)}\\ ={\left(e^{-\alpha T_y}\right)}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\left(e^{+\alpha T_x}\right)}^n\\ =c_y^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]c_x^n\\ =c_y^{m}g\left[m\right].\end{array}& \left(19\right)\end{array}$

(64) The constants c.sub.y and c.sub.x depend solely on the respective sampling periods T.sub.y and T.sub.x. Moreover, the computation in (19) can be performed recursively, i.e.
g[m+1]=g[m]+q[m+1]   (20)

(65) where the function q[m+1] takes the form

(66) $\begin{array}{cc}q\left[m+1\right]=\{\begin{array}{cc}0& {\lambda }_m<.Math.\left(m+1\right)\frac{T_y}{T_x}.Math.-1\\ \underset{n={\lambda }_m+1}{\overset{.Math.\left(m+1\right)\frac{T_y}{T_x}.Math.}{.Math.}}x\left[n\right]c_{\chi }^n& {\lambda }_m\ge .Math.\left(m+1\right)\frac{T_y}{T_x}.Math.-1\end{array}.& \left(21\right)\end{array}$

(67) There are two important distinctions to be made. Note that if T.sub.y<T.sub.x, i.e. the rate of output samples is higher than the rate of input samples, there will often be cases where q[m+1]=0 or if different from zero, it will at most consist of only the term q[m+1]=x[λ.sub.m+1].sub.cx.sup.λ.sup.m.sup.+1. If the rate of output samples is slower than the input rate, i.e. T.sub.y>T.sub.x, then there will always be at least one term in the summation to compute q[m+1] as shown in (17).

(68) The output samples are given by y[m]=c.sub.y.sup.mg[m] where, clearly, the factor c.sub.y.sup.m can be recursively computed by means of one multiplication for each output sampling rate and the corresponding exponentiation for non-uniform output sampling instants as described in the previous section. The intermediate sample values g[m] can be also be computed recursively as g[m]=g[m−1]+q[m], where q[m] is given by (21). Note again that the coefficients c.sub.x.sup.n to generate q[m] can be recursively computed and the number of coefficients needed for each output time step, i.e. M.sub.m, depends on the sample instants and the ratio T.sub.y/T.sub.x. Similarly, the coefficients c.sub.x.sup.n to compute q[m] can be computed recursively with the corresponding exponentiations for non-uniform input sampling instants.

(69) We can denote the input-output relationship in (20) by c.sub.x[n,m]. Note again that if T.sub.y<T.sub.x there will be instants at which q[m]=0 or, in other words g[m]=g[m−1], thus no computations whatsoever are made to compute g[m]. If we consider uniform input and output sequences, we can compute g[m] recursively using q[m] as the input to a linear time-invariant system with z-transform V(z)=1/1−z.sup.−1 (see FIG. 5). The output in this case is computed by at most one addition whenever q[m]≠0. Alternatively, the computation can also be rearranged in the way shown at the bottom of FIG. 5, i.e.

(70) $\begin{array}{cc}\begin{array}{c}y\left[m\right]=c_y^m\left(g\left[m-1\right]+q\left[m\right]\right)\\ =c_y{c}_y^{m-1}g\left[m-1\right]+c_y^{m}q\left[m\right]\\ =c_{y}y\left[m-1\right]+c_y^{m}q\left[m\right].\end{array}& \left(22\right)\end{array}$

(71) Thus, for an input c.sub.y.sup.mq[m], we can express y[m] as the output of a linear time-invariant system v.sub.y[m] with z-transform V.sub.y(z)=1/(1−c.sub.yz−1). However, the ordering of operations represented by the top block diagram in FIG. 5 is more convenient whenever we have instantaneous changes in the sampling rates since the parameters of v[m] are independent of changes in T.sub.y.

(72) We can generalize the system of the previous section to an impulse response formed by K first-order systems which can be considered as a parallel structure. In particular, we have that

(73) $\begin{array}{cc}h\left(t\right)=u\left(t\right)\underset{k=1}{\overset{K}{.Math.}}{a}_k{e}^{-{\alpha }_{k}t}& \left(23\right)\end{array}$

(74) for a.sub.k>0 and a.sub.k∈.

(75) In this case, the output y[m] will then be given by

(76) $\begin{array}{cc}\begin{array}{c}y\left[m\right]=\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]\underset{k=1}{\overset{K}{.Math.}}{a}_k{e}^{-{\alpha }_k{\mathrm{mT}}_y}{e}^{+{\alpha }_k{\mathrm{nT}}_x}\\ =\underset{k=1}{\overset{K}{.Math.}}{a_k\left(e^{-{\alpha }_k{T}_y}\right)}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\left(e^{+{\alpha }_k{T}_x}\right)}^n\\ =\underset{k=1}{\overset{K}{.Math.}}{a}_k{c}_{y,k}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]c_{x,k}^n=\underset{k=1}{\overset{K}{.Math.}}{a}_k{c}_{y,k}^m{g}_k\left[m\right].\end{array}& \left(24\right)\end{array}$

(77) The same principles with regard to operations described before extend to this case equally. Again, if the input and output sequences are non-uniform, we would have to take into account the corresponding exponentiation required to update the respective coefficients. FIG. 6 shows the parallel implementation of a non-uniform sampling rate converter when the underlying continuous-time filter is given by (23).

(78) In order to provide an idea of the computational demands of this algorithm, we can consider the number of additions, multiplications, the appropriate complexity that the exponentiation step adds, and the memory requirements. We will focus on the operations needed to generate one output sample.

(79) Thus, for a single first-order system and uniform sequences, we first have to keep in memory a, c.sub.y, c.sub.y.sup.m−1, c.sub.x, c.sub.x.sup.λ.sup.m−1, and g[m−1]. In order to compute g[m] we need 1.sub.M.sub.m.sub.≥1(M.sub.m) additions—since there are M.sub.m=l+Δ.sub.m terms in the residual summation and v[m] only requires one addition—and 2M.sub.m=2(1+Δ.sub.m) multiplications. Then, we need one multiplication to update the factor c.sub.y.sup.m and two multiplications to obtain y[m]=ac.sub.y.sup.mg[m]. Note that we have separated the factor a from c.sub.y since in the case of non-uniform output rates this leads to a more efficient exponentiation as shown in (14). This gives us a total of 2(M.sub.m+1)+1 multiplications per output sample.

(80) If the output rate is uniform, the corresponding constant a do not add computational complexity for the computation of ac.sub.y.sup.m since we can assume the values ac.sub.y.sup.m−1 and c.sub.y are kept in memory instead.

(81) If we have non-uniform input or output sequences, the added complexity relies on performing the corresponding exponentiations whenever the sampling instants do not fall into a uniform grid. In particular, let us denote the number of exponentiations corresponding to the coefficients {c.sub.x.sup.n} as

(82) $\begin{array}{cc}{E}_m:=\underset{n={\lambda }_{m-1}+1}{\overset{{\lambda }_m}{.Math.}}{1}_{{ϵ}_{x,n}\ne 1}\left({ϵ}_{x,n}\right)& \left(25\right)\end{array}$

(83) which, obviously, satisfies that E.sub.m≤M.sub.m. We may also have to perform one exponentiation for (e.sup.α.sup.k.sup.T.sup.y.sup.ϵ.sup.y,m).sup.m as shown in (14), and E.sub.m exponentiations for the respective coefficients of the form (e.sup.α.sup.k.sup.T.sup.x.sup.ϵ.sup.x,n).sup.n. This amounts to E.sub.m+1.sub.ϵ.sub.y,m.sub.≠1 (ϵ.sub.y,m) real exponentiations per output sample.

(84) The same principle of separation of variables is satisfied by an impulse response that takes the following form
h(t)=e.sup.−αte.sup.jω.sup.o.sup.tu(t)   (26)

(85) where α>0 and ω.sub.0∈. The operations can be rearranged by following the same principle shown in (19), i.e.

(86) 0$\begin{array}{cc}\begin{array}{c}y\left[m\right]=\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]e^{-\alpha \left({\mathrm{mT}}_y-{\mathrm{nT}}_x\right)}{e}^{j{\omega }_o\left({\mathrm{mT}}_y-{\mathrm{nT}}_x\right)}\\ ={\left(e^{-\alpha T_y+j{\omega }_o{T}_y}\right)}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\left(e^{+\alpha T_x-j{\omega }_o{T}_x}\right)}^n\\ ={\hat{c}}_y^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\hat{c}}_x^n={\hat{c}}_y^{m}g\left[m\right]\end{array}& \left(27\right)\end{array}$

(87) where the constants ĉ.sub.y and ĉ.sub.x can be precomputed or updated if there are changes in the sampling rates similarly to the description of first-order systems.

(88) We are interested in the case of real second-order systems that are causal and stable. These systems have an impulse response that can be expressed as
h(t)=ae.sup.−αt sin(ωt+ϕ)u(t)   (28)

(89) for a, ω and ϕ∈R and α>0. In this case, the associated computation to obtain the output samples y[m] can be carried out by rearranging the operations in a manner similar to the preceding, namely

(90) $\begin{array}{cc}\begin{array}{c}y\left[m\right]=\frac{a}{2j}{\left(e^{-\alpha T_y}\right)}^m[{e^{+j\varphi }\left(e^{+j\omega T_y}\right)}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\left(e^{+\alpha T_x-j\omega T_x}\right)}^n-\\ \text{}{e^{-j\varphi }\left(e^{-j\omega T_y}\right)}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\left(e^{+\alpha T_x+j\omega T_x}\right)}^n]\\ =\frac{a}{2j}{c}_y^m\left[e^{+j\varphi }{\tilde{c}}_y^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\hat{c}}_x^n-{e^{-j\varphi }\left({\hat{c}}_y^{*}\right)}^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\left({\hat{c}}_x^{*}\right)}^n\right]\\ =\frac{a}{2j}{c}_y^m\left[e^{+j\varphi }{\tilde{c}}_y^m\hat{g}\left[m\right]-{\left(e^{+j\varphi }{\hat{c}}_y^m\hat{g}\left[m\right]\right)}^{*}\right]\\ =\mathrm{Im}\left({\mathrm{ae}}^{+j\varphi }{\hat{c}}_y^m\hat{g}\left[m\right]\right)\end{array}& \left(29\right)\end{array}$

(91) where {tilde over (c)}.sub.y=e.sup.−jωT.sup.y, ĉ.sub.x=e.sup.(αT.sup.x.sup.−jωT.sup.x.sup.), and ĉ.sub.y=c.sub.y{tilde over (c)}.sub.y. FIG. 7 shows a block-diagram representation of the non-uniform sampling rate converter when h(t) is a second-order system. The operations involved are very similar to the first-order case (see FIG. 5) with the added number of real multiplications—now the coefficients are complex numbers—and the computationally inexpensive operation of keeping solely the imaginary part to generate the appropriate output sample.

(92) If we have a sum of second-order systems such as h(t)=u(t)Σ.sub.k=1.sup.Ka.sub.k e.sup.−α.sup.k.sup.t sin(ω.sub.kt+ϕ.sub.k), the generalized structure is constructed similarly to the case of first-order systems consisting of K parallel systems as in FIG. 7 with the respective coefficients.

(93) We have to keep in memory the complex values ae.sup.+jϕ, ĉ.sub.y, ĉ.sub.y.sup.m−1, ĉ.sub.x, ĉ.sub.x.sup.m−1, and ĝ[m−1].

(94) Evidently, we assume that the input x[n] is a real signal. The factor ĉ.sub.y.sup.m can be computed recursively with four real multiplications and two additions. Similarly to the situation of first-order systems, we separate the factor ae.sup.+jϕ to perform the exponentiation more efficiently as in (14) if required. The term ĝ[m] can also be computed recursively by using ĝ[m−1]. This requires the calculation of M.sub.m coefficients of the form ĉ.sub.x that can also be computed recursively with four multiplications and two additions per coefficient. This amounts to 6M.sub.m=6(l+Δ.sub.m) real multiplications and 2M.sub.m+21.sub.M.sub.m.sub.≥1(M.sub.m) additions in order to obtain ĝ[m]. As a result, we have a total of 6(M.sub.m+1)+4 real multiplications—since we are only interested in the imaginary part—and 2M.sub.m+21.sub.M.sub.m.sub.≥1(M.sub.m)+3 additions per output sample.

(95) If the input or output rate is always uniform, we could in principle combine the constant factor ae.sup.jϕ into ĉ.sub.y or ĉ.sub.x—depending on what rate is uniform—resulting in a slight reduction of memory and computational requirements. If we have non-uniform input and output sequences, updating the coefficients requires the corresponding exponentiations whenever the sampling instants do not fall into a uniform grid. Thus, using the notation in (25), this would require E.sub.m+1.sub.ϵ.sub.y,m.sub.≠1(ϵ.sub.y,m) complex exponentiations.

(96) We can also consider a system whose Laplace transform consists of repeated poles on the real axis. Transfer functions with repeated poles—real or in complex conjugate pairs—rarely appears in practice. However, we include the development here for illustrative purposes and to show how the separation property, described in (5), can be used to arrange the computation in other systems. In principle, a similar approach can be applied to the case of repeated pairs of complex conjugate pairs. The impulse response in the case of real poles with multiplicity can then be expressed in the following manner
h(t)=at.sup.Ne.sup.−αtu(t)   (30)
for α>0, N≥0, and a∈.

(97) Similarly to previous sections, we can then write the output of the discrete-time sampling rate converter as

(98) $\begin{array}{cc}\begin{array}{c}y\left[m\right]=a\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{\left({\mathrm{mT}}_y-{\mathrm{nT}}_x\right)}^N{\left(e^{-\alpha T_y}\right)}^m{\left(e^{+\alpha T_x}\right)}^n\\ =a{c}_y^m\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]c_x^n\underset{k=0}{\overset{N}{.Math.}}\left(\begin{array}{c}N\\ k\end{array}\right){\left({\mathrm{mT}}_y\right)}^{N-k}{\left(-{\mathrm{nT}}_x\right)}^k\\ =a{c}_y^m\underset{k=0}{\overset{N}{.Math.}}\left(\begin{array}{c}N\\ k\end{array}\right)T_y^{N-k}{m}^{N-k}\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{c_x^n\left(-{\mathrm{nT}}_x\right)}^k.\end{array}& \left(31\right)\end{array}$

(99) If the input and output sequences are uniform, the computation can be arranged as

(100) $\begin{array}{cc}y\left[m\right]=a{c}_y^m\underset{k=0}{\overset{N}{.Math.}}\left(\begin{array}{c}N\\ k\end{array}\right)T_y^{N-k}{T}_x^k{m}^{N-k}\underset{n=0}{\overset{{\lambda }_m}{.Math.}}x\left[n\right]{c_x^n\left(-n\right)}^k.& \left(32\right)\end{array}$

(101) By denoting the values

(102) ${\beta }_{N,k}=\left(\begin{array}{c}N\\ k\end{array}\right){T_y^{N-k}\left(-T_x\right)}^k,$
which can be precomputed and stored in memory, we can write the output as

(103) $\begin{array}{cc}y\left[m\right]=a{c}_y^m\underset{k=0}{\overset{N}{.Math.}}{\beta }_{N,k}{m}^{N-k}{\tilde{g}}_k\left[m\right]& \left(33\right)\end{array}$

(104) where {tilde over (g)}.sub.k[m] can be recursively computed as {tilde over (g)}.sub.k[m+1]={tilde over (g)}.sub.k[m]+{tilde over (q)}.sub.k[m+1]. The definition of {tilde over (q)}.sub.k[m] is analogous to (21) with the added factor n.sup.k. As shown before, the number of terms involve in the summation involved in {tilde over (q)}.sub.k[m] depends on the ratio T.sub.y/T.sub.x. This ordering of the computation gives us the structure shown in FIG. 8.

(105) Notice that if the multiplicity corresponds to N=0, the system in FIG. 8 reduces to the one shown in FIG. 5 and, obviously, all the considerations developed in that case applied equally to this case.

(106) If the input and output sequences are non-uniform, we need to introduce different definitions. In particular, we need to substitute β.sub.N,k by

(107) $\begin{array}{cc}{\tilde{\beta }}_{N,k,m}=\left(\begin{array}{c}N\\ k\end{array}\right){\left(T_y{ϵ}_{y,m}\right)}^{N-k}& \left(34\right)\end{array}$

(108) which explicitly depends on the corresponding output sampling instant. Consequently, the term {tilde over (g)}[m] takes the form

(109) $\begin{array}{cc}{\tilde{g}}_k\left[m\right]=\underset{n=0}{\overset{{\lambda }_m}{.Math.}}{x}_n{c_x^n\left(-n{T}_x{ϵ}_{x,n}\right)}^k.& \left(35\right)\end{array}$

(110) It is possible to generalize the previous case in a straightforward way to systems with an impulse response of the form

(111) $\begin{array}{cc}h\left(t\right)=\underset{i=1}{\overset{L}{.Math.}}{a}_i{t}^{N_i}{e}^{-{\alpha }_{i}t}u\left(t\right).& \left(36\right)\end{array}$

(112) In this case, we can write

(113) $\begin{array}{cc}y\left[m\right]=\underset{i=1}{\overset{L}{.Math.}}{a}_i{c}_{y,i}^m\underset{k=0}{\overset{N_i}{.Math.}}{\beta }_{N,k}^i{m}^{N_i-k}{\tilde{g}}_k^i\left[m\right].& \left(37\right)\end{array}$

(114) The structure can be readily combined in the manner shown in FIG. 9.

(115) In this case, irrespective of having uniform or non-uniform sequences, it is required at some stage to compute powers of the form a.sup.v for some a∈ and a positive integer v. The naive approach would require v−1 multiplications. However, this can be further reduced by resorting to addition-chain exponentiation. Here, we take the worst-case scenario by considering this naive approach.

(116) Consider the system with impulse response shown in (30). In order to generate one output sample y[m], we first need to store the (N+1) coefficients {β.sub.N,k}.sub.k=0.sup.N as well as a, c.sub.y, c.sub.y.sup.m−1, c.sub.x, and c.sub.x.sup.λ.sup.m−1. Likewise first- and second-order systems, keeping in memory these last four factors makes the computation more efficient for non-uniform sequences.

(117) In order to compute {tilde over (g)}.sub.k[m] we need 1.sub.M.sub.m.sub.≥2.Math.(M.sub.m−1)+1 additions and 2M.sub.m multiplications. For each output sample, we also have to compute {m.sup.k}.sub.k=0.sup.N and {n.sup.k}.sub.k=0.sup.N for n=1+λ.sub.m−1, . . . , λ.sub.m which requires (M.sub.m+1)N(N−1)/2 multiplications. Before combining all the channels (see FIG. 8), we need to multiply by the corresponding factors β.sub.N,km.sup.N−k which results in 2N+1 multiplications.

(118) The result of each channel is added together by means of N additions to generate an output sample. Thus, the computations per output sample reduce to 1.sub.M.sub.m.sub.≥2.Math.(M.sub.m−1)+1+N additions and (M.sub.m+1)N(N−1)/2+2M.sub.m+2N+1 multiplications. Note that we do not count as multiplications raising a number to zero or one, or multiplying by unity. The added complexity regarding non-uniform input or output sequences lies in updating the coefficients {tilde over (β)}.sub.N,k,m, which requires N(N−1)/2+(N−1) multiplications, and the corresponding exponentiations to update c.sub.x.sup.n and c.sub.y.sup.m.

(119) If our system can be expressed as the sum of L>0 distinct systems of the form shown in (30), the computational complexity is simply increased by a factor L.

(120) As mentioned in relation to FIG. 1, the x values may be formed as the output from an A/D converter 12 fed an analog signal.

(121) Also, in one embodiment, the signal input comprises an element 14 configured to receive data packets and derive from each data packet, a value x(tau) and a point in time, tau.