 Nonlinear feedback shift registers

This subsection summarizes selected results about nonlinear feedback shift registers. A function with n binary inputs and one binary output is called a Boolean function of n variables; there are 22 different Boolean functions of n variables.

• 6.36 Definition A (general) feedback shift register (FSR) of length L consists of L stages (or delay elements) numbered 0,1,... , L - 1, each capable of storing one bit and having one input and one output, and a clock which controls the movement of data. During each unit of time the following operations are performed:
• (i) the content of stage 0 is output and forms part of the output sequence;
• (ii) the content of stage i is moved to stage i - 1 for each i, 1 < i < L — 1; and
• (iii) the new content of stage L - 1 is the feedback bit Sj = /(sy-_i, .Sj_2,... , Sj_/,), where the feedback function f is a Boolean function and Sj_j is the previous content of stage L - i, 1 < i < L.

If the initial content of stage г is Sj € {0.1}foreach0 < i < L — l, then [sl_i,... , si,so] is called the initial state of the FSR.

Figure 6.7 depicts an FSR. Note that if the feedback function / is a linear function, then the FSR is an LFSR (Definition 6.7). Otherwise, the FSR is called a nonlinear FSR. Figure 6.7: A feedback shift register (FSR) of length L.

6.37 Fact If the initial state of the FSR in Figure 6.7 is [sl-ь • • ■ , si, so], then the output sequence s = so, si, S2, ■ • • is uniquely determined by the following recursion: • 6.38 Definition An FSR is said to be non-singular if and only if every output sequence of the FSR (i.e., for all possible initial states) is periodic.
• 6.39 Fact An FSR with feedback function/(«j_ ь Sj_2,... , sj_l) is non-singular if and only if / is of the form / = Sj-i ф g(sj-i, Sj-2,... , Sj_/,+i) for some Boolean function g.

The period of the output sequence of a non-singular FSR of length L is at most 2L.

• 6.40 Definition If the period of the output sequence (for any initial state) of a non-singular FSR of length L is 2L, then the FSR is called a dc Bruijn FSR, and the output sequence is called a dc Bruijn sequence.
• 6.41 Example (dc Bruijn sequence) Consider the FSR of length 3 with nonlinear feedback function f(xi, .x'2, жз) = 1фх'2Фжз®х1Х2. The following tables show the contents of the 3 stages of the FSR at the end of each unit of time t when the initial state is [0,0,0].
 t Stage 2 Stage 1 Stage 0 0 0 0 0 1 1 0 0 2 1 1 0 3 1 1 1
 t Stage 2 Stage 1 Stage 0 4 0 1 1 5 1 0 1 6 0 1 0 7 0 0 1

The output sequence is the de Bruijn sequence with cycle 0,0,0.1,1.1,0.1. □

Fact 6.42 demonstrates that the output sequence of de Bruijn FSRs have good statistical properties (compare with Fact 6.14(i)).

• 6.42 Fact (statistical properties of de Bruijn sequences) Let s be a de Bruijn sequence that is generated by a de Bruijn FSR of length L. Let k be an integer, 1 < к < L, and let s be any subsequence of s of length 2L + к — 1. Then each sequence of length к appears exactly 2L~k times as a subsequence of s. In other words, the distribution of patterns having fixed length of at most L is uniform.
• 6.43 Note (converting a maximum-length LFSR to a de Bruijn FSR) Let /?, be a maximum-

length LFSR of length L with (linear) feedback function Sj-2,... , Sj-l)- Then

the FSR R2 with feedback function Sj-2,... , Sj-l) = / Ф 2 • • • Sj_l+i

is a de Bruijn FSR. Here, s* denotes the complement of s,. The output sequence of R2 is obtained from that of Ri by simply adding a 0 to the end of each subsequence of L - 1 0’s occurring in the output sequence of Ri.