0
$\begingroup$

I'm sorry, if I got the wrong expressions, I'm gonna describe it:

I got bit-strings of n bits with k ones and want to minimize "collision" The collision count of two strings $a=(a_1,...,a_n), b=(b_1,...,b_n)$ is defined by $Coll(a,b):=\sum_{i=1}^n a_i b_i$ and $a,b$ are said to "collide", if $Coll(a,b)>0$. Of course this can be generalized to higher number of strings.

Now I'm looking for a "shift" $s$ (depending on $a$), that minimizes the shifted self-collision $\sum_{i=1}^n a_{i+s}a_i $ and (if possible) the $m$-fold shifted self-collision $\sum_{i=1}^n\prod_{j=1}^m a_{i+js} $ ($i+s>n$ may be replaced by $i^\prime\in\{1,...,n\}$ with $i^\prime\equiv i+s$ (mod n))

Now my questions are:

  1. Is this solvable faster than $O(n²)$? (computing the collision count for a shift needs $O(n)$ and there are at most $n$ shifts
  2. I'm coding my bit-strings by length of consecutive 0s between two 1s $(10011 \rightsquigarrow 200 )$. Does this help to compute the collision count without translating back to the bit-string?
  3. Is there already any theory on that?
  • 0
    On 2.: Yes, it helps if the bit strings are sparse; you can just keep track of the numbers of zeros left in the current run in both strings, and when they reach $0$ simultaneously you have a collision. If they're not sparse, this will be inefficient compared to just ANDing them a word at a time and looking up the bit counts in a table.2012-08-10

1 Answers 1

1

For the first question: Your "shifted self collision" is the same as a circular autocorrelation, so it can be computed using Fourier transform, which is $O(n \log(n))$

For example (Matlab/Octave)

 x=[1, 1, 0, 1, 0 ,0  ,0 ,0 ];  y=round(abs(ifft(abs(fft(x)).^2)))  y =      3   1   1   1   0   1   1   1