纠错码与最小距离

Question

我在网上看一个挑战(在King's网站)，虽然我理解它背后的一般想法，但我有点不知所措--也许措辞有点不对？以下是问题所在，我将在下面陈述我不理解的内容：

纠错码被广泛应用于从卫星通信到音乐CD的各种应用。其思想是将长度为k的二进制字符串编码为长度为n>k的二进制字符串，称为代码字，这样即使编码的某些位被损坏(例如，在CD上刮擦)，原始k位字符串仍然可以恢复。有三个与纠错码相关的重要参数:码字长度(n)、尺寸(k) (即未编码字符串的长度)和代码的最小距离(d)。两个码字之间的距离是汉明距离，即码字不同的位置数: 0010和0100位于距离2。码的最小距离是两个最接近对方的不同码字之间的距离。线性码是一种简单的纠错码，具有许多优点。其中之一是最小距离是最小距离，任何非零码字对零码字都有(由n个零组成的码字总是属于长度为n的线性码)。长度为n和维数为k的线性码的另一个优点是，它们可以用0和1的n×k生成矩阵来描述。编码k位字符串的方法是将其视为列向量，并将其乘以生成器矩阵。下面的示例显示了生成器矩阵以及字符串1001是如何编码的。graph.png矩阵乘法除模2(即0+1=1+0=1和0+0=1+1=0)外，一般都是这样做的。这个代码的代码集就是所有可以通过这种方式编码所有k位字符串而得到的向量。编写一个程序，计算几个长度最多为30，尺寸最多为15的线性纠错码的最小距离。每一段代码将作为一个生成矩阵。输入您将得到几个生成器矩阵作为输入。第一行包含一个整数T，表示测试用例的数量。每个测试用例的第一行给出了参数n和k，其中1≤n≤30，1≤k≤15和n>k是由单个空格分隔的两个整数。下面n条线描述了一个生成器矩阵。每一行都是矩阵的一行，具有k个间距分隔的条目，分别为0或1。每个生成器矩阵的输出输出一条具有对应线性码最小距离的单行。

样本输入1

2

7 4

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

0 1 1 1

1 0 1 1

1 1 0 1

3 2

1 1

0%0

1 1

样本输出1

3.

现在我的假设是，问题是，“编写一个程序，它可以接受矩阵形式的线性码，并说明从一个全零码字到最小距离是多少”，我只是不明白为什么第一个输入有3个输出，第二个输入有一个0？

很困惑。

有什么想法吗？

Answer 1

第一个例子是：

Input binary string: 1000
Resulting code: 1100001
Hamming distance to zero codeword 0000000: 3

第二个例子是：

Input binary string: 11
Resulting code: 000
Hamming distance to zero codeword 000: 0

您的目标是找到有效的非零码字(可以从一些非零k位输入字符串产生)，并返回该距离。

希望有帮助，问题的描述确实有点难以理解。

编辑。我在第一个例子中输入了错误。实际输入应该是1000而不是0001。此外，可能还不清楚输入字符串到底是什么，以及代码字是如何计算的。让我们看第一个样本。

Input binary string: 1000

这个二进制字符串通常是，而不是生成器矩阵的部分。它只是所有可能的非零4位字符串之一。让我们把它乘以生成器矩阵：

(1 0 0 0) * (1 0 0 0) = 1
(0 1 0 0) * (1 0 0 0) = 0
(0 0 1 0) * (1 0 0 0) = 0
(0 0 0 1) * (1 0 0 0) = 0
(0 1 1 1) * (1 0 0 0) = 0
(1 0 1 1) * (1 0 0 0) = 1
(1 1 0 1) * (1 0 0 0) = 1

找到产生“最小”码字的输入的一种方法是迭代所有2^k-1非零k位字符串，并计算每个字符串的码字。这对于k <= 15是可行的。

第一个测试用例0011的另一个例子(可以有多个输出“最小”的输入)：

(1 0 0 0) * (0 0 1 1) = 0
(0 1 0 0) * (0 0 1 1) = 0
(0 0 1 0) * (0 0 1 1) = 1
(0 0 0 1) * (0 0 1 1) = 1
(0 1 1 1) * (0 0 1 1) = 2 = 0 (mod 2)
(1 0 1 1) * (0 0 1 1) = 2 = 0 (mod 2)
(1 1 0 1) * (0 0 1 1) = 1

由此产生的代码0011001也具有到零码字的汉明距离3。在二进制表示中，没有4位字符串的代码小于3位.这就是为什么第一个测试用例的答案是3。