SUBMITTED BY:
ANKUSH GOYAL

---

[attachment=10842]
Introduction
A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The only linear function of single bits is xor, thus it is a shift register whose input bit is driven by the exclusive-or (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 which appears random and which has a very long cycle.
A n-bit LFSR is a n-bit length shift register with feedback to its input. The feedback is formed by XORing or XNORing the outputs of selected stages of the shift register - referred to as 'taps' - and then inputting this to the least significant bit (stage 0). Each stage has a common clock. The 'linear' part of the term 'LFSR' derives from the fact that XOR and XNOR are linear functions. An example of a 5-bit LFSR is shown below:
This has taps at stages 1 and 4 with XOR feedback. Here, the LS bit of the shift register is, by convention, shown at the left hand side of the shift register, with output being taken from the MS bit at the right hand side. It will produce a pseudorandom sequence of length 2n-1 states (where n is the number of stages) if the LFSR is of maximal length. The sequence will then repeat from the initial state for as long as the LFSR is clocked.
Applications
LFSRs can be implemented in hardware, and this makes them useful in applications that require very fast generation of a pseudo-random sequence, such as direct-sequence spread spectrum radio. LFSRs have also been used for generating an approximation of white noise in various programmable sound generators.
The Global Positioning System uses an LFSR to rapidly transmit a sequence that indicates high-precision relative time offsets.
Uses as counters
The repeating sequence of states of an LFSR allows it to be used as a clock divider, or as a counter when a non-binary sequence is acceptable as is often the case where computer index or framing locations need to be machine-readable. LFSR counters have simpler feedback logic than natural binary counters or Gray code counters, and therefore can operate at higher clock rates. However it is necessary to ensure that the LFSR never enters an all-zeros state, for example by presetting it at start-up to any other state in the sequence.
Uses in cryptography
LFSRs have long been used as pseudo-random number generators for use in stream ciphers (especially in military cryptography), due to the ease of construction from simple electro-mechanical or electronic circuits, long periods, and very uniformly distributed output streams. However, an LFSR is a linear system, leading to fairly easy cryptanalysis. For example, given a stretch of known plaintext and corresponding ciphertext, an attacker can intercept and recover a stretch of LFSR output stream used in the system described, and from that stretch of the output stream can construct an LFSR of minimal size that simulates the intended receiver. This LFSR can then be fed the intercepted stretch of output stream to recover the remaining plaintext.
Three general methods are employed to reduce this problem in LFSR-based stream ciphers:
• Non-linear combination of several bits from the LFSR state.
• Non-linear combination of the output bits of two or more LFSRs.
• Irregular clocking of the LFSR, as in the alternating step generator.
Uses in digital broadcasting and communications
To prevent short repeating sequences (e.g., runs of 0's or 1's) from forming spectral lines that may complicate symbol tracking at the receiver or interfere with other transmissions, linear feedback registers are often used to "randomize" the transmitted bit stream. This randomization is removed at the receiver after demodulation. When the LFSR runs at the same rate as the transmitted symbol stream, this technique is referred to as scrambling. When the LFSR runs considerably faster than the symbol stream, expanding the bandwidth of the transmitted signal, this is direct-sequence spread spectrum.
Digital broadcasting systems that use linear feedback registers:
• ATSC Standards (digital TV transmission system – North America)
• DAB (Digital Audio Broadcasting system – for radio)
• DVB-T (digital TV transmission system – Europe, Australia, parts of Asia)
• NICAM (digital audio system for television)
Other digital communications systems using LFSRs:
• IBS (INTELSAT business service)
• IDR (Intermediate Data Rate service)
• SDI (Serial Digital Interface transmission)
• Data transfer over PSTN (according to the ITU-T V-series recommendations)
• CDMA (Code Division Multiple Access) cellular telephony
• 100BASE-T2 "fast" Ethernet scrambles bits using an LFSR
• 1000BASE-T Ethernet, the most common form of Gigabit Ethernet, scrambles bits using an LFSR
• PCI Express 3.0
• USB 3.0
• IEEE 802.11a scrambles bits using an LFSR