Linear feedback shift register

A linear feedback shift register ( engl. linear feedback shift register, short LFSR) is a feedback shift register which can be used to generate strictly deterministic pseudo random number sequences. For feedback, the linear logical XOR function is being used.

Applications are in addition to the generation of pseudo random number sequences in the area fast digital synchronous counter, as these counters operate without carry, in the field of telecommunications and cryptography at scramblers to make data sequences spectrally white, in coding theory in the encoding and decoding of cyclic codes, such as in the cyclic redundancy check (CRC ) or the Hamming code, and in the digital modulation technique in code division multiple access (CDMA ), and in the field of steganography.

Linear feedback shift registers can be implemented efficiently both in hardware, such as FPGAs, as well as in software. In the software implementation, since most processors work with register widths greater than one bit, typically working with pre-calculated tables that map directly the internal state of the shift register.

• 3.1 Gold sequences
• 3.2 Kasami sequences
• 3.3 JPL consequences

Function

An LFSR is implemented in digital technology than a shift register having n storage elements. The individual memory elements are typical example D flip-flop which can each store a bit. In contrast to a conventional shift register composed represent between certain branches which the D flip-flop feedback. The number and position of these branches in the register chain in order to achieve the maximum possible period length 2n -1 by a primitive polynomial, the so-called generator polynomial is determined. n is in this case also equal to the degree of the generator polynomial.

A primitive polynomial as the generator is not mandatory but can result in non-primitive polynomials shorter period lengths. Shorter cycle lengths can also be reached with a smaller number of flip-flops and use of an appropriate primitive polynomial of a lower degree, so find as a generator polynomials almost exclusively primitive polynomials used.

To initialize, in English, this initial value is also referred to as a seed, the shift register can be filled with XOR feedback of any value, but not only with zeros. As a special case, an LFSR also have the maximum period length of 2n. In this case occurs after a run louder '0 ' in the shift register, which have to be detected and compensated for by an additional logic inversion by the feedback. Next also XNOR operations can be used instead of XOR operations, in this case, as a starting value and all values ​​except all ones allowed so again results in a maximum period of length 2n -1. Here, too, there is the possibility to achieve the period length 2n with an additional logic to the "forbidden" state to recognize all ones and to be compensated by an additional inversion of the feedback.

Like every other shift register also has the LFSR with clock input: At each clock pulse is changed to the following state and for a full pass of all combinations are 2n -1 clock pulses necessary.

An LFSR is because of its linearity of the generated series on its own for cryptologic applications a bad pseudo-random number generator. LFSR can be used as a basic element and, in conjunction with non-linear functions, or a combination of multiple LFSRs.

In addition to the conventional in digital circuitry, the binary LFSRs in GF ( 2) and non-binary LFSRs exist q is greater than 2, the XOR operation with a number of elements, it represents an addition modulo 2, in the general case by an addition modulo q replaced, the memory elements have ever been able to save q states.

Species

There are two different types in the realization of LFSRs:

Both types are equal to each other and have the same period length, although the effects produced are different. They differ in the realization, as shown in the figures, which represent the CLK clock input and Y is the output of the LFSR. XOR operators are shown with " ."

The two forms arise from the fact that each primitive polynomial of degree n> 2, a " Zwillingspolynom " has, which is also primitive. The two figures show a generator was used by the 8th grade for the Fibonacci LFSR:

The branch points correspond directly to the exponent. The equivalent to primitive generator polynomial of degree 8 in the Galois LFSR is:

Which is chosen the two equivalent forms of concrete depends, among other things, improvements in implementation. For example, the three XOR gates can be summarized with two inputs in the Fibonacci structure to an XOR gate with 4 inputs. This form can be used in FPGAs with lookup tables which have 4 inputs efficiently implemented.

Polynomauswahl

In addition to the degree n, which defines the period length, there are always several primitive polynomials which are mutually equivalent for a given degree n > 2. Depending on the application, additional selection criteria may be added. For example, so-called sparse generator polynomials are preferred in communications technology in the range of scramblers. These are polynomials, which make do with a minimum number of feedback points or with a minimum number of digits equal to 1 in the generator polynomial. This is because minimizing the hardware complexity, and further to minimize the multiplication of a reception error in the descrambler in self-synchronous scrambler. In the area of ​​coding theory as cyclic codes (CRC ) or cryptographic applications, however, densely populated polynomials by other selection criteria are preferred.

