discrete log-based FFT

[DGoncz@replikon.net]

The FFT (Fast Fourier Transform) is ubiquitous in PC music player
software and provides a power spectrum display. Such displays are
linear in frequency on the independent axis, and provide an
excessively spread-out "picture" of what is happening in the rhythm
section (bass and drums), while compressing what's going on at the
high end. It's all wrong, if you ask me.

I have R. D. Stuart's "An Introduction to Fourier Analysis" to refer
to.

Is there a fast tranform that will produce output that is logarithmic
in octaves, which is, after all, the way we hear music?

Doug Goncz
Replikon Research
Seven Corners, VA 22044-0394

[Ian Parker]

On 28 Jan, 08:17, DGo...@replikon.net wrote:
>
> I have R. D. Stuart's "An Introduction to Fourier Analysis" to refer
> to.
>
> Is there a fast tranform that will produce output that is logarithmic
> in octaves, which is, after all, the way we hear music?
>
I don't think so.This is due to the nature of the FFT. The FFT is
based on the roots of unity. And it is the roots of unity which allow
us to have an Nlog(2)N algorithm

http://en.wikipedia.org/wiki/Fast_Fourier_transform
http://en.wikipedia.org/wiki/Butterfly_diagram

The key passage in Wikipaedia is

More specifically, a decimation-in-time FFT algorithm on n = 2p inputs
with respect to a primitive n-th root of unity relies on O(nlogn)
butterflies of the form:

y0 = x0 + x1ω^k
y1 = x0 - x1ω^k

w=exp(2P1*i/n)

where k is an integer depending on the part of the transform being
computed. Whereas the corresponding inverse transform can
mathematically be performed by replacing ω with ω ^- 1 (and possibly
multiplying by an overall scale factor, depending on the normalization
convention), one may also directly invert the butterflies:

x(0) = 0.5(y(0) + y(1))
x(1) = 0.5w^-k(y(0) - y(1))
,
corresponding to a decimation-in-frequency FFT algorithm.

There is no way this can be put into octaves or indeed anything except
strict linear time.

What you can do is take a spline of the power spectrum and construct a
log scale. You can only do this though after it has got the linear
results.


- Ian Parker
ianparker2@gmail.com

[Oh No]

Thus spake DGoncz@replikon.net
>The FFT (Fast Fourier Transform) is ubiquitous in PC music player
>software and provides a power spectrum display. Such displays are
>linear in frequency on the independent axis, and provide an
>excessively spread-out "picture" of what is happening in the rhythm
>section (bass and drums), while compressing what's going on at the
>high end. It's all wrong, if you ask me.
>
>I have R. D. Stuart's "An Introduction to Fourier Analysis" to refer
>to.
>
>Is there a fast tranform that will produce output that is logarithmic
>in octaves, which is, after all, the way we hear music?
>

I was just trying to cast my mind back and think about how I used to do
this, quite a few years ago now, and about what is generally displayed.
Actually I think you have it the wrong way round. The displays are on an
octave (log) scale. The FFT has very little resolution for low pitches,
and huge resolution at high pitch, as compared to what we hear. If it
were displayed on a linear scale, you would get an extremely compressed
image of the bass section, and an extremely spread out picture of
transients and in the high end.

Regards

--
Charles Francis
moderator sci.physics.foundations.
charles (dot) e (dot) h (dot) francis (at) googlemail.com (remove spaces and
braces)

http://www.teleconnection.info/rqg/MainIndex

[Oh No]

Thus spake DGoncz@replikon.net
>The FFT (Fast Fourier Transform) is ubiquitous in PC music player
>software and provides a power spectrum display. Such displays are
>linear in frequency on the independent axis, and provide an
>excessively spread-out "picture" of what is happening in the rhythm
>section (bass and drums), while compressing what's going on at the
>high end. It's all wrong, if you ask me.
>
>I have R. D. Stuart's "An Introduction to Fourier Analysis" to refer
>to.
>
>Is there a fast tranform that will produce output that is logarithmic
>in octaves, which is, after all, the way we hear music?
>
Not as such, but it is not difficult to display the result of an FFT on
a log (octave) scale.

Regards

--
Charles Francis
moderator sci.physics.foundations.
charles (dot) e (dot) h (dot) francis (at) googlemail.com (remove spaces and
braces)

