生成具有高汉明距离的数字

Question

我正在寻找一种快速的方法来生成k个小于2^64的非负整数，在二进制下，这些数字之间的海明距离最小。例如，如果我要寻找k = 4个数字，并且它们应该小于2^4，则可以是：
0000
0011
1100
1111
最小的汉明距离将为2。
是否有一种快速算法来为给定的k生成这些数字？我的k将达到10 ^ 4。
或者，一个生成一组数字的算法，这些数字之间所有成对的汉明距离都大于给定值，也可以很好地使用。

- Leon

---

这是一个广阔的领域。实际上，您正在寻找一种可以使用64位编码10^4份数据的最优纠错码。请参见此链接 https://en.wikipedia.org/wiki/Hamming_bound（带有相关链接）以进入该主题。 - John Coleman

Answer 1

这里有一个非常简单的方法。找到可以表达k个不同数字所需的最小位数b。例如，对于k=4使用2位b。将64位分成大小为2的块。对于每个块，请为要生成的每个数字在可用的2^b >= k中分配不同的编号。

例如，对于k=4个数字，b位为00、01、10、11，这里有4种可能性:

0000

0101

1010

1111

如果您有c个块，则每个数字至少与每个其他数字在c个块的每个位上不同，因此保证的最小哈明分离度为c。

您还可以在每个块内对数字的选择进行排列，这将产生更多随机外观的示例，例如:

0011

0101

1000

1110

- mcdowella

Answer 2

由mcdowella提供的答案是一种非常好的方法，可以快速生成具有特定最小汉明距离的数字。但是，它不能保证所得到的汉明距离特别大（如果我理解正确，它将保证在10^4个64位数字中的任意两个数字之间至少有4个汉明距离，尽管实际的最小汉明距离可能更大）。如果您真的想要尽可能地使最小汉明距离变大，并且愿意花费更多的CPU周期来做到这一点，我建议使用Reed-Solomon代码。如果您需要10^4个数字，则可以将1、2、...、10000中的每个数字解释为长度为14的二进制消息，以在长度为64的二进制码字中进行编码。为此，您将使用[64,14,51]_2的Reed-Solomon代码，它将保证在所得到的64位数字中的任意两个数字之间至少有51个汉明距离。正如您从链接的维基百科文章中所看到的那样，构造相当复杂，但您应该能够使用开源实现（维基百科文章提供了一些链接），因此您不必重新发明轮子。

- John Coleman