Forums

uniform filter bank implementation.

Started by Craig July 2, 2003
I have a question with regards to going from a polyphase decimation
routine and adapting it to an actual filter bank to separate a large
bandwidth into smaller subbands.

I understand how polyphase filters works, that no problem, I am just
stuck on seeing how you make the transistion to a MxL (where M is the
number of channels, and L is the lenght of each filter bank)....
I have read previous posts, but no one has really had a detailed
discussion of how to create a filter bank, just for purposes of this
"soon to be tutorial", say we wanted to design a polyphase filter bank
to go from -fs/2 to fs/2, where we can define fs say, 96KHz.

so if I was just wanting to decimate the band to sample a signal that
is which lies somwhere in that region,
I would take some prototype low pass, or band pass filter H, and
seperate it into odd and even rows, then for all the H_odd you would
multply those rows by
-1 (this is same thing as multiply later by e^( -j * 2 * pi * k / L )
on each output row)
then I would take my input signal and do the same thing.  
Then you would simply filter each row by its like of the other...so if
you had
x(1,:) you would filter it using h(1,:) and so on, finially, you sum
each column, and that output vector is your new decimated signal.

Now I want to take that to the next level, and create a filter bank
using a similar approach, or some type of DFT matrix operation, like
outlined in many multirate filter books, but for me they seem to fudge
the issue, making it difficult for me to extract the exact operation
needed.
Any thoughts?

-C
Hi Craig

"Craig" <crrea2@umkc.edu> ha scritto nel messaggio
news:82396605.0307021238.443bbac@posting.google.com...

> I would take some prototype low pass, or band pass filter H, and > seperate it into odd and even rows, then for all the H_odd you would > multply those rows by > -1 (this is same thing as multiply later by e^( -j * 2 * pi * k / L ) > on each output row)
I guess you're talking about pseudo-QMF cosine modulated polyphase filter banks, like those adopted in MPEG audio. I reckon that the fact of multiplying every L prototype filter samples by -1 is like modulating later the output by the exponential factor you wrote. Maybe this is a way of saving some operation and making formulas a bit simpler (avoiding the fact of writing that modulation).
> then I would take my input signal and do the same thing.
here I don't understand: you just need to decimate the input signal, why should you multiply some of them by -1?
> Then you would simply filter each row by its like of the other...so if > you had > x(1,:) you would filter it using h(1,:) and so on, finially, you sum > each column, and that output vector is your new decimated signal.
That's correct since you're using modulated filters. But this is not an efficient way for doing a subband analysis. One can use polyphase (decimated) versions of the prototype filter and multiply the output samples by a modulation matrix who could be a DFT, a DCT or their fast versions.
> Now I want to take that to the next level, and create a filter bank > using a similar approach, or some type of DFT matrix operation, like > outlined in many multirate filter books, but for me they seem to fudge > the issue, making it difficult for me to extract the exact operation > needed. > Any thoughts?
There we go, just try to split the modulated filters in the prototype filter + a modulation matrix. If the prototype is MxL taps long, you'll have a modulation matrix whose dimension is MxM*L. Using polyphase versions is like using M filters with L taps each, so you could use a *shorter* matrix MxL. Using a cosine modulated matrix, whose elements are cos((m+0.5)(n-M/2)Pi/M) m=0...M-1, n=0...L-1 for the analysis bank and cos((m+0.5)(n+M/2)Pi/M) for the synthesis bank you will see why you need to multiply some taps of the prototype by -1 (the *long* matrix has periods that are multiplied by -1) Ok, mine is a bad explanation, further readings (with a more appropriate z transform based explanation) are in: P.P. Vaidyanathan, Multirate Systems and filterbanks, Prentice-Hall, 1993 and http://webpages.acs.ttu.edu/tkarp/publications.html let us know ;-) Emanuele, Italy
I guess I am just a little confused with the constant notation
switching, I am following Crochiere, since it is what I have available
to me.  The notation is rather abnoxious, and it isn't not clear what
is happening step by step so that I can implement the algorithm, I did
look at a lot of the papers on the website, but again they do the same
thing, where they skip steps and or make suddle notational changes,
but keep the same principle variable.
So, a step by step analysis would be nice.

