Building-Block Identification by Simultaneity Matrix

摘要

We propose a BB identification by simultaneity matrix (BISM) algorithm. The input is a set of l-bit solutions denoted by S. The number of solutions is denoted by n = |S|. The output is a partition of bit positions {0,... ,l-1}. The BISM is composed of Simultaneity-Matrix-Construction and Fine-Valid-Partition algorithms. Algorithm SMC is outlined as follows (ay denotes the matrix element at row i and column j, Count_S~(ab)(i, j) = |{x ∈ {0,... , n - 1} : s_x[i] = a and s_x[j] = b}| for all (i,j) ∈{0,... ,l-1}~2, (a,b) ∈ {0,1}~2, s_x[i] denotes the ith bit of xth solution, Random(0,1) gives a real random number between 0 and 1).