1
$\begingroup$

suppose $x_n$ is an $N$-point sequence with periodic auto-correlation $$ c_n=\sum_m x_m x_{(n+m) mod N} $$

How to find $N$-point sequence $y_n$ with periodic auto-correlation $d_n = c_n - A$, where $A$ is a constant?

$\endgroup$
  • $\begingroup$ You mean even if $A$ is valid, is it possible that there is not any $y_n$ leading to $d_n$ ? $\endgroup$ – Mahdi Khosravi Aug 22 '13 at 3:58
3
$\begingroup$

The periodic autocorrelation function is not defined correctly in the OP's question: it should be $$c_n = \sum_m x_m x_{(m+n) \bmod N} ~~\text{or} ~~ \sum_m x_m x_{(m-n) \bmod N}$$ depending on taste and not $c_n = \sum_m x_mx_{(n-m)\bmod N}$ which is a convolution not a correlation operation. Note also that there is an implicit assumption that $\mathbf x = (x_0, x_1, \ldots, x_{N-1})$ is a real-valued sequence, not a complex-valued sequence. Of course, the autocorrelation sequence $\mathbf c = (c_0, c_1, \ldots, c_{N-1})$ is also a real-valued sequence with the additional property that $c_0 \geq \max_n |c_n|$

With this correction, consider the sequence $\mathbf d = (c_0-A, c_1-A, \ldots, c_{N-1}-A)$, that is, $d_n = c_n-A$ for $0 \leq n < N$. Let the DFT of $\mathbf c$ be $\mathbf C = (C_0, C_1, \ldots, C_{N-1})$ where the $C_n = |X_n|^2$ are nonnegative real numbers. Note that the DFT of any autocorrelation sequence cannot have negative values. Now, the DFT of $\mathbf d$ is obviously $\mathbf D = \mathbf C - (NA,0,0,\ldots, 0)$ and so we see easily that

$\mathbf D$ cannot be the DFT of an autocorrelation function if $D_0 = C_0 -NA < 0$, that is, if $A > N^{-1}C_0$.

Note that $\displaystyle X_0 = \sum_{n=0}^{N-1} x_n$ and $\displaystyle C_0 = |X_0|^2 = \left|\sum_{n=0}^{N-1} x_n \right|^2.$ Let $\displaystyle \bar{x} = \frac{1}{N}\sum_{n=0}^{N-1} x_n = \frac{1}{N}X_0$.

So, let us assume from this point on that $A \leq N^{-1}C_0 = N\left|\bar{x}\right|^2$.
Is there a sequence $\mathbf y = (y_0, y_1, \ldots, y_{N-1})$ with autocorrelation function $\mathbf d$ whose DFT is $\mathbf D$?

The answer is Yes, Consider a sequence $\mathbf y$ with $n$-th term $y_n = x_n - a$. Its autocorrelation function is $$\sum_m y_m y_{(m+n)\bmod N} = \sum_m (x_m-a) (x_{(m+n)\bmod N} - a) = c_n + Na^2 - 2aX_0.$$ We want the quantity on the right to have value $c_n-A$, and so if we can find an $a$ such that $A = 2aX_0- Na^2$, we are done. Solving for $a$, we get that $$a = \frac{2X_0\pm \sqrt{ 4\left|X_0\right|^2-4NA}}{2N} = \frac{1}{N}X_0 \pm \sqrt{\left|\bar{x}\right|^2-A/N} = \bar{x} \pm \sqrt{\left|\bar{x}\right|^2-A/N}$$ Note that the quantity in the radical is nonnegative since we have assumed that $\frac AN \leq \left|\bar{x}\right|^2$ and so we do obtain a real-valued $\mathbf y$ as long as $A$ does not exceed its maximum value $N\left|\bar{x}\right|^2$. When $A$ does have its maximum possible value, $\mathbf y$ whose $n$-th term is $y_n = x_n - \bar{x}$ is just $\mathbf x$ "centered" to have "DC value" $0$ since we are subtracting off the average value of $\mathbf x$ from each component.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Thanks. I corrected the question. But the main question which is the way to reconstruct $y_n$ from $c_n-A$ has not received any attention. $\endgroup$ – Mahdi Khosravi Aug 21 '13 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.