Primitive polynomials of different degrees are listed in tables. The table below shows some primitive polynomials are given with minimal instrumentation:

Applications

Applications of LFSRs are, in addition to the input -mentioned areas, for modulo counters which count up to the period length and then be "overrun ", ie start all over again. This is much more efficient than an arithmetic ( "real" ) counter with carry logic (carry - logic), there being an n- bit addition some XOR operations are only necessary. However, we can not deduce the actual count directly on the state of the LFSR, which is why an LFSR counter is only suitable for certain applications, for example to calculate the index of a FIFO.

In the field of digital signal processing LFSR also be distinguished according to the clock speed in relation to the bit rate and symbol rate in the applications. The bit rate or symbol rate equal to the clock rate of the LFSRs there is a scrambler. Is the clock frequency of the LFSR is significantly higher than bit or symbol rate, the LFSR is used for the spectral spreading as described in the context of Direct Sequence Spread Spectrum (DSSS ) and therefore used in the field of code division multiple access (CDMA) is used. Through so-called composite LFSR sequences then can be formed, how they are used for example in the context of Global Positioning System (GPS) for navigation purposes.

With linear feedback shift register compressed bit vectors are determined for checking the function of a circuit in the signature analysis.

Composite LFSR

An extension, the combinations of the data strings of various LFSR represents the resultant new data strings may have different properties than the original LFSR. They may thus, for example, by a low autocorrelation suitable for applications in the field of Code Division Multiple Access, and the spectral spreading.

The composition of the output data sequence from the individual independent LFSRs is done by XORing the individual subsequences. Assign the LFSR different sequence lengths L = 2n -1 and different generator polynomials, can be generated code sequences with completely new properties. As a rule these combined cyclical sequences do not have the maximum possible length. The following are some important classes are represented by composite from LFSR registers code sequences:

Gold sequences

Gold sequences were presented in 1967 by Robert Gold and also have two LFSRs with different generator polynomials, however, of the same length m. The maximum length of the code sequence Gold sequence is therefore only 2m -1. Holding the initial state of a LFSR fixed and changes the initial state ( " phase shift " ) of the other cyclically to 2m-1 new code sequences can be created, all of which have a relatively small periodic cross-correlation maximum to each other, ie they are almost orthogonal to each other. This means that these code sequences can be used in the area of ​​code division multiple access ( CDMA) and thus enable a distinction depending on the Gold sequence used.

The Gold sequences are used in practice, most commonly spread-spectrum signals also for their ease of production. Applications are next mobile systems ( UMTS), which work with CDMA, even with the civil usable C / A code Global Positioning Systems GPS and wireless LANs.

Kasami sequences

Kasami sequences were introduced in 1966 by Tadao Kasami, and have a relatively small cross-correlation maximum to each other periodically, i.e., they are almost orthogonal to each other and how the Gold sequences in the area of ​​code division multiple access (CDMA) may be used. Applications of these LFSRs are like among others the Russian GLONASS positioning system where Kasami code sequences are used from the satellite generation GLONASS -K in code division multiple access ( CDMA).

Kasami code sequences are generated by first, a maximum sequence is formed, this is decimated and then decimated sequence with the maximum sequence by XOR - operation is repeatedly linked. There are two sets of Kasami code sequences, the small and the large group. The small group consists of two LFSRs, the large group is formed with three LFSRs.

To generate a Kasami code sequence from the small group of an LFSR is taken, shown in the right circuit below, which generates the result with. As a restriction must be straight. A second LFSR in the representation above, generates the sequence with the index factor. The final Kasamifolge is formed by the two partial sequences are XORed with each other:

The Kasami sequence has a length of. As a special take Kasami sequences both in the cross-correlation and autocorrelation, only the following four values ​​when the code sequence generated is represented with the following elements:

JPL consequences

JPL sequences consist of two LFSRs whose code sequence length La and Lb must be relatively prime. In this case, the code sequence length of the overall sequence generated Lc is equal to:

There may be more than two LFSRs using multiple XOR be connected at the output. It must be relatively prime to each other only every code sequence lengths of the individual LFSR.

Were developed JPL consequences in the Jet Propulsion Labs, which is also the name for these code sequences derived. Application areas are, among others, in the field of distance measurement by means of spread-spectrum signals in satellite and in the field of space technology and the military use and more accurate P / Y - code in the global positioning system GPS.