1
$\begingroup$

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?

2 Answers 2

0

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

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.

0

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.

  • 0
    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.2011-10-06