n 个等长比特串两两中汉明距离等且无也 0,虽说它们的最短长为小?

焦子南 1周前 129 比特 汉明距离
不妨设问题答案为 l(n) .显然 l(2)=1 ,因为长度为 1 的比特串“0”和“1”的汉明距离为 1 ;l(3)=3 ,因为不存在长度为 2 的 3 个比特串,两两之间汉明距离相等。但“001”、“010”和“100”三个串两两汉明距离为 2 ;l(4)=3 ,因为在上一条中三个比特串的基础上添加串“111”,这 4 个比特串两两汉明距离依然为 2 。问题是对任意的 n 求 l(n) 。我只知道 l(n)\leq n ,因为 n 阶单位矩阵的 n 列就满足要求。现在想知道除了 n=2…
其他回答
存在 8 个长度为 7 的串满足要求:
0000000
1111000
1100110
0011110
1010101
1001011
0110011
0101101

补充:可以归纳构造出 2^n 个长度为 2^n-1 的串。
设已有 2^k 个长度为 2^k-1 的串,两两距离为 2^(k-1). 先将所有串中所有 0, 1 替换为 00, 11 ,再在每个串末尾补一个 0 ,得到 2^k 个长度为 2^(k+1)-1 的串;将这 2^k 个串与 10101...1 异或,又得到另 2^k 个串,容易证明以上 2^(k+1) 个串两两距离均为 2^k.

补2:可说明 l(n)>=n-1 。设有 n 个长度为 m 的串满足要求,将每个串对应 R^m 的坐标(每个分量为 0 或 1 ),则这 n 个点两两距离(欧氏距离)相等,而 R^m 中两两距离相等的点最多有 m+1 个,故 n<=m+1 ,由此可得结论。
顺便可以确定 l(2^n)=2^n-1.

补3:若 l(n)=n-1 ,则 n 为 4 的倍数(1, 2 除外)
记 m=n-1 ,问题相当于在 m 维单位超立方体上取 m+1 个顶点,它们两两距离相等。容易证明这 m+1 个顶点的重心是 R^m 中唯一一个与这 m+1 个点等距的点,故必为超立方体中心 (1/2, ... , 1/2) 。n 个整数的平均数是 1/2 ,说明 n 是偶数。
设 n 个串两两汉明距离为 k ,则 m+1 个点两两距离 sqrt(k) ,可求得它们的重心与这 m+1 个点的距离均为 sqrt(k)*sqrt(m/(2(m+1))) ,它等于 m 维单位超立方体对角线长的一半 sqrt(m)/2 ,可解得
k=(m+1)/2=n/2
当 n>=3 时 k 必为偶数(因为不存在 3 个串两两汉明距离均为奇数),故 n 为 4 的倍数。
焦子南 1周前 0条评论
相关问答