Thread View: sci.math.research
2 messages
2 total messages
Started by Todd Moon
Tue, 01 Sep 1992 16:01
mixed-field arithmetic problems
Author: Todd Moon
Date: Tue, 01 Sep 1992 16:01
Date: Tue, 01 Sep 1992 16:01
54 lines
2820 bytes
2820 bytes
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
Re: mixed-field arithmetic problems
Author: Arthur Rubin
Date: Tue, 01 Sep 1992 19:51
Date: Tue, 01 Sep 1992 19:51
57 lines
3093 bytes
3093 bytes
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.
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads