🚀 go-pugleaf

chchmeds@otago.ac.nz writes:

>I need an algorithm to solve the following problem:

>Find a set of 32-bit binary numbers such that the Hamming distance
>between every pair of them is (at least) a given constant (say 16).
>We can stop finding numbers after we have 256 of them, but not before.

>The Hamming distance between two numbers is the number of bits in which they
>differ. 

>It is easy enough to get two numbers which differ in 16 positions. Getting
>a third which differs from *both* the previous two is a little more
>time-consuming, but not much.  But after 20 of them, it gets very sluggish
>indeed using a brute-force ("pick a random nunmber and try it") technique.

The problem you described is very hard to solve in general. There are
some bounds on the maximum number of codewords that a code may have
given a length and minimum hamming distance. I recommend looking
at chapter 17 of MacWilliams & Sloane, 'The Theory of Error Correcting
Codes' for a start.

Since I have the book handy, for your specific problem, Theorem 11 of
that chapter states that 'Provided suitable Hadamard matrices
exist, (i.e. not in general, but in fortunate cases, which n=32
is one) then

	A(4*d,2*d)=8*d

where

	A(n,d') = maximum number of codewords of any code with
                                                 ^^^ 
		 length n and minimum distance d'

while in your case

	n=4*d=32 ==> d=4

directly implies that the most codewords you can have is 8*d=64,
not 256 as you wanted.

>You may recognize such a set of numbers as a Hamming code. There are
>well-known methods for generating Hamming codes of distance 3 to 6; 
>unfortunately they don't generalise to other distances.

Such a set of numbers is just a binary code, a Hamming code is a
specific type of binary code. The term 'Hamming distance' is what
confuses people at first.

>Gordon
>Gordon Findlay
>Christchurch School of Medicine
>Gordon@chmeds.ac.nz

Serdar
>chchemds@otago.ac.nz
-- 
Serdar Boztas 
serdar@fawlty8.eng.monash.edu.au