Interpolation (779809), страница 2
Текст из файла (страница 2)
In fact, for this example, thedistortion can also be removed using a linear prediction model, which, for acosine signal, can be regarded as a data-adaptive narrow band-pass filter.10.1.4 The Factors That Affect Interpolation AccuracyThe interpolation accuracy is affected by a number of factors, the mostimportant of which are as follows:(a) The predictability, or correlation structure of the signal: as thecorrelation of successive samples increases, the predictability of asample from the neighbouring samples increases. In general,interpolation improves with the increasing correlation structure, orequivalently the decreasing bandwidth, of a signal.(b) The sampling rate: as the sampling rate increases, adjacent samplesbecome more correlated, the redundant information increases, andinterpolation improves.(c) Non-stationary characteristics of the signal: for time-varying signalsthe available samples some distance in time away from the missingsamples may not be relevant because the signal characteristics mayhave completely changed.
This is particularly important ininterpolation of a large sequence of samples.(d) The length of the missing samples: in general, interpolation qualitydecreases with increasing length of the missing samples.(e) Finally, interpolation depends on the optimal use of the data and theefficiency of the interpolator.The classical approach to interpolation is to construct a polynomialinterpolator function that passes through the known samples.
We continuethis chapter with a study of the general form of polynomial interpolation,and consider Lagrange, Newton, Hermite and cubic spline interpolators.Polynomial interpolators are not optimal or well suited to make efficient useof a relatively large number of known samples, or to interpolate a relativelylarge segment of missing samples.304InterpolationIn Section 10.3, we study several statistical digital signal processingmethods for interpolation of a sequence of missing samples. These includemodel-based methods, which are well suited for interpolation of small tomedium sized gaps of missing samples. We also consider frequency–timeinterpolation methods, and interpolation through waveform substitution,which have the ability to replace relatively large gaps of missing samples.10.2 Polynomial InterpolationThe classical approach to interpolation is to construct a polynomialinterpolator that passes through the known samples.
Polynomialinterpolators may be formulated in various forms, such as power series,Lagrange interpolation and Newton interpolation. These various forms aremathematically equivalent and can be transformed from one into another.Suppose the data consists of N+1 samples {x(t0), x(t1), ..., x(tN)}, wherex(tn) denotes the amplitude of the signal x(t) at time tn. The polynomial oforder N that passes through the N+1 known samples is unique (Figure 10.4)and may be written in power series form asxˆ (t ) = p N (t ) = a 0 + a1t + a 2 t 2 + a3t 3 + + a N t N(10.13)where PN(t) is a polynomial of order N, and the ak are the polynomialcoefficients.
From Equation (10.13), and a set of N+1 known samples, ax(t)P(ti)=x(t)t0 t1 t2 t3tFigure 10.4 Illustration of an Interpolation curve through a number of samples.305Polynomial Interpolationsystem of N+1 linear equations with N+1 unknown coefficients can beformulated asx(t 0 ) = a 0 + a1t 0 + a 2 t 02 + a 3 t 03 + + a N t 0Nx(t1 ) = a 0 + a1t1 + a 2 t12 + a 3t13 + + a N t1N(10.14)x(t N ) = a 0 + a1t N + a 2 t N2 + a3 t N3 + + a N t NNFrom Equation (10.14). the polynomial coefficients are given by a0 1 a1 1 a = 1 2 a N 1t0t 02t 03t1t2t12t 22t13t 23tNt N2t N3 t 0N t1N t 2N t NN −1 x(t 0 ) x(t1 ) x(t ) 2 x(t ) N (10.15)The matrix in Equation (10.15) is called a Vandermonde matrix.
For a largenumber of samples, N, the Vandermonde matrix becomes large and illconditioned. An ill-conditioned matrix is sensitive to small computationalerrors, such as quantisation errors, and can easily produce inaccurate results.There are alternative methods of implementation of the polynomialinterpolator that are simpler to program and/or better structured, such asLagrange and Newton methods. However, it must be noted that thesevariants of the polynomial interpolation also become ill-conditioned for alarge number of samples, N.10.2.1 Lagrange Polynomial InterpolationTo introduce the Lagrange interpolation, consider a line interpolator passingthrough two points x(t0) and x(t1):xˆ (t ) = p1 (t ) = x(t 0 ) +x(t1 ) − x(t 0 )(t − t 0 )t1 − t 0line slope(10.16)306Interpolationt −t0x(t1 )t1 −t0x(t )t −t1x(t0 )t0 −t1tt0t1Figure 10.5 The Lagrange line interpolator passing through x(t0) and x(t1),described in terms of the combination of two lines: one passing through(x(t0), t1) and the other through (x(t1), t0 ).The line Equation (10.16) may be rearranged and expressed asp1 (t ) =t − t0t −t1x(t0 ) +x(t1 )t 0 −t1t1 −t0(10.17)Equation (10.17) is in the form of a Lagrange polynomial.
Note that theLagrange form of a line interpolator is composed of the weightedcombination of two lines, as illustrated in Figure 10.5.In general, the Lagrange polynomial, of order N, passing through N+1samples {x(t0), x(t1), ... x(tN)} is given by the polynomial equationPN (t ) = L0 (t ) x(t 0 ) + L1 (t ) x(t1 ) + + L N (t ) x(t N )(10.18)where each Lagrange coefficient LN(t) is itself a polynomial of degree Ngiven byLi (t ) =N(t − t 0 ) (t − t i −1 ) (t − t i +1 ) (t − t N )t −t n=∏(t i − t 0 ) (t i − t i −1 ) (t i − t i +1 ) (t i − t N ) n=0 t i − t n(10.19)n ≠iNote that the ith Lagrange polynomial coefficient Li(t) becomes unity at theith known sample point (i.e. Li(ti)=1), and zero at every other known samplePolynomial Interpolation307(i.e.
Li(tj)=0, i ≠ j ). Therefore PN(ti)=Li(ti)x(ti)=x(ti), and the polynomialpasses through the known data points as required.The main drawbacks of the Lagrange interpolation method are asfollows:(a) The computational complexity is large.(b) The coefficients of a polynomial of order N cannot be used in thecalculations of the coefficients of a higher order polynomial.(c) The evaluation of the interpolation error is difficult.The Newton polynomial, introduced in the next section, overcomes some ofthese difficulties.10.2.2 Newton Polynomial InterpolationNewton polynomials have a recursive structure, such that a polynomial oforder N can be constructed by extension of a polynomial of order N–1 asfollows:p0 (t )= a 0(d.c.
value)p1 (t ) = a0 + a1 (t − t 0 )= p0 (t ) + a1 (t − t 0 )(ramp)p 2 (t ) = a0 + a1 (t − t 0 ) + a 2 (t − t 0 )(t − t1 )(quadratic)p1 (t )=+ a 2 (t − t 0 )(t − t1 )p3 (t ) = a0 + a1 (t − t 0 )+ a 2 (t − t 0 )(t − t1 ) + a3 (t − t 0 )(t − t1 )(t − t 2 )(cubic)p 2 (t )=+ a3 (t − t 0 )(t − t1 )(t − t 2 )(10.20)and in general the recursive, order update, form of a Newton polynomialcan be formulated asp N (t )= p N −1 (t )+ a N (t − t 0 )(t − t1 ) (t − t N −1 )(10.21)308InterpolationFor a sequence of N+1 samples {x(t0), x(t1), ...
x(tN)}, the polynomialcoefficients are obtained using the constraint p N (t i )= x(t i ) as follows: Tosolve for the coefficient a0, equate the polynomial Equation (10.21) at t=t0to x(t0):p N (t 0 )= p 0 (t 0 )= x(t 0 )=a0(10.22)To solve for the coefficient a1, the first-order polynomial p1(t) is evaluatedat t=t1:p1 (t1 )= x(t1 )=a0 + a1 (t1 – t 0 )= x(t 0 )+a1 (t1 – t 0 )(10.23)from whicha1 =x(t1 ) − x(t 0 )t1 − t 0(10.24)Note that the coefficient a1 is the slope of the line passing through thepoints [x(t0), x(t1)]. To solve for the coefficient a2 the second-orderpolynomial p2(t) is evaluated at t=t2:p 2 (t 2 )= x(t 2 )= a 0 + a1 (t 2 – t 0 )+a 2 (t 2 – t 0 )(t 2 – t1 )(10.25)p 2(t 2) = x (t 2)= a0 + a1(t 2 – t 0)+ a 2(t 2 – t 0)(t 2 – t 1)Substituting a0 and a1 from Equations (10.22) and (10.24) in Equation(10.25) we obtain x(t )− x(t1 ) x(t1 )− x(t 0 ) a2 = 2−(t 2 − t 0 )t1 −t 0 t 2 −t1(10.26)Each term in the square brackets of Equation (10.26) is a slope term, andthe coefficient a2 is the slope of the slope.
To formulate a solution for thehigher-order coefficients, we need to introduce the concept of divideddifferences. Each of the two ratios in the square brackets of Equation(10.26) is a so-called “divided difference”. The divided difference betweentwo points ti and ti–1 is defined asd1 (t i −1 , t i )=x(t i ) − x(t i −1 )t i − t i −1(10.27)309Polynomial InterpolationThe divided difference between two points may be interpreted as theaverage difference or the slope of the line passing through the two points.The second-order divided difference (i.e. the divided difference of thedivided difference) over three points ti–2 , ti–1 and ti is given byd 2 (t i −2 , t i ) =d1 (t i −1 , t i )−d1 (t i −2 , t i −1 )t i − t i −2(10.28)and the third-order divided difference isd 3 (t i −3 , t i ) =d 2 (t i −2 , t i )−d 2 (t i −3 , t i −1 )t i − t i −3(10.29)and so on.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
