数据包丢失(UDP)的纠错码 [英] Error correcting codes for packet loss (UDP)

问题描述

我不知道要寻找什么，因为我得到的所有与错误纠正代码"有关的东西都与您不知道错误位置的情况有关.因此，这些代码比我需要的要复杂得多，效率低下.

I have no real idea what to look for, since all I get with "Error correcting codes" is stuff related to cases where you don't know the location of the error. Thus those codes are much more complicated an inefficient than I need them to be.

在下面，请注意，位等于数据包(因为仅可能丢失整个数据包，因此该位比喻非常合适).

In the following, note that bits are equal to packets (because only a whole packet can be missing, thus the bit analogy fits very well).

是否存在已考虑到您已经知道哪些 k 位丢失的ECC，而仅提供了一种在这些 k 位置重建数据流的方法?另外，由ECC添加的位应该是独立的(最好).这样，如果数据的ECC部分内部发生数据包丢失，它仍然可以重构某些原始数据(并非总是会出现k个错误，大多数情况下不会有k个错误.因此，重要的是ECC可以容错自己的容错添加了ECC位).

Are there ECCs that take into account that you already know WHICH k-bits are missing and only provide you with a way to reconstruct the datastream in those k places? Additionally, the bits added by the ECC should be independent (preferably). Such that if packet loss occurs inside the ECC portion of the data, it still can reconstruct some of the original data (not always will there be k errors, mostly there will be none. So its important that the ECC is fault tolerant to its own ECC bits added).

这与IMO有很大的不同.对于一个简单的缺失位，我只能使用一个XOR位.但是我不够聪明，无法将其概括为n位.

That is a big difference IMO. For one missing bit its simple, I can just use one XOR bit. But I am not clever enough to generalize it to n-bits.

再说一次，我有一个 n 位流，我知道最多缺少 k 位(我真的知道到底是哪个位，它们是丢失，则无法进行损坏).现在，我需要一个编解码器，它可以以尽可能少的开销添加到数据流中来重建它们.我梦想着拥有(n + k)位来纠正 n 位流中的 k 随机位错误:).最重要的是，理想情况下，如果添加到 n 位数据流中的任何 k 个ECC位中的任何一个都损坏了，例如说 k 位被损坏，那么它仍然应该能够重建 n 位流中的(kc)位错误.

So again, I have a stream of n-bits, and I know that up to k bits are missing (I really know which ones exactly and that they are missing, corruption is not possible). Now I need a codec that can reconstruct them with as little overhead added to the datastream as possible. I am dreaming of having (n+k) bits to correct k random bit errors in an n bit stream :). On top of that, ideally, if any of those k ECC bits added to the n bit data stream gets corrupted, like say c bits of the k bits get corrupted, then it should still be able to reconstruct (k-c) bit errors in the n bit stream.

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

Please note ofc that I do not know the error positions in advance though xD.

示例:

我能想到的一个算法就是这个. n位数据流要加以保护以防止错误.

One algorithm I can think of is this. Datastream of n bits to be protected against errors.

让p是与n最小的相对素数.然后，通过递增j，对i =(p * j)mod n的数据流进行迭代，对通过选择每个偶数j的位获得的子流进行XOR.该子流具有n/2个元素.迭代后，我们获得了n/2个元素的奇偶校验.我们可以用相同的方式(取奇数j)获得另一半的奇偶校验.

Let p be the smallest relative primes to n. Then iterate through the datastream with i = (p * j) mod n, by incrementing j, XORing the substream obtained by selecting bits of every even j. This substream has n/2 elements. After iterating, we have obtained a parity for n/2 the elements. We can obtain another parity for the other half in the same way (taking odd j).

对于2位丢失，这可减少50％的错误.

This yields 50% error reduction for 2 bit losses.

好的一面是，我们现在可以任意改善.只需采用下一个较高的相对素数，然后再次执行相同操作即可.现在，我们有25％的错误机会.基本上，每次添加两个额外的奇偶校验位，我们就可以将错误机会减少一半.

The bright side is we can now get arbitrarily better. Just take the next higher relative prime and do the same again. Now we are at 25% error chance. Basically we can cut the error chance in a half each time we add two additional parity bits.

推荐答案

您需要删除代码(而不是错误检测代码).错误检测由链路和传输层负责.由于您正在尝试减轻UDP数据包的丢失，因此您已经知道丢失了哪些部分-丢失的数据包已丢失.

You need an erasure code (not an error detection code). Error detection is taken care of by the link and transport layer. Since you are trying to mitigate UDP packet loss, you already know which parts are missing -- the dropped packet is missing.

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

There is no such thing as erasures or errors on a byte (or bit) level, at least not with any reasonable likelihood (there are at least two underlying layers of protocols, sometimes three, each with a checksum, which makes sure of that). You either receive a complete, intact datagram, or you don't. Never anything in between.

Cauchy Reed Solomon码是您可以考虑的一类算法，它们将一定长度的 k 个数据块转换为 k + m 个块，并允许恢复最多提供 m 个擦除的原始数据.此类算法的一种特殊情况是 parity ，对于该算法，编码和解码都是简单的xor运算，并且 m = 1 .这是Raid-5中使用的算法，上面的评论中已经提到过.

Cauchy Reed Solomon codes is one class of algorithms you may consider, these transform k blocks of data of some length into k+m blocks, and allow restoration of the original data given at most m erasures. A special case for this kind of algorithm is parity, for which both encoding and decoding is a simple xor operation, and m=1. This is the very algorithm used in Raid-5, which was mentioned in a comment above.

总之，您要长发.

作为替代方案，如果您有大量数据要传输给多个参与方，并且想花哨的话，可以考虑使用源代码.这些复杂得多(因而也更慢)，位效率也更低，但是它们允许您创建任意数量的数据包，其中任何k 都将重构k个长度的原始消息.如果您能够多播到许多都想要一组大数据但不必同时开始下载的客户端，则可以节省大量带宽.

As an alternative, if you have a lot of data to transmit to several parties, and you want to be fancy, you can consider fountain codes. These are much more complicated (and thus slower) and less bit-efficient, but they allow you to create an arbitrary number of packets, of which any k will reconstruct the k-lenght original message. This allows you to save a lot of bandwidth if you are able to multicast to a lot of clients who all want one large set of data, but don't necessarily start downloading at the same time.

这篇关于数据包丢失(UDP)的纠错码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！