纠错码用于纠正数据包丢失（UDP）

Question

纠错码用于纠正数据包丢失（UDP）

7

我不知道该寻找什么，因为使用“错误校正码”只得到与你不知道错误位置相关的内容。因此，这些代码比我需要的复杂和低效。

请注意以下内容：在此处，"bits" 等于 "packets" (因为只有整个包可以丢失，因此比特类比非常合适)。

是否有纠错编码可以考虑您已经知道哪些"k"位缺失，并且仅提供重构数据流在这些"k"处的方法？此外，ECC添加的比特应独立（最好）。如果数据的ECC部分发生丢包，它仍然可以重构一些原始数据（并非总是会有k个错误，大多数情况下没有任何错误。因此，ECC对其自身添加的ECC比特具有容错性很重要）。

在我看来，这是一个很大的区别。对于一个丢失的比特，很简单，我只需使用一个异或比特即可。但是我不聪明到可以将其推广到n比特。

所以，再次强调，我有一个包含n比特的数据流，并且我知道最多有k比特丢失（我确实知道哪些比特丢失了，不可能出现损坏）。现在我需要一个编解码器，可以通过尽可能少地添加开销到数据流中来重构它们。我梦想着有（n+k）比特来修正n位数据流中的k个随机比特错误 : )。此外，如果ECC添加到n比特数据流中的任何这些k比特被损坏，例如c个k位比特被损坏，则仍应能够重构n比特数据流中的（k-c）比特错误。

请注意我当然不知道错误位置 :)

示例：

我可以想到的一种算法是这样的。要保护免受错误影响的n比特数据流。

让p成为相对素数最小的n。然后通过i = (p * j) mod n迭代数据流，通过选择每个偶数j的位异或子流来逐渐增加j。这个子流具有n/2个元素。迭代之后，我们已经获得了n/2个元素的奇偶校验。我们可以以同样的方式获取另一半的奇偶性（采用奇数j）。

这将为2比特丢失提供50%的错误减少。

好消息是我们现在可以变得任意更好。只需取下一个较高的相对素数再重复一次。现在我们的错误率为25％。基本上，每次添加两个附加的奇偶校验比特时，我们可以将错误率减半。

- thesaint

可能不完美的解决方案之一是随机洗牌，然后创建 n/k 个分组，为每个分组计算 XOR 位，并将这些 XOR 位随机混合到数据流中。这基本上可以容忍 k 个位置的比特损失，带有 k 比特的开销，但缺点是如果两个错误发生在同一组中，我们就会失败 :D。 - thesaint

2

作为灵感，可以看一下RAID-5。那里的算法处理数据丢失的情况。 - Steffen Ullrich

哦，谢谢，这是一个有趣的相关性 :) - thesaint

3个回答

1

Reed-Solomon编码RS（255,223,32）可以纠正影响255个字节中的16个或更少字节的所有错误模式 - 无论它们如何被破坏。如果您事先知道哪些字节已经损坏，则其功能甚至更高。这种类型的错误称为擦除。

RS（255，255-k）解码器可以纠正以下范围内的所有字节错误/擦除模式：

（2 * errorCount + erasureCount）<= k

这意味着编码器获取（255-k）字节的信息块并计算k字节的奇偶校验信息，将其与信息块一起作为255字节的块传输。

好消息是，在编码数据时不需要决定errorCount/erasureCount分布，只需告诉接收端的解码器要担心哪些字节位置，它将处理这些错误以及未知位置中的任何剩余错误（只要满足上述条件）。

在某些传输方案中，多个Reed-Solomon块被编码，然后在多个数据包中传输。这样，单个数据包丢失的缺失字节会分布在多个Reed-Solomon码字中。这通常称为交织。

您可以查看我的Reed-Solomon编码器/解码器 C语言实现。它可以处理错误和擦除，并且包含一个不错的测试工具。

- Jens

1

如果您正在发送无限精度的实数/复数，那么有一种简单的解决方案，基于这样一个事实：通过任何具有不同x坐标的d个点，存在唯一的次数为d-1的多项式。因此，给定d个数据点，您可以找到这个多项式（例如Lagrange插值），并在另外n个点上进行评估。如果丢弃d + n点中的任何n个值，则仍可以从其他n个点的值中恢复多项式。在实践中，这通常是不可用的，因为它在数值上不稳定。

在大型离散字母表上，您将询问与密码学中的秘密共享相关的内容，其中您希望能够在至少拥有n个密钥的情况下解码消息。您的目标略有不同，但一些有效的秘密共享技术可能会起作用。

你需要的是一个错误检测代码。这与纠错码并没有太大区别，最小距离为n的二进制码是一组二进制向量，以便任意两个不同向量之间至少有n个不同位。该码将使您能够检测n-1个错误，并且您可以在已知位置纠正n-1个错误（或在未知位置纠正（n-1）/2个错误）。

如果两个码字只在n个位置上不同，那么如果你失去了这些位置，你就无法区分这两个码字，因此你也无法恢复数据。

一些最简单的纠错码在结尾添加校验和。参见BCH codes，其中包含无限个代码族，其最小距离可任意大。拥有无限个代码族是很好的，因为在实践中，人们发送固定长度的小数据块，但在问题中，如果要优化您可以纠正的错误数量，则需要一个巨大的数据块。这些代码概括了添加奇偶校验位的思想：选择某个多项式p(x)，然后确保您发送的位是可被p(x)整除的多项式系数，使用模2（或有限域）的系数算术。例如，您可以向7个数据位添加8个校验位，然后通过已知位置纠正多达4个错误。在BCH代码中，当存在错误时恢复消息比许多其他代码更简单。一种解码方法与我提到的用于实值数据的插值多项式相关。

- Douglas Zare

谢谢你的解释。我不确定你的答案是否更适合，但我喜欢上面那个长发的东西是一个可以实际使用的工作实现，而我现在对这里的所有数学有点排斥 : )。 - thesaint

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Damon · Accepted Answer

您需要使用一种擦除码（而非错误检测码），因为连接层和传输层会处理错误检测。由于您正试图减轻UDP数据包丢失的影响，因此您已经知道了哪些部分缺失 - 缺少了丢失的数据包。

在字节（或位）级别上不存在擦除或错误，至少不可能有任何合理的可能性（至少有两个底层协议层，有时是三个，每个层都有校验和，这可以保证）。您要么收到完整、完好无损的数据报，要么没有。从来没有中间状态。

柯西里德-所罗门码是您可以考虑的一类算法，它们将长度为k的数据块转换为k+m块，并允许恢复原始数据，即使最多出现m个擦除。这种算法的一个特殊情况是“奇偶校验”，它的编码和解码都是简单的异或操作，且m=1。这是Raid-5中使用的算法，在上面的评论中提到过。

总之，您需要使用longhair。

作为替代方案，如果您要向多个方发送大量数据，并且想要变得复杂，请考虑“喷泉码”。这些代码要复杂得多（因此速度较慢），不太节省位数，但它们允许您创建任意数量的数据包，其中任何k都将重构k长度的原始消息。如果您能够组播到许多客户端，这将使您节省大量带宽，所有客户端都需要一个大型数据集，但不一定同时开始下载。