I am starting with a band pass, I could easily start w/ a lowpass
filter as well, it reallly doesn't matter, what ever is easier to
explain. FIR filter with a length of 256.
To keep it simple I would like to have 8 channels over fs/2.
And I want to be able to view each channel independately.  
So for each branch I need to do a frequency shift to get the filter
centered about the correct center frequency.  I am still attempting to
follow all the notation switching in Crochiere, in hopes that I will
see what exactly is happening from input to output.


So if someone could give me more direction as to what happens in each
stage of the process, ie from an algorithm stand point, I would
appreciate it a lot.

Thanks
-C





"Ema" <ziglio@people.it> wrote in message news:<_LIMa.924$7y2.18588@tornado.fastwebnet.it>...
> Hi Craig > > "Craig" <crrea2@umkc.edu> ha scritto nel messaggio > news:82396605.0307021238.443bbac@posting.google.com... > > > I would take some prototype low pass, or band pass filter H, and > > seperate it into odd and even rows, then for all the H_odd you would > > multply those rows by > > -1 (this is same thing as multiply later by e^( -j * 2 * pi * k / L ) > > on each output row) > I guess you're talking about pseudo-QMF cosine modulated polyphase filter > banks, like those adopted in MPEG audio. > I reckon that the fact of multiplying every L prototype filter samples by -1 > is like modulating later the output by the exponential factor you wrote. > Maybe this is a way of saving some operation and making formulas a bit > simpler (avoiding the fact of writing that modulation). > > > then I would take my input signal and do the same thing. > here I don't understand: you just need to decimate the input signal, why > should you multiply some of them by -1? > > > Then you would simply filter each row by its like of the other...so if > > you had > > x(1,:) you would filter it using h(1,:) and so on, finially, you sum > > each column, and that output vector is your new decimated signal. > That's correct since you're using modulated filters. But this is not an > efficient way for doing a subband analysis. One can use polyphase > (decimated) versions of the prototype filter and multiply the output samples > by a modulation matrix who could be a DFT, a DCT or their fast versions. > > > Now I want to take that to the next level, and create a filter bank > > using a similar approach, or some type of DFT matrix operation, like > > outlined in many multirate filter books, but for me they seem to fudge > > the issue, making it difficult for me to extract the exact operation > > needed. > > Any thoughts? > There we go, just try to split the modulated filters in the prototype filter > + a modulation matrix. > If the prototype is MxL taps long, you'll have a modulation matrix whose > dimension is MxM*L. > Using polyphase versions is like using M filters with L taps each, so you > could use a *shorter* matrix MxL. > Using a cosine modulated matrix, whose elements are > cos((m+0.5)(n-M/2)Pi/M) m=0...M-1, n=0...L-1 for the analysis bank > and > cos((m+0.5)(n+M/2)Pi/M) for the synthesis bank > you will see why you need to multiply some taps of the prototype by -1 (the > *long* matrix has periods that are multiplied by -1) > > Ok, mine is a bad explanation, further readings (with a more appropriate z > transform based explanation) are in: > P.P. Vaidyanathan, Multirate Systems and filterbanks, Prentice-Hall, 1993 > > and http://webpages.acs.ttu.edu/tkarp/publications.html > > let us know ;-) > Emanuele, Italy
"Craig" <crrea2@umkc.edu> ha scritto nel messaggio
news:82396605.0307030813.233f549c@posting.google.com...
> I guess I am just a little confused with the constant notation > switching, I am following Crochiere, since it is what I have available > to me. The notation is rather abnoxious, and it isn't not clear what > is happening step by step so that I can implement the algorithm, I did > look at a lot of the papers on the website, but again they do the same > thing, where they skip steps and or make suddle notational changes, > but keep the same principle variable. > So, a step by step analysis would be nice.
In my preeceding post, I din't use any notation at all, do you refer to Crochiere's notation? In my humble opinion, that book was well explaining but a bit old at the moment. It gives a description of multirate systems completely in the time domain, while a more modern z-transform based notation (like in Vaidyanathan) at the end lets you describe more complex systems (even those with perfect reconstruction) in a synthetic and coherent form. Crochiere starts by filter banks based on DFT. That is the bandpass filetrs are obtained by modulating the prototype filter with an exponential function. That means: multiplying the prototype lowpass filters with exponentials whose frequency is centered on the different bands. This is what you already did, I suppose. But this is like filtering the input sequence using the prototype filter and then modulating the output. filter (x(n), ( h(n)*e(j 2 pi f n) ) = filter( x(n), h(n) ) * e(j 2 pi f n) The coefficients of the first M colums of this matrix are the kernel of a DFT transformation. You could perform the filtering with the prototype filter using its polyphase versions. This is like using M filters (whose length is M, while the filter prototype
> I am starting with a band pass, I could easily start w/ a lowpass > filter as well, it reallly doesn't matter, what ever is easier to > explain. FIR filter with a length of 256. > To keep it simple I would like to have 8 channels over fs/2. > And I want to be able to view each channel independately. > So for each branch I need to do a frequency shift to get the filter > centered about the correct center frequency. I am still attempting to > follow all the notation switching in Crochiere, in hopes that I will > see what exactly is happening from input to output. > > > So if someone could give me more direction as to what happens in each > stage of the process, ie from an algorithm stand point, I would > appreciate it a lot. > > Thanks > -C > > > > > > "Ema" <ziglio@people.it> wrote in message
news:<_LIMa.924$7y2.18588@tornado.fastwebnet.it>...
> > Hi Craig > > > > "Craig" <crrea2@umkc.edu> ha scritto nel messaggio > > news:82396605.0307021238.443bbac@posting.google.com... > > > > > I would take some prototype low pass, or band pass filter H, and > > > seperate it into odd and even rows, then for all the H_odd you would > > > multply those rows by > > > -1 (this is same thing as multiply later by e^( -j * 2 * pi * k / L ) > > > on each output row) > > I guess you're talking about pseudo-QMF cosine modulated polyphase
filter
> > banks, like those adopted in MPEG audio. > > I reckon that the fact of multiplying every L prototype filter samples
by -1
> > is like modulating later the output by the exponential factor you wrote. > > Maybe this is a way of saving some operation and making formulas a bit > > simpler (avoiding the fact of writing that modulation). > > > > > then I would take my input signal and do the same thing. > > here I don't understand: you just need to decimate the input signal, why > > should you multiply some of them by -1? > > > > > Then you would simply filter each row by its like of the other...so if > > > you had > > > x(1,:) you would filter it using h(1,:) and so on, finially, you sum > > > each column, and that output vector is your new decimated signal. > > That's correct since you're using modulated filters. But this is not an > > efficient way for doing a subband analysis. One can use polyphase > > (decimated) versions of the prototype filter and multiply the output
samples
> > by a modulation matrix who could be a DFT, a DCT or their fast versions. > > > > > Now I want to take that to the next level, and create a filter bank > > > using a similar approach, or some type of DFT matrix operation, like > > > outlined in many multirate filter books, but for me they seem to fudge > > > the issue, making it difficult for me to extract the exact operation > > > needed. > > > Any thoughts? > > There we go, just try to split the modulated filters in the prototype
filter
> > + a modulation matrix. > > If the prototype is MxL taps long, you'll have a modulation matrix whose > > dimension is MxM*L. > > Using polyphase versions is like using M filters with L taps each, so
you
> > could use a *shorter* matrix MxL. > > Using a cosine modulated matrix, whose elements are > > cos((m+0.5)(n-M/2)Pi/M) m=0...M-1, n=0...L-1 for the analysis bank > > and > > cos((m+0.5)(n+M/2)Pi/M) for the synthesis bank > > you will see why you need to multiply some taps of the prototype by -1
(the
> > *long* matrix has periods that are multiplied by -1) > > > > Ok, mine is a bad explanation, further readings (with a more appropriate
z
> > transform based explanation) are in: > > P.P. Vaidyanathan, Multirate Systems and filterbanks, Prentice-Hall,
1993
> > > > and http://webpages.acs.ttu.edu/tkarp/publications.html > > > > let us know ;-) > > Emanuele, Italy
Sorry about my English in the last message, the lovely Outlook Express sent
it without my permission!

I'd like to correct what I wrote, it seems nonsense!

> But this is like filtering the input sequence using the prototype filter
and
> then modulating the output. > filter (x(n), ( h(n)*e(j 2 pi f n) ) = filter( x(n), h(n) ) * e(j 2 pi f
n) I'll try to be clearer. At a certain instant n, you are filtering an input sequence with a bank of filters, all obtained by modulating a prototype. so we'll have: x(n)*h0(0) + x(n-1)*h0(1) +...+ x(n-MxL+1)*h0(MxL-1) for the baseband filter x(n)*h1(0) + x(n-1)*h1(1) +...+ x(n-MxL+1)*h2(MxL-1) for band 1 filter x(n)*h2(0) + x(n-1)*h2(1) +...+ x(n-MxL+1)*h3(MxL-1) for band 2 filter, and so on if you write the filter hk(n) like this: hk(n)=p(n)*e(j 2Pi fk n), where p(n) is the prototype and fk is the center frequency in the band k, you'll have: x(n)*p(0)*e(j 2Pi f0 0) + x(n-1)*p(1)*e(j 2Pi f0 1) +...+ x(n-MxL+1)*p(MxL-1)*e(j 2Pi f0 MxL-1) for the baseband filter x(n)*p(0)*e(j 2Pi f1 0) + x(n-1)*p(1)*e(j 2Pi f1 1) +...+ x(n-MxL+1)*p(MxL-1)*e(j 2Pi f1 MxL-1) for band 1 x(n)*p(0)*e(j 2Pi f2 0) + x(n-1)*p(1)*e(j 2Pi f2 1) +...+ x(n-MxL+1)*p(MxL-1)*e(j 2Pi f2 MxL-1) for band 2 it's clear now that we can multiply the input sequence by the prototype and modulate all the products with the appropriate exponential sequence, and sum the results to obtain the output for each subbands. sum ( (x(n)*h(n)) * e(j 2pi fk n)) I hope this is what you were looking for! Ciao, Emanuele
Hi Ema, I would appreciate if someone would be able to advise/point me on
the following 2 implementations for a decimation by M Polyphase filter
bank.

Implementation 1 - I take a M point FFT on the output of each polyphase
subfilter to obtain each channel.

Implementation 2 - I add the outputs of all the polyphase subfilters and
then take a M point FFT to obtain M channels.

Would the 2 implementations vary with an variation in M?

I'm interested in finding out what the most computationally efficient
implementation is on an FPGA and so this question stems from that. If
implementation 2 is permissible then this leads to a faster computation as
the subfilter outputs don't have to be multiplexed with a FFT (provided
that 1 FFT is to be common for all sub-filters).

Thanks in advance 


>Sorry about my English in the last message, the lovely Outlook Express
sent
>it without my permission! > >I'd like to correct what I wrote, it seems nonsense! > >> But this is like filtering the input sequence using the prototype
filter
>and >> then modulating the output. >> filter (x(n), ( h(n)*e(j 2 pi f n) ) = filter( x(n), h(n) ) * e(j 2 pi
f
>n) > >I'll try to be clearer. At a certain instant n, you are filtering an
input
>sequence with a bank of filters, all obtained by modulating a prototype. > >so we'll have: >x(n)*h0(0) + x(n-1)*h0(1) +...+ x(n-MxL+1)*h0(MxL-1) for the baseband
filter
>x(n)*h1(0) + x(n-1)*h1(1) +...+ x(n-MxL+1)*h2(MxL-1) for band 1 filter >x(n)*h2(0) + x(n-1)*h2(1) +...+ x(n-MxL+1)*h3(MxL-1) for band 2 filter, >and so on > >if you write the filter hk(n) like this: hk(n)=p(n)*e(j 2Pi fk n), where >p(n) is the prototype and fk is the center frequency in the band k,
you'll
>have: > >x(n)*p(0)*e(j 2Pi f0 0) + x(n-1)*p(1)*e(j 2Pi f0 1) +...+ >x(n-MxL+1)*p(MxL-1)*e(j 2Pi f0 MxL-1) for the baseband filter >x(n)*p(0)*e(j 2Pi f1 0) + x(n-1)*p(1)*e(j 2Pi f1 1) +...+ >x(n-MxL+1)*p(MxL-1)*e(j 2Pi f1 MxL-1) for band 1 >x(n)*p(0)*e(j 2Pi f2 0) + x(n-1)*p(1)*e(j 2Pi f2 1) +...+ >x(n-MxL+1)*p(MxL-1)*e(j 2Pi f2 MxL-1) for band 2 > >it's clear now that we can multiply the input sequence by the prototype
and
>modulate all the products with the appropriate exponential sequence, and
sum
>the results to obtain the output for each subbands. > >sum ( (x(n)*h(n)) * e(j 2pi fk n)) > >I hope this is what you were looking for! >Ciao, Emanuele > > >