comb filters and fourier transforms for splitting sound into frequencies

On 22 Apr 2005 13:35:09 -0700, "Benry" <henrybg@gmail.com> wrote:

>A representation of what the Bins contain is all that is needed,
>correct?  The amplitude and frequency is what is needed.  I know that
>the bins are...well, the full FFT spectrum is just the additions of
>infinite sinc() functions...at least...well it's friday, so don't
>murder me for being ignorant.

Hi Benry,

  Jim & Jerry have given you some useful 
information.

It sounds (no pun intended) to me like you 
want to implement some sort of real-time 
spectrum analyzer, or maybe we should call it 
a "channelizer".  Such things are pretty 
common in DSP.

When I say "spectrum analyzer" I mean 
something like the equalizer displays that 
you see in the livingroom of audio nuts.
Oops, I mean "audio enthusiasts."
The EQ display is a group of vertical bars bouncing 
up and down in height as the spectrum of some audio 
signal changes with time.

You can build a spectrum analyzer by taking a 
single FFT of your signal and save the FFT results.
Take another FFT of your signal, shifted in time, and 
save those FFT results.  Shift your signal (again) in 
time and perform a third FFT and 
save those FFT results.

Now, let's say you're looking at bin 17 of your 
FFTs.  You should have a succession of X(17) 
values from all of those multiple FFTs that 
you performed.  That sequence of  
X(17) values ***is*** the output of a filter centered 
at the bin 17 center and whose passband is the 
good ol' sin(x)/x function.

How often (in time) you perform your FFTs determines
the output sample rate of your X(10) filter.

So if you perform multiple FFts you have built a spectrum 
analyzer (a "channelizer"), a bank of filters.  
I describe this kind of process in Chap 13 of the 2nd 
Edition of my book.  If there's no copy of the book 
available to you, Benry, check the following URL:

http://www.rfel.com/cgi-bin/search/search.pl?p=1&lang=en&include=&exclude=&penalty=0&mode=all&q=wola&submit=Search

Good Luck,
[-Rick-]

In article <116imdrfsipb692@corp.supernews.com>, Jim Thomas
<jthomas@bittware.com> wrote:

> ben wrote:
> > "split sound,... , into frequency bins" that is. each bin corresponding
> > to different smaller (than the full range of frequencies in the sound)
> > continuous ranges of frequencies.
> > 
> > prorgramatically be aware of which frequencies are occuring in a sound.
> > 
> > a sound recording contains multiple frequencies and those frequencies
> > are overlapping and intermixed together in a single stream of data.
> > instead of having only one stream i'd like to have multiple
> > streams/bands, each stream for a particular range of frequencies. 
> 
> I hope this does not offend you, but...

not at all
> 
> You do realize that the FFT does NOT produce a stream of data for every 
> frequency bin, don't you?  Rather, it produces a single complex number 
> for each bin.   The real portion of that number can be interpretted as 
> the amplitude of a cosine wave whose frequency equals the "bin" 
> frequency.  The imaginary part represents the amplitude of a sine wave 
> of that frequency.  A rectangular to polar conversion of this number 
> will give you tha amplitude and phase of a sinusoid of that frequency.
> 
> The output of a filter OTOH /is/ a stream of data.

yes but if you can use fft to tell which frequencies have or haven't
occured at this moment, and you keep doing fft's and reading the
results from those fft's then that's fine.

i just need to be able to be programmatically aware of what frequencies
are occuring when throughout the sound.

thanks, ben

In article <H42dnX0BttMG1_TfRVn-ig@rcn.net>, Jerry Avins <jya@ieee.org>
wrote:

> A crossover network used to feed different reproducers different 
> frequency ranges is an example of this. An extended version of this is a 
> filter bank. You might want to look at the inner workings of a "light 
> organ".

hmm, light organ sounds interesting. will have a look for info on that.
thanks.

