These two complexities were introduced to measure the stability of the linear complexity function, in analogy to the derivative of functions in Euclidean spaces. Where per( t ∞) = N denotes that t ∞ has period N. The reader may consult for more details on LFSRs. Consequently, the period of an LFSR with n stages always divides 2 n − 1. If the feedback polynomial C ( x ) has degree n and it is irreducible over F 2, with α being a root of C ( x ) in F 2 n, then the period of the LFSR is equal to the order of α in F 2 n. If the feedback polynomial C ( x ) is primitive over F 2, then each of the 2 n − 1 nonzero states of the associated nonsingular LFSR will produce an output of linear complexity n. L satisfies a triangle-like inequality, that is, L ( s ⊕ t ) ≤ L ( s ) + L ( t ), where s ⊕ t is the bitwise xor of s, t. If s is periodic of period T, then L ( s ) ≤ T. L ( s n ) = n if and only if s n = 0, 0, …, 0, 1. L ( s n ) = 0 if and only if s n is the all zero sequence of length n. The linear complexity satisfies the following properties. If s n is a finite binary sequence, then L ( s n ) is the length of the shortest LFSR which has s n as its first n terms. We shall use the concept heavily in Chapter 7. LFSRs can be applied in generating pseudo-random numbers, pseudo-noise sequences, fast digital counters, whitening sequences, cryptography, etc., and they can be implemented in both software and hardware. However, an LFSR with a well-chosen feedback function and seed can produce a sequence of bits which appears random (has good statistical properties) and which has a large period. Since any register has a finite number of possible states, it must eventually be periodic. The initial input of an LFSR is called a seed. The new content (the feedback bit) of the stage m − 1 would be obtained by xor-ing a subset of the content of the m stages. The content of stage i is shifted to stage i − 1, for 1 ≤ i ≤ m − 1 3. S i (the content of stage 0) forms part of the output 2. At time i, the following operations are performed : 1. A vector with entries s 0, …, s m − 1 would initialize the shift register. An LFSR of length m consists of m stages numbered 0, 1, …, m − 1, each capable of storing one bit, and a clock controlling data exchange. A linear feedback shift register (LFSR) is a shift register whose input bit is the output of a linear function of two or more of its previous states (taps).
0 kommentar(er)
