首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >使用ECC生成至少在d个汉明距离内的二进制字符串

使用ECC生成至少在d个汉明距离内的二进制字符串
EN

Stack Overflow用户
提问于 2018-10-16 02:09:30
回答 3查看 641关注 0票数 2

我想生成长度为n=128的二进制字符串,其属性是任何一对这样的字符串至少在d=10 hamming距离内。

为此,我尝试使用具有最小距离d=10的纠错码( ecc )。但是,我找不到具有128位长度的码字的纠错码。如果码字长度(n)和d略小于/大于128和10,这仍然适用于我。

是否存在具有此(类似)属性的ecc?有没有这方面的python实现?

EN

回答 3

Stack Overflow用户

发布于 2018-10-16 08:04:32

Reed-Muller码RM(3,7)具有:

  • 最小块大小为128位
  • 最小距离为16
  • 消息大小为64位

首先构造一个如下所示的基础:

代码语言:javascript
运行
复制
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子集创建的,例如:

代码语言:javascript
运行
复制
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来实现的。我不知道他们为什么这样做,似乎更直接地通过对行子集求和来实现。

票数 1
EN

Stack Overflow用户

发布于 2019-12-11 15:36:48

我也需要一模一样的东西。对我来说,这种天真的方法效果很好!只需生成随机比特串,并检查它们之间的汉明距离,逐步构建满足要求的字符串列表:

代码语言:javascript
运行
复制
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))

输出:

代码语言:javascript
运行
复制
[[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位字符串:

代码语言:javascript
运行
复制
import timeit
timeit.timeit(lambda: generate_hamm_arrays(n_values=128, size=100, min_hamming_dist=10), number=10)

>> 0.19202665984630585

希望这个解决方案对你来说也足够了。

票数 1
EN

Stack Overflow用户

发布于 2020-06-26 06:43:25

我的O(n*n!)解决方案(在N<14的合理时间内工作)

代码语言:javascript
运行
复制
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

代码语言:javascript
运行
复制
# generate largest group of codes

[format(num, f"0{N}b") for num in group_of_codes[ind]]

'0110100001','0001000010','1100001100','1010010111','1111111010','0001111101‘

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52822487

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档