Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Maximum length sequences (MLS) are a type of pseudorandom binary sequences with specific properties (see Wikipedia: Maximum length sequence, or m linear feedback shift register. Properties that hold include

  • Window property: A sliding window of length m, passed along an m-sequence for 2m-1 positions, will span every possible m-bit number, except all zeros, once and only once. That is, every state of an m-bit state register will be encountered, with the exception of all zeros.
  • Balance property: The number of "1"s in the sequence is one greater than the number of "0"s.

Is there a similar type of pseudorandom binary sequences known/constructible for which

  • the "Window property" holds, but
  • which are unbalanced, i.e. having p % ones and (100-p)% zeros ?
share|improve this question
1  
Doesn't the fact that each m-bit number appear exactly once forces the sequence to be balanced? (just take the frequency of ones in all non-zero m-bit numbers) –  Or Zuk May 13 '11 at 16:11
    
The name De Bruijn comes to mind. Gerhard "Ask Me About System Design" Paseman, 2011.05.13 –  Gerhard Paseman May 13 '11 at 17:01
    
Could you please explain what "passed along an m-sequence for 2m-1 positions" means? Even if 2m-1 should be $2^m-1$, I am still not totally sure about the meaning. As far as I understand, if this is really just the de Bruijn cycle question up to replacing Euler cycles by Euler walks (because you exclude 0000...0 and do not require the path to be a cycle), I wouldn't be surprised if you get slightly unbalanced strings, but they should not be too far from 50-50 for asymptotical counting reasons. –  darij grinberg May 13 '11 at 17:56

1 Answer 1

It's quite possible for the window property to fail for a ``balanced'' sequence (where 1 more 1's occur than 0's in a period of length $2^n-1$). For example a sequence of length $2^{n}-1$ made up of $2^{n-1}$ consecutive 1's followed by $2^{n-1}-1$ zeroes, taken as periodically repeating will have $2^{n-1}-n+1$ all 1 windows of length $n$ and $2^{n-1}-n+2$ all 0 windows of length $n$ with the remainder being windows of the form $$w_k=\underbrace{1111\cdots1}_{k~times}\underbrace{0000\cdots0}_{n-k~times}$$ for $k=1,2,\ldots,n-2$ and the complement of $w_k$ for $k=1,2,\ldots,n-1.$

The opposite, however is not possible. To see this take a sequence with the window property, and imagine fixing any bit position in the window as the window is slid along a full period of the sequence (with no loss of generality we can take this position to be the leftmost bit in the window, since we can go around the full cycle with any starting position we want in the cyclic sequence) . Now the windows range over the nonzero $n-$tuples over $\{0,1\}$ in a manner so that the consecutive windows are compatible sequences i.e., $$ x_k x_{k+1} \cdots x_{k+n-1}~~~\textrm{is followed by }~~~~x_k x_{k+1} \cdots x_{k+n-1}. $$ Since there is a one to one correspondence between these sequence of windows and the nonzero $n-$tuples by the window property, there is a one to one correspondence inherited by any fixed bit position, say the first, and a collection of $2^{n-1}-1$ 0's and $2^{n-1}$ 1's must be traced by this point by straightforward counting.

Put it another way, any sequence of period $2^n-1$ with the $n-$window property also has the $n-a$window property for any $a=1,2,\ldots, n-1$ and in one period each nonzero $(n-a)-$tuple occurs $2^{a}$ times while the zero $(n-a)-$tuple occurs $2^{a}-1$ times.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.