5

这更像是一个计算机科学/信息论问题，而不是一个简单的编程问题，所以如果有人知道一个更好的网站来发布这个，请告诉我。

假设我有一条 N 位数据，它将在 M 条消息中冗余发送，其中至少有 M-1 条消息将被成功接收。我对以每条消息更少的位数对 N 位数据进行编码的不同方法感兴趣。（这类似于RAID，但级别要小得多，其中 N = 8 或 16 或 32）

示例：假设 N = 16 和 M = 4。那么我可以使用以下算法：

1st and 3rd message: send "0" + bits 0-7
2nd and 4th message: send "1" + bits 8-15

如果我能保证 4 条消息中的 3 条能够通过，那么每个组中至少有一条消息能够通过。因此，我可以用 9 位或更少的位来完成这项工作，可能有一种方法可以用更少的总位来做到这一点，但我不确定如何。

是否有一些简单的编码/解码算法来做这种事情？这个问题有名字吗？（如果我知道它叫什么，我可以谷歌它！）

注意：在我的特定情况下，消息要么正确到达，要么根本没有到达（没有消息到达时有错误）。

（编辑：将第二部分移至单独的问题）

4

5 回答 5

5

（以下是不完整的答案。我以后可能会添加更多。）

您可能感兴趣的术语是通道编码：向源添加冗余，以使其在通过嘈杂的通道传输期间具有鲁棒性。在信息论中，信道编码的补充问题是源编码：减少源中的冗余以使用更少的比特来表示它。（这两个问题的结合称为联合信源信道编码。）

您的第一个问题要求查找频道代码。您给出的简单示例类似于重复代码，即您发送相同的消息两次以上（通常是奇数次），然后将最常收到的消息作为原始消息接受。

这段代码效率低下。要使用标准表示法，设 k = 原始消息中的位数，n = 传输消息中的位数。对于您的示例，k = 16 和 n = 36。编码效率的衡量标准是 k/n，其中越高意味着效率越高。在您的情况下，k/n = 0.44。这是低的。

重复码是一种简单的块码，即在每个 k 位块中添加冗余以创建 n 位码字。正如其他人提到的那样，Hamming和Reed-Solomon代码也是如此。使用一些基本的线性代数，汉明码相对容易理解。

这些应该足以让您自行搜索。祝你好运。

于 2010-01-28T20:14:32.407 回答
3

我不确定我是否正确理解了您问题的所有细节，但您的问题肯定是关于设计某种纠错代码。这是一个广阔的计算机科学领域，关于它的著作很多。从 wikipedia 开始，看看您是否可以获得任何简单的方案（如 Hamming 或 Reed-Solomon 代码）以适用于您的情况。

如果您不仅要处理符号损坏，还要处理符号删除，您应该查看纠删码，这绝对是一项更艰巨的任务，但在很多情况下都有很好的方法。

编辑：这个来自hackersdelight.org 的材料似乎是一个不错的介绍。

于 2010-01-28T20:07:21.607 回答
1

请参阅纠删码。

于 2010-01-28T20:03:37.660 回答
1

您正在寻找数据包擦除代码。只有两个有用的数据包擦除代码没有完全受专利保护，并且只有一个开源库可以实现这些代码。在这里找到它：http ://planete-bcast.inrialpes.fr/rubrique.php3?id_rubrique=5

于 2010-01-28T21:20:07.877 回答
1

这是一个非常简单的方案，其效率几乎是您的示例的两倍。

您将消息切成 (N/M)*2 位的块。相反，将其切成 N/(M-1) 位块。（如有必要，将其四舍五入。）第一个块src[0], 编码为自身：enc[0]=src[0]。最后一个块也一样：enc[M-1]=src[M-1]. 其他每个块都与其左邻居进行异或：enc[i]=src[i-1]^src[i]。

基本上就像你做的那样，在每个编码块前面加上一个 log(M) 位的序列号，这样接收器就可以知道哪个被丢弃了。（如果您可以确定无论哪个块到达都会按顺序到达，那么一个 1 位的序列号就可以了。只需交替 0 和 1。）

要解码，请依次从左侧和右侧异或，直到您击中丢弃的块。例如src[1] == enc[0]^enc[1]。（删除一个端点块不是特殊情况——例如，如果第一个块被删除，从右边的扫描恢复它，从左边的扫描长度为 0。）

于 2011-01-14T22:54:21.650 回答