DFT and bandpass filters

Andor wrote:

   ...

> The simplest thing would be to take a large FFT (say 4N or 8N, where N
> is the number of points of the logarithmic spectrogram) and interpolate
> in the low frequency band and average in the high frequency bands.

Are you sure about average? I'm under the impression that total energy 
in the band, rather than energy density, is usually displayed.

   ...

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

In summary, here are the methods of filtering:

1. FIR in the time domain (advantage: easy to implement)
2. FIR in the freq domain (advantage: faster computation than FIR in
time domain)
3. IIR in the time domain (advantage: much faster computation than FIR
in time/freq domain)

For information on IIR filters, see the Robert Bristow-Johnson's post.

The advantage of an FIR filter is that the coefficients are easy to
generate using available software, they are linear-phase (consistent
time delay across all frequencies), and can be very high-performance in
terms of frequency rejection.

Convolution is the method used for applying an FIR filter in the time
domain. There's a good explanation of FIR filters at the below link,
with a link to example code in "Part 4: Implementation." You can see
from this that FIR filters are easy to implement in the time domain.

http://www.dspguru.com/info/faqs/firfaq.htm

FIR filters can also be applied in the frequency domain, using "FFT
Convolution." This is essentially what you are doing now, by zeroing
out the bins you're not interested in. However, there are other steps
you need to take in order to make this work properly. If you want to
implement a filter in the frequency domain, you need 2 more pieces:

1. FIR coefficients (which you will FFT to the frequency domain).
2. Overlap-Add or Overlap-Save method.

Here's a good description of step 2, with step-by-step instructions for
how to implement it:
http://www.eptools.com/tn/T0001/PT15.HTM

Both methods (time domain and frequency domain FIR filtering) require
FIR filter coefficients. There are multiple ways of generating these,
one of which is the Windowed Sinc method. Google for Scilab and try its
wfir() function to generate your bandpass FIR filter coefficients.

Regards,
Bob

BobM wrote:

... a very nice summary of filtering. However, Michel ought to do

a single largish FFT with a window to reduce artifacts,

conversion to amplitude with phase ignored,

and combining bins into log-scale bands.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

> If course you can do that. The output of the overall DFT consists of
> many bins, each the same range of frequencies, covering (say) the audio
> band. First, convert Re and Im to amplitude. (I don't think you need the
> phase: right? Amplitude squared is easier, and just as good for
> converting to dB.) Sum the amplitudes of all the bins that lie in the
> range of one display bar. Going by octaves for example, 15 to 30 Hz,
> 30-60, 60-120, 120-240, 240-480, 480-960, 960-1920, 1920-3840, ....
> Those sums are your logarithmically-spaced spectral energies. There may
> be a better way than mine -- I haven't thought about it much or looked
> to see what's usually done, but my way gets the same results as yours
> with much less processing, hence less latency.
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.
> =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF

i think my idea was kinda different. it consists of :

-performing a FFT
-calculate every frequency needed, provided a lower frequency, a upper
frequency and the number of bands to do (i guess i'll mostly use values
between 500 and 1000), according to the log base 2 thing so i have a
lways the same number of bands for an octave (thus if you choose 640
bands for 10 octaves, you'll have 64 bands/octave)
-do a band pass for each band
-do a IFFT for each band
-calculate each bands envelope (i heard of a function to do that, but
right now its not my main concern)
-output each band as a line in a .bmp file (already got a function that
writes grey .bmp files)

the problem with that, is that i'll get quite smooth results, given the
relative narrowness of the bands, mostly for the lowest frequencies. i
was considering a trick, but i dont know whether it would give bogus
results or not. the idea is this, in order to obtain a sharper
enveloppe for a given band, it would be to calculate the envelope of
the original wave, then calculate the enveloppe of the bandstopped wave
(i mean that instead of doing a bandpass for the band i want to obtain
the envelope, i would rather do a bandstop to exclude the chosen range
of frequencies), and then substract the second enveloppe to the second
to obtain a envelope of the band.

is it a stupid idea, i mean, would it give a totally bogus result that
doesnt match to reality or is it something i should try to do?

by the way, i was thinking, when you do the DFT of lets say 256 samples
in the time domain, you can't detect some frequencies that are under a
certain limit, right? because i heard about i trick which consists on
taking for example 256 samples in the time domain, and add a huge
number of zero's after those 256 samples so you're FFT has much more
points. thats quite seducing but it made me think it probably prevents
you from detecting low frequencies, right?

> However, there are other steps
> you need to take in order to make this work properly. If you want to
> implement a filter in the frequency domain, you need 2 more pieces:
>
> 1. FIR coefficients (which you will FFT to the frequency domain).
> 2. Overlap-Add or Overlap-Save method.

that's one more thing i dont understand, why do i need FIR coefficients
and overlap-add or overlap-save to do a bandpass filter? i think jerry
avins is right all i need is a window.

by the way, i spent much time today and yesterday looking on google for
a description of overlap-add or overlap-save methods, but i still didnt
manage to understand what it does. it seems to be something like
windows that overlap... kinda... but i surely got it wrong.

anyways, i think windows that overlap is all i need to stop having
those artifacts right? byt he way, before i even start coding it, can
anyone tell me if the way i want to do the window thing is correct?
basically i want to multiply the first 8 samples (not sure i want 8
tho, someone suggested a half-dozen, anyone got a better value?) by the
first half of a sine-like wav (i mean values that go from the middle of
the "valley" (set to 0.0) up to the middle of the "peak" (set to 1.0))
and do the symmetrical thing for the last samples. with it im hopin to
get rid of the artifacts and obtain an accurate result

>Are you sure about average? I'm under the impression that total energy
>in the band, rather than energy density, is usually displayed.

Imagine taking the FFT of an impulse. Display the magnitude of all
bins: a straight line across the full frequency range, if you connect
the magnitude of each bin. If you want logarithmic spacing, my
algorithm still gives a straight line (interpolation of the magnitude
response in the low frequency bands, averaging in the high bands). If
you sum the energy, the high frequency display bars show an incorrect
increase in energy.

Regards,
Andor

Andor wrote:
>>Are you sure about average? I'm under the impression that total energy
>>in the band, rather than energy density, is usually displayed.
> 
> 
> Imagine taking the FFT of an impulse. Display the magnitude of all
> bins: a straight line across the full frequency range, if you connect
> the magnitude of each bin. If you want logarithmic spacing, my
> algorithm still gives a straight line (interpolation of the magnitude
> response in the low frequency bands, averaging in the high bands). If
> you sum the energy, the high frequency display bars show an incorrect
> increase in energy.

I'm aware of that. Since the energy content of music -- the usual input 
to these displays -- decreases with frequency, the input is often 
differentiated to create a more pleasing display. Summing rather than 
averaging accomplishes that by omitting a step instead of adding one. 
When you listen to an impulse, where does it _sound_ like the energy is 
concentrated?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

> Since the energy content of music -- the usual input
> to these displays -- decreases with frequency, the input is often
> differentiated to create a more pleasing display.

Interesting - this is the first time I hear of that. I'm not sure I
would be very pleased with a spectrum anlayzer with such behaviour,
though. I know that sometimes A-weighting is applied to accomodate
psychoacoustic effects, which is about equal to a differntiator
followed by a two-point average (raised cosine). Did you mean that?

> When you listen to an impulse, where does it _sound_ like the energy is
> concentrated?

Hard to say ... everywhere?

;-)