> You have a problem here. The longer the section of sound you analyze, 
> the more finely you can discriminate between frequencies close together. 
> The shorter the time allowed for analysis, the fewer "bins" you can 
> meaningfully have, and the fuzzier the boundaries between them. The 
> situation is analogous to Heisenberg's Uncertainty Principle of quantum 
> mechanics: if you know the momentum of a particle precisely, you can 
> have no idea of where it is. Conversely, if you know its location 
> precisely, you can have no idea how fast it moves. The analogy is 
> deeper: The product of the momentum and location uncertainties is fixed, 
> just as, with sound analysis, the product of the frequency and time 
> uncertainties is fixed.

like a see saw. i see.

right, thanks a lot,

ben.

In article <426a413b.151299640@news.sf.sbcglobal.net>, Rick Lyons
<R.Lyons@_BOGUS_ieee.org> wrote:

> On 22 Apr 2005 13:35:09 -0700, "Benry" <henrybg@gmail.com> wrote:
> 
> >A representation of what the Bins contain is all that is needed,
> >correct?  The amplitude and frequency is what is needed.  I know that
> >the bins are...well, the full FFT spectrum is just the additions of
> >infinite sinc() functions...at least...well it's friday, so don't
> >murder me for being ignorant.
> 
> Hi Benry,

i think you might be merging Benry and me together -- two different
people. just thought i'd mention that. doesn't really matter though.

>   Jim & Jerry have given you some useful 
> information.
> 
> It sounds (no pun intended) to me like you 
> want to implement some sort of real-time 
> spectrum analyzer, or maybe we should call it 
> a "channelizer". 

yes channeliser (if channels correspond to different, small ranges of
frequencies in the sound) sounds good to me. not necessarily real-time
right now, although i could see my requirement slipping over to
real-time so if real-time's quite possible, then great, yes, real-time
it is. would there be a major difference in the method used for
real-time and not real-time? but i'm not too fussed about the real-time
aspect right now although it might be a good idea to not cut that
possibility off.

> Such things are pretty 
> common in DSP.
> 
> When I say "spectrum analyzer" I mean 
> something like the equalizer displays that 
> you see in the livingroom of audio nuts.
> Oops, I mean "audio enthusiasts."
> The EQ display is a group of vertical bars bouncing 
> up and down in height as the spectrum of some audio 
> signal changes with time.

yup exactly, or also commonly in the software versions of a hifi's --
various software music players often have them, just because they can i
suppose.

the reason i'm after that is to be able to programmatically know what
frequencies are occuring in a sound and when, in order to go on and
further analyse the sound. perform basically the same function as what
the cochlea in the human ear does.

> 
> You can build a spectrum analyzer by taking a 
> single FFT of your signal and save the FFT results.
> Take another FFT of your signal, shifted in time, and 
> save those FFT results.  Shift your signal (again) in 
> time and perform a third FFT and 
> save those FFT results.
> 
> Now, let's say you're looking at bin 17 of your 
> FFTs.  You should have a succession of X(17) 
> values from all of those multiple FFTs that 
> you performed.  That sequence of  
> X(17) values ***is*** the output of a filter centered 
> at the bin 17 center and whose passband is the 
> good ol' sin(x)/x function.
> 
> How often (in time) you perform your FFTs determines
> the output sample rate of your X(10) filter.
> 
> So if you perform multiple FFts you have built a spectrum 
> analyzer (a "channelizer"), a bank of filters.  
> I describe this kind of process in Chap 13 of the 2nd 
> Edition of my book.  If there's no copy of the book 
> available to you , Benry, check the following URL:
> 
> http://www.rfel.com/cgi-bin/search/search.pl?p=1&lang=en&include=&exclude=&penalty=0&mode=all&q=wola&submit=Search
> 
> Good Luck,
> [-Rick-]

