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 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

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

is usually called the feedback matrix of the LFSR, and it satisfies the equation , where and denote the characteristic and the minimal polynomial of , respectively.

One may characterize the shift register sequences over by associating an arbitrary sequence over with the formal power series

Then is a shift register sequence if and only if belongs to the field of rational functions over . More precisely, can be obtained from the LFSR of length with feedback polynomial if and only if

(a5)

for a suitable polynomial with , and this correspondence between shift register sequences belonging to and polynomials is a bijection. For instance, the Fibonacci sequence, defined by the recursion with initial conditions over the rational numbers, belongs to the feedback polynomial , and the polynomial is simply . Thus, the formal power series describing is

(cf. Fibonacci numbers).

There exists a uniquely determined polynomial such that a given shift register sequence can be obtained from the LFSR with characteristic polynomial if and only if is a multiple of ; this polynomial is called the minimal polynomial of the shift register sequence . In other words, is the characteristic polynomial of the linear recurrence relation of least order that is satisfied by . If belongs to an LFSR of length with characteristic polynomial , then is actually the minimal polynomial of if and only if the first state vectors are linearly independent.

Let be a shift register sequence over a Galois field with minimal polynomial of degree . Then is ultimately periodic with least period (cf. Ultimately periodic sequence). Conversely, any ultimately periodic sequence over a Galois field is in fact a shift register sequence.

If belongs to the LFSR with feedback polynomial (a3), where , then is actually periodic and the feedback matrix is invertible. The particular shift register sequence determined by the initial conditions 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" through the left-most cell, where initially each cell is "empty" . The sequence is periodic with least period equal to the order of (that is, equals the least positive integer such that ). Moreover, the least period of any shift register sequence which can be obtained from the given LFSR divides . In particular, if and only if is a primitive polynomial for (cf. Galois field structure). Hence, there exists a periodic shift register sequence with least period belonging to an LFSR of length over . Any such sequence is called a maximal period sequence (for short, an -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 -sequences.

In the special case of an irreducible feedback polynomial over 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 be a root of in the extension field . Then the shift register sequences belonging to the given LFSR are precisely the sequences of the form

where is an arbitrary element of ; moreover, the element is uniquely determined by the sequence . Except for the trivial sequence belonging to , the sequences are periodic with least period equal to the order of (that is, the least positive integer such that ) and split into equivalence classes of 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)