FACTOID # 20: Statistically, Delaware bears more cost of the US Military than any other state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > LFSR

A linear feedback shift register is a shift register whose input is the exclusive-or of some of its outputs. The outputs that influence the input are called taps. A maximal LFSR produces an n-sequence, unless it contains all zeros. The tap sequence of an LFSR can be represented as a polynomial mod 2 - called the feedback polynomial. For example, if the taps are at positions 17 and 15 (as below), the polynomial is x17 + x15 + 1. If this polynomial is primitive, then the LFSR is maximal.

Image:LFSR-17bit.png

LFSR's 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.


Given an output sequence you can construct a LFSR of minimal size by using the Berlekamp-Massey algorithm


A Galois LFSR, or a LFSR in Galois configuration is a variation on typical LFSR design. In Galois configuration, the output is individually xor'ed with each tap, before becoming the new input. Galois LFSRs do not concatenate every tap to produce the new input, thus it is possible for each tap to be computed in parallel, increasing the speed of execution.


Use in cryptography

LFSRs have long been used as a pseudo-random number generator for use in stream ciphers (especially in military cryptography), due to the ease of construction from simple electromechanical or electronic circuits, long periods, and very uniformly distributed outputs. However the outputs of LFSRs are completely linear, leading to fairly easy cryptanalysis. 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 outputs of two or more LFSRs; or
  • Irregular clocking of the LFSR.

Important LFSR-based stream ciphers include A5/1, A5/2, and the shrinking generator.


External links

  • http://www.maxim-ic.com/appnotes.cfm/appnote_number/1743
  • http://www.ee.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html

  Results from FactBites:
 
Linear Feedback Shift Registers (1687 words)
By convention, the output bit of an LFSR that is n bits long is the nth bit; the input bit of an LFSR is bit 1.
By definition, the period of an LFSR is the length of the output stream before it repeats.
One characteristic of the LFSR output not shared with a random stream is that the LFSR stream is deterministic.
Linear feedback shift register - Wikipedia, the free encyclopedia (1063 words)
The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the sequence of values produced by the register is completely determined by its current (or previous) state.
LFSR's 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 long been used as a pseudo-random number generator for use in stream ciphers (especially in military cryptography), due to the ease of construction from simple electromechanical or electronic circuits, long periods, and very uniformly distributed outputs.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m