Constructing New NLFSR Functions with Optimal Periods

2. Preliminaries

An FSR contains n binary storage cells, also called stages as illustrated in Figure 1. Each cell is capable of holding a single bit, and each stage i ∈ {0, 1, …, n – 1} is associated with a state variable x_i that shows the current value of the stage. The feedback function f_i : {0, 1}ⁿ → {0, 1} computes the updated value of the cell n – 1 . The state of an FSR can be presented as a vector of values of its state variables (x_0,x₁ … x_{n– 1}). The period of an FSR is defined as the length of longest repeated output sequence can be obtained. The period is called optimal if its length is 2ⁿ – 1. The output sequence can be yielded by extracting the bit one by one. The value of the stage 0 determines the output of an FSR, while the input of an FSR is determined by the value of the stage n – 1. Including the output bit is essential in order to maximize the function period. Therefore, the FSR takes the following form: