🚀 go-pugleaf

Here is a problem in mixed field arithmetic.  In what follows, + will
denote addition over the field of reals, and | will denote addition
over GF(2).  Multiplication is over the reals.

consider a system of equations such as

a_1 c_0               + a_2 c_3               = s_0
a_1 c_1               + a_2 c_4               = s_1
a_1 c_2               + a_2 c_5               = s_2
a_1 (c_0 | c_1)       + a_2 (c_3 | c_5)       = s_3
a_1 (c_1 | c_2)       + a_2 (c_3 | c_4 | c_5) = s_4
a_1 (c_0 | c_1 | c_2) + a_2 (c_3 | c_5)       = s_5
a_1 (c_0 | c_2)       + a_2 (c_4 | c_5)       = s_6

where a_1 and a_2 are real and known, the s_i are real and known, and
the unknowns c_i are in GF(2) (that is, either 0 or 1).  Although the
problem has been written similar to a set of linear equations, it is
easy to verify that this is not a linear set of equations.

1) Find the set of c_i that satisfy this set of equations.  For this
problem, it can be accomplished simply by combinatorial search
techniques.  However, there are larger problems of interest similar to
for which searching is impractical.

2) Now consider the case of finding the "best" solution to the set of
equations where the equality does not hold -- there is unknown "noise"
in the equations:

a_1 c_0               + a_2 c_3               = s_0 + n_0
a_1 c_1               + a_2 c_4               = s_1 + n_1
a_1 c_2               + a_2 c_5               = s_2 + n_2
a_1 (c_0 | c_1)       + a_2 (c_3 | c_5)       = s_3 + n_3
a_1 (c_1 | c_2)       + a_2 (c_3 | c_4 | c_5) = s_4 + n_4
a_1 (c_0 | c_1 | c_2) + a_2 (c_3 | c_5)       = s_5 + n_5
a_1 (c_0 | c_2)       + a_2 (c_4 | c_5)       = s_6 + n_6

As before, a_i and s_i are known, but the noise n_i is not known.
Find the best (perhaps in least squares sense) set of c_i in GF(2).

What would be nice would be to have an algebra for these mixed field
problems, from which exact and pseudo-inverse solutions coulde be
obtained.

Any suggestions, comments, references, etc. would be greatly
appreciated.


Todd Moon
Electrical Engineering Dept., UMC 4120
Utah State University
Logan, UT  84322
801 750 2970
moon@moon.ee.usu.edu