Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Linear-feedback shift register
Summary
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a 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 well-chosen feedback function can produce a sequence of bits that appears random and has a very long cycle.
Applications of LFSRs include generating pseudo-random numbers, 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. 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.
The bit positions that affect the next state are called the taps. In the diagram the taps are [16,14,13,11]. The rightmost bit of the LFSR is called the output bit. The taps are XOR'd sequentially with the output bit and then fed back into the leftmost bit. The sequence of bits in the rightmost position is called the output stream.
The bits in the LFSR state that influence the input are called taps.
A maximum-length LFSR produces an m-sequence (i.e., it cycles through all possible 2m − 1 states within the shift register except the state where all bits are zero), unless it contains all zeros, in which case it will never change.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (2)
EE-530: Test of VLSI systems
Test of VLSI Systems covers theoretical knowledge related to the major algorithms used in VLSI test, and design for test techniques. Basic knowledge related to computer-aided design for test technique
EE-110: Logic systems (for MT)
Ce cours couvre les fondements des systèmes numériques. Sur la base d'algèbre Booléenne et de circuitscombinatoires et séquentiels incluant les machines d'états finis, les methodes d'analyse et de syn
Related lectures (15)
Test of VLSI Systems: BIST and Response Compaction
Covers BIST techniques, LFSRs, Response Compaction, MISR, and BILBO in VLSI systems.
Built-In Self-Test (BIST): Techniques and Implementations
Explores Built-In Self-Test (BIST) techniques in VLSI systems, covering benefits, drawbacks, implementation details, and the use of Linear Feedback Shift Registers (LFSRs) for test pattern generation.
Random Number Generators: Schrage's Algorithm
Explores Schrage's algorithm for generating random numbers and shift-register generators in computers.
Related publications (33)
An Asymmetric Perturbation Signal for Enhanced Perturbation Injection Capabilities of a Grid-Connected Converter
Drazen Dujic, Andrea Cervone, Jules Christian Georges Macé
Impedance estimation is an important tool for grid- converter interaction evaluation. Using existing grid-connected converters for perturbation injection enables grid impedance estimation during operation without additional hardware (namely dedicated pertu ...
2024Further Results on Efficient Implementations of Block Cipher Linear Layers
At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates r ...
2021Simulation-based Anomaly Detection and Damage Localization: An application to Structural Health Monitoring
Jan Sickmann Hesthaven, Caterina Bigoni
We propose a simulation-based decision strategy for the proactive maintenance of complex structures with a particular application to structural health monitoring (SHM). The strategy is based on a data-driven approach which exploits an offline-online decomp ...
2020Related people (8)
Related concepts (14)
Maximum length sequence
A maximum length sequence (MLS) is a type of pseudorandom binary sequence. They are bit sequences generated using maximal linear-feedback shift registers and are so called because they are periodic and reproduce every binary sequence (except the zero vector) that can be represented by the shift registers (i.e., for length-m registers they produce a sequence of length 2m − 1). An MLS is also sometimes called an n-sequence or an m-sequence. MLSs are spectrally flat, with the exception of a near-zero DC term.
Cryptographically secure pseudorandom number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG). Most cryptographic applications require random numbers, for example: key generation nonces salts in certain signature schemes, including ECDSA, RSASSA-PSS The "quality" of the randomness required for these applications varies.
Pseudorandom noise
In cryptography, pseudorandom noise (PRN) is a signal similar to noise which satisfies one or more of the standard tests for statistical randomness. Although it seems to lack any definite pattern, pseudorandom noise consists of a deterministic sequence of pulses that will repeat itself after its period. In cryptographic devices, the pseudorandom noise pattern is determined by a key and the repetition period can be very long, even millions of digits.