Linear-feedback shift register

src: i.ytimg.com

In computing, linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of the previous state.

The most commonly used linear function of a single bit is exclusive-or (XOR). Thus, LFSR is most often a shift register whose input bits are driven by XOR of some bits of the overall shift register value.

The initial value of LFSR is called the seed, and since the operation of the register is deterministic, the stream of values ​​generated by the register is determined by its current status (or earlier). Likewise, since the list has a number of possible circumstances, it should ultimately include repetitive cycles. However, LFSR with well-chosen feedback function can produce a sequence of bits that appear random and have very long cycles.

LFSR applications include generating pseudo-random numbers, pseudo-noise sequences, fast digital counters, and bleaching sequences. The implementation of LFSRs hardware and software is common.

The mathematics of cyclic redundancy checks, used to provide a quick check of transmission errors, is closely related to LFSR.

Video Linear-feedback shift register

Fibonacci LFSRs

The position of the bit that affects the next state is called a tap. In the diagram, tap [16,14,13,11]. The rightmost bit of the LFSR is called the output bit. XOR'd tap in sequence with output bits and then fed back to leftmost bit. The sequence of bits in the far right is called the output stream.

• The bits in the LFSR status that affect the input are called taps .
• The maximum length of the LFSR produces the m-order (eg, cycle through all possibilities 2 ^m Ã,-1 states in the shift register except for the state in which all bits are zero ), unless it contains all the zeros, in which case it will never change.
• As an alternative to XOR-based feedback in LFSR, one can also use XNOR. This function is an affine map, not a strict linear map, but produces an equivalent polynomial counter whose status is a complement of LFSR status. A country with everyone is illegal when using XNOR feedback, in the same way as a country with all zeroes is illegal when using XOR. The country is considered illegal because the counter will remain "locked" under these circumstances.

The sequence of numbers generated by LFSR or XNOR counterparts can be considered as a binary number system as valid as Gray code or a naturally binary code.

The tap setting for feedback in LFSR can be expressed in finite field arithmetic as a mod polynomial 2. This means that the coefficients of the polynomial must be 1s or 0s. These are called feedback polynomials or mutual characteristics polynomials. For example, if a tap is at the 16th, 14th, 13th, and 11th bits (as shown), the feedback polynomial is

${\ displaystyle x ^ {16} x ^ {14} x ^ {13} x ^ {11} 1.}$

The "one" in the polynomial does not match the tap - this corresponds to the input to the first bit (ie x ⁰ , which is equivalent to 1). The term strength represents the bits being tapped, calculated from the left. The first and last bits are always connected as inputs and outputs respectively.

LFSR is the maximum length if and only if the corresponding feedback polynomial is primitive. This means that the following conditions are required (but not sufficient):

• Number of taps even.
• The tap collection is co-prime simultaneously; ie, there should be no other than 1 common to all taps.

The primitive polynomial table from which a maximum-length LFSR can be constructed is given below and in reference.

There can be more than one sequence of maximum length length for the given LFSR length. Also, once a single maximum tap sequence has been found, others automatically follow. If the sequence of taps in n -bit LFSR is [ n , A , B , C , 0] , where the value 0 corresponds to x ⁰ Ã, = Ã, 1, then the corresponding "mirror" sequence is < span> [ n , n - C , n - B , n - A , 0] . So the sequence of taps [32, 7, 3, 2, 0] has as spins [32, 30, 29, 25, 0] . Both provide a maximum length sequence.

Examples in C are below:

If fast parity operations or popcount are available, the feedback bits can be calculated more efficiently as bit = parity (lfsr & amp; 0x002Du) or bit = popcnt (lfsr & amp; 0x002Du) & amp; 1 , effectively calculate the product of register point with characteristic polynomial.

This LFSR configuration is also known as a standard standard , many-to-one or external XOR . The alternate Galois configuration is described in the next section.

Maps Linear-feedback shift register

Galois LFSRs

Named after French mathematician ÃÆ'â € variste Galois, LFSR in Galois configuration, also known as modular , internal XORs , or one-to-many LFSR , is an alternative structure that can generate the same output stream as the conventional LFSR (but offset in time). In the Galois configuration, when the system is clocked, the un-tap bits are shifted one position to the right unchanged. The tap, on the other hand, is XORed with the output bit before being stored in the next position. The new output bit is the next input bit. The effect of this is that when the output bit is zero, all the bits in the register are shifted to the right unchanged, and the input bit becomes zero. When the output bit is one, the bits in the position press all the flips (if they are 0, they become 1, and if they are 1, they become 0), and then the entire register shifts to the right and the input bit becomes 1.

To generate the same output stream, the tap order is peer (see above) of the order for the conventional LFSR, if the flow will reverse. Note that the internal state of LFSR does not have to be the same. The displayed Galois list has the same output stream as the Fibonacci list in the first section. The time offset exists between the streams, so different starting points will be required to get the same output every cycle.

