Namespaces
Variants
Actions

Shift register sequence

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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 or recurrent sequence are more common. The classical reference on shift register sequences is [a1]; see also [a2] or [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 $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 [a5], [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.

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

\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).

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 $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). 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). 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 [a1], cf. also [a2] and 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. 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, suitable (non-linear) combinations of such sequences have been studied in this context, see, e.g., [a4].

References

[a1] S.W. Golomb, "Shift register sequences" , Aegean Park Press (1982)
[a2] D. Jungnickel, "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim (1993)
[a3] R. Lidl, H. Niederreiter, "Introduction to finite fields and their applications" , Cambridge Univ. Press (1994)
[a4] R. Rueppel, "Analysis and design of stream ciphers" , Springer (1986)
[a5] U. Tietze, C. Schenk, "Electronic circuits: Design and applications" , Springer (1991)
[a6] N. Weste, K. Eshraghian, "Principles of CMOS VLSI design" , Addison-Wesley (1985)
How to Cite This Entry:
Shift register sequence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Shift_register_sequence&oldid=51715
This article was adapted from an original article by Dieter Jungnickel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article