home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / research / 434 < prev    next >
Encoding:
Text File  |  1992-09-01  |  2.7 KB  |  70 lines
  1. Newsgroups: sci.math.research
  2. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!usenet
  3. From: moon@moon.ee.usu.edu (Todd Moon)
  4. Subject: mixed-field arithmetic problems
  5. Nntp-Posting-Host: moon.ee.usu.edu
  6. Message-ID: <MOON.92Sep1110158@moon.ee.usu.edu>
  7. Sender: Daniel Grayson <dan@math.uiuc.edu>
  8. X-Submissions-To: sci-math-research@uiuc.edu
  9. Organization: Utah State University Dept EE Logan, Utah
  10. X-Administrivia-To: sci-math-research-request@uiuc.edu
  11. Approved: Daniel Grayson <dan@math.uiuc.edu>
  12. Date: Tue, 1 Sep 1992 16:01:58 GMT
  13. Lines: 55
  14.  
  15.  
  16. Here is a problem in mixed field arithmetic.  In what follows, + will
  17. denote addition over the field of reals, and | will denote addition
  18. over GF(2).  Multiplication is over the reals.
  19.  
  20. consider a system of equations such as
  21.  
  22. a_1 c_0               + a_2 c_3               = s_0
  23. a_1 c_1               + a_2 c_4               = s_1
  24. a_1 c_2               + a_2 c_5               = s_2
  25. a_1 (c_0 | c_1)       + a_2 (c_3 | c_5)       = s_3
  26. a_1 (c_1 | c_2)       + a_2 (c_3 | c_4 | c_5) = s_4
  27. a_1 (c_0 | c_1 | c_2) + a_2 (c_3 | c_5)       = s_5
  28. a_1 (c_0 | c_2)       + a_2 (c_4 | c_5)       = s_6
  29.  
  30. where a_1 and a_2 are real and known, the s_i are real and known, and
  31. the unknowns c_i are in GF(2) (that is, either 0 or 1).  Although the
  32. problem has been written similar to a set of linear equations, it is
  33. easy to verify that this is not a linear set of equations.
  34.  
  35. 1) Find the set of c_i that satisfy this set of equations.  For this
  36. problem, it can be accomplished simply by combinatorial search
  37. techniques.  However, there are larger problems of interest similar to
  38. for which searching is impractical.
  39.  
  40. 2) Now consider the case of finding the "best" solution to the set of
  41. equations where the equality does not hold -- there is unknown "noise"
  42. in the equations:
  43.  
  44. a_1 c_0               + a_2 c_3               = s_0 + n_0
  45. a_1 c_1               + a_2 c_4               = s_1 + n_1
  46. a_1 c_2               + a_2 c_5               = s_2 + n_2
  47. a_1 (c_0 | c_1)       + a_2 (c_3 | c_5)       = s_3 + n_3
  48. a_1 (c_1 | c_2)       + a_2 (c_3 | c_4 | c_5) = s_4 + n_4
  49. a_1 (c_0 | c_1 | c_2) + a_2 (c_3 | c_5)       = s_5 + n_5
  50. a_1 (c_0 | c_2)       + a_2 (c_4 | c_5)       = s_6 + n_6
  51.  
  52. As before, a_i and s_i are known, but the noise n_i is not known.
  53. Find the best (perhaps in least squares sense) set of c_i in GF(2).
  54.  
  55. What would be nice would be to have an algebra for these mixed field
  56. problems, from which exact and pseudo-inverse solutions coulde be
  57. obtained.
  58.  
  59. Any suggestions, comments, references, etc. would be greatly
  60. appreciated.
  61.  
  62.  
  63. Todd Moon
  64. Electrical Engineering Dept., UMC 4120
  65. Utah State University
  66. Logan, UT  84322
  67. 801 750 2970
  68. moon@moon.ee.usu.edu
  69.  
  70.