MATLAB: How to Generate Array of mimimum consecutive bits (1’s or 0’s)

consecutive 1's or 0's

As a part of my Project. I would like to generate all possible combinations of 48 bit binary sequence with minimum consecutive bits. for eg : if min consecutive bits is 4, then it should generate all combinations of 48 bit binary sequences with consecutive 0's or 1's should be greater than 4. eg: 00000111100000…… etc or 11110000011111100000…..and so on. I tried different methods using normal Loop operations but its takes infinitely long time (counting 1's or 0's from 2^0 to 2^48). is there any function which i could use to implement this idea. It would be really helpful. Thanks a lot.

Best Answer

I think Prasad needs to think carefully about his problem, IF it requires all such sequences.
Lets look at a much smaller problem, for only 16 bit sequences. Assume that each constant subsequence is at least 4 bits long. The first subsequence may be composed of zeros, or ones, so clearly WLOG we can find all sequences where the first subsequence is composed of zeros.
Thus, if we have the sequence 0000111100001111, there is a mirrored sequence 1111000011110000 that corresponds to it. So we need only find those that start with zeros, then we can mirror them all at once.
A good way to think of the problem is NOT in terms of sequences of bits, but in terms of where the transitions occur. There are fewer transitions than bits, so this reduces the problem complexity a little.
Next, those transitions can be viewed as integer partitions of 16, where no element in the partition is less than 4 (assuming the minimum sub-sequence length is 4.) That is, we can write
16 = 2 + 3 + 4 + 5 + 2
which would correspond to the sequence of bits
0011100001111100
(Think about how this correspondence works, and why it is a simplification of the problem.)
Of course, that sequence does not satisfy the minimum length subsequence requirement. Using my partitions function (found on the file exchange)
partitions(16,4:16)
ans =
    4     0     0     0     0     0     0     0     0     0     0     0     0
    0     2     1     0     0     0     0     0     0     0     0     0     0
    1     0     2     0     0     0     0     0     0     0     0     0     0
    1     1     0     1     0     0     0     0     0     0     0     0     0
    2     0     0     0     1     0     0     0     0     0     0     0     0
    0     0     0     0     2     0     0     0     0     0     0     0     0
    0     0     0     1     0     1     0     0     0     0     0     0     0
    0     0     1     0     0     0     1     0     0     0     0     0     0
    0     1     0     0     0     0     0     1     0     0     0     0     0
    1     0     0     0     0     0     0     0     1     0     0     0     0
    0     0     0     0     0     0     0     0     0     0     0     0     1
Thus, the first row says we can write
16 = 4 + 4 + 4 + 4
thus as 4 fours. That implies the 16 bit sequence 0000111100001111, which except for its mirror, is the only on of that exact type. The second row tells us it can also be written as
16 = 5 + 5 + 6
Of course, there are 3 ways to permute those numbers, so we also have
16 = 5 + 6 + 5
16 = 6 + 5 + 5
Each of those permuted partitions corresponds to a unique 16 bit sequence, so we would have
0000000000111111
0000011111100000
0000001111100000
and then the mirror image of each of those sequences.
It is now fairly simple to generate all such 16 bit sequences from the call to partitions above. To do the same thing for 48 bit sequences will take a large amount of memory though, and MUCH CPU time, even with the tricks I have shown here.
Related Question