Calculator
Example Data Table
| Initial State | Taps | Mode | Direction | First Output Bits | Notes |
|---|---|---|---|---|---|
| 1001 | 4,1 | Fibonacci | Right | 1001110 | Good for checking manual XOR shifts. |
| 11101 | 5,3 | Fibonacci | Right | 1011101 | Shows how taps change the period. |
| 101011 | x^6+x+1 | Fibonacci | Right | 1101010 | Uses polynomial input instead of manual taps. |
Formula Used
For a Fibonacci update, the feedback bit is calculated over GF(2):
f = s[t1] XOR s[t2] XOR ... XOR s[tk]
After the XOR is found, the register shifts. The feedback bit enters the open side. The output bit is read from the selected side.
For a right shift, a common state update is:
new_state = [f, s1, s2, ..., s(n-1)]
The maximum nonzero period is:
Pmax = 2^n - 1
Here, n is the register length. A primitive tap polynomial can reach this maximum period. The all zero state is excluded because XOR feedback keeps it zero forever.
How to Use This Calculator
- Enter the starting binary state, such as 1001.
- Enter manual taps, or enter a polynomial like x^4+x+1.
- Select Fibonacci or Galois style shifting.
- Choose the shift direction and output side.
- Set the number of steps to generate.
- Press Calculate to view the result above the form.
- Use CSV or PDF download for records.
Understanding Linear Feedback Shift Registers
A linear feedback shift register is a compact binary machine. It stores bits in a fixed register. At each clock, the register shifts one place. A new bit enters from a feedback rule. That rule is a XOR sum of selected tap bits. The method is simple, yet it creates long deterministic sequences.
Why LFSR Math Matters
LFSR systems appear in coding theory, counters, scramblers, stream ciphers, test patterns, and simulation work. Their value comes from repeatable pseudo random behavior. A good tap set can visit every nonzero state before repeating. For an n bit register, that maximum period is 2^n − 1. The all zero state cannot leave itself, so it is avoided for normal sequence generation.
Choosing State and Taps
The seed sets the starting state. It must contain at least one one bit. Taps define the feedback polynomial. Different taps produce different periods. A primitive polynomial gives the longest possible cycle. Nonprimitive taps still work, but they may repeat early. This calculator helps you compare those choices without manual shifting.
Fibonacci and Galois Views
A Fibonacci LFSR forms one feedback bit from all taps, then inserts it during the shift. A Galois style update spreads the output bit through selected stages. Both are linear over GF(2). They can represent related sequences, but their state paths may differ when taps are written in a different convention.
Reading the Results
The output sequence shows the bit emitted at each step. The table lists the current state, feedback bit, and next state. Period detection marks the first repeated state within the requested limit. Balance, run length, transitions, and linear complexity add deeper checks. These values help judge whether the chosen setup is useful for a counter, teaching example, or data pattern.
Practical Advice
Start with a small register. Verify the shift direction and tap indexing. Increase the step limit when no repeat appears. Export CSV for spreadsheets. Use PDF for a compact record. When records are shared, keep the seed, taps, direction, and indexing together. These details define the sequence. One changed setting can create a different cycle. For classroom work, compare two tap sets side by side and note the first repeated state carefully.
FAQs
What is a linear feedback shift register?
It is a binary register that shifts bits and creates a new bit from XOR feedback. The feedback comes from selected tap positions.
What does a tap mean?
A tap is a selected state bit used in the XOR feedback rule. Changing taps changes the sequence and period.
Why is the all zero state bad?
XOR of zero bits gives zero. So an all zero register stays zero forever and produces no useful cycle.
What is the maximum LFSR period?
For n bits, the longest nonzero period is 2^n − 1. It requires a suitable primitive feedback polynomial.
What is Fibonacci mode?
Fibonacci mode builds one feedback bit from all taps. That bit is inserted after the register shifts.
What is Galois style mode?
Galois style mode uses the shifted output bit to affect selected stages. It is often efficient in hardware designs.
Can I use a polynomial instead of taps?
Yes. Enter a form like x^4+x+1. The degree must match the state length. Terms below the degree become tap positions.
Why export CSV or PDF?
CSV is useful for spreadsheet checks and graphing. PDF is useful for saving a compact report of the summary and steps.