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

Question

我正在寻找一种快速的方法来生成小于2 ^ 64的k个非负整数,其中,在基数2中,任意两个数之间的最小汉明距离尽可能高.

例如,如果我正在寻找k = 4的数字并且它们应该小于2 ^ 4它们可以是:
0000
0011
1100
1111
并且最小汉明距离将是2.

是否有快速算法为给定的k生成这些数字？我将得到大约10 ^ 4的k.

或者,产生一组数字的算法也可以正常工作,所述数字具有成对的汉明距离大于给定值.

Answer 1

这是一个相当简单的方法。找到可以表示 k 个不同数字的最小位数 = b。例如，对于 k=4，使用 b = 2 位。将 64 位划分为大小为 2 的块。对于每个块，为要生成的每个数字指定 2^b >= k 可用数字中的不同数字。

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

0000

0101

1010

1111

如果有 c 个块，则每个 c 个块的至少一位中的每个数字都与其他数字不同，因此保证的最小汉明间隔为 c。

您还可以排列每个块中数字的选择，这将产生更多随机的示例，例如

0011

0101

1000

1110