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