Welcome to MathOverflow

Question

0

1

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 ?

flag	asked May 13 2011 at 15:54 heckenpenner-rot 1

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 2011 at 16:11

The name De Bruijn comes to mind. Gerhard "Ask Me About System Design" Paseman, 2011.05.13 – Gerhard Paseman May 13 2011 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 2011 at 17:56

“Unbalanced” maximum length sequences?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.