Re: Autocorrelation matrix of a long sequence

On 17 Apr, 23:18, itakatz <itak...@xxxxxxxxx> wrote:
On Apr 17, 1:42 pm, Rune Allnor <all...@xxxxxxxxxxxx> wrote:





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

Thanks.

In the meantime I did the simple math and I indeed got that the DFT of
the time reversed signal is the c.c. of the DFT of the original
signal, up to a linear phase, which accounts for the fact that my time
reversed signal was x[N-n-1] instead of x[-n].

The practical implication would probably be that
you find the rxx[0] element of the autocorrelation
in array element with index N, instead of the element
with index 0.

Not a big deal, but a detail to keep track of.

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
    ... Convolution by DFT is circular, ... Time-reversing in time domain is not sufficient to ... (save some scaling coefficients), can alternatively be ...
    (comp.dsp)
  • Re: The inherent periodicity of the Discrete Fourier Transform
    ... Orwellian - linear convolution good, ... At least what DSP is concerned. ... are no work-arounds associated with the DFT. ... Since one can never store an infinitely long sequence, ...
    (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: DFT or DFS: Are they the same thing?
    ... DFT that shows that when the samples are shifted, ... convolution. ... There is no periodic extension. ... circular convolution fundamentally. ...
    (comp.dsp)