How do I optimize a set of sub-lists which can combine to recreate higher level lists?
I am writing a function which XORs 32 boolean variables to produce a 32 bit output. To this end I have 32 lists of boolean variables (the lists have between 12 and 17 elements). Every variable in list 0 can be XOR'd together to produce bit 0 of the output. Every variable in list 1 can be XOR'd to produce bit 1 of the output etc.
There are common variables between lists and I would like to find the optimum selection of sub-lists which combine the variables to reduce the total number of XORs. The hierarchy is limited to 2 deep so we can only have one layer of sub-lists.
Here is an example problem:
out_0: i_1, i_2, i_3, i_4, i_5, i_6
out_1: i_2, i_4, i_5, i_6, i_7, i_8
out_2: i_1, i_4, i_5, i_6, i_9
The simple solution just XORs every variable in each list. This solution requires 14 XORs:
out_0 = i_1 ⊕ i_2 ⊕ i_3 ⊕ i_4 ⊕ i_5 ⊕ i_6
out_1 = i_2 ⊕ i_4 ⊕ i_5 ⊕ i_6 ⊕ i_7 ⊕ i_8
out_2 = i_1 ⊕ i_4 ⊕ i_5 ⊕ i_6 ⊕ i_9
The associative property of the XOR function means we can improve on the simple solution by forming sub-lists which are included in the top level lists as required. 864
This solution requires 11 XORs:
x_0 = i_1 ⊕ i_6
x_1 = i_4 ⊕ i_5
out_0 = x_0 ⊕ x_1 ⊕ i_2 ⊕ i_3
out_1 = x_1 ⊕ i_2 ⊕ i_6 ⊕ i_7 ⊕ i_8
out_2 = x_0 ⊕ x_1 ⊕ i_9
This is an improvement but there are other sub-lists which may result in fewer XORs. I would like a method of determining the optimum choice of sub-lists.
It is also worth noting that when an input is XOR'd with itself it cancels. Therefore we can add redundant terms to maximize the utility of a sub-list. The following solution which requires 10 XORs would work:
x_3 = i_1 ⊕ i_2 ⊕ i_4 ⊕ i_5 ⊕ i_6
out_0 = x_3 ⊕ i_3
out_1 = x_3 ⊕ i_1 ⊕ i_7 ⊕ i_8 [i_1 included to cancel the i_1 inside x_3]
out_2 = x_3 ⊕ i_2 ⊕ i_9 [i_2 included to cancel the i_2 inside x_3]
I have run a simple greedy optimization which always selects the group which provides the greatest reduction in the number of XORs. For my system (a parallel CRC32 implementation) this optimization reduces the number of XORs by 37%. My optimization does not add redundant terms. Is there a better optimization I can run to find the global optimum? 946