长度为m、汉明权重为r的二进制串个数的确定，最多可以包含连续的k个零

Question

我在 MatLab 中遇到了一点问题。

我正在尝试计算具有给定汉明权重 r 的长度为 m 的二进制字的数量，其中最多只包含 k 个连续的零。汉明权重是二进制字中非零条目的数量。

我根据论文 "Constant-Weight and Constant-Charge Binary Run-Length Limited Codes" (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 和低字长以及汉明权重 r，该代码运行良好。在某些参数上，尤其是大参数，我得到了负面结果，这是不应该的。我已经尝试用 gammaln 函数替换 nchoosek 函数以避免溢出。但是我也得到了负面结果。

你知道我能做什么吗？谢谢你！

Answer 1

对于m足够小的你可以：

将长度为 m 的所有二进制字生成为矩阵，每个字排成一行。这可以通过 conversion to binary.
只保留权重为 r 的那些。 summing上述矩阵沿第二个维度可以得到每个词的权重。
计算没有 k+1 个连续零的单词数。可以通过观察 2D-convolution 的否定词的输出和 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

Answer 2

使用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.

长度为m、汉明权重为r的二进制串个数的确定，最多可以包含连续的k个零

Determination of the number of binary strings of length m and Hamming weight r, which can contain consecutive zeros up to k

algorithm

matlab

combinatorics