Interpolation using polyphase FIR filter: Finding coeffisients

Hi, 

I have a datastream that is sampled 4800 times pr second, but the rf front
end I am going to use accepts only input at 250000 samples pr second. 
Clearly I need a 52,0833 times interpolation. 

To achieve this I have planned to first interpolate 625 times, and then
decimate 12 times. I will do this in steps, for instance in steps of 5 for
the interpolation, and 4 for the decimation.

I have noticed that the best way of doing interpolation is to zero-stuff,
and then use a polyphase FIR filter to remove unwanted spectral images. My
problem is that I have never worked with digital signal processing before,
so I don't know how to find the coeffisients for the FIR filter. I would
be very grateful if someone could explain me how to find these
coeffisients!

I've downloaded a trial version of Scope FIR which can generate
coeffisients (limited to 32 taps in the trial version). But this program
needs parameters, and I am not shure what to choose to get the right
coeffisients:

-What type of filter: Simple Parks-McClellan, Advanced Parks-McClellan,
Windowed Sinc, Raised Cosine, Lth-Band (Nyquist), Inport/Boxcar, Maximally
Flat, CIC

-Passband upper frequency

-Stopband lower frequency

-Passband ripple

-Stopband Attenuation

I have also MatLab available if that would be any help.

Regards,
Jon
Trondheim, Norway

>I have noticed that the best way of doing interpolation is to zero-stuff,
>and then use a polyphase FIR filter to remove unwanted spectral images. 

almost. The trick with the polyphase filter is that the zero-stuffing and
decimation are actually omitted. Most of the samples exist only in the
head of the designer, because they are known to be zero and don't
contribute to the output.

I've written a short overview over polyphase filter here:
http://www.dsprelated.com/showarticle/22.php

There is a more advanced version (Farrow interpolator), and the page
contains a reference to a free paper.

I would start with Parks McClellan (aka equiripple), but keep an eye on
those outermost samples of the impulse response. They are not on a smooth
curve with the others.
Matlab has a filter design tool that can come in handy.

This doesn't tell the whole story, far from it. A textbook is for example:
http://www.dsprelated.com/books/60.php

Whether polyphase is the best approach is another question.

Cheers

Markus

To come back to the question, a possible signal chain _could_ look as
follows:

input at rate 1
upsampling filter by 2 => rate 2
upsampling filter by 2 => rate 4
upsampling filter by 2 => rate 8
upsampling filter by 2 => rate 16
upsampling filter by 2 => rate 32
Farrows from rate 32 to 52.08

Note that the first filter is the most critical, and it may be more
economic to combine some later stages.

The main idea is that I want to do all FIR filtering at the lowest
possible rate. It is easy to suppress the first alias band at 4.8 kHz,
when I'm running only at rate 2, but it will take many more taps if I try
the same at the high output rate: 
The length of the necessary impulse response remains the same in absolute
time units, but the number of taps increases with the rate.

Filter specs, shooting from the hip: 
Passband ripple < 0.1 dB
Stopband (alias band) attenuation: > 60 dB
OF COURSE this depends on YOUR requirements.

Hope that's useful.

-mn

On Sep 28, 12:57 pm, "mnentwig" <mnent...@elisanet.fi> wrote:
> >I have noticed that the best way of doing interpolation is to zero-stuff,
> >and then use a polyphase FIR filter to remove unwanted spectral images.
>
> almost. The trick with the polyphase filter is that the zero-stuffing and
> decimation are actually omitted. Most of the samples exist only in the
> head of the designer, because they are known to be zero and don't
> contribute to the output.

so you don't have to bother multiplying by zero and accumulating those
terms.

> I've written a short overview over polyphase filter here:http://www.dsprelated.com/showarticle/22.php
>
> There is a more advanced version (Farrow interpolator), and the page
> contains a reference to a free paper.
>
> I would start with Parks McClellan (aka equiripple), but keep an eye on
> those outermost samples of the impulse response. They are not on a smooth
> curve with the others.

if the OP is using MATLAB with the sig proc toolbox, i might suggest
firls(.) as an alternative to P-McC.  there are some other tricks.

