Linear-feedback shift register
Give a starting row of bits, the tap positions and a number of steps, and get the bit stream of a Fibonacci LFSR: seed 1000 with taps 4 and 1 over 8 steps emits 00011110 and ends at 1101. Handy for CRC drills and self-test patterns. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- State
- 1000
- Taps
- 4, 1
- Length
- 4
- Sequence
- 00011110
- Final state
- 1101
A linear-feedback shift register, or LFSR, is a compact digital machine that stores a row of bits and, on every clock pulse, XORs a handful of tap positions to compute a new input bit while shifting the rest. Designers use LFSRs to generate pseudorandom bit streams, cyclic-redundancy remainders, scrambling sequences, and built-in self-test patterns without storing a lookup table. This calculator accepts the initial register state as a string of zeros and ones, a list of 1-based tap positions counted from the left, and the number of clock steps to run. It implements a Fibonacci LFSR: each step emits the rightmost bit, shifts the register one place to the right, and inserts the XOR of the tapped bits on the left.
What a Fibonacci LFSR is and how each clock produces a bit
A linear-feedback shift register is a finite-state machine whose next input bit is a linear function of its current contents, taken over the two-element field GF(2). In hardware that linear function is just XOR. Positions are numbered from 1 on the left of the state string to n on the right.
On every clock the engine reads the bits at those taps, XORs them together to obtain a single feedback bit, emits the rightmost bit as the next output sample, shifts every bit one place toward the right, and writes the feedback bit into the vacant leftmost cell. Repeating that step produces a deterministic bit sequence whose period is at most 2^n minus one: the all-zero state is a fixed point, and every other state of a maximal-period (primitive) polynomial walks through all remaining 2^n minus one nonzero vectors before repeating.
Classic classroom polynomials such as x^4 plus x plus one, which corresponds to taps 4 and 1 on a four-bit register, reach that maximal period when started from a nonzero seed. Galois LFSRs XOR into several cells while shifting and produce a related but not identical stream for the same polynomial; this calculator does not emulate Galois wiring.
What you can do with it
Classroom LFSR and CRC drills
Clock a Fibonacci register from a seed and tap list, then compare the emitted bit sequence and final state against hand-worked homework or a textbook polynomial.
PRBS and built-in self-test prefixes
Generate a known prefix of a maximal-period LFSR stream to check that an FPGA, ASIC, or software scrambler matches the specified taps after reset.
FAQ
How does this linear-feedback shift register clock each step?
It implements a Fibonacci LFSR. The XOR of the bits at the 1-based tap positions is the feedback. The rightmost bit is emitted, the register shifts one place to the right, and the feedback bit is written into the leftmost cell.
How are tap positions numbered?
Taps are 1-based and counted from the left of the state string: the first character is position 1 and the last character is position n, where n is the register length. Polynomial x^4+x+1 on four bits is taps 4 and 1.
What does an all-zero seed produce?
All output bits stay 0 and the register stays all zeros, because XOR of zeros is zero. That fixed point is real LFSR behaviour, not an error. Use a nonzero seed for a nontrivial stream.
What happens if a tap is beyond the register length?
The run is refused with a message instead of wrapping the position around. Every tap must lie between 1 and the number of bits in the seed, counted from the left.
What is the longest sequence an LFSR can produce?
At most 2 to the power n minus 1 bits before it repeats, where n is the register length. Maximal-period taps, such as 4 and 1 on a four-bit register, reach that limit from any seed that is not all zeros.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/math/linear-feedback-shift-register \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"state":"1000","taps":[4,1],"steps":8}'const res = await fetch("https://api.kit.forhosting.com/math/linear-feedback-shift-register", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"state": "1000",
"taps": [
4,
1
],
"steps": 8
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/linear-feedback-shift-register",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"state": "1000",
"taps": [
4,
1
],
"steps": 8
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/linear-feedback-shift-register", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"state":"1000","taps":[4,1],"steps":8}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"state":"1000","taps":[4,1],"steps":8}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/linear-feedback-shift-register", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"state": "1000",
"taps": [
4,
1
],
"steps": 8
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.linear_feedback_shift_register",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_length | 64 |
max_steps | 4096 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
If any tap lies past the register length the task fails with invalid_input instead of inventing a wrap-around.
What a Fibonacci LFSR is and how each clock produces a bit
The Fibonacci form, which this endpoint implements, keeps a row of n bits and a list of tap positions.
Input contract, tap numbering, response shape, and errors
Whitespace inside state is ignored so a spaced nibble such as 1 0 0 0 is accepted. taps is a non-empty array of 1-based integer positions whose bits are XORed to form the Fibonacci feedback; each tap must lie between 1 and the register length inclusive. steps is the number of clocks to run, an integer from 1 to 4096; each clock emits one output bit. POST a JSON body with three required fields. state is the initial register as a string of 0 and 1 characters; the leftmost character is position 1 and the length of the string is the register width, from one to sixty-four bits. Aliases seed or register for state, tap_positions for taps, and n or count for steps are accepted. Missing fields, non-bits in state, non-integers, empty tap lists, and values outside the published limits fail with invalid_input naming the field and are not billed. On success the body echoes length, the canonical state string, taps, and steps; returns bits as an array of 0 and 1 integers in clock order; returns sequence as the same bits concatenated for copy-paste; and returns final_state, the register contents after the last shift, so a caller can resume the machine. Example: state 1000, taps 4 and 1, steps 8 yields bits 0,0,0,1,1,1,1,0, sequence 00011110, and final_state 1101.
Where an LFSR bit-sequence API earns its keep
Digital-design courses and HDL labs ask students to clock a Fibonacci LFSR by hand for a handful of steps and to match a datasheet polynomial against a bit dump; a deterministic oracle that uses the same left-to-right numbering and right-shift convention removes arguments about which end is bit zero. Failed validation does not consume balance. Built-in self-test and PRBS generators in silicon and FPGA fabrics are LFSRs at heart: verification scripts can call this endpoint to produce a known prefix of a maximal-period sequence and then check that a device-under-test emits the same prefix after reset.
Integration use cases
HDL testbench oracles
Drive unit tests with a deterministic bit dump so a Verilog or VHDL LFSR model cannot silently adopt the opposite shift direction or 0-based taps.
Technical questions
What happens if a tap exceeds the register length?
The task fails with invalid_input. A tap greater than n would describe a different polynomial; the handler refuses wrap-around so the contract stays honest.
What does the linear-feedback shift register calculator cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.