Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$
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?
