A question from Vaidyanathan's "Multirate Systems" book

Hello Earthlings,

  I recently ran across some material in 
Vaidyanathan's "Multirate Systems and Filter Banks" 
DSP book that discusses a way to improve the 
computational efficiency of polyphase filters 
used in non-integer decimation applications. 

Vaidyanathan's description (starting on page 128, 
and derived from a 1987 conference paper by 
C.-C Hsiao) sounds interesting except for one 
tiny little thing.  To implement this "nice trick, 
as Vaidyanathan calls it, we have to implement the 
inverse of a delay.  What I mean by that is:
if a single-sample delay is represented by 
z^(-1), 1/z, Vaidyanathan shows an element in 
his Figure 4.3-8 block diagrams represented by 
a "z" (z to the plus one power)!!!  

It looks something like:

        ???         Delay        Delay

       |----|      |-----|      |-----|
x(n)-->| z  |--*-->| 1/z |--*-->| 1/z |--> a(n)
       |----|  |   |-----|  |   |-----|
               |            |
               |            |------------> b(n)
               |           
               |-------------------------> c(n)

I've read his description just about as thoroughly 
as I can, but I still can't figure out how we can 
implement that initial "time advance by one sample" 
operation shown above.
I took a look at the original Hsaio conference paper, 
but found no discernable explanation for that 
troubesome "z" operation.  I even went through 
Stephan Hawking's "A Brief History of Time" book 
to see if there was some way to travel into the 
future to obtain future time samples.  I had no luck 
reading either Hsaio's or Hawking's material.

Can the decimation scheme in Vaidyanathan's 
Figure 4.3-8 block diagrams actually work in our 
universe?   :-)

Gosh, ... I know I'm making some sort of silly mistake 
here, but I'm darned if I can figure what it is? 

Hey wait a second.  After typing this post it just 
occurred to me that maybe this "nice trick" can only 
be used "offline", the situation where all the x(n) 
time samples are available before the decimation 
process begins.  However, neither Vaidyanathan nor 
Hsaio mentioned (as far as I know) an "offline only" 
restriction for their decimation filters.

Anyway, I'd sure appreciate it if one of you guys could 
straighten me out.

Thanks Guys,
[-Rick-]

Rick Lyons wrote:
> Hello Earthlings,
> 
>   I recently ran across some material in 
> Vaidyanathan's "Multirate Systems and Filter Banks" 
> DSP book that discusses a way to improve the 
> computational efficiency of polyphase filters 
> used in non-integer decimation applications. 
> 
> Vaidyanathan's description (starting on page 128, 
> and derived from a 1987 conference paper by 
> C.-C Hsiao) sounds interesting except for one 
> tiny little thing.  To implement this "nice trick, 
> as Vaidyanathan calls it, we have to implement the 
> inverse of a delay.  What I mean by that is:
> if a single-sample delay is represented by 
> z^(-1), 1/z, Vaidyanathan shows an element in 
> his Figure 4.3-8 block diagrams represented by 
> a "z" (z to the plus one power)!!!  
> 
> It looks something like:
> 
>         ???         Delay        Delay
> 
>        |----|      |-----|      |-----|
> x(n)-->| z  |--*-->| 1/z |--*-->| 1/z |--> a(n)
>        |----|  |   |-----|  |   |-----|
>                |            |
>                |            |------------> b(n)
>                |           
>                |-------------------------> c(n)
> 
> I've read his description just about as thoroughly 
> as I can, but I still can't figure out how we can 
> implement that initial "time advance by one sample" 
> operation shown above.
> I took a look at the original Hsaio conference paper, 
> but found no discernable explanation for that 
> troubesome "z" operation.  I even went through 
> Stephan Hawking's "A Brief History of Time" book 
> to see if there was some way to travel into the 
> future to obtain future time samples.  I had no luck 
> reading either Hsaio's or Hawking's material.
> 
> Can the decimation scheme in Vaidyanathan's 
> Figure 4.3-8 block diagrams actually work in our 
> universe?   :-)
> 
> Gosh, ... I know I'm making some sort of silly mistake 
> here, but I'm darned if I can figure what it is? 
> 
> Hey wait a second.  After typing this post it just 
> occurred to me that maybe this "nice trick" can only 
> be used "offline", the situation where all the x(n) 
> time samples are available before the decimation 
> process begins.  However, neither Vaidyanathan nor 
> Hsaio mentioned (as far as I know) an "offline only" 
> restriction for their decimation filters.
> 
> Anyway, I'd sure appreciate it if one of you guys could 
> straighten me out.
> 
> Thanks Guys,
> [-Rick-]
> 

Hi Rick,

