🚀 go-pugleaf

In <MOON.92Sep1110158@moon.ee.usu.edu> moon@moon.ee.usu.edu (Todd Moon) writes:


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

For equations of the form:

(E_i) a_1 f_i(C) + a_2 g_i(C) = s_i, we have:

If (1)  all of a_1, a_2, a_1+a_2, and a_1-a_2 are nonzero, then E_i
translates to f_i(C) = t_i_1 and g_i(C) = t_i_2.

If (2) a_2 = 0 , then E_i translates to f_i(C) = t_i

If (3) a_2 = a_1, then E_i translate to f_i(C) = 0 and g_i(C) = 0; or
f_i(C) | g_i(C) = 1; or f_i(C) = 1 and g_i(C) = 1

If (4) a_2 = -a_1, then E_i translates to f_i(C) = 0 and g_i(C) = 1; or
f_i(C) | g_i(C) = 0; or f_i(C) = 1 and g_i(C) = 0

If (5) a_1 = a_2 == 0 , then the equations do not depend upon the c's.

In any of these cases, the (E_i) reduce to a linear set of equations over
GF(2), which can be solved by the usual methods.

(This method fails if we have a_1, a_2, and a_3, and they are all equal. 
It works, for example, if the a_i's are "almost sum-distinct"; for any s
there are at most two sum(a_i c_i) equal to s.)


--
Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
My opinions are my own, and do not represent those of my employer.
My interaction with our news system is unstable; if you want to be sure I see a post, mail it.