Forums

interpolation accuracy, oversampling and fractional interpolation

Started by renaudin October 9, 2006
On 11 Oct 2006 15:21:28 -0700, "Viognier" <viognier@cox.net> wrote:

> >Eric Jacobsen wrote: > >> I'd still disagree, having used polyphase filters for many years for >> locking symbol clocks in digital recievers, with no measurable loss. >> > >I can see using polyphase to compensate for receiver sample clock phase >offset. Can it be used to compensate for receiver sample clock >frequency offset too ( as in the case when a fixed crystal asynchronous >ADC is being used)?
Absolutely. Polyphase structures are quite good at decimation (or even interpolation) at arbitrary rates. In my case this was one of the main motivations for using it, as it enabled a fixed-sampling-rate IF sampler and then programmable symbol rate decimation and resampling with the polyphase. Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
Eric Jacobsen wrote:
> On 11 Oct 2006 14:46:25 -0700, "robert bristow-johnson" > <rbj@audioimagination.com> wrote: > > >i kinda agree with Eric that polyphase interpolation (essentially > >designing an optimal LPF and keeping the impulse response in a table) > >is preferable to spline or polynomial interpolation for any bandlimited > >reconstruction but where i might agree with Viognier is because of the > >cost. you can't have a polyphase table that has all infinite possible > >fractional delays. but you *can* evaluate a polynomial for any > >fractional delay expressible in the machine arithmetic. but if you can > >afford some memory for the polyphase table, you can use a polynomial > >interpolation between entries of that table. > > As I mentioned elsewhere, in a practical system with fixed precision > there is a number of phases beyond which the coefficients won't change > when trying to increase the resolution. I looked at this years ago > when designing a polyphase for a comm receiver and trying to answer > the question of how many phases did we really need to not lose any > performance. > > In other words, for an example system that uses 8-bit precision for > the coefficients there will be some minimum phase change beyond which > the change in phase will result in coefficient changes that are below > the LSB in the current coefficients.
i think i understand. i think we get to the same place. for me, we have these images of the original input (hypothetically samples attached to uniformly spaced dirac impulses). we need to beat down those impulses to some degree before resampling. the polynomial interpolation can be expressed as convolving with something (a hypothetical impulse response) that will look more like a windowed sinc as the polynomial order (and the number of adjacent samples used in the interpolation) gets larger. we beat them images down to some level (by knowing what the hypothetical impulse response is) and assume what remains of all the images will get folded into the baseband. that is the noise that, in your case, should be less than 1 or 1/2 LSB.
> Surprisingly, I found that for our case that meant that with a very > practical number of phases we had essentially infinite phase > precision, or at least within the precision we were using one would > never tell the difference.
resampling is one thing. non-perfect accuracy of the reconstruction coefficients for a fast moving phase is gonna look something like noise. a precision delay (with a constant or slowly varying fractional-sample delay amount) is another thing. even with your 8 bit word width, a precise fractional delay that is roughly constant but slightly in error (because of the limited number of fixed fractional delays) will show itself not as noise, but as a small error in the delay or frequency response or transfer function. i dunno. i used to think i had a consistent and comprehensive way to look at it so to compare different methods. can't necessarily claim that now. r b-j
On Oct 12, 2:22 pm, "robert bristow-johnson"
<r...@audioimagination.com> wrote:
> Eric Jacobsen wrote: > > On 11 Oct 2006 14:46:25 -0700, "robert bristow-johnson" > > <r...@audioimagination.com> wrote: > > > >i kinda agree with Eric that polyphase interpolation (essentially > > >designing an optimal LPF and keeping the impulse response in a table) > > >is preferable to spline or polynomial interpolation for any bandlimited > > >reconstruction but where i might agree with Viognier is because of the > > >cost. you can't have a polyphase table that has all infinite possible > > >fractional delays. but you *can* evaluate a polynomial for any > > >fractional delay expressible in the machine arithmetic. but if you can > > >afford some memory for the polyphase table, you can use a polynomial > > >interpolation between entries of that table. > > > As I mentioned elsewhere, in a practical system with fixed precision > > there is a number of phases beyond which the coefficients won't change > > when trying to increase the resolution. I looked at this years ago > > when designing a polyphase for a comm receiver and trying to answer > > the question of how many phases did we really need to not lose any > > performance. > > > In other words, for an example system that uses 8-bit precision for > > the coefficients there will be some minimum phase change beyond which > > the change in phase will result in coefficient changes that are below > > the LSB in the current coefficients.i think i understand. i think we get to the same place. for me, we > have these images of the original input (hypothetically samples > attached to uniformly spaced dirac impulses). we need to beat down > those impulses to some degree before resampling. the polynomial > interpolation can be expressed as convolving with something (a > hypothetical impulse response) that will look more like a windowed sinc > as the polynomial order (and the number of adjacent samples used in the > interpolation) gets larger. we beat them images down to some level (by > knowing what the hypothetical impulse response is) and assume what > remains of all the images will get folded into the baseband. that is > the noise that, in your case, should be less than 1 or 1/2 LSB. > > > Surprisingly, I found that for our case that meant that with a very > > practical number of phases we had essentially infinite phase > > precision, or at least within the precision we were using one would > > never tell the difference.resampling is one thing. non-perfect accuracy of the reconstruction > coefficients for a fast moving phase is gonna look something like > noise. > > a precision delay (with a constant or slowly varying fractional-sample > delay amount) is another thing. even with your 8 bit word width, a > precise fractional delay that is roughly constant but slightly in error > (because of the limited number of fixed fractional delays) will show > itself not as noise, but as a small error in the delay or frequency > response or transfer function.
Wouldn't using weighted random selections of the two nearest table entries exchange noise for any absolute long term phase error? Or perhaps something similar to fraction saving instead of weighted random dithering. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Ron N. wrote:
> On Oct 12, 2:22 pm, "robert bristow-johnson" > <r...@audioimagination.com> wrote:
...
> > > > a precision delay (with a constant or slowly varying fractional-sample > > delay amount) is another thing. even with your 8 bit word width, a > > precise fractional delay that is roughly constant but slightly in error > > (because of the limited number of fixed fractional delays) will show > > itself not as noise, but as a small error in the delay or frequency > > response or transfer function. > > Wouldn't using weighted random selections of the two nearest > table entries exchange noise for any absolute long term phase > error? Or perhaps something similar to fraction saving instead > of weighted random dithering.
not a bad idea(s). one seems to be dithering the fractional time signal (before quantizing to the nearest discrete fractional delay) and the other is noise-shaping the same signal (with no error at DC). i think it would turn a discrete, stable, but slightly erroneous effective delay (similar to coefficient quantization) to the correct delay but with some jitter noise to the signal. being jitter, if the signal so delayed was a low frequency signal, the noise would be less than if it was the same amplitude but higher frequency content. r b-j
On 12 Oct 2006 14:22:12 -0700, "robert bristow-johnson"
<rbj@audioimagination.com> wrote:

