Interpolation for Dummies

I am trying to figure out interpolation (I have given up on decimation for
now).

My scenario is that I have 8 ksamples per second audio (from a phone line),
and I want to interpolate it to 96 ksamples per second.  I know my audio is
band limited within 0-4kHz, but other than that it could be anything --
human voice, modem tones, etc.

I understand the most basic concepts.  I could use linear interpolation,
where I connect the 8kHz dots with lines and then add 11 evenly spaced dots
along these lines.  I suppose I could do this and then run the result
through a LPF filter and it would improve it.  But I suspect these methods
are hardly state of the art.

I've also read that FIR filters can be created to directly interpolate a
signal, and there are other methods that I see mentioned but never
described.

My question is really whether there exists a good "interpolation for
dummies" reference that describes the processes at a high level.  I am
hoping that such a tutorial could give me some leads on what I really need
to be learning to try and understand it (to some degree).

Ian McBride wrote:
> I am trying to figure out interpolation (I have given up on decimation for
> now).
> 
> My scenario is that I have 8 ksamples per second audio (from a phone line),
> and I want to interpolate it to 96 ksamples per second.  I know my audio is
> band limited within 0-4kHz, but other than that it could be anything --
> human voice, modem tones, etc.
> 
> I understand the most basic concepts.  I could use linear interpolation,
> where I connect the 8kHz dots with lines and then add 11 evenly spaced dots
> along these lines.  I suppose I could do this and then run the result
> through a LPF filter and it would improve it.  But I suspect these methods
> are hardly state of the art.
> 
> I've also read that FIR filters can be created to directly interpolate a
> signal, and there are other methods that I see mentioned but never
> described.
> 
> My question is really whether there exists a good "interpolation for
> dummies" reference that describes the processes at a high level.  I am
> hoping that such a tutorial could give me some leads on what I really need
> to be learning to try and understand it (to some degree).

Ian:

The dspGuru site at "http://www.dspguru.com/sw/opendsp/alglib.htm" is a 
great start. They have C-code that performs interpolation/decimation 
using a FIR filter. I'm using their code and it performs as advertised.

This site has some nice comparisons between methods: 
"http://leute.server.de/wilde/resample.html#RandomNoiseUp".

Another good site with lots of detail : 
"http://ccrma-www.stanford.edu/~jos/Interpolation/Welcome.html".

Finally, in general, there are several books available that address 
"multirate" digital signal processing.

Good luck,
OUP

Ian McBride wrote:
>
> My question is really whether there exists a good "interpolation for
> dummies" reference that describes the processes at a high level.  I am
> hoping that such a tutorial could give me some leads on what I really need
> to be learning to try and understand it (to some degree).

This might help:
http://www.dspguru.com/info/faqs/mrfaq.htm

-- 
Jim Thomas            Principal Applications Engineer  Bittware, Inc
jthomas@bittware.com  http://www.bittware.com          (703) 779-7770
In theory, theory and practice are the same, but in practice, they're
not

On Fri, 18 Jul 2003 08:09:16 -0400, "Ian McBride"
<ianmcbride2003@yahoo.com> wrote:

Hello Ian,

>I am trying to figure out interpolation (I have given up on decimation for
>now).

Humm, I've always found decimation easier to understand than
interpolation.  Anyway ...

>My scenario is that I have 8 ksamples per second audio (from a phone line),
>and I want to interpolate it to 96 ksamples per second.  I know my audio is
>band limited within 0-4kHz, but other than that it could be anything --
>human voice, modem tones, etc.
>
>I understand the most basic concepts.  I could use linear interpolation,
>where I connect the 8kHz dots with lines and then add 11 evenly spaced dots
>along these lines.  I suppose I could do this and then run the result
>through a LPF filter and it would improve it.  But I suspect these methods
>are hardly state of the art.

Well, the most common method of interpolation is to 
stuff the 11 zeros in between your original samples 
and then lowpass filter the new sequence.  (As far as I know, 
there's no benefit in performing the 'linear interpolation' 
of putting the 11 dots on a straight line.)

There's away to perform accurate interpolation using the FFT,
if you're interested, but the above zero-stuffing and lowpass 
filtering is the most common method.