Regards,
Andor

Michel Rouzic wrote:
> that's one more thing i dont understand, why do i need FIR coefficients
> and overlap-add or overlap-save to do a bandpass filter? i think jerry
> avins is right all i need is a window.

I think Jerry means that if you only want to make a spectrogram display
from the frequency domain bin amplitudes, then you only need to do the
following:

1. Window the time domain data
2. FFT the windowed data
3. Group the bins into logarithmically spaced groups
4. Plot your amplitudes based on the grouped bins
5. Repeat for the next block of data

However, if you want to do a _bandpass_ filter, with the intention of
returning the data to the time domain, my understanding is that you
will also need FIR coefficients which you will multiply the data by in
the frequency domain. In addition, you will need to use Overlap-Add or
Overlap-Save to avoid time-domain wrap-around effects from doing this
multiplication in the frequency domain. Again, this is only if you
intend on returning the data to the time domain as (bandpass) filtered
data.

> by the way, i spent much time today and yesterday looking on google for
> a description of overlap-add or overlap-save methods, but i still didnt
> manage to understand what it does. it seems to be something like
> windows that overlap... kinda... but i surely got it wrong.

The second link I gave you in the previous post has a good explanation
of what Overlap-Save is, and how to implement it. Overlap-Add and
Overlap-Save are the methods used for FFT convolution. If you don't use
one of these methods and you try to filter in the frequency domain and
return to the time domain, you will get wrap-around effects in the time
domain.

> anyways, i think windows that overlap is all i need to stop having
> those artifacts right? byt he way, before i even start coding it, can
> anyone tell me if the way i want to do the window thing is correct?

Using a time-domain window will reduce artifacts in the frequency
domain. Assuming you want to display blocks of data at a time, you need
to multiply the entire block of data by the window in the time domain,
before applying the FFT. Common ones are Hamming, Hanning, Blackman,
etc. Try Scilab's window() function. It will generate the most common
window types.

I'm not clear as to what artifacts you're referring to, but judging
from past posts it looks to me as though you intend on returning the
data to the time domain as bandpass filtered data. In this case, you
will need to consider an FIR or IIR filter. However, if you only need a
spectrogram view, then Jerry's suggestion of windowing the data, taking
a large FFT, and grouping the bins together would be more efficient.

Bob

"Jerry Avins" <jya@ieee.org> wrote in message
news:QvCdnZrxSaCawDnfRVn-3Q@rcn.net...
> Andor wrote:
> >>Are you sure about average? I'm under the impression that total energy
> >>in the band, rather than energy density, is usually displayed.
> >
> >
> > Imagine taking the FFT of an impulse. Display the magnitude of all
> > bins: a straight line across the full frequency range, if you connect
> > the magnitude of each bin. If you want logarithmic spacing, my
> > algorithm still gives a straight line (interpolation of the magnitude
> > response in the low frequency bands, averaging in the high bands). If
> > you sum the energy, the high frequency display bars show an incorrect
> > increase in energy.
>
> I'm aware of that. Since the energy content of music -- the usual input
> to these displays -- decreases with frequency, the input is often
> differentiated to create a more pleasing display. Summing rather than
> averaging accomplishes that by omitting a step instead of adding one.
> When you listen to an impulse, where does it _sound_ like the energy is
> concentrated?

I've never heard a true Dirac impulse!  :-)  But I've heard plenty of one-sample
digital pulses, which is the z-domain equivalent.  It sounds like a very sharp
click, i.e. lots of high frequency energy.