包丢失纠错码(UDP)

Question

我真的不知道要找什么，因为我得到的所有“纠错代码”是相关的情况下，你不知道错误的位置。因此，这些代码比我所需要的要复杂得多，效率更低。

在下面，请注意，位等于包(因为只有整个包可以丢失，因此位类比非常适合)。

是否有ECC考虑到您已经知道哪些k位丢失了，并且只为您提供了一种在那些k个位置重建数据存储的方法？此外，由ECC添加的位应该是独立的(最好)。这样，如果数据包丢失发生在数据的ECC部分，它仍然可以重建一些原始数据(并不总是会有k个错误，大多数情况下不会出现任何错误)。因此，ECC对自己添加的ECC位具有容错性是很重要的。

这是一个很大的不同，海事组织。对于一个缺失的位--它很简单，我可以只使用一个XOR位。但我不够聪明，不能把它推广到n位。

因此，我有一个n位流，并且我知道在k位之前丢失了(我真的知道哪些比特是准确的，它们是缺失的，腐败是不可能的)。现在，我需要一个编解码器，它可以用尽可能少的开销来重构它们。我梦想拥有(n+k)位来纠正n位流中的k个随机位错误:)。在此基础上，理想情况下，如果添加到n位数据流中的任何k ECC位被破坏，比如k位的c位被破坏，那么它仍然能够在n位流中重建(k-c)位错误。

请注意ofc，我不知道错误的位置在预先通过xD。

示例：

我能想到的一个算法就是这个。保护n位的数据不受错误影响。

设p是n的最小相对素数，然后用i= (p * j) mod n迭代数据流，增加j，XORing选择偶数j的位得到的子流，该子流有n/2元素。经过迭代，我们得到了n/2元素的奇偶性。我们可以用同样的方法(取奇数j)得到另一半的奇偶。

这将使2位丢失的错误减少50%。

好的一面是我们现在可以任意地变得更好。只需取下一个较高的相对质数，然后再做一次。现在我们有25%的错误机会。基本上，我们可以减少一半的错误机会，每次我们增加两个额外的奇偶校验位。

Answer 1

您需要一个擦除代码(而不是错误检测代码)。差错检测由链路层和传输层负责。因为您试图减少UDP数据包丢失，所以您已经知道丢失了哪些部分--丢失的数据包丢失了。

在字节(或位)级别上不存在擦除或错误，至少没有任何合理的可能性(至少有两个底层协议层，有时是三个层，每个层都带有校验和，以确保这一点)。你要么收到一个完整的完整的数据报，要么你没有收到。

柯西里德所罗门码是一种你可以考虑的算法，这些算法把k个一定长度的数据块转换成k+m块，并允许恢复给出最多m个擦除的原始数据。这种算法的一个特例是奇偶校验，它的编码和解码都是简单的xor操作，而m=1就是Raid-5中使用的算法，在上面的评论中已经提到了这一点。

总之，你想要长发。

作为另一种选择，如果你有大量的数据要传送给几个人，而且你想要花哨，你可以考虑喷泉代码。这些信息要复杂得多(因此速度更慢)，而且更低的比特效率，但它们允许您创建任意数量的数据包，其中任何k将重构k长度原始消息。这允许您节省大量的带宽，如果您能够多播到许多客户端，他们都想要一个大的数据集，但不一定要同时开始下载。

Answer 2

如果你发送的是无限精确的实数/复数，那么就会有一个简单的解，它基于这样一个事实:通过具有不同x坐标的任意d点，就有一个唯一的d-1次多项式。所以，给定d个数据点，你找到这个多项式(比如拉格朗日插值)，并在n个点上对它进行评估。如果在d+n点的任意n处丢弃这些值，仍然可以从另一个n的值中恢复多项式。实际上，这通常是不可用的，因为它在数值上是不稳定的。

在一个大的离散字母表上，您可能会询问与密码学中的秘密共享相关的内容，在密码学中，当您有至少t个密钥时，您希望能够解码一条消息。您的目标略有不同，但一些高效的秘密共享技术可能会奏效。

您需要的是一个检错码.，它与纠错代码并没有太大的不同。具有最小距离n的二进制码是一组二进制向量，使得任意两个不同的向量在至少n个位置上不同。此代码将允许您检测n-1错误，并且可以更正已知位置的n-1错误(或未知位置的(n-1)/2错误)。

如果两个代码单词在n个位置上不同，那么如果丢失了这些位置，就无法区分代码单词，因此无法恢复数据。

一些最简单的纠错代码将校验和附加到末尾。关于任意大的最小距离的无限大码族，请参见BCH码。有一个无限的家庭是很好的，因为当人们在实践中发送小的固定数据块时，在您的问题中，如果您想优化错误的数量，那么您希望有一个巨大的块，这样您就可以为消息的扩展进行修正。这就推广了添加奇偶校验位的思想:您选择了一些多项式p(x)，然后确保您发送的位是可被p(X)除的多项式的系数，并使用系数算术mod 2(或在有限域中)。例如，您可以在7个数据位中添加8个检查位，然后在已知位置的情况下更正最多4个错误。在BCH码中，当存在错误时恢复消息比在许多其他代码中更简单。一种译码方法是与我提到的实值数据的插值多项式有关的.

Answer 3

里德-所罗门代码RS( 255 ,223,32)纠正了影响255个字节中的16个(或更少)的所有错误模式--不管它们是如何损坏的。如果您事先知道哪些字节已经损坏，那么功能就会更高。这种类型的错误称为擦除。

RS(255,255-k)解码器校正所有字节错误/擦除模式，限制在：

(2*错误计数+ erasureCount) <= k

它意味着编码器接受( 255 -k)字节的信息块，并计算奇偶校验信息的k字节，奇偶校验信息与信息块一起作为255字节的块传输。

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

在某些传输方案中，对多个里德-所罗门块进行编码，然后在多个分组中传输。这样，单个丢包中丢失的字节就会分散在多个里德-所罗门码字上。这常被称为交织。

您可以看看我的里德-所罗门编码器/解码器 C-实现。它处理错误和擦除，并有一个不错的测试平台包括在内。