• Galois LFSR does not merge each tap to generate new inputs (XORing is done in LFSR, and no XOR gates are serialized, therefore propagation time is reduced to one XOR over the entire chain), allowing each tap calculated in parallel, increasing the speed of execution.
• In LFSR software implementation, Galois form is more efficient, because XOR operations can be implemented word at a time: only the output bits must be checked individually.

Below is a sample C code for a 16-bit LFSR Galois example in the image:

Notice that

can also be written as

which can generate more efficient code on some compilers.

Galois LFSR Non-binary

Binary Galois LFSR as shown above can be generalized to any alphabet {0, 1,..., q Ã,-1} (for example, for binary, q = 2, and the alphabet is just {0, 1}). In this case, an exclusive or general component is generalized to an additional module- q (note that XOR is the addition of modulo 2), and the feedback bits (output bits) are multiplied (modulo- q ) with a value q , which is constant for each particular tap point. Note that this is also a generalization of the binary case, where the feedback is multiplied by 0 (no feedback, ie, no tap) or 1 (present feedback). Given the proper tap configuration, the LFSR can be used to generate the Galois field for arbitrary prime values ​​of q .

src: i.ytimg.com

Matrix form

${\ displaystyle k}  ÂÂ$ negara bagian register dalam konfigurasi fibonacci diberikan dengan menggunakan ${\ displaystyle C ^ {\ mathrm {T}}}  ÂÂ$ di tempat ${\ displaystyle C}  ÂÂ$ . Operasi transposisi pada matriks pendamping setara dengan menggunakan polinomial timbal balik, dan dengan demikian urutan bit yang dihasilkan dalam bentuk ini berlanjut ke arah yang sama.

This form generalizes naturally to random fields for both LFSR configurations.

src: ecetp.colorado.edu

Some polynomials for maximum LFSRs

The following table lists the maximum length polynomials for the register-shear length of up to 24. Note that more than one polynomial of maximum length may exist for each given shift-register length. A list of maximally long polynomial alternatives for shift-register length 4-32 (beyond which it is not feasible to store or transfer it) can be found here: http://www.ece.cmu.edu/~koopman/lfsr/index.html.

src: i.ytimg.com

The output stream property

• One and zero occur in "run". The output stream 1110010, for example, consists of four trajectories with lengths of 3, 2, 1, 1, in sequence. In a maximum LFSR period, 2 ^{n -1} runs occur (for example, a six bit LFSR has 32 operations). Exactly half of this process is one long bit, one quarter is two long bits, up to two runs of zero n Ã,-1 bit length, and one single run n long bit. This distribution is almost equal to the expected statistical value for a completely random sequence. However, the likelihood of finding this distribution in the sample sequence is really random rather low.
• the LFSR output stream is deterministic. If the current state and XOR gate position in LFSR are known, the next situation can be predicted. This is not possible with a completely random event. With LFSRs maximum, it is much easier to calculate the next status, as there is only an easy amount to be limited for each length.
• The output stream is reversible; LFSR with mirror tap will rotate the output sequence in reverse order.
• A value consisting of all zeros can not appear. Thus, a LFSR of n length can not be used to generate all 2 ⁿ values.

src: images.slideplayer.com

Apps

LFSRs can be implemented in hardware, and this makes them useful in applications that require the creation of very fast pseudo-random sequences, such as direct sequence radio distribution. LFSR has also been used to produce white noise approximations in various programmable sound generators.

Use as counters

Repeated sequences of LFSR conditions allow it to be used as a clock divider or as a counter when non-binary sequences are acceptable, as is often the case where computer index or framing locations should be machine-readable. The LFSR counter has a simpler logic of feedback than a natural binary counter or a Counter code counter, and therefore can operate at a higher clock speed. However, it is necessary to ensure that LFSR never enters all zero state, for example by arranging it at start-up to another country in sequence. Primitive polynomial tables show how LFSR can be arranged in Fibonacci or Galois form to give maximum period. One can obtain another period by adding to LFSR which has longer periods of some shorter logic sequence by passing through multiple states.

Usage in cryptography

LFSR has long been used as a pseudo-random number generator for use in stream ciphers (especially in military cryptography), due to the ease of construction of simple electromechanical or electronic circuits, long periods, and very uniform output streams. However, LFSR is a linear system, which leads to fairly easy code readings. For example, given the known plaintext strand and the corresponding ciphertext, the attacker can intercept and recover the LFSR output streams used in the described system, and from that the output stream can build a minimal LFSR size that simulates the intended receiver by using the Berlekamp-Massey algorithm. This LFSR can then be fed a captured output current stretch to recover the remaining plaintext.

Three common methods are used to mitigate this problem in LFSR-based flow ciphers:

• A non-linear combination of several bits of LFSR status;
• Non-linear combinations of output bits of two or more LFSRs (see also: generator shrink); or use the Evolutionary algorithm to introduce non-linearity.
• Irregular clocking of LFSR, as in the alternating step generator.

