Creating M-sequences

M-sequences are a special class of de Bruijn sequences.

An m-sequence is a N element pseudonoise sequence of numbers belonging to Z/pZ with the following properties:

1. The length, N, is p^k-1 for any k, integer.
2. With respect to any shift less than N, the autocorrelation of the sequence is equal to exactly zero except if p>2, then the second half of the sequence is the exact negative of the 1st half of the sequence.
3. The sequence is kth order counterbalanced.
   • Counterbalancing means that each label in the sequence appears k elements before or k elements after each other label in the sequence an identical number of times. Another phrasing of this is that every k-tuple of elements is present other than the k-tuple of all zeros.

The draw of the autocorrelation property is the fact that if each label is a stimulus in an fMRI, the sequence will seem random to the observer. Also, the BOLD signal can be paired with the actual stimulus present rather than be effected by the correlation between the stimuli.

The counterbalancing properties serve two purposes. First, if the researchers wish to examine the effect of contrast between two stimuli, the sequence must be 1st order counterbalanced so that the subject sees each contrast the same number of times. Second, counterbalancing controls for carry over effects.

• Note: In m-sequences used for fMRI, the label 0 represents the blank stimulus.

1. For any q which is relatively prime to N, if you choose every qth element in the sequence until the length of the new sequence is N, the resulting sequence is also an m-sequence. When choosing, clearly one must imagine that the m-sequence has a period of N and therefore has a correlation of 1 with respect to the shift of N.
2. Another m-sequence can also be created by adding a shifted version of the original sequence to the orignal sequence, mod p. This is equivalent to simply shifting the sequence.

There is a m-file which was created by Giedrius Buracas (2). This is available online at:
http://www.cnl.salk.edu/giedrius/professional/m-seqs/msequences.htm
or available here at
mseq.m

In order to create an m-sequence where p= 2, 3, or 5 and k is a reasonable size, the input for this function is mseq(p,k). This will output a m-sequence of the correct length and counterbalancing.

M-sequences can be generated by primitive polynomials of the k splitting field of GF(p), more simply known as polynomials with coefficients in Z/pZ. I will call this field SP. A primitive polynomial is a polynomial such that its order is the order of SP, thus it can cyclically generate SP. Now imagine that the coefficients of this polynomial are stripped out to be the beginning k elements of a sequence. These coefficients are then added, mod p, by the original primitive polynomial, which we can now call a Shift Register Generator. This will create an ordering of all possible k-tuples of elements because the primitive polynomial's powers are all the elements SP. The coefficients to these polynomials are all the possible k-tuples. Below is a simple graphic (3) displaying this process:

<center> <img src=http://upload.wikimedia.org/wikipedia/commons/9/99/Lfsr.gif> </center>

The key to creation of a m-sequence is the choice of p, which is subject to limitations. In order for SP to be a field, Z/pZ must be a field. This means that p must be prime. If SP is not a field, there is no element of SP that can cyclically generate SP, therefore no primitive polynomial exists. Clearly, no m-sequence can then be created using the same method.

In order to create an pseudo-m-sequence whose elements belong to the ring Z/qZ one can do so through one of the following methods. Note that these sequences are not actually m-sequences but are approximations of these sequences. Thus, the properties listed above, especially relating to using a base m-sequence to create many other m-sequences, do not hold.

This method capitalizes on the second resulting useful property listed above. The steps are listed below:

1. Take a base m-sequence of sufficient length, multiply it by some integer, a, and shift the sequence linearly. The length chosen should be longer than the theoretical length of an m-sequence with parameters q and k.
2. Add the modified sequence to the original sequence.
3. Rinse and Repeat to get the correct number of element types.
4. Possibly relabel element types so that they belong to Z/qZ.
5. Test to see which useful properties were maintained.

The choice of a is specific. One must choose a such that when the two sequences are added, no element type will be created by two different sums. If a=2, and a ternary base sequence is used, [0 1 2] + [0 2 4] will generate [0 1 2 2 3 4 4 5 6], thus the sequence will have too many 2's and 4's and be unbalanced.

This method can generate perfectly counterbalanced sequences and maintains some of the autocorrelation properties. The correlation with respect to most shifts will be zero, but at a small number of points, correlation will be present. The choice of shift will effect both these properties.

<blockquote> Example: Z/9Z with first and second order counterbalancing

1. Starting with base m-sequence, p=3 and k=6, the sequence was multiplied by 3 and shifted by +2 to yield a sequence of [0 3 6].
2. The sequence was then added to the original sequence so that a sequence of [0 1 2 3 4 5 6 7 8] was generated.

This shift maintained first and second order counterbalancing. The sum of the absolute value of its autocorrelation is 3.78. </blockquote>

Much thanks is given to Giedrius Buracas for guidance using this method.

• This method creates a messier m-sequence and is generally not recommended for use unless the additive method fails.

In this method, a mapping from a real m-sequence to the desired m-sequence is made in this way: <center> original m-sequence &rarr new m-sequence <br> [0 1] &rarr 5 </center> <br>

Clearly, this method is limited by the number of possible n-tuples in the base sequence. Also, one must chose from n-tuples within the same non-shifted base m-sequence. Paired tuples between m-sequences yield worse results. One must also keep in mind that the zero k-tuple is also omitted in the original m-sequence.<br> Also, one must choose the n-tuples so that they are independent of any n-tuple around it. For example, for second order counterbalancing, the 2-tuple must be [0 x 1] where x is irrelevant to the map. Generally, a minimum of cb-1 placeholders are needed if cb is the order of counterbalancing desired. Other types of n-tuple offsets are possible.

