View source for Shift register sequence

''recursive sequence, recurrent sequence''

A sequence which can be obtained as the output of a linear feedback shift register. The term  "shift register sequence"  stems from the engineering literature; in mathematics, the terms [[Recursive sequence|recursive sequence]] or recurrent sequence are more common. The classical reference on shift register sequences is [[#References|[a1]]]; see also [[#References|[a2]]] or [[#References|[a3]]] for expositions.

A linear feedback shift register of length $n$ (LFSR) is a time-dependent device (running on a clock) of $n$ cells each capable of holding a value from some [[Field|field]] $F$, such that with each clock cycle the contents of the cells are shifted cyclically by one position (to the right, say). While the LFSR discards (or outputs) the rightmost entry $b_0$ (and replaces it by $b_1$), it computes the linear function

\begin{equation}c_1b_{n-1}+...+c_nb_0\end{equation}

of the present state vector $(b_0,...,b_{n-1})$ and the feedback coefficients $(c_1,...,c_n)$, see Fig.a1. Thus, the box with the entry  "ADD"  stands for an adder over $F$, and the circle with entry $c_i$ indicates multiplication by $c_i\in F$. (The question of how this might be realized in hardware is not addressed here; see [[#References|[a5]]], [[#References|[a6]]].) In practice, the case of the binary field $\text{GF}(2)$ is by far the most important one, but the general notion of an LFSR serves as a good intuitive way of modelling recursive sequences.

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/s130270a.gif" />

Figure: s130270a

A linear feedback shift register

Given the initial conditions $(a_0,..,a_{n-1})$, after $t$ clock cycles the LFSR will hold the state vector $\mathbf{a}^{\langle t+1\rangle}=(a_t,..,a_{t+n-1})$, where

\begin{equation}a_{t+n-1}=c_1a_{t+n-2}+...+c_na_{t-1}\end{equation}

Thus, the shift register sequence $\mathbf{a}=(a_k)$ produced by the LFSR will satisfy a linear recurrence relation of order $n$; namely, for $k\geq n$:

\begin{equation}a_k=\sum^n_{i=1}c_ia_{k-i}\end{equation}

With the convention $c_0=-1$, one defines the feedback polynomial of the LFSR as

\begin{equation}f(x)=-c_0-...-c_nx^n\end{equation}

its reciprocal polynomial

\begin{equation}f^*(x)=x^n-c_1x^{n-1}-...-c_{n-1}x-c_n\end{equation}

is called the characteristic polynomial of the LFSR. Using its companion matrix

\begin{equation}
A=\left(\begin{array}{cccccc}
0 & 0 & \square & \square & 0 & c_{n} \\
1 & 0 & \square & \square & 0 & c_{n-1} \\
0 & 1 & \ddots & \square & \vdots & \vdots \\
\vdots & 0 & \ddots & \ddots & \vdots & \vdots \\
\vdots & \vdots & \square & \ddots & 0 & c_{2} \\
0 & 0 & \square & \square & 1 & c_{1}
\end{array}\right),
\end{equation}

the recursion (a2) can be rewritten in terms of the state vectors as

\begin{equation}\mathbb{a}^{\langle t+1\rangle}=\mathbb{a}^{\langle t\rangle}A\;\text{for}\;t\geq 0\end{equation}

$A$ is usually called the feedback matrix of the LFSR, and it satisfies the equation $m_A=\chi_A=f^*$, where $\chi_A$ and $m_A$ denote the characteristic and the minimal polynomial of $A$, respectively.

One may characterize the shift register sequences over $F$ by associating an arbitrary sequence $\mathbb{a}=(a_k)$ over $F$ with the [[Formal power series|formal power series]]

\begin{equation}a(x)=\sum^{\infty}_{k=0}a_kx^k\in F[[x]]\end{equation}

Then $\mathbb{a}$ is a shift register sequence if and only if $a(x)$ belongs to the field $F(x)$ of rational functions over $F$. More precisely, $\mathbb{a}$ can be obtained from the LFSR of length $n$ with feedback polynomial $f\in F[x]$ if and only if

\begin{equation}a(x)=\frac{g(x)}{f(x)}\end{equation}

for a suitable polynomial $g\in F[x]$ with $\deg g<n$, and this correspondence between shift register sequences $\mathbf{a}$ belonging to $f$ and polynomials $g$ is a bijection. For instance, the Fibonacci sequence, defined by the recursion $a_k=a_{k-1}+a_{k+2}$ with initial conditions $(a_0,a_1)=(1,1)$ over the rational numbers, belongs to the feedback polynomial $f(x)=1-x-x^2$, and the polynomial $g(x)$ is simply g(x)=1. Thus, the formal power series describing $\mathbf{a}$ is

\begin{equation}a(x)=\frac{1}{1-x-x^2}=1+x+2x^2+3x^3+5x^4+8x^5+13x^6+21x^7+34x^8+...\end{equation}

(cf. [[Fibonacci numbers|Fibonacci numbers]]).

There exists a uniquely determined polynomial $m$ such that a given shift register sequence $\mathbf{a}$ can be obtained from the LFSR with characteristic polynomial $f^*$ if and only if $f^*$ is a multiple of $m$; this polynomial is called the minimal polynomial of the shift register sequence $\mathbf{a}$. In other words, $m$ is the characteristic polynomial of the linear recurrence relation of least order that is satisfied by $\mathbf{a}$. If $\mathbf{a}=(a_k)$ belongs to an LFSR of length $n$ with characteristic polynomial $f^*$, then $f^*$ is actually the minimal polynomial of $\mathbf{a}$ if and only if the first $n$ state vectors $a^{\langle 0\rangle},...,a^{\langle n-1\rangle}$ are linearly independent.

Let $\mathbf{a}=(a_k)$ be a shift register sequence over a [[Galois field|Galois field]] $F=\text{GF}(q)$ with minimal polynomial $m$ of degree $n$. Then $\mathbf{a}$ is ultimately periodic with least period $r_0\leq q^n-1$ (cf. [[Ultimately periodic sequence|Ultimately periodic sequence]]). Conversely, any ultimately periodic sequence over a Galois field is in fact a shift register sequence.

If $\mathbf{a}=(a_k)$ belongs to the LFSR with feedback polynomial (a3), where $c_n\neq 0$, then $\mathbf{a}$ is actually periodic and the feedback matrix $A$ is invertible. The particular shift register sequence $\mathbf{d}$ determined by the initial conditions $(0,...,0,1)$ is called the impulse-response sequence for the given LFSR. This name is motivated by thinking of the LFSR of Fig.a1 as being started by sending the  "impulse"  $1$ through the left-most cell, where initially each cell is  "empty" . The sequence $\mathbf{d}$ is periodic with least period $r_0$ equal to the order of $A$ (that is, $r_0$ equals the least positive integer $e$ such that $A^e=1$). Moreover, the least period of any shift register sequence $\mathbf{a}$ which can be obtained from the given LFSR divides $r_0$. In particular, $r_0=q^n-1$ if and only if $f$ is a primitive polynomial for $F$ (cf. [[Galois field structure|Galois field structure]]). Hence, there exists a periodic shift register sequence with least period $q^n-1$ belonging to an LFSR of length $n$ over $F=\text{GF}(q)$. Any such sequence is called a maximal period sequence (for short, an $m$-sequence) or a pseudo-noise sequence (for short, a PN-sequence). The latter name stems from the fact that these sequences can be used as pseudo-random sequences for certain engineering applications; indeed, they satisfy the axioms formulated by S.W. Golomb [[#References|[a1]]], cf. also [[#References|[a2]]] and [[Pseudo-random numbers|Pseudo-random numbers]]. The impulse response sequences belonging to LFSRs with primitive feedback polynomials are essentially (up to cyclical equivalence) the only $m$-sequences.

In the special case of an irreducible feedback polynomial $f$ over $F=\text{GF}(q)$ there is an easy explicit description of the associated shift register sequences in terms of the trace function, cf. [[Galois field structure|Galois field structure]]. For this, let $n$ be a root of $f^*$ in the extension field $E=\text{GF}(q^n)$. Then the shift register sequences belonging to the given LFSR are precisely the sequences $\mathbf{s}=(s_k)$ of the form

\begin{equation}s_k=\text{Tr}_{E/F}(\theta\;\alpha^k),k\geq 0\end{equation}

where $\theta$ is an arbitrary element of $E$; moreover, the element $\theta$ is uniquely determined by the sequence $\mathbf{s}$. Except for the trivial sequence $\mathbf{0}$ belonging to $\theta=0$, the sequences $\mathbf{s}$ are periodic with least period $r_0$ equal to the order of $\alpha$ (that is, the least positive integer $e$ such that $\alpha^e=1$) and split into $(q^n-1)/r_0$ equivalence classes of $r_0$ sequences each.

While shift register sequences per se are too weak for use in [[Cryptography|cryptography]], suitable (non-linear) combinations of such sequences have been studied in this context, see, e.g., [[#References|[a4]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.W. Golomb,   "Shift register sequences" , Aegean Park Press  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Jungnickel,   "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim  (1993)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R. Lidl,   H. Niederreiter,   "Introduction to finite fields and their applications" , Cambridge Univ. Press  (1994)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Rueppel,   "Analysis and design of stream ciphers" , Springer  (1986)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  U. Tietze,   C. Schenk,   "Electronic circuits: Design and applications" , Springer  (1991)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  N. Weste,   K. Eshraghian,   "Principles of CMOS VLSI design" , Addison-Wesley  (1985)</TD></TR></table>