I don't know the exact details without looking at the book more closely, 
but instead of advancing the signal - can you delay all the others by a 
sample. If you are combining different signals what is important is the 
relative difference not the absolute one.

Cheers,
David

Rick Lyons wrote:
> Hello Earthlings,
> 
>   I recently ran across some material in 
> Vaidyanathan's "Multirate Systems and Filter Banks" 
> DSP book that discusses a way to improve the 
> computational efficiency of polyphase filters 
> used in non-integer decimation applications. 
> 
> Vaidyanathan's description (starting on page 128, 
> and derived from a 1987 conference paper by 
> C.-C Hsiao) sounds interesting except for one 
> tiny little thing.  To implement this "nice trick, 
> as Vaidyanathan calls it, we have to implement the 
> inverse of a delay.  What I mean by that is:
> if a single-sample delay is represented by 
> z^(-1), 1/z, Vaidyanathan shows an element in 
> his Figure 4.3-8 block diagrams represented by 
> a "z" (z to the plus one power)!!!  
> 
> It looks something like:
> 
>         ???         Delay        Delay
> 
>        |----|      |-----|      |-----|
> x(n)-->| z  |--*-->| 1/z |--*-->| 1/z |--> a(n)
>        |----|  |   |-----|  |   |-----|
>                |            |
>                |            |------------> b(n)
>                |           
>                |-------------------------> c(n)
> 
> I've read his description just about as thoroughly 
> as I can, but I still can't figure out how we can 
> implement that initial "time advance by one sample" 
> operation shown above.
> I took a look at the original Hsaio conference paper, 
> but found no discernable explanation for that 
> troubesome "z" operation.  I even went through 
> Stephan Hawking's "A Brief History of Time" book 
> to see if there was some way to travel into the 
> future to obtain future time samples.  I had no luck 
> reading either Hsaio's or Hawking's material.
> 
> Can the decimation scheme in Vaidyanathan's 
> Figure 4.3-8 block diagrams actually work in our 
> universe?   :-)
> 
> Gosh, ... I know I'm making some sort of silly mistake 
> here, but I'm darned if I can figure what it is? 
> 
> Hey wait a second.  After typing this post it just 
> occurred to me that maybe this "nice trick" can only 
> be used "offline", the situation where all the x(n) 
> time samples are available before the decimation 
> process begins.  However, neither Vaidyanathan nor 
> Hsaio mentioned (as far as I know) an "offline only" 
> restriction for their decimation filters.
> 
> Anyway, I'd sure appreciate it if one of you guys could 
> straighten me out.

Isn't offline rather similar to making the pipe a bit longer. :-)

Steve

"Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message
news:41b470cc.196117296@news.sf.sbcglobal.net...
>
> Hello Earthlings,
>
>   I recently ran across some material in
> Vaidyanathan's "Multirate Systems and Filter Banks"
> DSP book that discusses a way to improve the
> computational efficiency of polyphase filters
> used in non-integer decimation applications.
>
> Vaidyanathan's description (starting on page 128,
> and derived from a 1987 conference paper by
> C.-C Hsiao) sounds interesting except for one
> tiny little thing.  To implement this "nice trick,
> as Vaidyanathan calls it, we have to implement the
> inverse of a delay.  What I mean by that is:
> if a single-sample delay is represented by
> z^(-1), 1/z, Vaidyanathan shows an element in
> his Figure 4.3-8 block diagrams represented by
> a "z" (z to the plus one power)!!!

I've had the same problem when I've used his text to solve some polyphase
decomposition problems.
The way I dealt with it was to add a fixed delay equal to the largest
positive power of z at the input. This would give me a z^0 and several z^-ve
values (depending on my resampling ratios). So I then implemented them as
delays and jumped around the time advance that his text suggests.
It seemed to make sense to me and the fact that my design worked made me
feel a little better about it.

Hope this helps.

Cheers
Bhaskar

>
> It looks something like:
>
>         ???         Delay        Delay
>
>        |----|      |-----|      |-----|
> x(n)-->| z  |--*-->| 1/z |--*-->| 1/z |--> a(n)
>        |----|  |   |-----|  |   |-----|
>                |            |
>                |            |------------> b(n)
>                |
>                |-------------------------> c(n)
>
> I've read his description just about as thoroughly
> as I can, but I still can't figure out how we can
> implement that initial "time advance by one sample"
> operation shown above.
> I took a look at the original Hsaio conference paper,
> but found no discernable explanation for that
> troubesome "z" operation.  I even went through
> Stephan Hawking's "A Brief History of Time" book
> to see if there was some way to travel into the
> future to obtain future time samples.  I had no luck
> reading either Hsaio's or Hawking's material.
>
> Can the decimation scheme in Vaidyanathan's
> Figure 4.3-8 block diagrams actually work in our
> universe?   :-)
>
> Gosh, ... I know I'm making some sort of silly mistake
> here, but I'm darned if I can figure what it is?
>
> Hey wait a second.  After typing this post it just
> occurred to me that maybe this "nice trick" can only
> be used "offline", the situation where all the x(n)
> time samples are available before the decimation
> process begins.  However, neither Vaidyanathan nor
> Hsaio mentioned (as far as I know) an "offline only"
> restriction for their decimation filters.
>
> Anyway, I'd sure appreciate it if one of you guys could
> straighten me out.
>
> Thanks Guys,
> [-Rick-]
>

