Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's define a regular bit string as a string which can be represented by repetition of some smaller string (e.g. 01010101 or 001001001 or 11111).

Suppose we have some bit string of length N (N can be large). We can flip up to M bits in this string. Is there a way to calculate how many regular strings can we generate from a given string by flipping up to M bits?

share|improve this question
add comment

2 Answers 2

up vote 0 down vote accepted

Let $p\geqslant 1$ (the period) be such that $N=p\,r$ for some $r$. And let $t$ be a bit-string with $|t|=p$. Then, to generate the bit-string $t^r$ from some bit-string $s$ requires $$d(s,t)=\sum_{i=1}^N|s_i-t_{i\; \bmod\; p}|$$ bits to be flipped.

So the number of regular strings with period $p$ that can be generated by flipping no more than $M\,$ bits of $s$ is $$R(s,p)=\#\{\;t\;:\;|t|=p\;\; \wedge\;\; d(s,t)\leqslant M \;\}.$$ Note that this also counts regular strings with periods that are factors of $p$, so the total number of regular strings that can be generated by flipping no more than $M\,$ bits of $s$ is $$T(s)=\sum_{p<N,\;p|N}\Big(R(s,p)\;-\!\!\sum_{q<p,\;q|p}R(s,q)\Big).$$

The calculation of $d(s,t)$ can be optimised by pre-analysing $s$. For $1\leqslant i\leqslant p$, let

$$e_i(s,p)=\sum_{j=0}^{r-1}s_{jp+i}$$

be the number of $1$-bits in $s$ at position $i$ in the period. To generate a $0$-bit at each position $i$ in the period, $e_i(s,p)$ bits would need flipping at that position, and to generate a $1$-bit, $r-e_i(s,p)$ bits would need flipping. This gives us a faster way of calculating $d(s,t)$: $$d(s,t)=\sum_{i=1}^pe_i(s,p)+t_i(r-2e_i(s,p)).$$

More sophisticated analysis of the $e_i(s,p)$ values would avoid the need to loop through all possible patterns for each period size to get $R(s,p)$.

Obviously if $$\sum_{i=1}^p\textrm{min}\big(e_i(s,p),r-e_i(s,p)\big)>M,$$ then no regular strings with period $p$ can be generated.

share|improve this answer
add comment

You can start by factoring N. Each factor represents a way to divide the string into factors is a way that you can make a regular string. Then by comparing the existing strings to see how many bits must be flipped to make them agree. For example, suppose N=12 and the string is 000110111000. We can factor 12 into 1*12 and see that there are 5 1 bits and 7 0 bits, so to make this a regular string repeating a group of 1 would require flipping 5 bits. If we factor 12 into 3*4 it is currently

0001

1011

1000

By taking the majority vote at each position, we can find a regular string flipping 3 bits, going to 100110011001. You can do the same for each factoring of N.

Added: I get that for repeated substrings of length N/2 or N/3 you would expect to have to flip a minimum of about N/4 bits. For substrings of length N/2, the first and second halves will agree in N/4 positions and you can flip either bit in the other N/4. So you will have about $2^{N/4}$ choices of repeated string. Each additional 2 bits you are allowed to flip lets you choose another position to flip both bits. For substrings of length N/3 you will have only one choice with the minimum number of bits to flip. Each additional bit would allow you to flip two bits at one position instead of one. Once you have three spare bits you could flip a position where the bits agree.

share|improve this answer
    
Yes this is the obvious route. For string of length 12 there will be 2^6 strings with period 6. Some of these strings will require flipping 3 bits, some 4, etc. Let's say M is 5. We need to find how many regular strings can we generate by flipping less than 5 bits. This will be the sum of number of regular strings we generated by flipping 0, 1, 2, 3, and 4 bits. But for N > 30 iterating through all possible regular strings it unfeasible. –  man Oct 6 '11 at 18:37
    
In my example I had lined up the 4 bit patters, but forgot double returns so they didn't show up. You can then look at how many bits need to be flipped. As I said, you need to flip a minimum of 3 in this example, but you could do it with 5 by going to 3*0001, 3*1011, or 3*1000. If you match up the two halves, each place they disagree you have to flip 1. Then you can select as many of the other places to flip 2 as are allowable. –  Ross Millikan Oct 6 '11 at 18:48
    
With 5 you can also go to the 3*0011 in your example. The question is not the strings themselves but how many of them can we generate. For big N testing all possible regular strings is unfeasible. Given M there have to be some way to compute the number of periodic strings we can generate not testing each of them. –  man Oct 6 '11 at 19:01
add comment

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.