How to find which subset of bitfields xor to another bitfield? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T01:19:27Z http://mathoverflow.net/feeds/question/41036 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield How to find which subset of bitfields xor to another bitfield? Bram Cohen 2010-10-04T16:15:04Z 2010-10-04T19:02:51Z <p>I have a somewhat coding-oriented problem. I have a bunch of bitfields and would like to calculate what subset of them to xor together to achieve a certain other bitfield, or if there isn't a way to do it discover that no such subset exists.</p> <p>I'd like to do this using a free library, rather than original code, and I'd strongly prefer something with Python bindings (using Python's built-in math libraries would be acceptable as well, but I want to port this to multiple languages eventually). Also it would be good to not take the memory hit of having to expand each bit to its own byte.</p> <p>Some further clarification: I only need a single solution. My matrices are the opposite of sparse. I'm very interested in keeping the runtime to an absolute minimum, so using algorithmically fancy methods for inverting matrices is strongly preferred. Also, it's very important that the specific given bitfield be the one outputted, so a technique which just finds a subset which xor to 0 doesn't quite cut it.</p> <p>And I'm generally aware of gaussian elimination. I'm trying to avoid doing this from scratch!</p> <p>cross-posted to stackoverflow, because it's unclear where the right place for this question is - <a href="http://stackoverflow.com/questions/3855479/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield">http://stackoverflow.com/questions/3855479/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield</a></p> http://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield/41049#41049 Answer by Apurva for How to find which subset of bitfields xor to another bitfield? Apurva 2010-10-04T18:57:00Z 2010-10-04T19:02:51Z <p>The ways to solve it may vary based on which varies more frequently: the dictionary $A$ used to generate the wanted bitstring $B$, or the bitstring $B$.</p> <p>First, fix the length of the words we are talking about to $n$ bits.</p> <p>The dictionary $A$ is a set of $n$-bit long words $A=${$a_1,a_2,...a_m$}, $a_i \in${$0,1$}${}^n$.</p> <p>Given an insufficient dictionary, it may not be possible to generate all possible bit patterns of length $n$. For example, if $C$={ 1000, 0011, 0001}, then it is impossible for the dictionary $C$ to generate the bit-pattern $x_4 1 x_2 x_1$, a 4-bit string with the $2^2$ value set to $1$.</p> <p>It may make sense given a dictionary $A$ of $n$-bit length words to <strong>test</strong> the dictionary as a viable signal generator by seeing if it is possible to create the "single-bit-on" patterns in the dictionary $C$ defined as</p> <ul> <li><p>$C=${$c_1, c_2, ..., c_{n}$}</p></li> <li><p>such that {$c_m = d_n d_{n-1}...d_2 d_1$} where </p></li> <li>$d_j=1$ if $j=m$, and </li> <li>$d_j=0$ if $j\ne m$</li> </ul> <p>If it is not possible for the dictionary $A$ to generate the dictionary $C$, then there will be certain bit patterns which are not reachable by using words in the dictionary $A$ and the binary-operation XOR.</p> <p>Once a mapping is generated from $A$ to the single-bit-on dictionary $C$, it is a simple task to create the mapping from $A$ to an arbitrary bit pattern, $B$. Take the bits which are on in $B$, and take the mappings which generate those single bits on in $C$, and concatenate them together.</p> <p>An even number of XOR's for any particular bit pattern in $C$ cancel each other out, leaving a single count of whichever elements in $A$ would generate bit-pattern $B$.</p> <p>One quick observation: the dictionary $A$ of $n$-bit long words must contain at least $n$ words for it to be able to generate all possible $n$-bit long strings, and none of them should be linear combinations of the other.</p> <p>For example, the alphabet X={0001, 1000} is too small to be able to generate all possible 4-bit long words, simply from the observation that it only contains two words of 4-bit length.</p> <p>The alphabet Y={0001, 0011, 0010, 1000, 1001} has enough words to possibly span all possible 4-bit length words, however $Y_2 = Y_1$ <strong>XOR</strong> $Y_3$, and $Y_5 = Y_1$ <strong>XOR</strong> $Y_4$. It is not possible to generate the bit patterns $a1cd$, where $a,c,d \in${0,1} using alphabet $Y$. Even though $Y$ is defined as $5$ elements, it really only contains 3 degrees of freedom, as two of the elements can be defined as linear combinations of the others.</p> <p>In other words, using gaussian elimination on your dictionary using XOR as the operation on the right may be the best way to test or assess your dictionary, with the caveat that if your dictionary does not contain at least as many words as there are bits in each word then your dictionary will not suffice to generate all possible bit patterns.</p> <p>It's also possible to think of this as operations of a message being passed along the nodes of an $n$-dimensional hypercube. But that's just a different way of thinking of it.</p>