CLR cover

Additional Problem 16: Primitive Trinomials and Simple PN Sequences

\( \def\LS{\mathsf{LShift}} \)

We consider sequences of binary words of length $n$, each containg at least one nonzero bit. Denote $N=2^k-1$. A sequence of distinct words $w_1,w_2,\ldots,w_N$ is said to be a simple PN sequence (PN means "Pseudo Noise") iff there is a number (parameter) $k$ such that for each $i\lt N$ $$w_i=a_0a_1a_2\cdots a_{n-1}\Rightarrow w_{i+1}=a_1a_2a_3\cdots a_{n-1}a_0', \ \mbox{where}\ a_0'=a_0\ \mbox{xor}\ a_k,$$ In other words PN sequence is a (simply generated) Hamiltonian path in a de Bruijn graph containing all nodes except $0^n$. Sequences of this type are also called maximal LFSR sequences (LFSR stands for "Linear Feedback Shift Register").

Observation. If $w_1,w_2,\ldots,w_N$ is a PN sequence then $(n-1)$-length suffix of $w_i$ is not necessarily a prefix of $w_{i+1}$.

In this exercise we discuss how simple PN sequences can be derived from primitive trinomials over $Z_2$ (the field of bits) of the form $P(x)=x^n+x^k+1$. Such a polynomial is primitive if all polynomials $x^i \ \mbox{modulo}\ P(x)$ are distinct, for $1\le i \le 2^n-1$ (it is maximal number of nonzero binary polynomials of degree smaller than $n$).

A very partial list of primitive trinomials is

$x^3+x+1,\ x^3+x^2+1,\ x^4+x+1,\ x^4+x^3+1,\ x^5+x^2+1,$
$x^6+x+1,\ x^7+x+1,\ x^9 + x^4 + 1,\ x^{10} + x^3 + 1,\ x^{100}+x^{37}+1,\ x^{900}+x+1$

Assume $P(x)=x^n+x^k+1$ is primitive binary polynomial of degree $n$. Construct and prove correctness of a simple PN sequence of $n$-words, using this polynomial.

Each binary polynomial $W(x)=a_0x^{n-1}+a_1x^{n-1}+\cdots +a_{n-1}$ can be represented as $str(W)=a_0a_1\cdots a_{n-1}$. Let $W_i= x^i \ \mbox{modulo}\ P(x))$. The sequence $str(W_1),\, str(W_2),\,..str(W_N), \ \mbox{where}\ N=2^n-1,$ is "almost" a required PN sequence. All these words are distinct and closely related. The problem in is that $(n-1)$-length suffix of $str(W_i)$ is not necessarily a prefix of $str(W_{i+1})$.