# how to prove sequence y uphold golomb's third axiom

given $\{ x_k \}$ is a m-seq of order $n$, we define $\{ y_k \}$ to be a $m$ digits number: $$y_i=x_ix_{i+1}...x_{i+m-1}$$ for every integer $n \ge m \ge 1$

how can I show that $\{ y_k \}$ upholds golomb's third axiom which says that the auto-correlation: $$c_{yy}(\tau)=\left\{\begin{matrix} 2^n-1 & ,\tau=0\\ Const & ,\tau \ne 0 \end{matrix}\right.$$ I'm having troubles understanding how to show that it is the same const for every $\tau$

• You mean $y_i$ is an $m-$bit string? How do you define the autocorrelation in this case? it will be a vector autocorrelation. Feb 2, 2016 at 12:10
• You probably meant to say "for fixed integer $m$ in the range $[1,n]$". Apr 27, 2016 at 3:18

The full $m-$sequence (periodically repeated to avoid modular addition in the subscript} with $$C_{xx}(\tau):=\sum_{k=0}^{2^n-2} (-1)^{x_k+x_{k+\tau}}$$ satisfies $C_{xx}(\tau)=-1+\delta(\tau)(2^n),$ where $\delta$ is the dirac delta function. Now, one might define an $m-$symbol partial correlation function, whose average is proportional to what you want, if the average is taken over all starting points in one period. But this function itself is nearly binomially distributed and not constant over nonzero $\tau,$ for $m\leq n$. To be clear, I am referring to a function of the form $$C_{xx}(i,m,\tau):=\sum_{k=0}^{i+m-1} (-1)^{x_k+x_{k+\tau}}$$ and its average $$\overline{C_{xx}(m,\tau)}=\frac{\sum_{i=0}^{2^n-2}C_{xx}(i,m,\tau)}{2^n-1},$$ which arises in communication applications.
Finally if you just take the $y_k$ to be an integer in $\{0,\ldots,2^m-1\}$ by letting the vector $(x_k,x_{k+1},\ldots,x_{k+m-1})$ be the binary representation of the integer $y_k$, then due to equidistribution of $m-$tuples under the Golomb postulate the correlation function $$C_{yy}(\tau):=\sum_{k=0}^{2^n-2} (-1)^{y_k+y_{k+\tau}}$$ will also be two valued since tuple equidistribution implies equidistribution of $y_k$ modulo 2, and the exponent might as well be reduced modulo 2. So you get the same distribution as that of the correlation $C_{xx}(\tau)$. Was this the point of your original question?