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 2^{2} 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 2^{L}.
- 6.40 Definition If the period of the output sequence (for any initial state) of a non-singular FSR of length L is 2^{L}, 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 2^{L} + к — 1. Then each sequence of length к appears exactly 2^{L}~^{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 R_{2} 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 R_{2} 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.