great, very useful information -- thanks. will keep that and more than
likely follow your advice. but, originally i was asking about the
differences and similarities between the results from any good fourier
transform implemention, such as what you've described above, and any
good comb filter implemention[*] when using both of those methods to
analyse which frequencies are occuring; a comparison of the results
you'd get from those two methods -- can they both achieve the same
thing -- in theory? if they can't in what way would they likely differ?
etc etc -- a general comparison between the two is what i was asking
about -- how their end results would compare? Benry gave a good, useful
answer in this thread to that (the first answer to the original
question) which i was pretty pleased with -- if it's roughly correct
that is -- he said himself he's wasn't entirely sure on it. his answer
seemed pretty reasonable to me though.

[*] imagine a clever, good, flexible implentation of what comb filter
brings to mind -- i know that's vague but just imagine a dynamic, full
on, involved implemention of what comb filter implies.

Benry pointed out a practical difference: with the fourier transform
method it's fairly easy to look at all frequencies -- get a full
overview, where as with a comb filter type of method you're only going
to see what you look for, so with comb filters it'd be quite hard and
time consuming to get a reasonable full picture of the occuring
frequencies. so the comb filter potentially has a very blinkered
characteristic to it.

but he also hinted that possibly, in theory, both the fourier transform
method and the comb filter method _could_ give much the same results --
so if both methods were carried out exceptionally fully and brilliantly
neither set of results would be particularly different or better than
the other. even if it's just theory, that's really useful for me just
to know.

thanks very much, ben.

Stan Pawlukiewicz wrote:

> Beg to differ, but it has been shown in the literature that the DFT is 
> indeed a special case of a multirate filter bank.

We've had this argument here before and I still can't agree. 
  Each point of a DFT is an inner product of some number of 
cycles of a sinusoid with a sequence of data points.  It is 
a static computation on a sequence of data points.  A filter 
produces output continuously in response to input presented 
continuously.  They could hardly be different so far as I 
can see.

OTOH if the DFT was computed anew for each new sample 
throwing away the oldest in the sequence, then each point of 
the DFT is in fact a filter output with the coeficients 
being a sinusoid.  But to say that a one shot DFT is 
intrinsically a filter seems totally wrong to me.

I'm curious as to what kind of filter an FIR with 
coeficients taken from a sinuoid actually is.  Never heard 
of one being used per se.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

On Sun, 24 Apr 2005 01:14:08 -0700, Bob Cain
<arcane@arcanemethods.com> wrote:

>
>
>Stan Pawlukiewicz wrote:
>
>> Beg to differ, but it has been shown in the literature that the DFT is 
>> indeed a special case of a multirate filter bank.
>
>We've had this argument here before and I still can't agree. 
>  Each point of a DFT is an inner product of some number of 
>cycles of a sinusoid with a sequence of data points.  It is 
>a static computation on a sequence of data points.  A filter 
>produces output continuously in response to input presented 
>continuously.  They could hardly be different so far as I 
>can see.
>
>OTOH if the DFT was computed anew for each new sample 
>throwing away the oldest in the sequence, then each point of 
>the DFT is in fact a filter output with the coeficients 
>being a sinusoid.  But to say that a one shot DFT is 
>intrinsically a filter seems totally wrong to me.

Hi Bob,

   you just just hit the key issue here with 
your "computed anew" phrase..

If you perform repetitive DFTs, a new DFT for each 
new x(n) input sample that arrives, the resulting 
sequence for a single DFT bin output is equivalent 
to the output a nonrecursive FIR filter.
That equivalent filter has complex coefficients and 
its passband is centered at the center of whichever bin 
you're looking at.

So, ... computing repetitive 64-point DFTs is an implementation 
of a bank of 64 FIR bandpass filters whose passband 
centers are equally spaced from -Fs/2 to Fs/2.

When you compute a single bin value of a DFT, you 
perform some multiplies and sum the products.
When you compute a single tapped-dealy line FIR filter 
output value , you 
perform some multiplies and sum the products.

The problem is that we spend years trying to 
understand all the spectrum analysis 
characteristics (and subtleties) of the DFT, and 
it is NOT AT ALL obvious that the DFT can be viewed 
as a filter.

Hope that makes some sense.
[-Rick-]

