linear feedback shift register
E646779
A linear feedback shift register is a sequential digital circuit that generates deterministic pseudorandom bit sequences by shifting bits and feeding back a linear function of its previous state.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
finite-state machine
ⓘ
pseudorandom sequence generator ⓘ sequential digital circuit ⓘ shift register ⓘ |
| advantage |
high-speed operation
ⓘ
low hardware complexity ⓘ |
| basedOn | recurrence relation over GF(2) ⓘ |
| cannotGenerate | all-zero state in maximum-length configuration ⓘ |
| characterizedBy |
feedback polynomial
ⓘ
register length ⓘ tap positions ⓘ |
| clockedBy | discrete time steps ⓘ |
| hasComponent |
clock input
ⓘ
feedback network ⓘ feedback taps ⓘ output bit line ⓘ series of storage elements ⓘ |
| hasProperty |
bit-oriented
ⓘ
deterministic ⓘ linear over GF(2) ⓘ maximum-length sequence possible when feedback polynomial is primitive ⓘ periodic sequence ⓘ pseudorandom output ⓘ |
| hasType |
Fibonacci LFSR
NERFINISHED
ⓘ
Galois LFSR NERFINISHED ⓘ external XOR LFSR ⓘ internal XOR LFSR ⓘ |
| input | initial seed value ⓘ |
| limitation | linear structure vulnerable to cryptanalysis ⓘ |
| mathematicallyModeledAs | linear recurrence over GF(2) ⓘ |
| maximumPeriod | 2^n - 1 states for n-bit LFSR with primitive polynomial ⓘ |
| operatesOn | binary sequences ⓘ |
| output | pseudorandom bit stream ⓘ |
| relatedTo |
Gold codes
ⓘ
cyclic redundancy check ⓘ m-sequences ⓘ |
| stateSpace | 2^n possible states for n-bit register ⓘ |
| usedIn |
built-in self-test
ⓘ
cryptography ⓘ error correction coding ⓘ error detection ⓘ hardware random number generators ⓘ pseudo-noise sequence generation ⓘ scramblers ⓘ spread-spectrum communications ⓘ stream ciphers ⓘ |
| uses |
exclusive OR gates
ⓘ
flip-flops ⓘ linear feedback function ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.