# Interpolation

Started by March 25, 2008
```On Mar 30, 8:42 pm, dbd <d...@ieee.org> wrote:
> On Mar 30, 12:23 pm, Gordon Sande <g.sa...@worldnet.att.net> wrote:
>
> > ...
> > Interpolation would be anytime the new samples are at other than the
> > the old places. The new places could be more closely spaced than the
> > old ones or less closely spaced. This just an alternate phrasing of
> > what you have said. Maybe some would find it easy to remember. After
> > all an interpolation formulae just matches the old values.
> > ...
>
> Thank you for demonstrating the misconception common in one of the
> problem areas I pointed out to Rick Lyons. Resampling formulas -
> do_not- match the old samples when they include anti-alias filtering.

that's not always true.

the requirement for resampled samples to match the old samples is that
the impulse response of the anti-aliasing filter, h(t), have

h(0) = 1

h(nT) = 0    for all integer n <> 0

that is the necessary and  sufficient requirement.

now, it is certainly the case that some optimizing of that impulse
response will make an interpolation kernal that does not satisfy the
above requiremen, but there is a whole class of impulse responses,
namely windowed sinc() functions, that do.  and if N (the polyphase
FIR filter length) is large enough, the aliases are very well antied.

but, for a fixed and limited N, i'm not saying that windowed sinc()
functions are the best, *but* what would be interesting is if such
constaints are applied to an optimization alg, you can always divided
by a sinc().  you never get division by zero except at places where it
is 0/0 and then you can use L'Hopital's rule.  it would be interesting
to see the effective "window function" that you get from such a
division of one function by another.

i know that when using Lagrange and Hermite interpolation, that the
output *does* go through the input points.  i thought at one time
(about the time that Duane Wise and i did this little interpolation
paper) i took a look at the resulting window function that i got when
i divided the Lagrange or Hermite interoplation kernel with a sinc()
function.  of course, it didn't match any window that i saw before,
and it wasn't usually continuous (at least some derivative showed
discontinuities in the part of the window that was non-zero).

> A new sample -has- been calculated even though it is at the same time
> as one of the original samples. fred harris' explicit separation of
> these processes into a resampling operation and filtering operation
> might help people understand this.

for me, all that is needed to understand the interpolation,
resampling, and/or fractional delay issue is the Nyquist/Shannon
sampling and reconstruction theorem.

> Can we define things to make it harder to make this mistake?

can you define the mistake explicitly for me?

if it is the semantic that for "interpolation", the interpolated
samples *must* agree with the original samples when their times
coincide, then i think that such is a good semantic.  but "sample rate
conversion", "resampling", and "fractional-sample delay" are not
necessarily the same thing as "interpolation".  *sometimes* procedures
we call "sample rate conversion", "resampling", and "fractional-sample
delay" do using interpolation as a method to decide what value to use
for those samples at in-between times, but sometimes they use
something else.

r b-j
```
```On Mar 30, 8:42 pm, dbd <d...@ieee.org> wrote:
> On Mar 30, 12:23 pm, Gordon Sande <g.sa...@worldnet.att.net> wrote:
>
> > ...
> > Interpolation would be anytime the new samples are at other than the
> > the old places. The new places could be more closely spaced than the
> > old ones or less closely spaced. This just an alternate phrasing of
> > what you have said. Maybe some would find it easy to remember. After
> > all an interpolation formulae just matches the old values.
> > ...
>
> Thank you for demonstrating the misconception common in one of the
> problem areas I pointed out to Rick Lyons. Resampling formulas -
> do_not- match the old samples when they include anti-alias filtering.

that's not always true.

the requirement for resampled samples to match the old samples is that
the impulse response of the anti-aliasing filter, h(t), have

h(0) = 1

h(nT) = 0    for all integer n <> 0

that is the necessary and  sufficient requirement.

now, it is certainly the case that some optimizing of that impulse
response will make an interpolation kernal that does not satisfy the
above requiremen, but there is a whole class of impulse responses,
namely windowed sinc() functions, that do.  and if N (the polyphase
FIR filter length) is large enough, the aliases are very well antied.

but, for a fixed and limited N, i'm not saying that windowed sinc()
functions are the best, *but* what would be interesting is if such
constaints are applied to an optimization alg, you can always divided
by a sinc().  you never get division by zero except at places where it
is 0/0 and then you can use L'Hopital's rule.  it would be interesting
to see the effective "window function" that you get from such a
division of one function by another.

i know that when using Lagrange and Hermite interpolation, that the
output *does* go through the input points.  i thought at one time
(about the time that Duane Wise and i did this little interpolation
paper) i took a look at the resulting window function that i got when
i divided the Lagrange or Hermite interoplation kernel with a sinc()
function.  of course, it didn't match any window that i saw before,
and it wasn't usually continuous (at least some derivative showed
discontinuities in the part of the window that was non-zero).

> A new sample -has- been calculated even though it is at the same time
> as one of the original samples. fred harris' explicit separation of
> these processes into a resampling operation and filtering operation
> might help people understand this.

for me, all that is needed to understand the interpolation,
resampling, and/or fractional delay issue is the Nyquist/Shannon
sampling and reconstruction theorem.

> Can we define things to make it harder to make this mistake?

can you define the mistake explicitly for me?

if it is the semantic that for "interpolation", the interpolated
samples *must* agree with the original samples when their times
coincide, then i think that such is a good semantic.  but "sample rate
conversion", "resampling", and "fractional-sample delay" are not
necessarily the same thing as "interpolation".  *sometimes* procedures
we call "sample rate conversion", "resampling", and "fractional-sample
delay" do using interpolation as a method to decide what value to use
for those samples at in-between times, but sometimes they use
something else.

r b-j
```
```On Mar 30, 8:42 pm, dbd <d...@ieee.org> wrote:
> On Mar 30, 12:23 pm, Gordon Sande <g.sa...@worldnet.att.net> wrote:
>
> > ...
> > Interpolation would be anytime the new samples are at other than the
> > the old places. The new places could be more closely spaced than the
> > old ones or less closely spaced. This just an alternate phrasing of
> > what you have said. Maybe some would find it easy to remember. After
> > all an interpolation formulae just matches the old values.
> > ...
>
> Thank you for demonstrating the misconception common in one of the
> problem areas I pointed out to Rick Lyons. Resampling formulas -
> do_not- match the old samples when they include anti-alias filtering.

that's not always true.

the requirement for resampled samples to match the old samples is that
the impulse response of the anti-aliasing filter, h(t), have

h(0) = 1

h(nT) = 0    for all integer n <> 0

that is the necessary and  sufficient requirement.

now, it is certainly the case that some optimizing of that impulse
response will make an interpolation kernal that does not satisfy the
above requiremen, but there is a whole class of impulse responses,
namely windowed sinc() functions, that do.  and if N (the polyphase
FIR filter length) is large enough, the aliases are very well antied.

but, for a fixed and limited N, i'm not saying that windowed sinc()
functions are the best, *but* what would be interesting is if such
constaints are applied to an optimization alg, you can always divided
by a sinc().  you never get division by zero except at places where it
is 0/0 and then you can use L'Hopital's rule.  it would be interesting
to see the effective "window function" that you get from such a
division of one function by another.

i know that when using Lagrange and Hermite interpolation, that the
output *does* go through the input points.  i thought at one time
(about the time that Duane Wise and i did this little interpolation
paper) i took a look at the resulting window function that i got when
i divided the Lagrange or Hermite interoplation kernel with a sinc()
function.  of course, it didn't match any window that i saw before,
and it wasn't usually continuous (at least some derivative showed
discontinuities in the part of the window that was non-zero).

> A new sample -has- been calculated even though it is at the same time
> as one of the original samples. fred harris' explicit separation of
> these processes into a resampling operation and filtering operation
> might help people understand this.

for me, all that is needed to understand the interpolation,
resampling, and/or fractional delay issue is the Nyquist/Shannon
sampling and reconstruction theorem.

> Can we define things to make it harder to make this mistake?

can you define the mistake explicitly for me?

if it is the semantic that for "interpolation", the interpolated
samples *must* agree with the original samples when their times
coincide, then i think that such is a good semantic.  but "sample rate
conversion", "resampling", and "fractional-sample delay" are not
necessarily the same thing as "interpolation".  *sometimes* procedures
we call "sample rate conversion", "resampling", and "fractional-sample
delay" do using interpolation as a method to decide what value to use
for those samples at in-between times, but sometimes they use
something else.

r b-j
```
```On Mar 30, 7:48 pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Mar 30, 8:42 pm, dbd <d...@ieee.org> wrote:

> ...
> > On Mar 30, 12:23 pm, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> > > ...
> > > After all an interpolation formulae just matches the old values.
> > > ...
>
> > Thank you for demonstrating the misconception common in one of the
> > problem areas I pointed out to Rick Lyons. Resampling formulas -
> > do_not- match the old samples when they include anti-alias filtering.
>
> that's not always true.
>
> the requirement for resampled samples to match the old samples is that
> the impulse response of the anti-aliasing filter, h(t), have
>
>     h(0) = 1
>
>     h(nT) = 0    for all integer n <> 0
>
> that is the necessary and  sufficient requirement.
>
> now, it is certainly the case that some optimizing of that impulse
> response will make an interpolation kernal that does not satisfy the
> above requiremen, but there is a whole class of impulse responses,
> namely windowed sinc() functions, that do.  and if N (the polyphase
> FIR filter length) is large enough, the aliases are very well antied.

When the sinc function is used as a prototype filter in windowed
filter design, the width of the sinc is scaled wider in time for
lowpass responses narrower than the Nyquist band. This would be done
for any lowpass anti-aliasing filter designed for sample rate
reduction with this method. No such filters satisfy the necessary and
sufficient conditions. There may be many resampling functions that do
meet those criteria. Since my example was in downsampling, none of
those functions are suitable as anti-aliasing filters.

> ...
> r b-j

Dale B. Dalrymple
```
```On Mar 30, 7:48 pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Mar 30, 8:42 pm, dbd <d...@ieee.org> wrote:

> ...
> > On Mar 30, 12:23 pm, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> > > ...
> > > After all an interpolation formulae just matches the old values.
> > > ...
>
> > Thank you for demonstrating the misconception common in one of the
> > problem areas I pointed out to Rick Lyons. Resampling formulas -
> > do_not- match the old samples when they include anti-alias filtering.
>
> that's not always true.
>
> the requirement for resampled samples to match the old samples is that
> the impulse response of the anti-aliasing filter, h(t), have
>
>     h(0) = 1
>
>     h(nT) = 0    for all integer n <> 0
>
> that is the necessary and  sufficient requirement.
>
> now, it is certainly the case that some optimizing of that impulse
> response will make an interpolation kernal that does not satisfy the
> above requiremen, but there is a whole class of impulse responses,
> namely windowed sinc() functions, that do.  and if N (the polyphase
> FIR filter length) is large enough, the aliases are very well antied.

When the sinc function is used as a prototype filter in windowed
filter design, the width of the sinc is scaled wider in time for
lowpass responses narrower than the Nyquist band. This would be done
for any lowpass anti-aliasing filter designed for sample rate
reduction with this method. No such filters satisfy the necessary and
sufficient conditions. There may be many resampling functions that do
meet those criteria. Since my example was in downsampling, none of
those functions are suitable as anti-aliasing filters.

> ...
> r b-j

Dale B. Dalrymple
```
```On Mar 30, 7:48 pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Mar 30, 8:42 pm, dbd <d...@ieee.org> wrote:

> ...
> > On Mar 30, 12:23 pm, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> > > ...
> > > After all an interpolation formulae just matches the old values.
> > > ...
>
> > Thank you for demonstrating the misconception common in one of the
> > problem areas I pointed out to Rick Lyons. Resampling formulas -
> > do_not- match the old samples when they include anti-alias filtering.
>
> that's not always true.
>
> the requirement for resampled samples to match the old samples is that
> the impulse response of the anti-aliasing filter, h(t), have
>
>     h(0) = 1
>
>     h(nT) = 0    for all integer n <> 0
>
> that is the necessary and  sufficient requirement.
>
> now, it is certainly the case that some optimizing of that impulse
> response will make an interpolation kernal that does not satisfy the
> above requiremen, but there is a whole class of impulse responses,
> namely windowed sinc() functions, that do.  and if N (the polyphase
> FIR filter length) is large enough, the aliases are very well antied.

When the sinc function is used as a prototype filter in windowed
filter design, the width of the sinc is scaled wider in time for
lowpass responses narrower than the Nyquist band. This would be done
for any lowpass anti-aliasing filter designed for sample rate
reduction with this method. No such filters satisfy the necessary and
sufficient conditions. There may be many resampling functions that do
meet those criteria. Since my example was in downsampling, none of
those functions are suitable as anti-aliasing filters.

> ...
> r b-j

Dale B. Dalrymple
```
```On Mar 30, 7:48 pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Mar 30, 8:42 pm, dbd <d...@ieee.org> wrote:

> ...
> > On Mar 30, 12:23 pm, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> > > ...
> > > After all an interpolation formulae just matches the old values.
> > > ...
>
> > Thank you for demonstrating the misconception common in one of the
> > problem areas I pointed out to Rick Lyons. Resampling formulas -
> > do_not- match the old samples when they include anti-alias filtering.
>
> that's not always true.
>
> the requirement for resampled samples to match the old samples is that
> the impulse response of the anti-aliasing filter, h(t), have
>
>     h(0) = 1
>
>     h(nT) = 0    for all integer n <> 0
>
> that is the necessary and  sufficient requirement.
>
> now, it is certainly the case that some optimizing of that impulse
> response will make an interpolation kernal that does not satisfy the
> above requiremen, but there is a whole class of impulse responses,
> namely windowed sinc() functions, that do.  and if N (the polyphase
> FIR filter length) is large enough, the aliases are very well antied.

When the sinc function is used as a prototype filter in windowed
filter design, the width of the sinc is scaled wider in time for
lowpass responses narrower than the Nyquist band. This would be done
for any lowpass anti-aliasing filter designed for sample rate
reduction with this method. No such filters satisfy the necessary and
sufficient conditions. There may be many resampling functions that do
meet those criteria. Since my example was in downsampling, none of
those functions are suitable as anti-aliasing filters.

> ...
> r b-j

Dale B. Dalrymple
```
```On Mar 31, 12:36 am, dbd <d...@ieee.org> wrote:

>
> When the sinc function is used as a prototype filter in windowed
> filter design, the width of the sinc is scaled wider in time for
> lowpass responses narrower than the Nyquist band.

that's a choice that someone might make.

> This would be done
> for any lowpass anti-aliasing filter designed for sample rate
> reduction with this method.

that is what you would want to do, particularly if you knew or assumed
that there was sufficient energy in the high frequencies of the pre-
sample-rate-reduced signal.  if you didn't think such was the case, or
for some reason didn't care, or if you were upsampling, then the
windowed sinc function is not so scaled.

> No such filters satisfy the necessary and
> sufficient conditions. There may be many resampling functions that do
> meet those criteria. Since my example was in downsampling, none of
> those functions are suitable as anti-aliasing filters.

again, it's how tough of a standard you want.  and if you are
confident that there is sufficient energy in the top octave

as far as interpolation is concerned (as opposed to the issue of
removing frequency components before sample rate reduction), this is
necessary and sufficient:

+inf
x(t) = SUM{ x(nT)*sinc((t-nT)/T) }
n=-inf

but, like any practical implementation, you won't be adding up all of
terms.  likewise is the downsampling antialiasing.  it's not defining.

r b-j
```
```On Mar 31, 12:36 am, dbd <d...@ieee.org> wrote:

>
> When the sinc function is used as a prototype filter in windowed
> filter design, the width of the sinc is scaled wider in time for
> lowpass responses narrower than the Nyquist band.

that's a choice that someone might make.

> This would be done
> for any lowpass anti-aliasing filter designed for sample rate
> reduction with this method.

that is what you would want to do, particularly if you knew or assumed
that there was sufficient energy in the high frequencies of the pre-
sample-rate-reduced signal.  if you didn't think such was the case, or
for some reason didn't care, or if you were upsampling, then the
windowed sinc function is not so scaled.

> No such filters satisfy the necessary and
> sufficient conditions. There may be many resampling functions that do
> meet those criteria. Since my example was in downsampling, none of
> those functions are suitable as anti-aliasing filters.

again, it's how tough of a standard you want.  and if you are
confident that there is sufficient energy in the top octave

as far as interpolation is concerned (as opposed to the issue of
removing frequency components before sample rate reduction), this is
necessary and sufficient:

+inf
x(t) = SUM{ x(nT)*sinc((t-nT)/T) }
n=-inf

but, like any practical implementation, you won't be adding up all of
terms.  likewise is the downsampling antialiasing.  it's not defining.

r b-j
```