# What happens to signal, if we offset periodic auto-correlation?

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?

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

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.

• 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. Aug 21 '13 at 18:04