Hi Rick,

It seems that many of us have got into the trouble of the "non-causality"
created by that z^(+1) in Vaidyanathan's book.

Just to complement whay Bhaskar wrote, have a look at this thread in
comp.dsp archives http://tinyurl.com/668qw I hope this helps in clarifying,
as it did for me.

Regards,

--
Jaime Andr�s Aranguren Cardona
jaac@nospam.sanjaac.com
SanJaaC Electronics
Soluciones en DSP
www.sanjaac.com

(Remove "nospam" from e-mail address)

"Rick Lyons" <r.lyons@_BOGUS_ieee.org> escribi&#4294967295; en el mensaje
news:41b470cc.196117296@news.sf.sbcglobal.net...
>
> Hello Earthlings,
>
>   I recently ran across some material in
> Vaidyanathan's "Multirate Systems and Filter Banks"
> DSP book that discusses a way to improve the
> computational efficiency of polyphase filters
> used in non-integer decimation applications.
>
> Vaidyanathan's description (starting on page 128,
> and derived from a 1987 conference paper by
> C.-C Hsiao) sounds interesting except for one
> tiny little thing.  To implement this "nice trick,
> as Vaidyanathan calls it, we have to implement the
> inverse of a delay.  What I mean by that is:
> if a single-sample delay is represented by
> z^(-1), 1/z, Vaidyanathan shows an element in
> his Figure 4.3-8 block diagrams represented by
> a "z" (z to the plus one power)!!!
>
> It looks something like:
>
>         ???         Delay        Delay
>
>        |----|      |-----|      |-----|
> x(n)-->| z  |--*-->| 1/z |--*-->| 1/z |--> a(n)
>        |----|  |   |-----|  |   |-----|
>                |            |
>                |            |------------> b(n)
>                |
>                |-------------------------> c(n)
>
> I've read his description just about as thoroughly
> as I can, but I still can't figure out how we can
> implement that initial "time advance by one sample"
> operation shown above.
> I took a look at the original Hsaio conference paper,
> but found no discernable explanation for that
> troubesome "z" operation.  I even went through
> Stephan Hawking's "A Brief History of Time" book
> to see if there was some way to travel into the
> future to obtain future time samples.  I had no luck
> reading either Hsaio's or Hawking's material.
>
> Can the decimation scheme in Vaidyanathan's
> Figure 4.3-8 block diagrams actually work in our
> universe?   :-)
>
> Gosh, ... I know I'm making some sort of silly mistake
> here, but I'm darned if I can figure what it is?
>
> Hey wait a second.  After typing this post it just
> occurred to me that maybe this "nice trick" can only
> be used "offline", the situation where all the x(n)
> time samples are available before the decimation
> process begins.  However, neither Vaidyanathan nor
> Hsaio mentioned (as far as I know) an "offline only"
> restriction for their decimation filters.
>
> Anyway, I'd sure appreciate it if one of you guys could
> straighten me out.
>
> Thanks Guys,
> [-Rick-]
>

On Mon, 6 Dec 2004 12:55:30 -0500, "Jaime Andr�s Aranguren Cardona"
<jaac@nospam.sanjaac.com> wrote:

>Hi Rick,
>
>It seems that many of us have got into the trouble of the "non-causality"
>created by that z^(+1) in Vaidyanathan's book.
>
>Just to complement whay Bhaskar wrote, have a look at this thread in
>comp.dsp archives http://tinyurl.com/668qw I hope this helps in clarifying,
>as it did for me.
>
>Regards,
>
>--
>Jaime Andr&#4294967295;s Aranguren Cardona

Hello Jaime,
  thanks, I'll take a look at that thread.

[-Rick-]

On Mon, 6 Dec 2004 09:23:22 -0800, "Bhaskar Thiagarajan"
<bhaskart@my-deja.com> wrote:

  (snipped)