Key LFSR-based key streams include A5/1 and A5/2, used in GSM mobile phones, E0, used in Bluetooth, and shrinking generators. The A5/2 cipher has been damaged and both A5/1 and E0 have serious flaws.

Linear feedback shift register has a strong relationship with linear congruence generator.

Usage in circuit testing

LFSR is used in testing circuits for pattern-test generation (for complete testing, pseudo-random testing or pseudo-complete testing) and for signature analysis.

Generation test-pattern

Complete LFSRs are generally used as pattern generators for complete testing, as they include all possible inputs for the input circuit n . LFSRs long and weighted LFSRs are widely used as pseudo-random pattern-test generators for pseudo-random test applications.

Signature analysis

In the built-in self-test (BIST) technique, storing all circuit output on the chip is not possible, but circuit output can be compressed to form a signature that will be compared to a golden signature (from a good circuit) to detect errors. Because this compression is lossy, there is always the possibility that the wrong output also produces the same signature with the golden signature and the error can not be detected. This condition is called a masking or aliasing error. BIST is completed with a multi-input signature register (MISR or MSR), which is a type of LFSR. The standard LFSR has a single XOR or XNOR gate, where the gate input is connected to several "taps" and the output is connected to the input of the first flip-flop. A MISR has the same structure, but the input to each flip-flop is fed through the XOR/XNOR gate. For example, a 4-bit MISR has a 4-bit parallel output and a 4-bit parallel input. The input of the first flip-flop is XOR/XNORd with the parallel input bit and the "tap". Each other flip-flop input is XOR/XNORd with the previous flip-flop output and the corresponding parallel input bit. As a result, the subsequent MISR situation depends on the last few states to oppose only the current circumstances. Therefore, MISR will always produce the same golden signature given that the input sequence is the same every time.

Usage in digital broadcasting and communication

Randomization

To prevent short repetition sequences (eg, running 0 or 1) from forming spectral lines that can complicate the tracking of symbols in the receiver or interfere with other transmissions, the sequence of data bits is combined with the output of linear-feedback registers prior to modulation and transmission. This randomization is removed in the recipient after the demodulation. When LFSR runs at the same bit rate as the transmitted symbol stream, this technique is called scrambling. When LFSR runs much faster than the flow of symbols, the sequence of bits generated by LFSR is called chipping code . The chipping code is combined with data using exclusively or before transmission using binary phase-shift keying or similar modulation methods. The resulting signal has a higher bandwidth than the data, and therefore this is a spread-spectrum communication method. When used only for spectrum-scattered properties, this technique is called the direct sequence spread spectrum; when it is used to distinguish multiple signals transmitted in the same channel at the same time and frequency, it is called a multiple passcode division.

Schemes should not be confused with encryption or encryption; scramble and spread with LFSR do not protect the information from wiretapping. They are instead used to produce equivalent streams that have convenient engineering properties to enable robust and efficient modulation and demodulation.

Digital broadcasting systems that use linear-feedback registers:

• Standard ATSC (digital TV transmission system - North America)
• DAB (Digital Audio Broadcasting system - for radio)
• DVB-T (digital TV transmission system - Europe, Australia, parts of Asia)
• NICAM (digital audio system for television)

Other digital communication systems use LFSR:

• INTELSAT (IBS) business services
• Intermediate data rate (IDR)
• SDI (Digital Serial Interface transmission)
• Transfer data via PSTN (as per ITU-T V-series recommendations)
• CDMA (Code Division Multiple Access) mobile phone
• 100BASE-T2 "fast" Ethernet scrambles bits using LFSR
• 1000BASE-T Ethernet, the most common form of Gigabit Ethernet, scrambles bits using LFSR
• PCI Express 3.0
• SATA
• Serial attached SCSI (SAS/SPL)
• USB 3.0
• IEEE 802.11a randomizes bits using LFSR
• The Bluetooth Low Energy Link Layer utilizes LFSR (referred to as bleaching)
• Satellite navigation systems such as GPS and GLONASS. All current systems use LFSR output to generate some or all of their starting code (as chipping code for CDMA or DSSS) or to modulate the carrier without data (such as GPS, CL L2 start code). GLONASS also uses multi-frequency access sharing in combination with DSSS.

Other uses

LFSR is also used in radio jamming systems to generate pseudo-random sounds to raise the noise floor of the target communication system.

The German signal time DCF77, in addition to amplitude locking, uses phase-shifted locking driven by a 9-phase LFSR to improve the accuracy of received time and the robustness of the data flow in the presence of noise.

src: i.ytimg.com

See also

• Pinwheel
• Mersenne twister
• Maximum length order
• Analog feedback shift register
• NLFSR, Non-Linear Feedback Shift Register
• The ring counters
• Pseudo-random binary order

src: images.slideplayer.com

References

src: i.ytimg.com

External links

Source of the article : Wikipedia