>I've also read that FIR filters can be created to directly interpolate a
>signal, and there are other methods that I see mentioned but never
>described.

Humm.  Am not sure exactly what you mean, but almost every DSP
textbook discusses interpolation.  It's not a terribly 
difficult subject.  You'll figure it out.

>My question is really whether there exists a good "interpolation for
>dummies" reference that describes the processes at a high level.  I am
>hoping that such a tutorial could give me some leads on what I really need
>to be learning to try and understand it (to some degree).
>

I noticed that Smith's DSP book (on the web at www.dspguide.com)
doesn't discuss interpolation to the depth you're seeking.
So you'll have to get a textbook, or search the web.
(Ya might seach on "interpolation tutorial'.)

Good Luck,
[-Rick-]

"Jim Thomas" <jthomas@bittware.com> wrote in message
news:3F1800AA.C0893999@bittware.com...
>
> This might help:
> http://www.dspguru.com/info/faqs/mrfaq.htm

Great!  Just shove zeros in there and run it through an FIR..  ..WOW..

OK.  Another question.  Lets say I have FSK data at 1200 bits per second.  I
translate 0's to -5000Hz and 1's to +5000Hz and compose a "baseband" of 1
sample per bit.  Can I zero stuff this with 79 zeroes, run it through an FIR
filter to get my filtered FSK baseband?  This seems confusing.  I'm
surprised that all of those zeroes wouldn't give you DC output with minor
"bumps" showing up 1200 times a second.

Thanks!


>
> --
> Jim Thomas            Principal Applications Engineer  Bittware, Inc
> jthomas@bittware.com  http://www.bittware.com          (703) 779-7770
> In theory, theory and practice are the same, but in practice, they're
> not

"Ian McBride" <ianmcbride2003@yahoo.com> wrote in message
news:bfagg9$1sv$1@slb3.atl.mindspring.net...
> "Jim Thomas" <jthomas@bittware.com> wrote in message
> news:3F1800AA.C0893999@bittware.com...
> >
> > This might help:
> > http://www.dspguru.com/info/faqs/mrfaq.htm
>
> Great!  Just shove zeros in there and run it through an FIR..  ..WOW..
>
> OK.  Another question.  Lets say I have FSK data at 1200 bits per second.
I
> translate 0's to -5000Hz and 1's to +5000Hz and compose a "baseband" of 1
> sample per bit.  Can I zero stuff this with 79 zeroes, run it through an
FIR
> filter to get my filtered FSK baseband?  This seems confusing.  I'm
> surprised that all of those zeroes wouldn't give you DC output with minor
> "bumps" showing up 1200 times a second.
>

Let's see if I understand:
FSK
+/-5,000Hz
Modulation of one bit per symbol: 0=-5,000Hz, 1=+5,000Hz
Bit/symbol rate of 1200 bits per second
You didn't say what the carrier frequency is.
You didn't say what the sample rate is.

I guess you consider the FSK baseband to be -1="0" and +1="1", something
like that?

Assign a carrier frequency of 50,000Hz.  Then the data has this as a center
frequency and the bandwidth will be something greater than 10kHz.

It appears what you would want to do is decimate, not interpolate and in the
process you would need to demodulate - which might be part of decimation.  I
think there's a nonlinear process needed here.

Fred

"Rick Lyons" <ricklyon@REMOVE.onemain.com> wrote in message
news:3f1804b6.17234828@news.earthlink.net...
> On Fri, 18 Jul 2003 08:09:16 -0400, "Ian McBride"
> <ianmcbride2003@yahoo.com> wrote:
>
> Hello Ian,
>
> >I am trying to figure out interpolation (I have given up on decimation
for
> >now).
>
> Humm, I've always found decimation easier to understand than
> interpolation.  Anyway ...
>
> >My scenario is that I have 8 ksamples per second audio (from a phone
line),
> >and I want to interpolate it to 96 ksamples per second.  I know my audio
is
> >band limited within 0-4kHz, but other than that it could be anything --
> >human voice, modem tones, etc.
> >
> >I understand the most basic concepts.  I could use linear interpolation,
> >where I connect the 8kHz dots with lines and then add 11 evenly spaced
dots
> >along these lines.  I suppose I could do this and then run the result
> >through a LPF filter and it would improve it.  But I suspect these
methods
> >are hardly state of the art.
>
> Well, the most common method of interpolation is to
> stuff the 11 zeros in between your original samples
> and then lowpass filter the new sequence.  (As far as I know,
> there's no benefit in performing the 'linear interpolation'
> of putting the 11 dots on a straight line.)

In fact, "connecting the dots" is usually a "bad idea" for two reasons:

1) If the in-between data is all zeros, the FIR filter can be optimized to
execute _much_ faster.  The zero valued samples can simply be skipped since
they contribute nothing to the result.