Bob Cain wrote:
> 
> 
> Stan Pawlukiewicz wrote:
> 
>> Beg to differ, but it has been shown in the literature that the DFT is 
>> indeed a special case of a multirate filter bank.
> 
> 
> We've had this argument here before and I still can't agree.  Each point 
> of a DFT is an inner product of some number of cycles of a sinusoid with 
> a sequence of data points.  It is a static computation on a sequence of 
> data points.  A filter produces output continuously in response to input 
> presented continuously.  They could hardly be different so far as I can 
> see.
> 
> OTOH if the DFT was computed anew for each new sample throwing away the 
> oldest in the sequence, then each point of the DFT is in fact a filter 
> output with the coeficients being a sinusoid.  But to say that a one 
> shot DFT is intrinsically a filter seems totally wrong to me.
> 
> I'm curious as to what kind of filter an FIR with coeficients taken from 
> a sinuoid actually is.  Never heard of one being used per se.
> 
> 
> Bob

Consider the title of chapter 6 of Elliot and Rao's "Fast Transforms, 
Algorithms, Analysis,and Applications", Academic Press, 1982,  "DFT 
FIlter shapes and Shaping".  You can look at Gilbert Strang's book on 
wavelets where in the introduction, he points out that filters can be 
expressed as Matrix vector products.  A waveneumber filter can have a 
single output.  I can make a replica correlator out of a matched filter 
sampled at a single point.  Does sampling the matched filter at a single 
point unmake it as a matched-filter?

You're free to believe what you want but I can show you books and 
articles that interperet the DFT a special sort of multirate filter 
bank.  Show me books or articles that say a DFT is in no circumstance a 
filter.

Stan Pawlukiewicz <spam@spam.mitre.org> writes:

> Bob Cain wrote:
> > Stan Pawlukiewicz wrote:
> 
> >
> 
> >> Beg to differ, but it has been shown in the literature that the DFT
> >> is indeed a special case of a multirate filter bank.
> 
> > We've had this argument here before and I still can't agree.  Each
> > point of a DFT is an inner product of some number of cycles of a
> > sinusoid with a sequence of data points.  It is a static computation
> > on a sequence of data points.  A filter produces output continuously
> > in response to input presented continuously.  They could hardly be
> > different so far as I can see.
> 
> > OTOH if the DFT was computed anew for each new sample throwing away
> > the oldest in the sequence, then each point of the DFT is in fact a
> > filter output with the coeficients being a sinusoid.  But to say
> > that a one shot DFT is intrinsically a filter seems totally wrong to
> > me.
> 
> > I'm curious as to what kind of filter an FIR with coeficients taken
> > from a sinuoid actually is.  Never heard of one being used per se.
> 
> > Bob
> 
> 
> Consider the title of chapter 6 of Elliot and Rao's "Fast Transforms,
> Algorithms, Analysis,and Applications", Academic Press, 1982,  "DFT
> FIlter shapes and Shaping".  You can look at Gilbert Strang's book on
> wavelets where in the introduction, he points out that filters can be
> expressed as Matrix vector products.  A waveneumber filter can have a
> single output.  I can make a replica correlator out of a matched
> filter sampled at a single point.  Does sampling the matched filter at
> a single point unmake it as a matched-filter?
> 
> 
> You're free to believe what you want but I can show you books and
> articles that interperet the DFT a special sort of multirate filter
> bank.  Show me books or articles that say a DFT is in no circumstance
> a filter.

Hi Stan,

I agree with you, but I think you're leaving out a few details. Namely,
how DOES one process an indefinite stream of input data with the N-point DFT to provide
N indefinite streams of output data? Is the DFT taken every sample? Every N/2
samples? Every N samples? What? I think this is the question Bob is asking,
and as I've only "heard" the "DFT is a filterbank" argument and not seen it
operate in action, I'd like to know the answer as well.
-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

