Generating de Bruijn sequence over Galois fields using primitive polynomial

Question

This question is related to Greg Slodkowicz's question and the discussion about this paper.

We define a de Bruijn sequence of order $k$ over the set of $l$ distinct symbols as a cyclic sequence of length $l^k$, containing all possible letters sub-sequences of length $k$ exactly once. In the mentioned paper, they say that for any arbitrary Galois field - $GF(p^n)$, for $p$ a prime number and $n$ an integer, a de Bruijn sequence of order $k$ over all elements can be generated by the following recursion:

\begin{equation} s_i=\theta_{k-1}s_{i-1} + \dots + \theta_0s_{i-k}, \end{equation}

with arithmetic performed over $GF(p^n)$ and $\theta_i\in GF(p^n)$ so the polynomial $\sum_{i=0}^{k-1}\theta_i x^i$ is primitive. In Greg Slodkowicz's question, it was mentioned that the considered polynomial seems to be actually $x^k - \sum_{i=0}^{k-1}\theta_i x^i$. I find it hard to get the right primitive polynomial by which in the paper they illustrated the construction of the de Bruijn sequence over $GF(4)$ with what seems to be $k=2$ in Figure 3a. If we have $GF(4)=\{0,1,2,3\}$ with the known addition and multiplication:

addition and multiplication tables,

how does one get, using primitive polynomial and the suggested recursion equation, the generated sequence in the paper in Figure 3a? i.e.,

\begin{equation} 011210331302232, \end{equation}

so, with the addition of a single $0$ to the beginning, we get the de Bruijn sequence over $GF(4)$ with k=2.

Answer 1

Looking at the de Bruijn sequences with alphabet $GF(4)$ and over $GF(16)$ only, as that seems to be your main interest.

I rather think of $GF(4)$ as $$GF(4)=\{0,1,\beta,\beta+1\}.$$ If only to match with my notation in this old answer. Commonly $\alpha$ is used in place of $\beta$, but in that answer I wanted to avoid symbol overload. Does not matter, because we can rename the elements if we so desire.

Here $\beta$ satisfies the equation $\beta^2=\beta+1$ which together with $1+1=0$ determines the arithmetic completely. In your notation my $\beta$ can be either $2$ or $3$ and $\beta+1$ is the other. Makes no difference which way you define, because there is an isomorphism of the field $GF(4)$ interchanging $\beta$ and $\beta+1$.

In the linked answer I show that both $m_1(x)=x^2+x+\beta$ and $m_2(x)=x^2+x+\beta+1$ are primitive polynomials. These are the minimal polynomials of the zeros of $x^4+x+1$ over $GF(4)$. The other primitive polynomials are the reciprocals (scaled to be monic) $$ m_2(x)=\beta x^2m_2(1/x)=x^2+\beta x+\beta $$ and $$ m_4(x)=\beta^2 x^2m_1(1/x)=x^2+\beta^2x+\beta. $$ The latter two are the minimal polynomials of the zeros of $x^4+x^3+1$, the reciprocal of $x^4+x+1$.

This leaves you with four possible recurrency relations $$ \begin{aligned} s_i&=s_{i-1}+\beta s_{i-2},\\ s_i&=s_{i-1}+\beta^2s_{i-2},\\ s_i&=\beta s_{i-1}+\beta s_{i-2},\\ s_i&=\beta^2s_{i-1}+\beta^2s_{i-2}. \end{aligned} $$ Your sequence begins $0,1,1$ which rules out the latter two. The first recurrence relation leads to the cycle (starting from $0,1$) $$ 0,1,1,\beta^2,1,0,\beta,\beta,1,\beta,0,\beta^2,\beta^2,\beta,\beta^2,(0,1,1,\ldots), $$ which seems to match with what you want under the labelling $\beta=3$, $\beta^2=2$. Anyway, we can easily check that the resulting sequence has the de Bruijn -property: every ordered pair of elements (other than $0,0$) appears exactly once in the cycle as consecutive entries.