> >Eric Jacobsen wrote: >> On 11 Oct 2006 14:46:25 -0700, "robert bristow-johnson" >> <rbj@audioimagination.com> wrote: >> >> >i kinda agree with Eric that polyphase interpolation (essentially >> >designing an optimal LPF and keeping the impulse response in a table) >> >is preferable to spline or polynomial interpolation for any bandlimited >> >reconstruction but where i might agree with Viognier is because of the >> >cost. you can't have a polyphase table that has all infinite possible >> >fractional delays. but you *can* evaluate a polynomial for any >> >fractional delay expressible in the machine arithmetic. but if you can >> >afford some memory for the polyphase table, you can use a polynomial >> >interpolation between entries of that table. >> >> As I mentioned elsewhere, in a practical system with fixed precision >> there is a number of phases beyond which the coefficients won't change >> when trying to increase the resolution. I looked at this years ago >> when designing a polyphase for a comm receiver and trying to answer >> the question of how many phases did we really need to not lose any >> performance. >> >> In other words, for an example system that uses 8-bit precision for >> the coefficients there will be some minimum phase change beyond which >> the change in phase will result in coefficient changes that are below >> the LSB in the current coefficients. > >i think i understand. i think we get to the same place. for me, we >have these images of the original input (hypothetically samples >attached to uniformly spaced dirac impulses). we need to beat down >those impulses to some degree before resampling. the polynomial >interpolation can be expressed as convolving with something (a >hypothetical impulse response) that will look more like a windowed sinc >as the polynomial order (and the number of adjacent samples used in the >interpolation) gets larger. we beat them images down to some level (by >knowing what the hypothetical impulse response is) and assume what >remains of all the images will get folded into the baseband. that is >the noise that, in your case, should be less than 1 or 1/2 LSB. > >> Surprisingly, I found that for our case that meant that with a very >> practical number of phases we had essentially infinite phase >> precision, or at least within the precision we were using one would >> never tell the difference. > >resampling is one thing. non-perfect accuracy of the reconstruction >coefficients for a fast moving phase is gonna look something like >noise.
Yes, but it can be made to be noise that's at or below the quantization level, or lower, depending.
>a precision delay (with a constant or slowly varying fractional-sample >delay amount) is another thing. even with your 8 bit word width, a >precise fractional delay that is roughly constant but slightly in error >(because of the limited number of fixed fractional delays) will show >itself not as noise, but as a small error in the delay or frequency >response or transfer function.
A comm guy would think of that as jitter in the symbol recovery clock.
>i dunno. i used to think i had a consistent and comprehensive way to >look at it so to compare different methods. can't necessarily claim >that now.
As far as conceptualizing the effects on the coefficients for the timing jitter case, what I realized was that at some combination of phase resolution and coefficient quantization, there's a point where changing the desired sampling phase stops changing the coefficients. In other words, for a given set of fixed-precision coefficients, there is some number of phases above which the coefficient sets will just start repeating themselves as you add more phases, since the differences in the coefficient sets is less than the precision in the coefficients. You could design a polyphase system with N phases, with N a very large number that gives you extremely fine precisions, and think that you have reduced the effective jitter in the resampling process. But it could be that if you looked at the coefficient sets that adjacent FIRs, with different phases, are identical because the coefficient precision is less than that required to discern that difference in phase. Whether a case like that really results in timing jitter or not is arguable, since the coefficients are still correct in each case for the precision used. In practice I used a reasonable N where the coefficient sets did not duplicate and we had no measurable loss in performance from theoretical. So, one could also argue, perhaps, that there is no resampling jitter in that case and you have, therefore, effectively infinite precision in the time resolution of the resampling in a practical system with a finite number of phases. One could do some experiments to verify this, of course, and I've not done them. ;) Eric Jacobsen Minister of Algorithms, Intel Corp. My opinions may not be Intel's opinions. http://www.ericjacobsen.org
If you are interpolating short sequences, you might want to investigate 
perfect interpolation.  This is implemented via and forward FFT into the 
frequency domain, append zeroes to the FFT output, and then perform an inverse 
FFT.  This results in no change in the frequency domain characteristics though 
getting the scaling right can cause problems.  Parsaval is your friend in this 
case.

