我想生成长度为n=128的二进制字符串,其属性是任何一对这样的字符串至少在d=10 hamming距离内。
为此,我尝试使用具有最小距离d=10的纠错码( ecc )。但是,我找不到具有128位长度的码字的纠错码。如果码字长度(n)和d略小于/大于128和10,这仍然适用于我。
是否存在具有此(类似)属性的ecc?有没有这方面的python实现?
发布于 2018-10-16 08:04:32
Reed-Muller码RM(3,7)具有:
首先构造一个如下所示的基础:
def popcnt(x):
return bin(x).count("1")
basis = []
by_ones = list(range(128))
by_ones.sort(key=popcnt)
for i in by_ones:
count = popcnt(i)
if count > 3:
break
if count <= 1:
basis.append(((1 << 128) - 1) // ((1 << i) | 1))
else:
p = ((1 << 128) - 1)
for b in [basis[k + 1] for k in range(7) if ((i >> k) & 1) != 0]:
p = p & b
basis.append(p)
然后,您可以使用它们的任何线性组合,这些组合是由基本行的XORing子集创建的,例如:
def encode(x, basis):
# requires x < (1 << 64)
r = 0
for i in range(len(basis)):
if ((x >> i) & 1) != 0:
r = r ^ basis[i]
return r
在其他一些实现中,我发现这是通过对基本矩阵的列进行点积,然后减少模2来实现的。我不知道他们为什么这样做,似乎更直接地通过对行子集求和来实现。
发布于 2019-12-11 15:36:48
我也需要一模一样的东西。对我来说,这种天真的方法效果很好!只需生成随机比特串,并检查它们之间的汉明距离,逐步构建满足要求的字符串列表:
def random_binary_array(width):
"""Generate random binary array of specific width"""
# You can enforce additional array level constraints here
return np.random.randint(2, size=width)
def hamming2(s1, s2):
"""Calculate the Hamming distance between two bit arrays"""
assert len(s1) == len(s2)
# return sum(c1 != c2 for c1, c2 in zip(s1, s2)) # Wikipedia solution
return np.count_nonzero(s1 != s2) # a faster solution
def generate_hamm_arrays(n_values, size, min_hamming_dist=5):
"""
Generate a list of binary arrays ensuring minimal hamming distance between the arrays.
"""
hamm_list = []
while len(hamm_list) < size:
test_candidate = random_binary_array(n_values)
valid = True
for word in hamm_list:
if (word == test_candidate).all() or hamming2(word, test_candidate) <= min_hamming_dist:
valid = False
break
if valid:
hamm_list.append(test_candidate)
return np.array(hamm_list)
print(generate_hamm_arrays(16, 10))
输出:
[[0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1]
[1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1]
[1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0]
[1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1]
[0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1]
[1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1]
[1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0]
[0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0]
[1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1]
[0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0]]
只要你不想要一个非常密集的字符串列表(字符串中的少量比特+大的汉明距离),它就不会太慢。根据您的规范(128位字符串,汉明距离为10,这是没有问题的),我们可以在一个非常弱的cpu上在0.2秒内生成1000位字符串:
import timeit
timeit.timeit(lambda: generate_hamm_arrays(n_values=128, size=100, min_hamming_dist=10), number=10)
>> 0.19202665984630585
希望这个解决方案对你来说也足够了。
发布于 2020-06-26 06:43:25
我的O(n*n!)解决方案(在N<14的合理时间内工作)
def hammingDistance(n1, n2):
return bin(np.bitwise_xor(n1, n2)).count("1")
N = 10 # binary code of length N
D = 6 # with minimum distance D
M = 2**N # number of unique codes in general
# construct hamming distance matrix
A = np.zeros((M, M), dtype=int)
for i in range(M):
for j in range(i+1, M):
A[i, j] = hammingDistance(i, j)
A += A.T
def recursivly_find_legit_numbers(nums, codes=set()):
codes_to_probe = nums
for num1 in nums:
codes.add(num1)
codes_to_probe = codes_to_probe - {num1}
for num2 in nums - {num1}:
if A[num1, num2] < D:
"Distance isn't sufficient, remove this number from set"
codes_to_probe = codes_to_probe - {num2}
if len(codes_to_probe):
recursivly_find_legit_numbers(codes_to_probe, codes)
return codes
group_of_codes = {}
for i in tqdm(range(M)):
satisfying_numbers = np.where(A[i] >= D)[0]
satisfying_numbers = satisfying_numbers[satisfying_numbers > i]
nums = set(satisfying_numbers)
if len(nums) == 0:
continue
group_of_codes[i] = recursivly_find_legit_numbers(nums, set())
group_of_codes[i].add(i)
largest_group = 0
for i, nums in group_of_codes.items():
if len(nums) > largest_group:
largest_group = len(nums)
ind = i
print(f"largest group for N={N} and D={D}: {largest_group}")
print("Number of unique groups:", len(group_of_codes))
N=10和D=6的最大组:6唯一组的数量: 992
# generate largest group of codes
[format(num, f"0{N}b") for num in group_of_codes[ind]]
'0110100001','0001000010','1100001100','1010010111','1111111010','0001111101‘
https://stackoverflow.com/questions/52822487
复制相似问题