Generating numbers, with a high distance from interference

Question

I am looking for a quick way to generate k non-negative integers less than 2 ^ 64, of which in base 2 the minimum Hamming distance between any two numbers is as high as possible.

For example, if I was looking for k = 4 numbers, and they should be less than 2 ^ 4, they could be:
0000
0011
1100
1111
And the minimum Hamming distance would be 2.

Is there a quick algorithm to generate these numbers for a given k? I will have k of order 10 ^ 4.

Alternatively, an algorithm that creates a set of numbers that have all pairwise Hamming distances greater than a given value will also work fine.

Answer 1

This is a pretty trivial way. Find the smallest number of bits = b that can express k different numbers. For instance. for k = 4, use b = 2 bits. Divide 64 bits into pieces of size 2. For each fragment, give each number a different number from the available 2 ^ b> = k.

eg. for k = 4 numbers b bits are 00, 01, 10, 11 and there are 4 possibilities:

0000

0101

1010

1111

If you have c chunks, then each number differs from the number from each other by at least one bit of each of the c-fragments, so the minimum guaranteed separation of hamming is c.

You can also rearrange the selection of numbers inside each fragment, which will lead to more random examples, such as

0011

0101

1000

1,110

Answer 2

The answer due to mcdowella is a very good way to quickly generate numbers with some minimum Hamming distance from each other. But this does not guarantee that the final Hamming distances are especially large (if I understand it correctly, this would guarantee a Hamming distance of at least 4 between any two of 10 ^ 4 64-bit numbers, although the actual minimum Hamming distance could be greater). If you really want to get the minimum Hamming distance as much as possible and are ready to spend a few more processor cycles, I would recommend using Reed-Solomon code . If you need 10 ^ 4 numbers, you can interpret each number in 1,2, ..., 10000 as a binary message of length 14, which should be encoded in binary codewords of length 64. For this, you would use the Reed-Solomon code [ 64,14,51] _2, which would guarantee a Hamming distance of at least 51 between any two of the received 64-bit numbers. As you can see from the related Wikipedia article, the design is quite complex, although you should be able to use an open source implementation (the Wikipedia article contains some links), so you don’t have to reinvent the wheel.