This method must again be tested to see to what extent these sequences have the properties of m-sequences. A first and second order counterbalanced sequence has been found. The sum of the absolute value of its autocorrelation is 16.

1. Davies, WDT (1970) System Identification for Self Adaptive Control. Wiley-Ineterscience: New York. (44-132).
2. Giedrius T. Buracas, SNL-B, Salk Institute. Register values are taken from: WDT Davies, System Identification for self-adaptive control. Wiley-Interscience, 1970. When using mseq code for design of FMRI experiments, please, cite: G.T.Buracas & G.M.Boynton (2002) Efficient Design of Event-Related fMRI Experiments Using M-sequences. NeuroImage, 16, 801-813.
3. SRG figure is a public domain image. For more information on it, see: http://en.wikipedia.org/wiki/Image:Lfsr.gif
4. Giedrius Buracas' website and his powerpoint presentation about m-sequences and fMRI
5. Use of m-sequences in continuous carry-over fMRI experiments

• Buracas m-sequence generator p=2, 3,or 5.:
  mseq.m
• Buracas m-sequence generator for any base ≤31 by search:
  mseqSearch.m
• Testing For Counterbalancing and Autocorrelation:
  mtest.m
• Additive Shift for q=9:
  mseqburmeth.m
• Additive Shift for q=9 iterative testing for least correlated 2nd order counterbalanced sequence:
  mseqburitertest.m
• Finding 8th degree Primitive Polynomials, mod 9:
  primpoly9.m
  • Note: none exist for mod 9, but this can be used as a template for finding other primitive polynomials for different cases.
• Informative N-Tuples:
  mseqgen.m

Example of a 9-level m-sequence:

0 0 3 0 1 6 0 6 3 2 4 6 3 3 4 7 7 3 0 2 6 0 4 3 1 5 6 8 1 5 8 8 1 7 8 6 0 7 3 2 2 6 5 4 4 0 5 4 1 0 4 7 1 3 1 8 6 6 7 5 5 2 0 2 5 0 3 2 1 6 5 6 4 1 4 4 8 5 3 6 0 8 3 2 6 6 4 5 4 5 0 5 2 1 2 5 7 3 1 2 6 7 4 5 2 5 2 3 2 3 6 3 8 4 8 6 3 7 4 8 2 3 8 3 8 6 8 7 5 7 2 1 1 5 7 8 1 0 8 7 2 7 1 4 1 8 4 6 6 3 5 4 7 0 3 1 1 6 7 6 5 0 4 2 1 4 5 8 5 1 6 2 6 3 4 4 7 5 3 2 0 6 5 2 4 2 3 4 3 7 5 8 2 1 8 5 6 6 1 5 3 8 0 8 8 2 7 8 4 0 6 4 2 4 4 3 5 5 7 0 1 1 0 7 7 2 0 1 5 0 8 2 2 8 5 4 6 0 3 3 1 7 6 6 0 5 3 1 0 6 7 2 5 1 3 2 8 6 4 7 4 3 2 5 6 3 1 4 6 8 3 5 6 7 1 5 1 8 2 6 8 4 5 6 5 1 4 2 8 4 4 6 5 3 4 0 7 4 2 2 4 5 3 5 0 7 2 2 1 5 5 8 0 1 8 0 6 8 2 5 8 3 1 6 6 6 5 5 4 0 0 4 0 1 4 0 8 4 2 6 4 4 4 5 5 5 0 0 2 0 0 5 0 1 2 0 7 5 2 2 2 5 5 3 0 0 6 0 2 3 0 3 6 1 8 3 6 6 8 5 5 6 0 1 3 0 8 6 2 7 3 4 2 7 4 4 2 5 4 3 0 5 6 1 1 3 7 8 8 0 7 8 2 0 8 5 2 6 2 4 3 3 5 7 7 1 0 1 7 0 6 1 2 3 7 3 8 2 8 8 4 7 6 3 0 4 6 1 3 3 8 7 8 7 0 7 1 2 1 7 5 6 2 1 3 5 8 7 1 7 1 6 1 6 3 6 4 8 4 3 6 5 8 4 1 6 4 6 4 3 4 5 7 5 1 2 2 7 5 4 2 0 4 5 1 5 2 8 2 4 8 3 3 6 7 8 5 0 6 2 2 3 5 3 7 0 8 1 2 8 7 4 7 2 3 1 3 6 8 8 5 7 6 1 0 3 7 1 8 1 6 8 6 5 7 4 1 2 4 7 3 3 2 7 6 4 0 4 4 1 5 4 8 0 3 8 1 8 8 6 7 7 5 0 2 2 0 5 5 1 0 2 7 0 4 1 1 4 7 8 3 0 6 6 2 5 3 3 0 7 6 2 0 3 5 1 7 2 6 1 4 3 8 5 8 6 1 7 3 6 2 8 3 4 6 7 3 5 2 7 2 4 1 3 4 8 7 3 7 2 8 1 4 8 8 3 7 6 8 0 5 8 1 1 8 7 6 7 0 5 1 1 2 7 7 4 0 2 4 0 3 4 1 7 4 6 2 3 3 3 7 7 8 0 0 8 0 2 8 0 4 8 1 3 8 8 8 7 7 7 0 0 1 0 0 7 0 2 1 0 5 7 1 1 1 7 7 6 

Page Created by Wesley Kerr