home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2858 < prev    next >
Encoding:
Internet Message Format  |  1993-01-11  |  1.3 KB
  1. Xref: sparky comp.theory:2858 comp.programming:3443
  2. Path: sparky!uunet!munnari.oz.au!comp.vuw.ac.nz!canterbury.ac.nz!otago.ac.nz!chchmeds
  3. From: chchmeds@otago.ac.nz
  4. Newsgroups: comp.theory,comp.programming
  5. Subject: Hamming codes algorithm needed
  6. Message-ID: <1993Jan12.160004.505@otago.ac.nz>
  7. Date: 12 Jan 93 16:00:04 +1300
  8. Organization: University of Otago, Dunedin, New Zealand
  9. Lines: 25
  10.  
  11. I need an algorithm to solve the following problem:
  12.  
  13. Find a set of 32-bit binary numbers such that the Hamming distance
  14. between every pair of them is (at least) a given constant (say 16).
  15. We can stop finding numbers after we have 256 of them, but not before.
  16.  
  17. The Hamming distance between two numbers is the number of bits in which they
  18. differ. 
  19.  
  20. It is easy enough to get two numbers which differ in 16 positions. Getting
  21. a third which differs from *both* the previous two is a little more
  22. time-consuming, but not much.  But after 20 of them, it gets very sluggish
  23. indeed using a brute-force ("pick a random nunmber and try it") technique.
  24.  
  25. You may recognize such a set of numbers as a Hamming code. There are
  26. well-known methods for generating Hamming codes of distance 3 to 6; 
  27. unfortunately they don't generalise to other distances.
  28.  
  29. TIA for any pointers.
  30. Gordon
  31. ---
  32. Gordon Findlay
  33. Christchurch School of Medicine
  34. Gordon@chmeds.ac.nz
  35. chchemds@otago.ac.nz
  36.