Linear feedback shift register

Introduction

A Linear Feedback Shift Register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function is exclusive-or (XOR). An LFSR is a shift register that, when clocked, shifts the bits of its content one position to the left, and the new bit entering the register is a linear function of the previous bits. LFSRs are widely used in various applications, including cryptography, error detection and correction, and digital signal processing.

Structure and Operation

An LFSR consists of a sequence of flip-flops connected in series, with the output of the last flip-flop fed back to the input of the first flip-flop through a linear function, typically an XOR gate. The feedback function determines the sequence of bits generated by the LFSR.

Feedback Polynomial

The feedback polynomial, also known as the characteristic polynomial, defines the feedback function of the LFSR. It is a polynomial over the Galois field GF(2), where the coefficients are either 0 or 1. The degree of the polynomial corresponds to the number of flip-flops in the LFSR. For example, an LFSR with a feedback polynomial of degree 4 can be represented as: \[ P(x) = x^4 + x + 1 \] This polynomial indicates that the feedback function involves the XOR of the first and fourth flip-flops.

State Transition

The state of an LFSR is the content of its flip-flops at any given time. When the LFSR is clocked, the bits are shifted to the left, and the new bit entering the register is computed using the feedback function. The state transition can be represented as: \[ S_{t+1} = (S_t \ll 1) \oplus (S_t \& P) \] where \( S_t \) is the current state, \( \ll \) denotes the left shift operation, \( \& \) denotes the bitwise AND operation, and \( P \) is the feedback polynomial.

Types of LFSRs

There are several types of LFSRs, each with different properties and applications.

Fibonacci LFSR

In a Fibonacci LFSR, the feedback function is applied to the output of the flip-flops, and the result is fed back to the input of the first flip-flop. This type of LFSR is named after the Fibonacci sequence, as the feedback function can be seen as a linear combination of previous states.

Galois LFSR

In a Galois LFSR, the feedback function is applied at each flip-flop, and the result is fed back to the input of the next flip-flop. This type of LFSR is named after the mathematician Évariste Galois, who developed the theory of finite fields.

Applications

LFSRs have a wide range of applications in various fields due to their simplicity and efficiency.

Cryptography

LFSRs are used in stream ciphers, where they generate a pseudorandom bit sequence that is XORed with the plaintext to produce the ciphertext. Examples of stream ciphers that use LFSRs include the A5/1 algorithm used in GSM mobile communications and the Grain family of stream ciphers.

Error Detection and Correction

LFSRs are used in cyclic redundancy check (CRC) codes, which are widely used for error detection in digital communications and storage. The CRC code is generated by treating the data as a polynomial over GF(2) and dividing it by a generator polynomial, which is implemented using an LFSR.

Digital Signal Processing

LFSRs are used in pseudo-random number generation (PRNG) for applications such as Monte Carlo simulations, spread spectrum communications, and scrambling of digital signals. The pseudorandom sequences generated by LFSRs have desirable statistical properties, such as long periods and uniform distribution.

Mathematical Properties

LFSRs have several important mathematical properties that make them useful in various applications.

Periodicity

The period of an LFSR is the length of the sequence before it repeats. The maximum period of an LFSR with \( n \) flip-flops is \( 2^n - 1 \), which occurs when the feedback polynomial is a primitive polynomial. A primitive polynomial is a polynomial that cannot be factored into polynomials of lower degree over GF(2).

Linear Complexity

The linear complexity of an LFSR is the length of the shortest LFSR that can generate a given sequence. A sequence with high linear complexity is desirable in cryptographic applications, as it is more resistant to linear attacks.

Autocorrelation

The autocorrelation of an LFSR sequence measures the similarity between the sequence and a shifted version of itself. A sequence with low autocorrelation is desirable in applications such as spread spectrum communications, where it reduces interference between signals.

Implementation

LFSRs can be implemented in hardware or software, depending on the application requirements.

Hardware Implementation

In hardware, LFSRs are typically implemented using flip-flops and XOR gates. The flip-flops store the state of the LFSR, and the XOR gates implement the feedback function. Hardware implementations of LFSRs are efficient in terms of area and power consumption, making them suitable for applications such as embedded systems and cryptographic hardware.

Software Implementation

In software, LFSRs are implemented using shift registers and bitwise operations. The state of the LFSR is stored in a variable, and the feedback function is implemented using bitwise XOR and shift operations. Software implementations of LFSRs are flexible and can be easily adapted to different applications, such as simulation and random number generation.

Advantages and Limitations

LFSRs have several advantages and limitations that should be considered when choosing them for a specific application.

Advantages

**Simplicity**: LFSRs are simple to implement in both hardware and software.
**Efficiency**: LFSRs have low computational complexity and require minimal resources.
**Predictability**: The sequences generated by LFSRs are deterministic and can be easily reproduced.

Limitations

**Linear Nature**: The linear nature of LFSRs makes them vulnerable to linear attacks in cryptographic applications.
**Periodicity**: The period of an LFSR sequence is limited by the length of the register and the choice of feedback polynomial.
**Correlation**: The sequences generated by LFSRs may exhibit undesirable correlation properties in certain applications.

References

Close-up of a digital circuit board with visible shift registers.