查找 12 个 32 位数字，每个数字对之间至少有 17 位差异

Question

找到 12 个 32 位数字，其中每对至少在 17 个位置上有位不同。

我正在努力寻找解决这个问题的最佳算法。更一般的问题是：找到“n”个 32 位数字，使得它们中的每对至少在“m”个位置上有位不同。

我的第一个方法是随机选择一个数字，或者从 6 (00000110) 开始，然后再次选择其他随机数字。然后进行异或运算并计算异或结果的二进制表示形式中有多少个 1，这将表明数字有多少个位置不同。如果条件被接受，我们可以存储这两个数字并执行相同的过程，直到达到所需的数字数量。然而，这种算法似乎不是最佳的，因为我们选择随机数，因此它可以“永远”持续下去。

*更新 我准备了这样的代码，对于 m = 16 它实际上返回 12 个结果，但是对于 17 （我需要的）它停止在 9 个结果并且代码永远不会完成。我想知道在[0, 2^32]范围内是否有可能没有这十二个数字，但如何证明呢？

import random

def hamming_distance(x, y):
    dist = 0

    # The ^ operator sets to 1 only the bits that are different
    val = x ^ y
    while val > 0:
        # We then count the bit set to 1 using the Peter Wegner way
        val = val & (val - 1)  # Set to zero val's lowest-order 1
        dist += 1

    # Return the number of differing bits
    return dist


def solution(n = 12, m = 17):
    result = [0]

    while len(result) < n:
        r = random.randint(0,2**32)

        if all(hamming_distance(r,el) >= m for el in result):
            result.append(r)
            print(result)
    
    return result


print(solution())

Answer 1

我们构造一组 12 个码字，每个码字有 32 位，最小距离为 17。轮廓为

• 使用数论（特别是二次余数模 11），构造一组 12 个码字，每个码字具有 11 位，使得最小距离为 6。
• 每个比特总共复制三份，从而获得一组 12 个码字，每个码字有 33 位，使得最小距离为 18。
• 删除每个码字的低位。

我用Python实现了下面的构造。

import itertools


def min_distance(code):
    return min((x ^ y).bit_count() for (x, y) in itertools.combinations(code, 2))


quadratic_residues = {pow(x, 2, 11) for x in range(11)}
code11 = {sum(1 << ((y + z) % 11) for y in quadratic_residues) for z in range(11)}
code11.add(0)
assert len(code11) == 12
assert min_distance(code11) == 6

c = 1 + (1 << 11) + (1 << 22)
code33 = {c * x for x in code11}
assert len(code33) == 12
assert min_distance(code33) == 18

code32 = {x >> 1 for x in code33}
assert len(code32) == 12
assert min_distance(code32) == 17
for x in sorted(code32):
    print(hex(x))

输出：

0x0
0x1da3b476
0x3b4768ed
0x4768ed1d
0x68ed1da3
0x768ed1da
0x8ed1da3b
0xa3b4768e
0xb4768ed1
0xd1da3b47
0xda3b4768
0xed1da3b4

Answer 2

随机选择一个代码有利于渐近信道容量，但正如下面的参数所示，您正处于可能的边缘。几乎可以肯定，如果有一组码字，它就会有一些抽象的代数逻辑。

\n

（将下面的文字留给后人，但基本上我重新推导了Plotkin 界限。）

\n

相反，假设存在一组码字 W \xe2\x8a\x86 {0, 1} ³²使得 |W| = 12 并且，对于所有 {w, x} \xe2\x8a\x86 W，我们有 d(w, x) \xe2\x89\xa5 17，其中 d 表示其参数不同的位置数（汉明距离） 。我声称

\n

\n

\xe2\x88\x91 _{w,x\xe2\x88\x88W} d(w, x) \xe2\x89\xa5 12\xc2\xb711\xc2\xb717 + 2\xc2\xb76\xc2\xb75 = 2304。

\n

\n

右侧第一项直接来自假设。第二项源自宇称论证。分解 W = E \xe2\x88\xaa O 其中 E 是具有偶校验的码字集合，O 是具有奇校验的码字集合。对于所有 {w, x} \xe2\x8a\x86 E，我们有 d(w, x) \xe2\x89\xa5 18，因为偶校验的两个码字之间的距离是偶数。同样，对于所有 {w, x} \xe2\x8a\x86 O，我们有 d(w, x) \xe2\x89\xa5 18。因此我们有 |E| (|E| \xe2\x88\x92 1) + |O| (|O| \xe2\x88\x92 1) \xe2\x89\xa5 2\xc2\xb76\xc2\xb75 对最小距离 18。

\n

现在我们应用线性代数。设 V \xe2\x8a\x86 {1, \xe2\x88\x921} ³²为代码向量集合，我们通过将每个 0 替换为 1，将每个 1 替换为 \xe2\x88\ 来从代码字导出代码向量。 x921。（正式的逐元素变换是 v[i] = (\xe2\x88\x921) ^w[i]。）

\n

\n

\xe2\x88\x91 _{w,x\xe2\x88\x88W} (32 \xe2\x88\x92 2 d(w, x)) = \xe2\x88\x91 _{u,v\xe2\x88\x88V} (u\ xc2\xb7v) = \xe2\x80\x96\xe2\x88\x91 _{v\xe2\x88\x88V} v\xe2\x80\x96 ² \xe2\x89\xa5 0,

\n

\n

其中第一个等式来自汉明距离和点积的关系，其余的来自标准线性代数论证。将第一个不等式加倍并添加到第二个不等式中：

\n

\n

\xe2\x88\x91 _{w，x\xe2\x88\x88W} 32 \xe2\x89\xa5 2\xc2\xb72304。

\n

\n

有趣的是，两边都是 12\xc2\xb712\xc2\xb732 = 4608。像这样的参数排除了 13 个码字。

\n