# non integer interpolation

Started by August 6, 2008
```  Hi All,

I am trying to understand how a non-integer interpolating filter works.
For ex: In a 1.5 case, you would upsample by 3 and then down sample by
2.

How is the convolution between input samples and filter coefficients
choosen given that there are 3 sub filter?

for an interolation by 3 filter

the 1st sub filter(for a 15 tap) would be

Y1(n)=x(n)*h(0)+x(n-3)*h(3)+x(n-6)*h(6)+x(n-9)*h(9)+x(n-12)*h(12)
Y2(n)=x(n-1)*h(1)+x(n-4)*h(4)+x(n-7)*h(7)+x(n-10)*h(10)+x(n-13)*h(13)
Y3(n)=x(n-2)*h(2)+x(n-5)*h(5)+x(n-8)*h(8)+x(n-11)*h(11)+x(n-14)*h(14)

How would these change for a interpolation by 1.5 case?

Chivak

```
```On Aug 6, 9:25 pm, "chivak" <cd_pra...@hotmail.com> wrote:
>   Hi All,
>
>   I am trying to understand how a non-integer interpolating filter works.
>   For ex: In a 1.5 case, you would upsample by 3 and then down sample by
> 2.
>
>    How is the convolution between input samples and filter coefficients
> choosen given that there are 3 sub filter?
>
>  for an interolation by 3 filter
>
>  the 1st sub filter(for a 15 tap) would be
>
>  Y1(n)=x(n)*h(0)+x(n-3)*h(3)+x(n-6)*h(6)+x(n-9)*h(9)+x(n-12)*h(12)
>  Y2(n)=x(n-1)*h(1)+x(n-4)*h(4)+x(n-7)*h(7)+x(n-10)*h(10)+x(n-13)*h(13)
>  Y3(n)=x(n-2)*h(2)+x(n-5)*h(5)+x(n-8)*h(8)+x(n-11)*h(11)+x(n-14)*h(14)
>
>  How would these change for a interpolation by 1.5 case?
>
>    Chivak

I'm not sure at what you are asking exactly, but in the most
simplistic
case, to interpolate by 1.5, one can do:

Upsample by 3 --> LPF fc=pi/6 --> LPF fc=pi/4 --> Decimate by 2

So one can combine the two filters in the middle.

Or, one can write the sequence of operations as a polyphase
structure since half of the samples of the filter will be discarded
in
the end anyway.

Perhaps what you're looking for is how to write the operations
efficiently, such as using a filter bank or polyphase structure?

http://cnx.org/content/m10433/latest/

Julius
```
```On Aug 6, 10:25 pm, "chivak" <cd_pra...@hotmail.com> wrote:
>   Hi All,
>
>   I am trying to understand how a non-integer interpolating filter works.
>   For ex: In a 1.5 case, you would upsample by 3 and then down sample by
> 2.
>
>    How is the convolution between input samples and filter coefficients
> choosen given that there are 3 sub filter?
>
>  for an interolation by 3 filter
>
>  the 1st sub filter(for a 15 tap) would be
>
>  Y1(n)=x(n)*h(0)+x(n-3)*h(3)+x(n-6)*h(6)+x(n-9)*h(9)+x(n-12)*h(12)
>  Y2(n)=x(n-1)*h(1)+x(n-4)*h(4)+x(n-7)*h(7)+x(n-10)*h(10)+x(n-13)*h(13)
>  Y3(n)=x(n-2)*h(2)+x(n-5)*h(5)+x(n-8)*h(8)+x(n-11)*h(11)+x(n-14)*h(14)
>
>  How would these change for a interpolation by 1.5 case?
>
>    Chivak
Assuming n starts at 1 you take the output of
Y1(1) and Y3(1) then take Y2(2) then take Y1(3) and Y3(3) ....

This is essentially just decimating the output by 2 i.e. you take
every other sample.

Cheers,
Dave
```
```>On Aug 6, 10:25 pm, "chivak" <cd_pra...@hotmail.com> wrote:
>>   Hi All,
>>
>>   I am trying to understand how a non-integer interpolating filter
works.
>>   For ex: In a 1.5 case, you would upsample by 3 and then down sample
by
>> 2.
>>
>>    How is the convolution between input samples and filter
coefficients
>> choosen given that there are 3 sub filter?
>>
>>  for an interolation by 3 filter
>>
>>  the 1st sub filter(for a 15 tap) would be
>>
>>  Y1(n)=x(n)*h(0)+x(n-3)*h(3)+x(n-6)*h(6)+x(n-9)*h(9)+x(n-12)*h(12)
>>  Y2(n)=x(n-1)*h(1)+x(n-4)*h(4)+x(n-7)*h(7)+x(n-10)*h(10)+x(n-13)*h(13)
>>  Y3(n)=x(n-2)*h(2)+x(n-5)*h(5)+x(n-8)*h(8)+x(n-11)*h(11)+x(n-14)*h(14)
>>
>>  How would these change for a interpolation by 1.5 case?
>>
>>    Chivak
>Assuming n starts at 1 you take the output of
>Y1(1) and Y3(1) then take Y2(2) then take Y1(3) and Y3(3) ....
>
>This is essentially just decimating the output by 2 i.e. you take
>every other sample.
>
>Cheers,
>Dave
>

Thanx Dave,

I have another question : I'm thinking that its not possible to take
advantage of symmetry in case of polyphase interpolation filters

Am i correct ?

Thanx,
Chivak.

```
```On Aug 8, 6:25 pm, "chivak" <cd_pra...@hotmail.com> wrote:
> >On Aug 6, 10:25 pm, "chivak" <cd_pra...@hotmail.com> wrote:
> >>   Hi All,
>
> >>   I am trying to understand how a non-integer interpolating filter
> works.
> >>   For ex: In a 1.5 case, you would upsample by 3 and then down sample
> by
> >> 2.
>
> >>    How is the convolution between input samples and filter
> coefficients
> >> choosen given that there are 3 sub filter?
>
> >>  for an interolation by 3 filter
>
> >>  the 1st sub filter(for a 15 tap) would be
>
> >>  Y1(n)=x(n)*h(0)+x(n-3)*h(3)+x(n-6)*h(6)+x(n-9)*h(9)+x(n-12)*h(12)
> >>  Y2(n)=x(n-1)*h(1)+x(n-4)*h(4)+x(n-7)*h(7)+x(n-10)*h(10)+x(n-13)*h(13)
> >>  Y3(n)=x(n-2)*h(2)+x(n-5)*h(5)+x(n-8)*h(8)+x(n-11)*h(11)+x(n-14)*h(14)
>
> >>  How would these change for a interpolation by 1.5 case?
>
> >>    Chivak
> >Assuming n starts at 1 you take the output of
> >Y1(1) and Y3(1) then take Y2(2) then take Y1(3) and Y3(3) ....
>
> >This is essentially just decimating the output by 2 i.e. you take
> >every other sample.
>
> >Cheers,
> >Dave
>
> Thanx Dave,
>
>     I have another question : I'm thinking that its not possible to take
>   advantage of symmetry in case of polyphase interpolation filters
>
>  Am i correct ?
>

It might be possible to take advantage of symmetry - but my gut
feeling is it would be difficult for the general case and probably not
worth the effort.

Cheers,
Dave

```
```On Aug 8, 6:25 pm, "chivak" <cd_pra...@hotmail.com> wrote:
> >On Aug 6, 10:25 pm, "chivak" <cd_pra...@hotmail.com> wrote:
> >>   Hi All,
>
> >>   I am trying to understand how a non-integer interpolating filter
> works.
> >>   For ex: In a 1.5 case, you would upsample by 3 and then down sample
> by
> >> 2.
>
> >>    How is the convolution between input samples and filter
> coefficients
> >> choosen given that there are 3 sub filter?
>
> >>  for an interolation by 3 filter
>
> >>  the 1st sub filter(for a 15 tap) would be
>
> >>  Y1(n)=x(n)*h(0)+x(n-3)*h(3)+x(n-6)*h(6)+x(n-9)*h(9)+x(n-12)*h(12)
> >>  Y2(n)=x(n-1)*h(1)+x(n-4)*h(4)+x(n-7)*h(7)+x(n-10)*h(10)+x(n-13)*h(13)
> >>  Y3(n)=x(n-2)*h(2)+x(n-5)*h(5)+x(n-8)*h(8)+x(n-11)*h(11)+x(n-14)*h(14)
>
> >>  How would these change for a interpolation by 1.5 case?
>
> >>    Chivak
> >Assuming n starts at 1 you take the output of
> >Y1(1) and Y3(1) then take Y2(2) then take Y1(3) and Y3(3) ....
>
> >This is essentially just decimating the output by 2 i.e. you take
> >every other sample.
>
> >Cheers,
> >Dave
>
> Thanx Dave,
>
>     I have another question : I'm thinking that its not possible to take
>   advantage of symmetry in case of polyphase interpolation filters
>
>  Am i correct ?
>
>  Thanx,
>   Chivak.

There is no symmetry there to exploit. Although the interpolator is
linear phase, the sub-filters are asymmetric and nonlinear phase. Each
subfilter has its distortion cancelled by another one.

John
```
```On Aug 13, 9:35 pm, John <sampson...@gmail.com> wrote:

> There is no symmetry there to exploit.

I disagree.  Each reduced-rate output sample of a polyphase decimation
FIR  is still a function of all of the coefficients.  What it true is
that every input sample propagating through the delay line will never
encounter every coefficient (instead it will encounter every nth one)
but every coefficient still feeds into each reduced rate output
sample.  And that can be exploited to halve the number of mutliply
accumulates by pre-adding the symmetric pairs, though managing the
polyphase delay lines in a way that enables this is a royal pain.
```
```On Aug 13, 10:57 pm, cs_post...@hotmail.com wrote:
> On Aug 13, 9:35 pm, John <sampson...@gmail.com> wrote:
>
> > There is no symmetry there to exploit.
>
> I disagree.  Each reduced-rate output sample of a polyphase decimation
> FIR  is still a function of all of the coefficients.  What it true is
> that every input sample propagating through the delay line will never
> encounter every coefficient (instead it will encounter every nth one)
> but every coefficient still feeds into each reduced rate output
> sample.  And that can be exploited to halve the number of mutliply
> accumulates by pre-adding the symmetric pairs, though managing the
> polyphase delay lines in a way that enables this is a royal pain.

The OP wanted to interpolate by 1.5. To do that efficiently we stuff
every input sample into a circular delay line that is one-third as
long as the filter. We then cycle through three tap subsets, executing
a MAC loop every other time:

h(1:3:end)  MAC loop & save
h(2:3:end)
h(3:3:end)  MAC loop & save
h(1:3:end)
h(2:3:end)  MAC loop & save
h(3:3:end)
etc

Although the filter h is symmetric, the tap subsets shown above are
not.

John
```
```On Aug 14, 6:06 am, John <sampson...@gmail.com> wrote:

> Although the filter h is symmetric, the tap subsets shown above are
> not.

Thanks, now I get it: while the polyphase decimator uses every
coefficient to generate each less frequent output, the polyphase
interpolator can skip the ones that line up with zerod input samples.
And this application collapses the two into each other.
```