﻿ Linear feedback shift register - Wikipedia, the free encyclopedia

Linear feedback shift register

From Wikipedia, the free encyclopedia

Jump to: navigation, search






[edit] How it works

The list of the bits positions that affect the next state is called the tap sequence. In the diagram below, the sequence is [16,14,13,11].

  • The outputs that influence the input are called taps (blue in the diagram below).
  • A maximal LFSR produces an n-sequence (i.e. cycles through all possible 2n − 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.



x11 + x13 + x14 + x16 + 1.


  • The LFSR will only be maximal if the number of taps is even
  • The tap values in a maximal LFSR will be relatively prime
  • There can be more than one maximal tap sequence for a given LFSR length
  • Once one maximal tap sequence has been found, another automatically follows. If the tap sequence, in an n-bit LFSR, is [n,A,B,C,0], where the 0 corresponds to the x0 = 1 term, then the corresponding 'mirror' sequence is [n,n-C,n-B,n-A,0]. So the tap sequence [32,3,2,0] has as its counterpart [32,30,29,0]. Both give a maximal sequence.

[edit] Output-stream properties

  • Ones and zeroes occur in 'runs'. The output stream 0110100, for example consists of five runs of lengths 1,2,1,1,2, in order. In one period of a maximal LFSR, 2n − 1 runs occur (for example, a six bit LFSR will have 32 runs). Exactly 1 / 2 of these runs will be one bit long, 1 / 4 will be two bits long, up to a single run of zeroes n − 1 bits long, and a single run of ones n bits long. This same property is statistically expected in a truly random sequence.
  • LFSR outputs streams are deterministic. If you know the present state, you can predict the next state. This is not possible with truly random events such as nuclear decay.
  • The output stream is reversible; an LFSR with mirrored tap sequence will cycle through the states in reverse order.

[edit] A drop in replacement for Gray Code counters

Some applications need to mark individual locations along a certain distance with unique values. For example, most tape measures mark each inch or centimeter with a unique number using the decimal numeral system. When computer index or framing locations need to be machine-readable, they are often marked using a LFSR sequence, because LFSR counters are simpler and faster than any other kind of binary counter. LFSRs are faster than natural binary counters and Gray code counters. Given an output sequence you can construct a LFSR of minimal size by using the Berlekamp-Massey algorithm.

[edit] Galois LFSRs

A Galois LFSR, or a LFSR in Galois configuration, is an alternate structure that can generate the same sequences as a conventional LFSR.

In Galois configuration, when the system is clocked, bits that are not taps are shifted as normal. The taps, on the other hand, are XOR'd with the new output, which also becomes the new input. To generate the same sequence, the order of the taps is the reverse of the order for the conventional LFSR.

  • Galois LFSRs do not concatenate every tap to produce the new input (the XOR'ing is done within the LFSR and no XOR's are run in serial, therefore the propagation times are reduced to that of one XOR rather than a whole chain), thus it is possible for each tap to be computed in parallel, increasing the speed of execution.

Image:Galois LFSR.png

C code example of 32-bit maximal period Galois LFSR:

 unsigned int lfsr = 1; 
   lfsr = (lfsr >> 1) ^ (-(signed int)(lfsr & 1) & 0xd0000001u); /* taps 32 31 29 1 */

[edit] Applications


The Global Positioning System uses a LFSR to rapidly transmit a sequence that indicates high-precision relative time offsets. The Nintendo Entertainment System video game console also has a LFSR as part of its sound system. ([1])

[edit] Uses 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

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

[edit] Uses in digital broadcasting and communications



Digital broadcasting systems that use linear feedback registers

Other digital communications systems using LFSR:

  • IBS (INTELSAT business service)
  • IDR (Intermedaite Data Rate service)
  • SDI (Serial Digital Interface transmission)
  • Data transfer over PSTN (according to the ITU-T V-series recommendations)

[edit] See also

[edit] External links

Personal tools