Abstract:
An interpolator comprises a delay line, a state-variable computer coupled to the delay line and configured to compute initial conditions for at least one interpolation interval, an integrator stack coupled to the state-variable computer and configured to process the initial conditions, and a direct load of state variables for producing a sequence of interpolated output samples. The interpolator&#39;s filter order and polynomial order may be selected independently. The filter order may exceed the polynomial order. The state-variable computer may be made computationally efficient in order to approximate general interpolator designs.

Description:
BACKGROUND  
       [0001]     1. Field of the invention  
         [0002]     The present invention relates generally to methods and circuits for performing digital sample rate conversion. More particularly, the present invention relates to a method and circuit for performing digital interpolation of signal samples using a state-variable computer and an array of integrators.  
         [0003]     2. Discussion of the Related Art  
         [0004]     An interpolator is a digital electronic circuit typically used to increase the sampling rate of data. In particular, an interpolator estimates one or more interpolated values between two successive sampled data values. There are several types of conventional interpolators, including finite impulse response (FIR) interpolators, half-band interpolators, cascaded integrator-comb (CIC) interpolators, and polynomial interpolators.  
         [0005]     FIR interpolators typically require many multipliers and adders, which increase circuit complexity and cost. CIC interpolators may also require a large number of adders, and full precision is typically required in the integrator section of the circuit. Low-order polynomial interpolators (such as quadratic interpolators) may be implemented using a small number of multipliers. However, a quadratic interpolator may have relatively poor aliasing rejection. The desirability of implementing a digital interpolation circuit having an optimal combination of good performance and minimal complexity for minimizing circuit cost and size is well known in the art.  
       SUMMARY OF THE INVENTION  
       [0006]     In view of the foregoing background, embodiments of the present invention may provide an interpolator and related methods wherein the interpolator provides good performance, but which is also relatively simple in circuit requirements, such as the number of multipliers.  
         [0007]     In one embodiment, an interpolator comprises a delay line, a state-variable computer coupled to the delay line and configured to compute initial conditions for seeding an interpolation, and an integrator stack coupled to the state-variable computer and configured to process a direct load of initial conditions for producing interpolated sample values. An interpolator having a polynomial order K interpolates M points between each data point. The interpolator includes K integrators whose initial conditions are seeded from an (N+1)-tap delay line or memory stack at a rate 1/M times the integration rate. The value N is the filter order, which represents the maximum delay (in samples) used in creating each set of K+1 initial conditions. The filter order N of the interpolator need not be directly related to the polynomial order K, but rather, it may be adapted. Typically, the filter order N exceeds the polynomial order K. However, in some embodiments, the polynomial order K may exceed the filter order N. A related method embodiment of the invention may provide for interpolation wherein the filter order is selected as part of a procedure to provide for a predetermined filter response for an interpolator having a given polynomial order.  
         [0008]     An interpolator according to an embodiment of the invention may include a means for generating a low-rate sequence of sample values. Initial conditions or state variables are computed from the sample values at an up-sample rate 1/M for input to an interpolator stack. A means for computing initial conditions may process each sample in the delayed input sample stream for processing by a means for performing integration. A means for direct loading of state variables into the means for performing integration may also be included. In an embodiment of an interpolator having polynomial order K, the means for performing integration comprises K+1 registers, the means for computing initial conditions provides K+1 outputs to the means for performing integration, and the means for generating a plurality of delayed samples includes a plurality N+1 of delay components that is typically greater than K+1. However, the plurality of delay components may be less than K+1. The means for direct loading of state variables may or may not be included in this embodiment.  
         [0009]     In another embodiment of the invention, for any given up-sample rate M, an interpolator&#39;s filter order N and polynomial order K may be selected independently. The filter order N may exceed the polynomial order K. In some cases, the polynomial order K may exceed the filter order N.  
         [0010]     Various functional elements, separately or in combination, depicted in the Figures may take the form of a microprocessor, digital signal processor, application specific integrated circuit, field programmable gate array, or other logic circuitry programmed or otherwise configured to operate as described herein. Accordingly, the interpolator may take the form of programmable features executed by a common processor or discrete hardware unit.  
         [0011]     These and other embodiments of the invention are described with respect to the figures and the following description of the preferred embodiments.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]     Embodiments of an interpolator according to the present invention are understood with reference to the waveform diagrams of  FIGS. 1A-1E , the schematic block diagram of  FIG. 2 , and the flow diagrams of  FIGS. 3 and 4 .  
         [0013]      FIG. 1A  is a waveform diagram that illustrates two specified points, or samples in a discrete-time sequence {(y[Mn]} (e.g., y[Mj] and y[(M+1)j]).  
         [0014]      FIG. 1B  is a waveform diagram that illustrates a linear spline interpolation between the two specified points that employs a first-order polynomial (i.e., a straight line).  
         [0015]      FIG. 1C  is a waveform diagram that illustrates a parabola that employs a second-order polynomial.  
         [0016]      FIG. 1D  is a waveform diagram that illustrates a cubic doublet that employs a third-order polynomial.  
         [0017]      FIG. 1E  is a waveform diagram of a spline generated from a superposition of waveforms shown in  FIGS. 1B, 1C , and  1 D that interpolates between the two specified points.  
         [0018]      FIG. 2  is a schematic diagram of an interpolator in accordance with an embodiment of the invention.  
         [0019]      FIG. 3  is a flow diagram that shows a method embodiment of the invention.  
         [0020]      FIG. 4  is a flow diagram that shows an alternative method embodiment of the invention. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0021]     The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art.  
         [0022]     A continuous-time signal y(t) is sampled to produce a low-rate sequence {y[Mj]}, where y[Mj]=y(Mt 0 j), 1/Mt 0  is the sample rate, and j is an integer. A desired sequence {z[j]} is synthesized at a rate 1/t 0 . For purposes of discussion, it is customary to normalize t 0  to 1 and refer to the sample rate as 1/M. In order to obtain the desired sequence {z[j]} from {y[Mj]}, it is necessary to find sequences of interpolated values (i.e., output samples) z[i], where Mj≦i≦M(j+1) for all values of j.  
         [0023]     An interpolation polynomial of order K is given by 
 
 P ( x,  α   )=α K   x   K +α K−1   x   K−1 + . . . +α 1   x+α   0 , 
 
 wherein the terms α k  represent coefficients and the variables x may express sample indices i. For example, an interpolated data value may be expressed by 
 
 z[i]=P[i,  α [j]],    Mj≦i≦M ( j+ 1), 
 
 where  α [j] denotes the polynomial coefficients determined by y[Mj] and y[M(j+1)]. Embodiments of the invention may produce interpolated values z[i] using a polynomial interpolation of order K of the low-rate sequence {y[Mj]}. 
 
         [0024]     Discrete polynomial interpolations P[i] of order K may be recursively described in terms of P (K) [i] (which denotes the K th  discrete derivative, or difference, of P and is constant over the interpolation interval) and the initial values of all lower-order derivatives P (k) [i] for which k=(K−1), . . . ,0. The highest-order nonzero derivative of the polynomial P is constant over the interpolation interval, and is denoted by 
 
 P   (K)   [i]=P   (K)   [Mj],  for all  Mj≦i≦M (j+1). 
 
 Each derivative may be computed via a difference equation that uses the next-higher-order derivative as a slope to increment in each sample interval: 
 
 P   (kε[K−1.0])   [i]=P   (k)   [i− 1]+ P   (k+1)   [i].  
 
 By repeating the linear recursion for successively lower polynomial orders, P is reached at order zero: 
 
 P[i]=P   (0)   [i].  
 
         [0025]     Embodiments of the invention may include interpolators having a Nyquist response, as well as non-Nyquist interpolators. When emulating the response of a low-pass Nyquist filter (such as a raised-cosine filter with a bandwidth of  
           f   c     =       f   s       2   ⁢   M         ,       
 
 where f c  is the cutoff frequency, and f s  is the sampling frequency), the impulse response of the interpolator at any low-rate sampling points contains no non-zero contributions from samples at other low-rate points. Thus, if the filter response is normalized such that the impulse response at zero has a value of one, the input samples y[Mj] may be used without modification in the output stream, and P may be designed to interpolate these points as 
 
 P   (0)   [Mj]=y[Mj].  
 
         [0026]     The slope at the endpoint samples may be set equal to the derivative of the filter impulse response at the endpoints. In an embodiment represented by  FIGS. 1A-1E , N=3 to satisfy the requirement that P interpolate two specified points (e.g., y[Mj] and y[(M+1)j]) and that P have a specified slope at these points. In this case, the polynomial P may be separated into three components, each of which provides a unique contribution to the slope and value of P: 
 
 P[i]=P   1   [i]+P   2   [i]+P   3   [i] 
 
 Component P 1  interpolates linearly from Mj to M(j+1 )−1, such as shown in  FIG. 1B .  FIG. 1C  shows that component P 2  generates a parabola, starting and ending at zero, with starting and ending slopes chosen such that their difference is equal to the difference between the slopes commanded by the filter impulse response. In  FIG. 1D , component P 3  generates an antisymmetric cubic doublet, also starting and ending at zero, crossing zero at mid-interval and having the same starting and ending slopes. 
 
         [0027]      FIG. 1E  shows a superposition of these interpolations, which permits arbitrary value and slope at the endpoints of the interpolation interval, which can be set by selecting initial conditions. P 1  is responsible for setting the endpoint values of the interpolation, while P 2  and P 3  are responsible for endpoint slopes only. These properties permit simple omission of P 2  and P 3 , or P 3  alone, to yield lower-order approximations with no change to the lower-order interpolators.  
         [0028]     For K=3, the following interpolation relationships may be generated:  
           P   k     (   2   )       ⁡     [   i   ]       =         P   k     (   2   )       ⁡     [   0   ]       +       iP   k     (   3   )       ⁡     [   0   ]             
           P   k     (   1   )       ⁡     [   i   ]       =         P   k     (   1   )       ⁡     [   0   ]       +       ∑     l   =   0       i   -   1       ⁢       P   k     (   2   )       ⁡     [   l   ]               
           P   k     (   0   )       ⁡     [   i   ]       =         P   k     (   0   )       ⁡     [   0   ]       +       ∑     l   =   0       i   -   1       ⁢       P   k     (   1   )       ⁡     [   l   ]               
       Using   ⁢           ⁢   the   ⁢           ⁢   identities       
             ∑     i   =   1       k   -   1       ⁢   i     =           k   ⁡     (     k   -   1     )       2     ⁢           ⁢   and   ⁢           ⁢       ∑     i   =   1       k   -   1       ⁢     i   2         =         k   ⁡     (     k   -   1     )       ⁢     (       2   ⁢   k     -   1     )       6         ,       
 
 the lower-order interpolator stage values may be expressed directly in terms of i and initial conditions P k   (q) [0]:  
                 P   k     (   1   )       ⁡     [   i   ]       =         P   k     (   1   )       ⁡     [   0   ]       +       iP   k     (   2   )       ⁡     [   0   ]       +       1   2     ⁢     i   ⁡     (     i   -   1     )       ⁢       P   k     (   3   )       ⁡     [   0   ]                           P   k     (   0   )       ⁡     [   i   ]       =         P   k     (   0   )       ⁡     [   0   ]       +       iP   k     (   1   )       ⁡     [   0   ]       +       1   2     ⁢     i   ⁢     (     i   -   1     )       ⁢       P   k     (   2   )       ⁡     [   0   ]         +     
     ⁢       (           (     i   -   2     )     ⁢     (     i   -   1     )     ⁢     (       2   ⁢   i     -   3     )       12     +         (     i   -   2     )     ⁢     (     i   -   1     )       4       )     ⁢       P   k     (   3   )       ⁡     [   0   ]                       =         P   k     (   0   )       ⁡     [   0   ]       +       iP   k     (   1   )       ⁡     [   0   ]       +       1   2     ⁢     i   ⁡     (     i   -   1     )       ⁢       P   k     (   2   )       ⁡     [   0   ]         +           (     i   -   2     )     ⁢     (     i   -   1     )     ⁢   i     6     ⁢       P   k     (   3   )       ⁡     [   0   ]                     
 
 The previous equations may also be expressed in matrix form as  
         [             P   k     (   3   )       ⁡     [   i   ]                   P   k     (   2   )       ⁡     [   i   ]                   P   k     (   1   )       ⁡     [   i   ]                   P   k     (   0   )       ⁡     [   i   ]             ]     =       [         1       0       0       0           i       1       0       0               i   ⁡     (     i   -   1     )       ⁢     /     ⁢   2         i       1       0               i   ⁡     (     i   -   2     )       ⁢     (     i   -   1     )     ⁢     /     ⁢   6             i   ⁡     (     i   -   1     )       ⁢     /     ⁢   2         i       1         ]     ⁡     [             P   k     (   3   )       ⁡     [   0   ]                   P   k     (   2   )       ⁡     [   0   ]                   P   k     (   1   )       ⁡     [   0   ]                   P   k     (   0   )       ⁡     [   0   ]             ]           
 
 This matrix equation demonstrates that each component P k   (0)  of the interpolator ouput is a linear function of the initial conditions. 
 
         [0029]     Equations represented by the matrix may employ the interpolation factor M, as well as starting and ending slopes and values required for P 1 , P 2 , and P 3 , to compute initial conditions for an integrator at the beginning of each interpolation interval. The initial value for linear component P 1  of a Nyquist filter is given by P 1   (0) [0]=y[Mj], which represents a sample value at the start of the interpolation interval. The initial slope is  
           P   1     (   1   )       ⁡     [   0   ]       =           y   ⁡     [     M   ⁡     (     j   +   1     )       ]       -     y   ⁡     [   Mj   ]         M     .         
 
 In embodiments that employ a filter whose impulse response is not unity at i=0 and zero at i=Mj, the initial conditions for P 1  may be computed by evaluating the filter values at the interpolation interval endpoints and using them instead of the y values. 
 
         [0030]     An expression for P 2  may be derived using an initial value of zero, an initial slope P 2   (1) [0]=s 2 , and an ending slope P 2   (1) [M+1]of −s 2 :  
           P   2     (   2   )       ⁡     [   0   ]       =         -   2     ⁢     s   2         (     M   +   1     )           
 
 An expression for P 3  that employs initial and ending values P 3   (0) [0]=P 3   (0) [M]=0 and initial and ending slopes  
                   P   3     (   1   )       ⁡     [   0   ]       =         P   3     (   1   )       ⁡     [     M   ⁢           -           ⁢   1     ]       ⁢           =           ⁢     s   3         ,   yields                   P   3     (   2   )       ⁡     [   0   ]       =       -     1   2       ⁢     (     M   -   2     )     ⁢       P   3     (   3   )       ⁡     [   0   ]                   
 
 Using appropriate substitutions from previous equations, the following expression is obtained  
           P   3     (   3   )       ⁡     [   0   ]       =       12   ⁢     s   3           (     M   -   2     )     ⁢     (     M   -   1     )             
 
         [0031]     The slopes desired at the start and end of the interpolation interval may be selected simply to be equal to the slopes h[Mj] and h[M] of the prototype (e.g., raised cosine) filter being emulated. From the desired slopes, s 2  and s 3  may be computed by requiring that the P 2  parabola endpoint slopes span the difference between h[Mj] and h[M(j+1)] and requiring that the P 3  doublet endpoint slopes are equal to the slope remaining after the slopes of P 1  and P 2  have been subtracted from the desired slopes  
               s   2     =         h   ⁡     [     M   ⁡     (     j   +   1     )       ]       -     h   ⁡     [   Mj   ]         2               and               s   3     =       h   ⁡     [   Mj   ]       -     s   2     -         P   1     (   0   )       ⁡     [   0   ]       .                 
 
 A complete set of initial conditions for an interpolation interval may be calculated from the previous expressions for s 2  and s 3 . A superposition enables initial conditions for P to be set to the sum of the component initial condition values  
             P     (   q   )       ⁡     [   0   ]       =       ∑     k   =   1     K     ⁢       P   k     (   q   )       ⁡     [   0   ]           ,     1   ≤   q   ≤   K     ,       
 
 which permits a single integrator to be used rather than the sum of the outputs of multiple integrators. 
 
         [0032]     For an L-lobe linear-phase Nyquist filter whose starting and ending derivatives are zero, the cost of the above computation is only (L−1)/2+4 multiplies per input sample, and is independent of the upsampling factor M. A better match to an arbitrary desired response may be achieved by treating the initial conditions for P 1 , P 2 , and P 3  as parameters to a numerical optimization designed for that purpose. It should be noted that all initial condition computations described above may amount to no more than the computation of linear combinations of low-rate input samples at the output sample rate.  
         [0033]     In hardware implementations that may be sensitive to chained computations, the initial conditions may be computed directly as a matrix multiplication, wherein the matrix coefficients may be derived using at least some of the previous equations or by numerical optimization. Interpolators that use optimization to compute the matrix coefficients have been shown to provide a high-precision emulation of a five-lobe raised cosine filter. When optimal rectangular-spectrum low-pass filtering is the optimization target, very good results may be achieved as well.  
         [0034]     Some embodiments of the invention may trade performance for computational simplicity. For example, in the five-lobe case, the initial conditions are computed with the matrix equation  
             [         P     (   0   )       ⁡     [   Mj   ]       ⁢           ⁢   …   ⁢           ⁢       P     (   K   )       ⁡     [   Mj   ]         ]     T     =       A   ⁡     [       y   ⁡     [     M   ⁡     (     j   -   3     )       ]       ⁢           ⁢   …   ⁢           ⁢     y   ⁡     [     M   ⁡     (     j   +   2     )       ]         ]       T       ,     
     ⁢   where       
       A   =           0       0       1       0       0       0             c   1             -   2     ⁢     c   1           0         2   ⁢     c   1             -     c   1           0             c   2             -     3   2       ⁢     c   2             2   ⁢     c   2             -     c   2           0           -     1   2       ⁢     c   2                 c   3           -     c   3             2   ⁢     c   3               -   2     ⁢     c   3             c   3           -     c   3             .         
 
 The entire matrix multiplication is characterized by functions of only three constants. Furthermore, the addition operations for each row can be factored out and performed prior to multiplication by the constants. The constant multiplications shown may be implemented as simple shifts, with the exception of the constant 3/2, which requires two shifts and an addition. The performance of interpolators with matrices constrained in this way (i.e., a constrained case) can approach the performance of interpolators having unconstrained matrices. Although the exemplary embodiment may suffer some performance loss, the simplicity of the resulting hardware design can make this embodiment advantageous. 
 
         [0035]      FIG. 2  illustrates an interpolator embodiment of the invention. An input sample stream at rate 1/M is fed through an N+1-length delay line or memory stack whose outputs are processed by an state-variable computer to compute K+1 initial conditions at the input sample rate. The term “delay line,” as used herein, includes equivalent components or processes configured to delay the input sample stream. The maximum delay (or equivalently, the number of input samples) used in computing each initial condition is referred to as the filter order of the interpolator. One or more of the delay components between the first and last delay components may be unused without changing the filter order. Each update of the K+1 initial conditions at rate 1/M resets the order-K integrator stack for an M-sample interpolation at (normalized) rate 1.  
         [0036]     An integrator stack, which consists of a cascade of simple registers (each of which is labeled “register”) whose inputs are summed with the register value at the output sample rate, generates an output sample stream at the register corresponding to the lowest polynomial order. This embodiment provides for a direct load of state variables P (q) [Mj], 0≦q≦K into the integrators at the beginning of each sample interval.  
         [0037]     The exemplary embodiment shown in  FIG. 2  has a filter order of five in which six inputs are provided to the state-variable computer. This interpolator embodiment employs a polynomial order of three. Thus, four inputs are provided to the integrator stack. While a prior-art interpolator having a polynomial order of K processes K+1 inputs to provide for initial conditions, embodiments of the present invention may employ a filter order that exceeds the polynomial order. Thus, the number of delay components (i.e., inputs to the state-variable computer) may exceed the number of stages in the integrator stack. The independence of these two quantities allows a degree of freedom in selecting the polynomial order K and the filter order N that is also independent of the up-sample rate M. Exemplary embodiments of the invention may provide for alternative numbers of delay components and/or filter orders, which may be selected such as to adjust filter shape. The design equations permit an approximation of initial conditions to realize interpolators with nearly arbitrary responses.  
         [0038]      FIG. 3  is a flow diagram that shows a method embodiment of the invention. An input sample stream is delayed by a sequence of delay components  301 . Initial conditions for each sample are computed from the delayed input sample stream for processing by an integrator stack  302 . A direct load of state variables P (n) [Mk] is also injected into the integrator stack to control the interpolator trajectory during an M-sample interpolation interval  303  of rate-1 samples.  
         [0039]      FIG. 4  is a flow diagram that shows an alternative method embodiment of the invention. An interpolator having a polynomial order K is produced by providing for an integrator stack having K+1 registers coupled to K+1 outputs of an state-variable computer  401 , providing for coupling the state-variable computer to a delay line comprising a plurality of delay components  402 , and selecting the filter order N to be greater than the polynomial order K  403 . The filter order of the interpolator may be selected as part of a procedure to provide for a predetermined filter response.  
         [0040]     Embodiments of the invention may be employed in sigma-delta digital-to-analog converters, in which data in the digital domain is up-sampled prior to conversion to analog. Since the integrator stack initial conditions may include any number of input samples, various embodiments may provide for filter responses with an arbitrary number of lobes, and thus an arbitrarily sharp cutoff frequency. Also, there is some freedom (via numerical optimization) to approximate target filter response shapes, such as channel-matched filters used in communications. Some embodiments of the invention may be incorporated into sigma-delta digital-to-analog converters to produce channel filters integrated into the interpolation filter.  
         [0041]     Logic implementations of embodiments of the invention may be considerably smaller than prior-art interpolators that perform multiple simultaneous multiplies at the output sample rate. In some embodiments of the invention, multiplication is performed only at the low input sample rate. In the constrained case described previously, only three multiplies are required at the sample rate. Because of the low multiplication rate, multiplies may be serialized to save hardware. For example, an embodiment having an up-sample rate M=8 employing a five-lobe constrained matrix multiply with two complete interpolators and simultaneous generation of two output samples per clock cycle may occupy only 24,000 gates when synthesized with the 90-nm TSMC standard cell library.  
         [0042]     Various interpolation techniques are described in F. Francesconi, G. Lazzari, V. Liberali, F. Maloberti, G. Torelli, “A Novel Interpolator Architecture for SD DACs,” Department of Electronics, University of Pavia, Via Abbiategrasso, 209-27100 Pavia, Italy, Genova Ricerche, Via dell&#39;Acciaio, 139-16152 Genova, Italy, which is hereby incorporated by reference. Some embodiments of the invention may combine integrators using direct load of state variables and superposition to reduce the size of the integrator stack. Integrator stack interpolation embodiments may be implemented on single-instruction, multiple-data processors, such as the Intel Pentium/SSE2 and other architectures that support multiple simultaneous add operations.  
         [0043]     Modem sigma-delta converters use a brick-wall FIR filter or filters, cascaded with one or more sinc 3  filters to bring the sample rate from baseband to the modulator rate, which can be from about ten times to several thousand times the baseband rate. Embodiments of the present invention may be used as an adjunct to (or outright replacement of) conventional filtering schemes. For example, a sigma-delta converter may be implemented using a cascade of interpolators based on one or more interpolator embodiments described herein.  
         [0044]     While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and are herein described in detail. It should be understood, however, that it is not intended to limit the invention to the particular form disclosed, but rather, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the claims.