2 clarified similarity of this to gaussian elimination

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$.

First, fix the length of the words we are talking about to $n$ bits.

The dictionary $A$ is a set of $n$-bit long words $A=${$a_1,a_2,...a_m$}, $a_i \in${$0,1$}${}^n$.

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$.

It may make sense given a dictionary $A$ of $n$-bit length words to test 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

• $C=${$c_1, c_2, ..., c_{n}$}

• such that {$c_m = d_n d_{n-1}...d_2 d_1$} where

• $d_j=1$ if $j=m$, and
• $d_j=0$ if $j\ne m$

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.

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.

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$.

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.

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.

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$ XOR $Y_3$, and $Y_5 = Y_1$ XOR $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.

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.

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.

1

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$.

First, fix the length of the words we are talking about to $n$ bits.

The dictionary $A$ is a set of $n$-bit long words $A=${$a_1,a_2,...a_m$}, $a_i \in${$0,1$}${}^n$.

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$.

It may make sense given a dictionary $A$ of $n$-bit length words to test 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

• $C=${$c_1, c_2, ..., c_{n}$}

• such that {$c_m = d_n d_{n-1}...d_2 d_1$} where

• $d_j=1$ if $j=m$, and
• $d_j=0$ if $j\ne m$

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.

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.

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$.

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.

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.

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$ XOR $Y_3$, and $Y_5 = Y_1$ XOR $Y_4$. It is not possible to generate the bit patterns $a1cd$, where $a,c,d \in${0,1} using alphabet $Y$.