# What is a LFSR (Linear-feedback shift register)

## What’s an LFSR?

It's like a line of buckets (each holding 0 or 1) that pass their bits to the next bucket. Some buckets use a simple rule (called XOR) to create a new bit.

### Explanation of the Algorithm

The algorithm described functions as a type of Linear Feedback Shift Register (LFSR), which is commonly used for generating pseudo-random sequences. Here's how it works step by step:

1. **Initialization**: You start with a 3-bit register initialized with a seed value. In the example, the initial seed is `101`.
2. **Bit Shifting**: Each cycle involves shifting all bits to the right, where the leftmost bit shifts out and is replaced by a new bit.
3. **Feedback Calculation**: The new bit is determined using the XOR operation on specific bits of the current register, dictated by the polynomial rule. For the given polynomial ( x^3 + x^2 + 1 ), this means XORing the bits corresponding to ( x^3 ) and ( x^2 ).
4. **Iteration**: This process is repeated, feeding the newly generated bit into the register and propagating the shift until you return to the seed value or achieve the desired length of sequence.

By repeatedly applying these steps, you can produce sequences useful in simulations, cryptographic applications, or any scenario requiring pseudo-random number generation.

## **Maximum Period**

For an LFSR with an **L**-bit register:

The maximum period of the sequence that can be generated by the LFSR is **2ᴸ - 1**.

## **Why Does It Matter?**

* It creates patterns that look random but repeat after a while.
* Used in cryptography, electronics, and games to generate secure or random-looking data.

## Quick Example:

Start with `101`

Function C(x) is defined as:

C(x) = x³ + x² + 1

### Understand arguments:

**Initial State:** 101

**Register size**: 3 bits (since the highest power is x³)

**Feedback rule**: XOR the bits corresponding to x³ (3rd bit) and x²  (2nd bit) to generate the new bit.

<table><thead><tr><th data-type="number">Cycle</th><th>Register</th><th>XOR (Feedback)</th><th data-type="number">Output</th></tr></thead><tbody><tr><td>0</td><td>101</td><td>0 ⊕ 1 = 1</td><td>1</td></tr><tr><td>1</td><td>110</td><td>1 ⊕ 0 = 1</td><td>1</td></tr><tr><td>2</td><td>111</td><td>1 ⊕ 1 = 0</td><td>0</td></tr><tr><td>3</td><td>011</td><td>1 ⊕ 1 = 0</td><td>0</td></tr><tr><td>4</td><td>001</td><td>0 ⊕ 1 = 1</td><td>1</td></tr><tr><td>5</td><td>100</td><td>0 ⊕ 0 = 0</td><td>0</td></tr><tr><td>6</td><td>010</td><td>1 ⊕ 0 = 1</td><td>1</td></tr><tr><td>7</td><td>101</td><td>0 ⊕ 1 = 1</td><td>1</td></tr></tbody></table>

**Maximum Period:** 2³ - 1 = 8-1 = 7

This means the 3-bit LFSR will generate 7 unique states before repeating


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://iq0.gitbook.io/iq0/a/what-is-a-lfsr-linear-feedback-shift-register.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.