> Whether polyphase is the best approach is another question.

what's the (efficient) alternative?  using APFs?  you can think of
linear (or polynomial) interpolation as comparable to polyphase, but
with different FIR coefs with infinite resolution on the fractional
delay time.

r b-j

On Sep 28, 8:19 am, "MrAlfred" <jonne...@online.no> wrote:
> I have a datastream that is sampled 4800 times pr second, but the rf front
> end I am going to use accepts only input at 250000 samples pr second.
> Clearly I need a 52,0833 times interpolation.
>
> To achieve this I have planned to first interpolate 625 times, and then
> decimate 12 times. I will do this in steps, for instance in steps of 5 for
> the interpolation, and 4 for the decimation.
>
> I have noticed that the best way of doing interpolation is to zero-stuff,
> and then use a polyphase FIR filter to remove unwanted spectral images. My
> problem is that I have never worked with digital signal processing before,
> so I don't know how to find the coeffisients for the FIR filter. I would
> be very grateful if someone could explain me how to find these
> coeffisients!
>
> I've downloaded a trial version of Scope FIR which can generate
> coeffisients (limited to 32 taps in the trial version). But this program
> needs parameters, and I am not shure what to choose to get the right
> coeffisients:

A single 32-tap filter will not allow you to directly
upsample by a factor of 625 after zero stuffing.  You
could upsample by 5 and repeat that 4 times. Or you
could use 625 different 32-tap filters, one for each
phase, but you wouldn't need to use all of them in
sequence, just every 12th one from a circular array.

But you haven't specified the quality or performance
bounds you require, which effects choices such as the
algorithms allowed (IIR vs. FIR) and the filter order
or length.  If performance isn't a limiting factor,
you could just start by multiplying your entire input
stream by a phase shifted Sinc function for every
output (see the slow Quick & Dirty interpolator on my
web dsp page: http://www.nicholson.com/rhn/dsp.html )
And if quality isn't a factor, you could just duplicate
input samples as needed.

How do you know you need a FIR?


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

>if the OP is using MATLAB with the sig proc toolbox, i might suggest
>firls(.) as an alternative to P-McC.  there are some other tricks.

Thanks, I'll remember that one. _Very_ useful information. 
So far I've been using a modified Parks McClellan script from Fred Harris'
course notes, to get a slope into the stopband, this is more general.

>> Whether polyphase is the best approach is another question.
>what's the (efficient) alternative?  using APFs?  you can think of
>linear (or polynomial) interpolation as comparable to polyphase, but
>with different FIR coefs with infinite resolution on the fractional
>delay time.

I don't know :) 
But I'm sure that some consultant is laughing right now after reading
this, "if he knew..."
The oversampling rate is so high that I'd probably try to go to 64 and
simply discard samples. If that's not good enough, linear interpolation,
or use only (for example) 3 bits from an 8 bit polyphase counter to index
the banks. Right, all that _is_ polyphase.

Also, there may be a good opportunity to use multiplierless IIRs to get
the rate up from 4 onwards with very little cost.

But never mind, since the OP mentioned that he just started DSP, it's
probably most important just to get it to work, not to make it efficient.

-mn

If performance isn't a limiting factor,
>you could just start by multiplying your entire input
>stream by a phase shifted Sinc function for every
>output (see the slow Quick & Dirty interpolator on my
>web dsp page: http://www.nicholson.com/rhn/dsp.html )
>And if quality isn't a factor, you could just duplicate
>input samples as needed.

This isn't "Dirty" at all, it's the best I could do :)

But good point... if it's sufficient to upsample the signal "offline" (not
in real time), that's the way to go.
A slightly faster implementation of the above idea is here:

http://www.elisanet.fi/mnentwig/webroot/FFT_interpolation_example/index.html

It assumes the signal is cyclic, therefore leave enough space on one side
(zero padding). Otherwise it's optimal, the ringing is a feature not a
bug.

-mn

On 28 Sep, 17:19, "MrAlfred" <jonne...@online.no> wrote:
> Hi,
>
> I have a datastream that is sampled 4800 times pr second, but the rf front
> end I am going to use accepts only input at 250000 samples pr second.
> Clearly I need a 52,0833 times interpolation.