http://www.teleconnection.info/rqg/MainIndex

[Arnold Neumaier]

Ian Parker schrieb:
> On 28 Jan, 08:17, DGo...@replikon.net wrote:
>> I have R. D. Stuart's "An Introduction to Fourier Analysis" to refer
>> to.
>>
>> Is there a fast tranform that will produce output that is logarithmic
>> in octaves, which is, after all, the way we hear music?

You might want to look at wavelet transforms.
http://en.wikipedia.org/wiki/Wavelet_transform#Wavelet_transform
They do something different than Fourier transforms, but work by octaves.

Arnold Neumaier

[Ian Parker]

On 29 Jan, 21:59, Arnold Neumaier <Arnold.Neuma...@univie.ac.at>
wrote:
> Ian Parker schrieb:
>
> > On 28 Jan, 08:17, DGo...@replikon.net wrote:
> >> I have R. D. Stuart's "An Introduction to Fourier Analysis" to refer
> >> to.
>
> >> Is there a fast tranform that will produce output that is logarithmic
> >> in octaves, which is, after all, the way we hear music?
>
> You might want to look at wavelet transforms.
> http://en.wikipedia.org/wiki/Wavelet_transform#Wavelet_transform
> They do something different than Fourier transforms, but work by octaves.
>
I am not sure that that helps you. The reasons are the following :-

You STILL need your maximum sampling rate which will probably be around
20kHz for high quality. This means that at you highest frequency you
will need to integrate with an N*M algorithm where M is the length of
your wavelet.

Either that OR you construct wavelets in the Fourier domain. A Fourier
Transform is essentially a convolution. In the FD therefore you obtain a
wavelet by term by term multiplication and then taking the Inverse
Transform of the result.

- Ian Parker

[p.kinsler@ic.ac.uk]

DGoncz@replikon.net wrote:
> Is there a fast tranform that will produce output that is logarithmic
> in octaves, which is, after all, the way we hear music?

Discrete FT's use kernel functions which are sin/cos or
the complex exponential; with frequencies that are multiples
of some spacing frequency omega.

All you need, therefore, is a new set of kernel functions
with a nonlinear frequency spacing matched to your wishes.

I make no claims as to how easy or hard this might be, as I
really have no idea. Although I might speculated that perhaps
some sort of wavelet basis might be adapted to get you
(more or less) what you want?


--
---------------------------------+---------------------------------
Dr. Paul Kinsler
Blackett Laboratory (PHOT) (ph) +44-20-759-47734 (fax) 47714
Imperial College London, Dr.Paul.Kinsler@physics.org
SW7 2AZ, United Kingdom. http://www.qols.ph.ic.ac.uk/~kinsle/

[robert bristow-johnson]

On Feb 3, 1:27*pm, p.kins...@ic.ac.uk wrote:
> DGo...@replikon.net wrote:
> > Is there a fast tranform that will produce output that is logarithmic
> > in octaves, which is, after all, the way we hear music?
>
> Discrete FT's use kernel functions which are sin/cos or
> the complex exponential; with frequencies that are multiples
> of some spacing frequency omega.
>
> All you need, therefore, is a new set of kernel functions
> with a nonlinear frequency spacing matched to your wishes. *

but it won't be the FFT (as depicted by Gauss, Cooley, or Tukey).

>
> I make no claims as to how easy or hard this might be, ...

here's a paper:

Brown, J.C., (1991). ``Calculation of a Constant Q Spectral
Transform", J. Acoust. Soc. Am. 89, 425-434.

i *have* seen FFT algorithms with "pruning of the tree" so that fewer
high-frequency bins in the last FFT pass are computed than the low
frequency components. it's like in the top octave, they kick out 7
out of 8 bins (and don't bother to calculate them), the next to top
octave they kick out 3 out of 4, the octave below that 1 out of 2, and
below that they keep all of the bins (and interpolate if they want to
display it on a log-frequency scale).

BTW, IMO the best newsgroup to plop this topic on is comp.dsp. in
fact, if you Google "log FFT" with or without quotes, you'll get some
hits in comp.dsp. (Not to imply that the physikers here don't know
about the FFT, just that the FFT really is a topic well contained and
discussed in the discipline of DSP.)

r b-j