>
>I've had the same problem when I've used his text to solve some polyphase
>decomposition problems.
>The way I dealt with it was to add a fixed delay equal to the largest
>positive power of z at the input. This would give me a z^0 and several z^-ve
>values (depending on my resampling ratios). So I then implemented them as
>delays and jumped around the time advance that his text suggests.
>It seemed to make sense to me and the fact that my design worked made me
>feel a little better about it.
>
>Hope this helps.
>
>Cheers
>Bhaskar

Hi Bhaskar,

  it sounds like you solved this problem.
Sorry to be so "thick-skulled", but can you answer a 
couple of questions for me?  

Looking at the following block diagram, how can I add 
delays so that sample x(n+1) is available to me 
at time instant n?


         ???         Delay        Delay

        |----|      |-----|      |-----|
 x(n)-->| z  |--*-->| 1/z |--*-->| 1/z |--> a(n)
        |----|  |   |-----|  |   |-----|
                |            |
                |            |------------> b(n)
                |
                |-------------------------> x(n+1)


Can you tell me what your term "z^-ve" means?

I'd sure like to figure this out.
Thanks Bhaskar,
[-Rick-]

"Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message
news:41b78cd4.399900843@news.sf.sbcglobal.net...
> On Mon, 6 Dec 2004 09:23:22 -0800, "Bhaskar Thiagarajan"
> <bhaskart@my-deja.com> wrote:
>
>   (snipped)
> >
> >I've had the same problem when I've used his text to solve some polyphase
> >decomposition problems.
> >The way I dealt with it was to add a fixed delay equal to the largest
> >positive power of z at the input. This would give me a z^0 and several
z^-ve
> >values (depending on my resampling ratios). So I then implemented them as
> >delays and jumped around the time advance that his text suggests.
> >It seemed to make sense to me and the fact that my design worked made me
> >feel a little better about it.
> >
> >Hope this helps.
> >
> >Cheers
> >Bhaskar
>
> Hi Bhaskar,
>
>   it sounds like you solved this problem.
> Sorry to be so "thick-skulled", but can you answer a
> couple of questions for me?
>
> Looking at the following block diagram, how can I add
> delays so that sample x(n+1) is available to me
> at time instant n?
>
>
>          ???         Delay        Delay
>
>         |----|      |-----|      |-----|
>  x(n)-->| z  |--*-->| 1/z |--*-->| 1/z |--> a(n)
>         |----|  |   |-----|  |   |-----|
>                 |            |
>                 |            |------------> b(n)
>                 |
>                 |-------------------------> x(n+1)
>
>
> Can you tell me what your term "z^-ve" means?
Hi Rick

Sorry, I shouldn't have assumed that "z^-ve value" would read as "z raised
to negative values"...anyways, that's what I meant.
In your diagram, you have taken one segment of the diagram from the book -
I'm not sure how I can help solve just this one section without using the
other half.

If you see the diagram,
one branch uses x(n+1) and the other branch uses x(n).
My method was to apply a z^-1 to both branches. This would result in x(n)
for the top branch and x(n-1) for the bottom branch. In the end, I think it
is important to preserve the fact that the top branch leads the bottom by 1
unit of delay.

I'd be glad to answer more questions if you have any - not that I can
promise I'll have answers but I'll certainly try.

Cheers
Bhaskar




>
> I'd sure like to figure this out.
> Thanks Bhaskar,
> [-Rick-]

On Wed, 8 Dec 2004 16:04:28 -0800, "Bhaskar Thiagarajan"
<bhaskart@my-deja.com> wrote:


  (snipped)

>Hi Rick

Hi Bhaskar,

   I haven't been ignoring you,
I've just been pretty busy. 

  (snipped)
>
>If you see the diagram,
>one branch uses x(n+1) and the other branch uses x(n).
>My method was to apply a z^-1 to both branches. This would result in x(n)
>for the top branch and x(n-1) for the bottom branch. In the end, I think it
>is important to preserve the fact that the top branch leads the bottom by 1
>unit of delay.

Yes Yes Yes!
Darn, ... as you say I was focusing in on only 
part of the system instead of looking at the 
whole system.

I wonder why neither Vaidyanathan nor C.-C Hsiao 
explained this issue (to guys like me) as 
well as you just did.

>I'd be glad to answer more questions if you have any - not that I can
>promise I'll have answers but I'll certainly try.

Good job Bhaskar!  That's *another* beer I owe you!
(I hope you're keeping track.)

>Cheers
>Bhaskar

Thanks, ... I won't make this mistake again!
[-Rick-]

Rick wrote:

] Good job Bhaskar! That's *another* beer I owe you!
] (I hope you're keeping track.)
(-: If he's not, Google will. :-)

Ciao,

Peter K.