> Regards,
> Jon
> Trondheim, Norway

Given your address -- you wouldn't by any chance be located at
or near NTNU? If so, go and ask Professor Tor Ramstad. If anyone
can help, it would be him.

Rune

Thank you all for your replies! I have to stress that I have no experience
with digital signal processing at all, I am a complete novice in this
field. I have only used linear interpolation before, so please bear with
me even if you'll find my questions stupid :)

Mnentwig wrote:
>Filter specs, shooting from the hip: 
>Passband ripple < 0.1 dB
>Stopband (alias band) attenuation: > 60 dB
>OF COURSE this depends on YOUR requirements.

My problem is that I really don't know what my requirements are. I know
that I have a signal, and that I want it to be interpolated, but I don't
know the requirements in terms of filter specs or what passband and
stopband really means. What I know: 

-Datastream output now sampled at 4800 times pr second
-Have to be interpolated to 250000 samples pr second without repeating
specters

Can the coeffisients be found with just this information? In other words,
can the filter specs be calculated out of this information? If not, what
more do I need to know?

Ron N wrote:
>A single 32-tap filter will not allow you to directly
>upsample by a factor of 625 after zero stuffing. You
>could upsample by 5 and repeat that 4 times. 

That was my plan.

Ron N wrote:
>But you haven't specified the quality or performance
>bounds you require, which effects choices such as the
>algorithms allowed (IIR vs. FIR) and the filter order
>or length. If performance isn't a limiting factor,
>you could just start by multiplying your entire input
>stream by a phase shifted Sinc function for every
>output (see the slow Quick & Dirty interpolator on my
>web dsp page: http://www.nicholson.com/rhn/dsp.html )
>And if quality isn't a factor, you could just duplicate
>input samples as needed.
>
>How do you know you need a FIR?

I am using OSSIE (ossie.wireless.vt.edu), which is an open source effort
in the field of software defined radio. They have made code for an
interpolator, which only require the interpolation factor and the
coeffisients as parameters. This code uses a FIR filter. If there is an
easy way to find the coeffisients, I will probably use this code for my
project.

Rune Allnor wrote:
>Given your address -- you wouldn't by any chance be located at
>or near NTNU? If so, go and ask Professor Tor Ramstad. If anyone
>can help, it would be him.

I am sitting at IT-bygget at NTNU, so I will try contact him. Thank you!


Regards,
Jon
Trondheim, Norway

On Oct 3, 7:50 am, "MrAlfred" <jonne...@online.no> wrote:
> Thank you all for your replies! I have to stress that I have no experience
> with digital signal processing at all, I am a complete novice in this
> field. I have only used linear interpolation before, so please bear with
> me even if you'll find my questions stupid :)
>
> Mnentwig wrote:
> >Filter specs, shooting from the hip:
> >Passband ripple < 0.1 dB
> >Stopband (alias band) attenuation: > 60 dB
> >OF COURSE this depends on YOUR requirements.
>
> My problem is that I really don't know what my requirements are. I know
> that I have a signal, and that I want it to be interpolated, but I don't
> know the requirements in terms of filter specs or what passband and
> stopband really means. What I know:
>
> -Datastream output now sampled at 4800 times pr second
> -Have to be interpolated to 250000 samples pr second without repeating
> specters
>
> Can the coeffisients be found with just this information? In other words,
> can the filter specs be calculated out of this information?

The problem is that filter coefficients *can* be found from this
information, an infinite number of sets of coefficients, including
just 1.0 (duplicate the nearest sample).  If 1.0 isn't good enough,
why not?  If 1.0 isn't good enough, then you must have some
unstated lower bound on interpolation accuracy.

For some metrics, the "quality" of a filter will increase with the
number of coefficients, without bound.  Where do you stop if
you don't want to filter infinitely?  If you don't want an infinite
FIR computation, then you must have some unstated upper
bound of quality of interpolation.  Some number of bits of
precision or something.

If you use some canned software package, it probably has
some assumed precision or quality level built in.  If it's SDR,
then maybe there is some SNR at which you want to be able
to recover some signal?


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M