The other thing I was thinking is that if you are interpolating by a multiple 
than can be factored into the product of small integers, interpolating by 
those small factors, probably smallest first, will result in a better result 
with fewer FLOPS.  It's sort of the reverse of decimation.

In article <1160606443.029373.8350@m73g2000cwd.googlegroups.com>, "Ron N." 
<rhnlogic@yahoo.com> wrote:
>On Oct 9, 7:57 am, "Mark" <makol...@yahoo.com> wrote: >> I have always been confused about the relationship between this kind of >> interpolation (linear, cubic, spline etc) and the kind used in DSP >> audio work for up sampling. In audio up-sampling we just insert zero >> value samples and then pass the result through a low pass filter to >> remove the image frequencies. > >The DSP kind of interpolation usually assumes the the data is >from a bandlimited signal (or "close enough"). Other polynomial >types of interpolation usually have an error bounded by the >existance, continuity, or peak magnitude of some number of >derivatives of the function. > >How are these two different types of constraints related? > >
Have anyone tried to implement the polynomial based interpolator proposed
by Vesma Jussi? I tried to solve the optimization problem using fminsearch
in matlab. But it wasn't successful. Please advice. Thank you.




dspunrelated wrote:
> Have anyone tried to implement the polynomial based interpolator proposed > by Vesma Jussi?
after Googling and looking at the papers i could get for free online, i don't see what particular new idea Jussi, et. al. is offering. the concept of interpolating using a variety of fitted polynomials is not new (i personally like Hermite, but B-spline might attenuate the images even better). and interpolating over-sampled input using polynomials (this is what you do if you want to use Parks-McClellan or similar to optimally design your interpolation LPF, but are left with a bunch of finite phases or fractional sample delays). Duane Wise and i did a paper (following Zolzer and followed by Olli Niemitalo http://yehar.com/dsp/deip.pdf who did a better and more complete job). there's not a lot more math that is left that you can throw at the problem. r b-j
robert bristow-johnson wrote:
> dspunrelated wrote: > > Have anyone tried to implement the polynomial based interpolator proposed > > by Vesma Jussi? > > after Googling and looking at the papers i could get for free online, i > don't see what particular new idea Jussi, et. al. is offering. the > concept of interpolating using a variety of fitted polynomials is not > new (i personally like Hermite, but B-spline might attenuate the images > even better). and interpolating over-sampled input using polynomials > (this is what you do if you want to use Parks-McClellan or similar to > optimally design your interpolation LPF, but are left with a bunch of > finite phases or fractional sample delays).
My impression was that this interpolator was based on polynomial interpolation of segments of your Parks-McClellan kernel (instead of simple table-look-up, or a single-difference table-look-up approximation). So there will be no finite phases or fractional sample delays. But I could have misread the citation. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Ron N. wrote:
> robert bristow-johnson wrote: > > dspunrelated wrote: > > > Have anyone tried to implement the polynomial based interpolator proposed > > > by Vesma Jussi? > > > > after Googling and looking at the papers i could get for free online, i > > don't see what particular new idea Jussi, et. al. is offering. the > > concept of interpolating using a variety of fitted polynomials is not > > new (i personally like Hermite, but B-spline might attenuate the images > > even better). and interpolating over-sampled input using polynomials > > (this is what you do if you want to use Parks-McClellan or similar to > > optimally design your interpolation LPF, but are left with a bunch of > > finite phases or fractional sample delays). > > My impression was that this interpolator was based on polynomial > interpolation of segments of your Parks-McClellan kernel (instead > of simple table-look-up, or a single-difference table-look-up > approximation).
but that is precisely what Duane and I and Olli were doing. what are these "segments" of the interpolation kernal, if not a table lookup. how is that different?
> So there will be no finite phases or fractional sample delays.
you mean "finite [precision] phases or fractional sample delays", right? if so, again, how is that different? (i.e. *sure* there are finite precision phases or fractional sample delays, if there are segments and it becomes infinite precision when we use polynomials or some other continuously evaluated function to interpolate within a segment.) still don't see what the big deel is. r b-j