[music-dsp] Zero padded FFT's vs Discrete Cosine/Sine Transform

[robert bristow-johnson]

on 11/15/2004 19:48, Koen Vos at kvos at qualcomm.com wrote:

> With some work you could indeed replace the IFFT by an IDCT operating on
> only the positive frequencies. But that probably won't gain you much, as
> this IDCT is often implemented with the same IFFT you just eliminated :)
> 
> Are you applying a window (eg Hanning) to your data before the FFT? That
> would complicate the reuse of results from previous overlapping windows.
> 
> Other things you could look into:
> 
> 1. No need to zero pad the data al the way to twice the length. You only
> need as many zeros as the order of the autocorrelation you're after (10th
> order ac -> 10 zeros). Padding more zeros won't change your final result.

when we square and abs in one domain (in this case, the discrete frequency
domain), we are multiplying two spectrums together, X[k] and conj(X[k]).
multiplying in one domain means convoluting in the other and with the DFT
(or FFT) that means circular convolution.  if we don't zero pad to twice the
length, is there not a danger of aliasing?  maybe it's not a problem for
autocorrelation, but it's not immediately obvious to me why not.

> 2. Both your FFT and IFFT operate on real data (I presume). FFTs exist that
> are optimized for real data. Alternatively, you can use a single FFT to
> compute two spectra, by placing the two data vectors in the real and
> imaginary parts of the FFT input. Afterwards you'll need to "unscramble"
> the result, using properties of (anti-)symmetry of the spectra of real and
> imaginary data. Similar for the IFFT.

that's a good old trick.  useful for fast convolution.

better use a good floating-point FFT.  don't do this with small word-size
because one data vector will contaminate the other, due to quantization.

> Or use a single FFT to compute the
> Fourier transform of the current window and the inverse Fourier transform
> of the previous window.

that's a trick i never thought of.  instead of doing things two buffers at a
time.  it shouldn't be much different in computational burden but should
simplify the code.

> 3. If you need just a few autocorrelation coefficients, compute them
> directly in time.

if it's pitch detection, there are likely some he won't need.  if it's LPC
or similar, he'll need them all.

r b-j

 
> At 04:00 PM 11/15/2004, Philip Mcleod wrote:
>> I am doing alot of autocorrelations, using using the following method
>> - Zero pad data window to twice its length
>> - FFT
>> - Square and abs (or imag part times real part) of the co-efficients
>> - IFFT
>> 
>> Is it possible to use a Discrete Cosine and sine transforms instead
>> of an FFT - without having to zero pad to get the same result. I.e. saving
>> some computation?
>> Is this common practice?
>> I really don't under stand the DCT and DST that well, maybe this dosn't
>> work.
>> Just wondering whether it is worth spending time looking into this.
>> 
>> Also my data windows are overlapping sometimes 50% or 75%.
>> Is it possible to store some partially computed values from previous FFT's
>> or DCT's to speed up the next one which is overlapped?