Linear feedback shift register (LFSR) refers to, given the output of the previous state, the linear function of the output is then used as the input shift register. The XOR operation is the most common single-bit linear function: XOR operations are performed on some bits of the register as input, and then the bits in the register are overall shifted.
The shift register is a common device for generating signals and sequences. It is divided into two categories: linear and nonlinear. The famous sequence and sequence are generated by linear and nonlinear feedback shift registers, respectively. Linear feedback shift register (LFSR) is usually composed of dynamic or static master-slave flip-flop. The feedback loop consists of XOR gates. Its characteristics are usually characterized by a characteristic polynomial. The two-input XOR gate is used to calculate the characteristic polynomial of the maximum or near maximum length of the feedback function without rectifying the register. The characteristic of this circuit is its simple structure. Its upper limit shift speed depends on the delay time of the shift unit and the delay time of the two-input XOR gate. Therefore, a higher speed can be obtained [1]. The shift unit in the linear feedback shift register is composed of a master-slave edge trigger. In the shift unit of this structure, the master-slave two-pole latch, under the control of the two-phase non-overlapping clock, causes the data to be sampled on the rising edge of the clock and is held until the next rising edge of the clock. The four shift units in the circuit are all composed of dynamic master-slave edge-type flip-flops, and each shift operation requires data to pass through two stages of latches in sequence.
The initial value assigned to the register is called the "seed", because the operation of the linear feedback shift register is deterministic, so the data stream generated by the register is completely determined by the state of the register at that time or before. Moreover, because the state of the register is limited, it will eventually be a repeated cycle. However, with primitive polynomials, linear feedback shift registers can generate sequences that appear random and have very long cycle periods. The shift register has a simple structure and a fast running speed. Most practical key stream generators are based on shift registers. The theory of shift registers has also become the basis of modern stream cipher systems.
Applications of linear feedback shift registers include generating pseudo-random numbers, pseudo-random noise sequences, fast digital counters, and scramblers. The application of linear feedback shift register in hardware and software is very common. The mathematical principle used to quickly check transmission errors in cyclic redundancy check is closely related to the linear feedback shift register.
The bits that affect the next state are called taps. In Figure 1, the tap sequence is [16,14,13,11]. The rightmost bit of the LFSR is the output bit. The taps perform an exclusive OR operation with the output bits in turn, and then feed back to the leftmost bit. The sequence generated at the rightmost position is called the output stream.
The bits that affect the next state of LFSR are called taps
The maximum length LFSR generates an M sequence (for example, only the LFSR with a certain sequence can pass all 2n − 1 internal states, excluding all zero states), unless it is all zero, that is, the state never changes as Based on the replacement of LFSR with XOR operation, LFSR can also be given the same OR operation. Corresponding to the invalid state of the LFSR using the exclusive OR gate in the all-zero state, the LFSR using the same OR gate is also invalid in the state of all "1". Sequences generated by LFSR or LFSR based on XOR gates can be considered as binary sequences that are as effective as Gray codes or natural binary codes.
In LFSR, the setting of taps can be expressed by a modulo 2 polynomial in finite field arithmetic. This means that all coefficients in the polynomial must be "1" or "0". This polynomial is called a feedback polynomial or characteristic polynomial. For example, the taps in the figure are the 16th, 14th, 13th, and 11th bits, and the corresponding characteristic polynomial is:
The constant “1” in the polynomial does not represent a certain tap, it refers to a bit input (for example, equivalent to 1 ). The exponent in the polynomial represents the tap position from left to right. The first and last bits generally correspond to the input and output bits. LFSR can reach the maximum length if and only if the corresponding feedback polynomial is the original polynomial. This means that the following conditions are necessary:
The number of taps must be an even number.
The taps cannot appear in pairs, they must be relatively prime.
The original polynomial table that generated the longest LFSRs can be found through the link below. This type of LFSR has also become the standard, many-to-one or external XOR gate LFSR.
In different branches of mathematics, primitive polynomials have different meanings:
In domain theory, a primitive polynomial is the smallest polynomial of a primitive element with finite expansion of the finite field GF(pm) (domain theory).
In algebra (especially ring theory), if all coefficients of an integer polynomial are coprime, it is called a primitive polynomial. The primitive polynomial is very helpful for determining irreducible polynomials, and the irreducibility of high-order polynomials Polynomial decision has always been an incomplete problem.
The irreducible polynomials in the finite field are all primitive polynomials, which has an important effect on communication coding and cryptography. Each rational coefficient polynomial can be written as the product of a rational number and a primitive polynomial. The product of two primitive polynomials of the Gaussian lemma (ring) is still the primitive polynomial.
Stream cipher is a type of private key cryptosystem. Stream ciphers and block ciphers use a fixed transformation to process a set of data in a plaintext sequence. The encryption process is to convert the original plaintext such as messages, voices, and images into data, and then convert it. The same key sequence is encrypted bit by bit to generate a ciphertext sequence and sent to the receiver. The receiver uses the same key sequence to decrypt the ciphertext bit by bit to recover the plaintext. The development of modern digital electronic technology has enabled key sequences to be easily generated using shift register-based circuits, coupled with effective mathematical tools, the stream cipher has developed rapidly and has reached a more mature stage. At the same time, because the stream cipher does not exist Data expansion and error propagation, the hardware encryption and decryption speed is fast, and easy to implement, so stream ciphers are widely used in practice. Some properties that the key stream sequence must satisfy analyze the feedback shift register, which is an important part of the key stream generator, including the characteristics of the linear feedback shift register sequence and important indicators that measure the strength of the stream cipher system. In stream ciphers, since the plaintext sequence and the key sequence are encrypted bit by bit, the key sequence must have a length equivalent to the plaintext sequence. However, such a key sequence is difficult to distribute and manage. In fact, the key sequence is determined by the key space. The shorter key in the medium is generated by some algorithm.
FPGA XC4000E Family 28K Gates 2432 Cells 0.35um Technology 5V 208-Pin HSPQFP EP
FPGA XC5200 Family 16K Gates 1296 Cells 83MHz 0.5um Technology 5V 144-Pin TQFP
Xilinx TQFP
FPGA Spartan-3E Family 500K Gates 10476 Cells 657MHz 90nm Technology 1.2V 256-Pin FTBGA
CPLD CoolRunner -II Family 750 Gates 32 Macro Cells 200MHz 0.18um, CMOS Technology 1.8V 32-Pin QFN EP
Support
