长度为m的二进制字符串数的确定和汉明重量r，它可以包含连续的零到k。
长度为m的二进制字符串数的确定和汉明重量r，它可以包含连续的零到k。
提问于 2017-07-18 15:47:38
我在MatLab上有个小问题。
我试图用给定的汉明重量r计算长度为m的二进制单词数，它只包含k个连续的零。汉明重量是二进制词中非零项的数目。
我基于论文“恒定重量和恒电荷二进制游程限制码”(Kurmaev)实现了以下代码。
%% Different cases for the weight r
if (r==0)
if (m<=k)
numberOfBinaryStrings = 1;
else
numberOfBinaryStrings = 0;
end
else
%% Computation of the number of binary strings
% Determination of the sum bound
bound = min(m,k);
d = k+1;
tmp = 0;
for j=0:bound
for s=0:r-1
if (m-j-1-s*d < r-1)
bin1 = 0;
else
bin1 = nchoosek(m-j-1-s*d,r-1);
end
if (m-j-1-(k+1)-s*d < r-1)
bin2 = 0;
else
bin2 = nchoosek(m-j-1-(k+1)-s*d,r-1);
end
tmp = tmp + (-1)^s * nchoosek(r-1,s) * ( bin1 - bin2 );
end
end
numberOfBinaryStrings = tmp;结束
在给定的k和低字长及Hamming重量的情况下，代码运行良好。在某些参数，特别是大参数下，我得到了不应该出现的负结果。为了避免溢出，我已经尝试用gammaln函数替换nchoosek函数。但在这里我也得到了负面的结果。
你知道我能做什么吗？谢谢!
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-07-18 18:27:49
利用http://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic在Matlab中得到任意大小的整数。这将消除任何可能的溢出问题。
如果这不能解决您的问题，那么您就会在某个地方出现逻辑错误。在这种情况下，我建议产生另一种解决方案，并试图产生一个最小的不同的例子。那就试试找出原因。
下面是Python中的另一个解决方案，您可以使用它进行比较。
#! /usr/bin/env python
stored_word_counts = {}
def word_counts(word_length, ones, max_zero_run):
if 0 == ones:
if max_zero_run < word_length:
# Impossible.
return 0
else:
# String of all zeros.
return 1
key = (word_length, ones, max_zero_run)
if key not in stored_word_counts:
# We will try all places we can put a 1.
mid = (ones+1)/2 # Cut in half, round up.
ones_before = mid - 1
ones_after = ones - mid
stored_word_counts[key] = sum(
word_counts(pos, ones_before, max_zero_run) * word_counts(word_length - pos - 1, ones_after, max_zero_run)
for pos in xrange(ones_before, word_length - ones_after)
)
return stored_word_counts[key]
print(word_counts(50, 20, 5)) # Change this line as needed.Stack Overflow用户
发布于 2017-07-18 16:54:12
对于足够小的m，您可以：
- 生成长度为
m的所有二进制单词作为一个矩阵，每一个单词都在一行中。这可以通过转换为二进制轻松地完成。 - 只保留那些重量的
r。每一个词的权重都可以通过求和，沿着第二维得到上面的矩阵。 - 数一下没有
k+1连续零的单词数。这些词可以通过观察二维卷积输出带有k+1向量的否定词来检测。
代码：
m = 7;
r = 4;
k = 2;
h = dec2bin(0:2^m-1) - '0'; % step 1
h = h(sum(h,2)==r, :); % step 2
result = sum(all(conv2(1-h, ones(1,k+1), 'valid') < k+1, 2)); % step 3页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/45171613
复制相关文章
相似问题
腾讯云开发者
