A smaller Sidel'nikov sequence is embedded into a longer one. When and how?

52 Views Asked by At

Cyclotomic classes

Let $p$ be an odd prime and $\alpha$ a primitive element of $\mathbb{F}_{p}$. We can decompose $\mathbb{F}_{p}^{*}$ into $M$ disjoint subsets,

$D_{\ell}=\left\{ \alpha^{Mi+\ell}\mid0\leq i\leq\frac{p-1}{M}-1\right\} ,\:0\leq\ell\leq M-1$

which are called the cyclotomic classes of $\mathbb{F}_{p}$ of order $M$.

Sidel'nikov Sequences

Define another partition $S_{0}=D_{0}-1$, replacing the element $0$ with $-1$, and $S_{\ell}=D_{\ell}-1$, for $\ell\neq0$. Then, the $M$-ary Sidel'nikov sequence $s\left(t\right)$ of period $p-1$ is defined as

$s\left(t\right)=\begin{cases} \ell, & \textrm{if}\:\alpha^{t}\in S_{\ell}\\ 0 & \textrm{if}\:t=\frac{p-1}{2} \end{cases}$

Embedding of sequences

Assuming the case for binary sequences, i.e. $M=2$, let $p_{S}$ and $p_{L}$ be odd primes with $p_{L}>p_{S}$. Consider $\alpha$, $\beta$ to be primitive elements of $\mathbb{F}_{p_{S}}$ and $\mathbb{F}_{p_{L}}$, respectively. For a smaller sequence $g_{\alpha}\left(t\right)$ to be embedded into a longer $f_{\beta}\left(t\right)$ sequence we must have:

$\forall\alpha^{t}\in S_{1}^{\left(p_{S}\right)}\Rightarrow\beta^{t+m}\in S_{1}^{\left(p_{L}\right)}$

as $t$ runs through $0\ldots p_{S}-2$. The exponent $t+m$ is computed modulo $p_{L}-1$ to address the circular nature of the sequences. The fixed integer $m\in\left[0,\ldots,p_{L}-2\right]$ is called positional marking, and defines the time instant where the smaller sequence begins in the longer one.

Example

Consider $\alpha=2$ a primitive element of $\mathbb{F}_{5}$. For $M=2$ a balanced partition of $\mathbb{F}_{5}^{*}$ is given by $S_{0}=\left\{ 0,3\right\} $ and $S_{1}=\left\{ 1,2\right\} $. Running $t$ through $0\ldots3$ the resulting Sidel'nikov binary sequence $g_{2}\left(t\right)$ is 0011. Note that as $t$ increases we read the sequence digits (bits) from right to left. Now let's test the existence of this smaller sequence into a longer one. Consider $\beta=7$ a primitive element of $\mathbb{F}_{13}$. For $M=2$ the resulting Sidel'nikov binary sequence $f_{7}\left(t\right)$ is 010010 0011 11. We see that $m=2$ marks the time instant where the smaller sequence exists in the larger one. If we consider $\beta=6$ then the resulting Sidel'nikov binary sequence $f_{6}\left(t\right)$ is 0110100 0011 1 and in this case $m=1$ is the value of the positional marking.

How could I explain when $g\subset f$? Is there such a morphism?

Context

I'm an electronics engineer working with codes in the context of telecommunications applications. Previous work on the subject can be found here. I've studied Zech logarithms and associated properties [Huber K.] but could not find a proper path of investigation. I've recently come across arXiv paper 1705.05564v3 and wonder if I should look into monoid theory.