home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2859 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  2.5 KB
  1. Xref: sparky comp.theory:2859 comp.programming:3444
  2. Newsgroups: comp.theory,comp.programming
  3. Path: sparky!uunet!munnari.oz.au!bruce.cs.monash.edu.au!monu6!fawlty8.eng.monash.edu.au!serdar
  4. From: serdar@fawlty8.eng.monash.edu.au (Serdar Boztas)
  5. Subject: Re: Hamming codes algorithm needed
  6. Message-ID: <serdar.726817207@fawlty8.eng.monash.edu.au>
  7. Sender: news@monu6.cc.monash.edu.au (Usenet system)
  8. Organization: Monash University, Melb., Australia.
  9. References: <1993Jan12.160004.505@otago.ac.nz>
  10. Date: Tue, 12 Jan 1993 05:40:07 GMT
  11. Lines: 60
  12.  
  13. chchmeds@otago.ac.nz writes:
  14.  
  15. >I need an algorithm to solve the following problem:
  16.  
  17. >Find a set of 32-bit binary numbers such that the Hamming distance
  18. >between every pair of them is (at least) a given constant (say 16).
  19. >We can stop finding numbers after we have 256 of them, but not before.
  20.  
  21. >The Hamming distance between two numbers is the number of bits in which they
  22. >differ. 
  23.  
  24. >It is easy enough to get two numbers which differ in 16 positions. Getting
  25. >a third which differs from *both* the previous two is a little more
  26. >time-consuming, but not much.  But after 20 of them, it gets very sluggish
  27. >indeed using a brute-force ("pick a random nunmber and try it") technique.
  28.  
  29. The problem you described is very hard to solve in general. There are
  30. some bounds on the maximum number of codewords that a code may have
  31. given a length and minimum hamming distance. I recommend looking
  32. at chapter 17 of MacWilliams & Sloane, 'The Theory of Error Correcting
  33. Codes' for a start.
  34.  
  35. Since I have the book handy, for your specific problem, Theorem 11 of
  36. that chapter states that 'Provided suitable Hadamard matrices
  37. exist, (i.e. not in general, but in fortunate cases, which n=32
  38. is one) then
  39.  
  40.     A(4*d,2*d)=8*d
  41.  
  42. where
  43.  
  44.     A(n,d') = maximum number of codewords of any code with
  45.                                                  ^^^ 
  46.          length n and minimum distance d'
  47.  
  48. while in your case
  49.  
  50.     n=4*d=32 ==> d=4
  51.  
  52. directly implies that the most codewords you can have is 8*d=64,
  53. not 256 as you wanted.
  54.  
  55. >You may recognize such a set of numbers as a Hamming code. There are
  56. >well-known methods for generating Hamming codes of distance 3 to 6; 
  57. >unfortunately they don't generalise to other distances.
  58.  
  59. Such a set of numbers is just a binary code, a Hamming code is a
  60. specific type of binary code. The term 'Hamming distance' is what
  61. confuses people at first.
  62.  
  63. >Gordon
  64. >Gordon Findlay
  65. >Christchurch School of Medicine
  66. >Gordon@chmeds.ac.nz
  67.  
  68. Serdar
  69. >chchemds@otago.ac.nz
  70. -- 
  71. Serdar Boztas 
  72. serdar@fawlty8.eng.monash.edu.au 
  73.