i asked about a comparison (differences/similarities/pros/cons) between
two methods: 1. amdf/comb filtering, 2. fft/fourier transforms, for
achieving the same goal: splitting sound into various frequency bands
throughout the sound (like a graphic equaliser in hifi's).

i think a reasonably correct comparison/comment is: there's not a lot
of difference between the results that the two methods can provide,
assuming a good implemention of both. the results from carrying out
either method to accomplish the goal aren't destined to be inherently
different by choosing one of the mentioned methods as opposed to the
other? (from an end results point of view that is).

i know Benry asnwered that (thanks Benry), and sorry to go on, but it'd
be great to get confirmation of that if possible?

thanks very much, ben.


p.s. i now realise that amdf isn't different or more than comb
filtering at all (which is i thought and said earlier) -- they're the
same thing.

Randy Yates wrote:
> Stan Pawlukiewicz <spam@spam.mitre.org> writes:
> 
> 
>>Bob Cain wrote:
>>
>>>Stan Pawlukiewicz wrote:
>>
>>>>Beg to differ, but it has been shown in the literature that the DFT
>>>>is indeed a special case of a multirate filter bank.
>>
>>>We've had this argument here before and I still can't agree.  Each
>>>point of a DFT is an inner product of some number of cycles of a
>>>sinusoid with a sequence of data points.  It is a static computation
>>>on a sequence of data points.  A filter produces output continuously
>>>in response to input presented continuously.  They could hardly be
>>>different so far as I can see.
>>
>>>OTOH if the DFT was computed anew for each new sample throwing away
>>>the oldest in the sequence, then each point of the DFT is in fact a
>>>filter output with the coeficients being a sinusoid.  But to say
>>>that a one shot DFT is intrinsically a filter seems totally wrong to
>>>me.
>>
>>>I'm curious as to what kind of filter an FIR with coeficients taken
>>>from a sinuoid actually is.  Never heard of one being used per se.
>>
>>>Bob
>>
>>
>>Consider the title of chapter 6 of Elliot and Rao's "Fast Transforms,
>>Algorithms, Analysis,and Applications", Academic Press, 1982,  "DFT
>>FIlter shapes and Shaping".  You can look at Gilbert Strang's book on
>>wavelets where in the introduction, he points out that filters can be
>>expressed as Matrix vector products.  A waveneumber filter can have a
>>single output.  I can make a replica correlator out of a matched
>>filter sampled at a single point.  Does sampling the matched filter at
>>a single point unmake it as a matched-filter?
>>
>>
>>You're free to believe what you want but I can show you books and
>>articles that interperet the DFT a special sort of multirate filter
>>bank.  Show me books or articles that say a DFT is in no circumstance
>>a filter.
> 
> 
> Hi Stan,
> 
> I agree with you, but I think you're leaving out a few details. Namely,
> how DOES one process an indefinite stream of input data with the N-point DFT to provide
> N indefinite streams of output data? Is the DFT taken every sample? Every N/2
> samples? Every N samples? What? I think this is the question Bob is asking,
> and as I've only "heard" the "DFT is a filterbank" argument and not seen it
> operate in action, I'd like to know the answer as well.

Multirate filters generalize filters so that the number of input points 
don't have to equal the number of output points.  I don't know what you 
mean by "indefinite".  I don't think Bob asked any question.  IMHO, he 
voiced the opinion that filters necessarily involve streaming sequences 
of data.  I think filters are a bit more general.  In image processing, 
people use filters without the concept of a sequential stream.  You make 
a output pixel by operating on a set of input pixels. I don't see any 
stream or natural ordering being necessary on the input side.

   Consider the FILTFILT function in matlab.  You put M points in and 
you get M points out.  They use a trick so that the causal and 
anti-causal passes cancel out the startup and ending transients.  Is 
FILTFILT a filter?, after all since filtering is convolution and the 
convolution of an IIR filter with a finite sequence is necessarily an 
infinite sequence, it cannot be, or do we note that we don't really care 
about the zeros appended the to the front and back of the sequence that 
don't matter.