Maximum Length Sequence Article Index for
Maximum 		Shopping
Maximum 		Website Links For
Maximum 		 

Information About

Maximum Length Sequence
  CATEGORIES ABOUT MAXIMUM LENGTH SEQUENCE
   
pseudorandomness
   
polynomials
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



They are Polynomial Ring s generated using maximal Linear Feedback Shift Register s and are so called because they are Periodic and reproduce every Binary Sequence that can be reproduced by the shift registers (i.e., for m registers they produce a sequence of length 2^{m}-1). They are also sometimes called N-sequence s or m-sequences. Maximum length sequences are Spectrally Flat , with the exception of a zero DC term, and are used instead of Impulse Response s because, being longer, they inject more energy into a system; extracted impulse responses thus have a higher Signal-to-noise Ratio (SNR).


GENERATION OF MAXIMUM LENGTH SEQUENCES


MLS are generated using maximal linear feedback shift registers. An MLS generating system with four shift registers is shown in Fig. 1. This can be expressed using the recursive relation,

:a_3(n+1) = a_0(n) + a_1(n).

Because MLS are periodic and shift registers cycle through every possible binary value (with the exception of the zero vector), registers can be initialized to any state, with the exception of the zero vector.

MLS are inexpensive to implement in hardware or software, and relatively low-order feedback shift registers can generate long sequences; a sequence generated using 20 shift registers is 2^{20}-1 samples long, which is equivalent to approximately 23.8 seconds if played back as audio with a sampling rate of 44.1 kHz.


PROPERTIES OF MAXIMUM LENGTH SEQUENCES


Maximum Length Sequences are Pseudorandom Binary Sequence s and have the following properties.

1. Balance Property.

The number of 1s in the sequence is one greater than the number of 0s in the sequence.

2. Run Property.

Of all the 'runs' in the sequence of each type (i.e. runs consisting of 1s and runs consisting of 0s)
  • One half of the runs are of length 1.

  • One quarter of the runs are of length 2.

  • One eighth of the runs are of length 3.

    • ....


A 'run' is a sub-sequence of 1s or 0s inside the ML that is being concerned. The number of 'runs' is the number of such subsequences.

3. Correlation Property.

The Autocorrelation and Cross-correlation of the ML sequence is periodic and binary valued.


Example

Take the following sequence which is 31 bits long:

0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1

1. Number of 1s = 16, number of 0s = 15; therefore 'balance property' is fulfilled.

2. runs consisting of 0s = 8

  • 8 = 4)


  • 8 = 2)


  • 8 = 1)


  • 8 = 0.5 => 1)



runs consisting of 1s = 8

  • 8 = 4)


  • 8 = 2)


  • 8 = 1)


  • 8 = 0.5)


  • 8 = 0.25 => 1)



EXTRACTION OF IMPULSE RESPONSES


If a Linear Time Invariant (LTI) system's impulse response is to be measured using a MLS, the response can be extracted from the measured system output ''y''(''n'') by taking its cross-correlation with the MLS sequence. This is because the Autocorrelation of a MLS is 1 for zero-lag, and nearly zero (−1/''N'' where ''N'' is the sequence length) for all other lags; in other words, the autocorrelation of the MLS can be said to approach unit impulse function as MLS sequence length increases.

If the impulse response of a system is ''h''(''n'') and the MLS is ''s''(''n''), then

  • s)(n).\,


Taking the cross-correlation with respect to ''s''(''n'') of both sides,

  • {\phi}_{ss}


and assuming that φ''ss'' is an impulse (valid for long sequences)

:h(n) = {\phi}_{sy}.\,



SEE ALSO