Re: Autocorrelation matrix of a long sequence

On 17 Apr, 09:54, itakatz <itak...@xxxxxxxxx> wrote:
4)  Compute the DFT of the zero-padded frame
5)  Compute the periodogram as the squared magnitude
    of the spectrum coefficients
6)  Compute the IDFT of the periodogram

Rune

A little bit off-topic:

Since multiplication in frequency domain is the same as (circular)
convolving in the time domain,

Convolution by DFT is circular, which is why you need
to zero-pad before computing the DFT. The convolution
of two N-length sequences gives as result a sequence
with at most 2N-1 non-zero elements. Zero-padding to
at least 2N-1 total length allocates the space needed
to avoid wrap-around effects. Depending on what
implementation of the FFT you have available, you might
zero-pad further, to the next power of 2.

shouldn't one of the segments be time-
reversed before zero-padding and DFTing?

Time-reversing in time domain is not sufficient to
handle wrap-around effects from circular convolution,
since you don't change the length of the input sequence.

With pen and paper your trick might work, but in the
computer you need to allocate memory and find a map
from the 'true' index space k = -N,...,N to the RAM
address space, BaseAddress + {0,1,...2N}.

Essentially, you need to do some book-keeping to find
out if the rxx[0] coefficient turns out in the index 0
position of the buffer, or in the index N position.

in that way the auto-
correlation is re-written as a convolution, and then it is ok to
compute it in the freq domain. Am I right?

In time domain, reversing the direction of a sequence x[n]
is written as x[-n]. It's a standard excercise in most DSP
books to show that if

x[n] <-> X[k]

is a DFT pair, then

x[-n] <-> X'[k]

where X' is the complex conjugate of X, is also a DFT pair.
Well, this is correct at least when x[n] is real-valued,
it might not be for complex-valued x[n].

Anyway, convolving x[n] by x[-n] in time domain, which
is a common estimator for the autocorrelation function
(save some scaling coefficients), can alternatively be
computed in frequency domain as a product of the DFTs:

Sxx[k] = X[k]X'[k] = |X[k]|^2.

Hence my algorithm works, once the relevant scaling
coefficients have been accounted for.

Rune
.

Relevant Pages

  • Re: Autocorrelation matrix of a long sequence
    ... Convolution by DFT is circular, ... Time-reversing in time domain is not sufficient to ... (save some scaling coefficients), can alternatively be ...
    (comp.dsp)
  • Re: Autocorrelation matrix of a long sequence
    ... to zero-pad before computing the DFT. ... zero-pad further, to the next power of 2. ... handle wrap-around effects from circular convolution, ... (save some scaling coefficients), can alternatively be ...
    (comp.dsp)
  • Re: The inherent periodicity of the Discrete Fourier Transform
    ... interesting with the DFT, ... convolution isn't "periodic", it just says that if you filter N input samples through a length-N filter, it takes, somewhat obviously, 2N-1 steps to push the whole signal through the filter. ... You need the so-called zero-padding not to circumvent "circular convolution" but simply to get plain non-folded convolution done right. ... If convolution in the time domain is indeed equivalent to multiplication in the frequency domain, and there is no such thing as "periodic" or "circular" convolution in the time domain, then there can't be any frequency domain equivalent. ...
    (comp.dsp)
  • Re: DFT Function
    ... all values of the output array are very close to 1.0. ... shape (by connecting close-by points of the DFT) to ... the FT is the sequence of Fourier coefficients). ... David Bernier ...
    (sci.math)
  • Re: real exact pruned DFT?
    ... coefficients are scattered b) I need my solution to be ... rounding) to the DFT. ... First, by "exact algorithm", the original poster certainly means ...
    (comp.dsp)