Editing Linear-feedback shift register (section)

{{Short description|Type of shift register in computing}}
{{Redirect|LFSR|the airport using that ICAO code|Reims – Champagne Air Base}}
{{Use American English|date = March 2019}}
{{More citations needed|date=March 2009}}

In [[computing]], a '''linear-feedback shift register''' ('''LFSR''') is a [[shift register]] whose input bit is a [[Linear#Boolean functions|linear function]] of its previous state.

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

The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the stream of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle. However, an LFSR with a [[Primitive polynomial (field theory)|well-chosen feedback function]] can produce a sequence of bits that appears random and has a [[Maximal length sequence|very long cycle]].

Applications of LFSRs include generating [[Pseudorandomness|pseudo-random numbers]], [[Pseudorandom noise|pseudo-noise sequences]], fast digital counters, and [[whitening sequences]]. Both hardware and software implementations of LFSRs are common.

The mathematics of a [[cyclic redundancy check]], used to provide a quick check against transmission errors, are closely related to those of an LFSR.<ref>{{Cite web|url=https://www.ti.com/lit/an/spra530/spra530.pdf|title=Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x|last=Geremia|first=Patrick|publisher=Texas Instruments|page=6|access-date=October 16, 2016}}</ref> In general, the arithmetics behind LFSRs makes them very elegant as an object to study and implement. One can produce relatively complex logics with simple building blocks. However, other methods, that are less elegant but perform better, should be considered as well.