2) Linear interpolation is a low-pass filtering operation, and not a very
good one at that.  It introduces some roll-off in the pass-band which is a
problem in some applications.  True, it does give you some additional
stop-band attenuation, but you are almost always better off to skip the
linear interpolation and use the time saved to do a better (longer) single
FIR.

On Mon, 21 Jul 2003 12:24:50 -0700, "Jon Harris"
<jon_harrisTIGER@hotmail.com> wrote:

  (snipped)
>>
>> Well, the most common method of interpolation is to
>> stuff the 11 zeros in between your original samples
>> and then lowpass filter the new sequence.  (As far as I know,
>> there's no benefit in performing the 'linear interpolation'
>> of putting the 11 dots on a straight line.)
>
>In fact, "connecting the dots" is usually a "bad idea" for two reasons:
>
>1) If the in-between data is all zeros, the FIR filter can be optimized to
>execute _much_ faster.  The zero valued samples can simply be skipped since
>they contribute nothing to the result.

Hi Jon,


  VERY GOOD POINT !!!


[-Rick-]
>

"Rick Lyons" <ricklyon@REMOVE.onemain.com> wrote in message
news:3f1d70f5.21806828@news.earthlink.net...
> On Mon, 21 Jul 2003 12:24:50 -0700, "Jon Harris"
> <jon_harrisTIGER@hotmail.com> wrote:
>
>   (snipped)
> >>
> >> Well, the most common method of interpolation is to
> >> stuff the 11 zeros in between your original samples
> >> and then lowpass filter the new sequence.  (As far as I know,
> >> there's no benefit in performing the 'linear interpolation'
> >> of putting the 11 dots on a straight line.)
> >
> >In fact, "connecting the dots" is usually a "bad idea" for two reasons:
> >
> >1) If the in-between data is all zeros, the FIR filter can be optimized
to
> >execute _much_ faster.  The zero valued samples can simply be skipped
since
> >they contribute nothing to the result.
>
> Hi Jon,
>
>
>   VERY GOOD POINT !!!
>
>
> [-Rick-]

This is just another way of saying what a time-domain "polyphse" filter is
doing, right?
I thought your book made it much clearer than most Rick.

Fred

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:YOeTa.3375$Jk5.2341110@feed2.centurytel.net...
>
> "Rick Lyons" <ricklyon@REMOVE.onemain.com> wrote in message
> news:3f1d70f5.21806828@news.earthlink.net...
> > On Mon, 21 Jul 2003 12:24:50 -0700, "Jon Harris"
> > <jon_harrisTIGER@hotmail.com> wrote:
> >
> >   (snipped)
> > >>
> > >> Well, the most common method of interpolation is to
> > >> stuff the 11 zeros in between your original samples
> > >> and then lowpass filter the new sequence.  (As far as I know,
> > >> there's no benefit in performing the 'linear interpolation'
> > >> of putting the 11 dots on a straight line.)
> > >
> > >In fact, "connecting the dots" is usually a "bad idea" for two reasons:
> > >
> > >1) If the in-between data is all zeros, the FIR filter can be optimized
> to
> > >execute _much_ faster.  The zero valued samples can simply be skipped
> since
> > >they contribute nothing to the result.
> >
> > Hi Jon,
> >
> >
> >   VERY GOOD POINT !!!
> >
> >
> > [-Rick-]
>
> This is just another way of saying what a time-domain "polyphse" filter is
> doing, right?
> I thought your book made it much clearer than most Rick.
>
> Fred

Yes.  In my way of looking at things, the polyphase filter thing is just a
mathematical formalization of some simple optimizations that would be pretty
obvious to most people if when implementing interpolation.