Interpolation by rational factor

When you interpolate a signal by an integer M you stuff M-1 zero between 
each sample and send the upsampled sequence though a low-pass filter.

What do you do if M is a rational number >1 ???

Jens <jens@invalidxyzcom> wrote:

>When you interpolate a signal by an integer M you stuff M-1 zero between 
>each sample and send the upsampled sequence though a low-pass filter.
>
>What do you do if M is a rational number >1 ???

Try a Lagrangian interpolator.

There have been about three discussions of this on comp.dsp in the past 
year or so.

Steve

On 10/18/2010 07:29 PM, Jens wrote:
> When you interpolate a signal by an integer M you stuff M-1 zero between
> each sample and send the upsampled sequence though a low-pass filter.
>
> What do you do if M is a rational number >1 ???

If M = P/Q you stuff P-1 zeros, lowpass filter, then every Qth sample 
from the resulting signal -- whether P > Q or the obverse.

Or you use a polyphase filter.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

Tim Wescott <tim@seemywebsite.com> wrote:
> On 10/18/2010 07:29 PM, Jens wrote:
>> When you interpolate a signal by an integer M you stuff M-1 zero between
>> each sample and send the upsampled sequence though a low-pass filter.

>> What do you do if M is a rational number >1 ???
 
> If M = P/Q you stuff P-1 zeros, lowpass filter, then every Qth sample 
> from the resulting signal -- whether P > Q or the obverse.

Sounds good, but does anyone actually do that?

Consider sample rate conversion for digital audio.

I have a CD recorder that will accept different input rates and
convert to 44.1kHz for recording.  I believe it isn't even
synchronous.

Consider digital TV, where the horizontal sampling rate is different
from the screen size * line rate.  Or, even more, for screen lines
and frame rate?  I can almost see doing it per line, but collecting
the pixels in a column and doing the zero stuff/filter/decimate
would take way too long.

-- glen

On 10/18/2010 08:32 PM, glen herrmannsfeldt wrote:
> Tim Wescott<tim@seemywebsite.com>  wrote:
>> On 10/18/2010 07:29 PM, Jens wrote:
>>> When you interpolate a signal by an integer M you stuff M-1 zero between
>>> each sample and send the upsampled sequence though a low-pass filter.
>
>>> What do you do if M is a rational number>1 ???
>
>> If M = P/Q you stuff P-1 zeros, lowpass filter, then every Qth sample
>> from the resulting signal -- whether P>  Q or the obverse.
>
> Sounds good, but does anyone actually do that?
>
> Consider sample rate conversion for digital audio.
>
> I have a CD recorder that will accept different input rates and
> convert to 44.1kHz for recording.  I believe it isn't even
> synchronous.
>
> Consider digital TV, where the horizontal sampling rate is different
> from the screen size * line rate.  Or, even more, for screen lines
> and frame rate?  I can almost see doing it per line, but collecting
> the pixels in a column and doing the zero stuff/filter/decimate
> would take way too long.
>
> -- glen

"Or use a polyphase filter".

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

glen herrmannsfeldt wrote:
> Tim Wescott <tim@seemywebsite.com> wrote:
> 
>>On 10/18/2010 07:29 PM, Jens wrote:
>>
>>>When you interpolate a signal by an integer M you stuff M-1 zero between
>>>each sample and send the upsampled sequence though a low-pass filter.
> 
> 
>>>What do you do if M is a rational number >1 ???
> 
>  
> 
>>If M = P/Q you stuff P-1 zeros, lowpass filter, then every Qth sample 
>>from the resulting signal -- whether P > Q or the obverse.
> 
> 
> Sounds good, but does anyone actually do that?
> 
> Consider sample rate conversion for digital audio.
> 
> I have a CD recorder that will accept different input rates and
> convert to 44.1kHz for recording.  I believe it isn't even
> synchronous.

Most of inexpensive audio cards work at fixed sample rate which is 
typicaly 48 or 44.1kHz. All of the other sample rates are made by 
interpolation in the driver. That interpolation is fairly crude, 
something like linear between the adjacent samples.

> Consider digital TV, where the horizontal sampling rate is different
> from the screen size * line rate.  Or, even more, for screen lines
> and frame rate?  I can almost see doing it per line, but collecting
> the pixels in a column and doing the zero stuff/filter/decimate
> would take way too long.

Oh, video is the area of really dumb algorithms. They have to be fast, 
and the accuracy isn't important.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On 10/18/2010 11:07 PM, Tim Wescott wrote:

>
> "Or use a polyphase filter".
>

Tim,

I've never thought of a polyphase implementation as anything but a FIR 
filter.  So, one has to know what one has in mind *first*.  Then a 
polyphase implementation might be just the thing because of efficiency.

Did I miss something?

Fred

"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message 
news:i9j3fm$4n3$1@news.eternal-september.org...

> Consider digital TV, where the horizontal sampling rate is different
> from the screen size * line rate.  Or, even more, for screen lines
> and frame rate?  I can almost see doing it per line, but collecting
> the pixels in a column and doing the zero stuff/filter/decimate
> would take way too long.

Nope. That's what we do.
Typically I use a fourth, sixth, or eighth-order polyphase filter
for up-conversion. Horizontally, the delay elements are registers.
Vertically they are line delays.

This is all fairly easy to do in an FPGA these days.

For down-conversion I will often use higher-order filters, but
the output pixel rate is lower, so no more hardware is needed.

Usually this can be seperable, so that keeps the hardware simple.
(non-separable filters are not needed for simple zoom).

Pete 

On 10/19/2010 03:53 AM, Fred Marshall wrote:
> On 10/18/2010 11:07 PM, Tim Wescott wrote:
>
>>
>> "Or use a polyphase filter".
>>
>
> Tim,
>
> I've never thought of a polyphase implementation as anything but a FIR
> filter. So, one has to know what one has in mind *first*. Then a
> polyphase implementation might be just the thing because of efficiency.
>
> Did I miss something?
>
> Fred

I didn't see anything in the OP's post that ruled out an FIR filter. 
I'm pretty sure you could do a polyphase IIR filter (I've posted a 
thumbnail sketch of it here) -- but I haven't actually tried it, because 
I rarely need to do any sample rate conversions beyond simple decimation.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

Speaking of interpolation... Recently I fucked up (or had a valuable 
learning experience, if you put it in politically correct way). The 
problem could be stated as the following: estimate the phase of a 
sampled signal using digital PLL. The PLL was locked by adjustment of 
the "secondary" sample rate vs the incoming fixed "primary" sample rate. 
So the interpolation by an arbitrary factor was used. That interpolation 
resulted in the unexpectedly large timing errors; although the rms 
accuracy of the interpolator initially seemed to be adequate. The 
problem is that interpolation error is in fact deterministic rather then 
being the white noise like. That reminds me of quantization noise; may 
be, add some dither to the interpolator timing to break the periodical 
dependencies?


Not very long ago Dale asked me what is the origin of the rule to 
increase the stopband requirements of a filter by N times if you are 
planning to decimate this filter into N subfilters. That's simple: when 
the filter is decimated, its response is aliased. The N times 
requirement corresponds to the worst case. It generally doesn't matter 
if the filter is designed by Parks-McClellan, Windowed or any other method.





Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com