丢包纠错码 (UDP)
Error correcting codes for packet loss (UDP)
我真的不知道要寻找什么，因为我从 "Error correcting codes" 得到的都是与您不知道错误位置的情况相关的东西。因此，这些代码比我需要的要复杂得多，效率也低得多。
在下文中，请注意比特等于数据包（因为只能丢失一个完整的数据包，因此比特类比非常合适）。
是否有 ECC 考虑到您已经知道缺少 k 位并且只为您提供一种在 中重建数据流的方法k 个地方？此外，ECC 添加的位应该是独立的（最好）。这样如果数据的ECC部分发生丢包，它仍然可以重建一些原始数据（并不总是有k个错误，大多数会有none。所以重要的是ECC是错误的容忍其自身添加的 ECC 位）。
在我看来，这是一个很大的不同。对于缺少一位很简单，我可以只使用一个 XOR 位。但是我不够聪明，无法将其概括为n位。
所以，我有一个 n 位的流，我知道最多 k 位丢失（我真的确切地知道哪些以及它们丢失了，腐败是不可能的）。现在我需要一个编解码器来重建它们，同时尽可能少地增加数据流的开销。我梦想有 (n+k) 位来纠正 k 随机位错误 n比特流 :)。最重要的是，理想情况下，如果添加到 n 位数据流的任何 k ECC 位被破坏，比如 [=32= k 位的 ]c 位被损坏，那么它应该仍然能够重建 (k-c) 位错误n 比特流。
请注意ofc虽然xD我不知道错误位置。
示例：
我能想到的一种算法是这样的。要防止错误的 n 位数据流。
令 p 为 n 的最小相对素数。然后用 i = (p * j) mod n 迭代数据流，通过递增 j，对通过选择每个偶数 j 的位获得的子流进行异或。此子流有 n/2 个元素。迭代后，我们得到了 n/2 个元素的奇偶校验。我们可以用同样的方法得到另一半的另一个奇偶校验（取奇数j）。
对于 2 位丢失，这会产生 50% 的错误减少。
好的一面是我们现在可以任意变得更好。只需取下一个更高的相对质数并再次执行相同的操作。现在我们有 25% 的错误机会。基本上，每次我们添加两个额外的奇偶校验位时，我们都可以将错误机会减少一半。
如果您要发送无限精度 real/complex 数字，将有一个简单的解决方案，基于这样一个事实，即通过具有不同 x 坐标的任何 d 个点，都有一个唯一的 d-1 次多项式。因此，给定 d 个数据点，您可以找到此多项式（例如使用拉格朗日插值）并在 n 个以上的点上对其进行评估。如果您丢弃 d+n 点中任意 n 处的值，您仍然可以从其他 n 处的值恢复多项式。实际上这通常是不可用的，因为它在数值上不稳定。
在一个大的离散字母表上，您会问一些与密码学中的 secret sharing 相关的问题，您希望能够在 n 中至少有 t 个密钥时解码消息。您的目标略有不同，但一些有效的秘密共享技术可能会奏效。
你需要的是一个error detecting code. 这与纠错码没什么不同。具有最小距离 n 的二进制代码是一组二进制向量，因此任何两个不同的向量至少在 n 个地方不同。此代码将让您检测到 n-1 个错误，并且您可以更正已知位置的 n-1 个错误（或未知位置的 (n-1)/2 个错误）。
如果两个码字只有n个地方不一样，那么丢掉这几个地方，就无法区分码字，也就无法恢复数据。
一些最简单的纠错码将校验和附加到末尾。请参阅 BCH codes 以了解具有任意大最小距离的无限代码族。拥有一个无限的家庭是件好事，因为虽然人们在实践中发送固定的小数据块，但在您的问题中，如果您想要优化可以纠正消息扩展的错误数量，那么您希望拥有一个巨大的数据块。这些概括了添加奇偶校验位的想法：您选择一些多项式 p(x)，然后确保您发送的位是可被 p(x) 整除的多项式的系数，系数算术 mod 2 (或在有限域中）。例如，您可以将 8 个校验位添加到 7 个数据位，然后纠正最多 4 个位置已知的错误。在 BCH 代码中，在出现错误时恢复消息比在许多其他代码中更简单。一种解码方法与我提到的用于实值数据的插值多项式有关。
您需要一个擦除代码（不是错误检测代码）。 link 和传输层负责错误检测。由于您正在尝试减少 UDP 数据包丢失，因此您已经知道丢失了哪些部分——丢失的数据包丢失了。
不存在字节（或位）级别的擦除或错误之类的事情，至少没有任何合理的可能性（至少有两个底层协议，有时是三个，每个协议都有一个校验和，这确保这一点）。您要么 收到完整、完整的数据报，要么您没有。从来没有介于两者之间。
Cauchy Reed Solomon 码是您可能会考虑的一种 class 算法，这些算法将 k 一定长度的数据块转换为 k+m 块，并允许恢复最多 m 次擦除的原始数据。这种算法的一个特例是 parity，编码和解码都是简单的异或运算，m=1。这正是 Raid-5 中使用的算法，在上面的评论中提到过。
一句话，你想要longhair。
作为替代方案，如果你有很多数据要传输给多方，并且你想要花哨，你可以考虑喷泉代码。这些更复杂（因此更慢）并且比特效率更低，但它们允许您创建任意数量的数据包，其中 any k 将重建 k-lenght 原始消息.如果您能够向许多都需要一大组数据但不一定同时开始下载的客户端进行多播，这可以让您节省大量带宽。
Reed-Solomon 代码 RS(255,223,32) 纠正了影响 255 个字节中的 16 个（或更少）字节的所有错误模式 - 无论它们如何损坏。如果您事先知道哪些字节已损坏，则功能会更高。这种类型的错误称为擦除。
RS(255, 255-k) 解码器纠正所有字节 error/erasure 模式，其边界为：
(2*errorCount + erasureCount) <= k
表示编码器取(255-k)字节的信息块，计算出k字节的校验信息，作为255字节的块与信息块一起发送。
好东西是你不需要在编码数据的时候决定errorCount/erasureCount分布，只要告诉接收端的解码器需要担心哪些字节位置，它就会处理这些错误以及未知位置中的任何剩余错误（只要满足上述条件）。
在一些传输方案中，多个 Reed-Solomon 块被编码，然后在多个数据包中传输。这样，单个数据包丢失造成的丢失字节分布在多个 Reed-Solomon 代码字中。这通常称为交织。
你可以看看我的 Reed-Solomon Encoder/Decoder C 实现。它处理错误和擦除，并包含一个很好的测试台。
我真的不知道要寻找什么，因为我从 "Error correcting codes" 得到的都是与您不知道错误位置的情况相关的东西。因此，这些代码比我需要的要复杂得多，效率也低得多。
在下文中，请注意比特等于数据包（因为只能丢失一个完整的数据包，因此比特类比非常合适）。
是否有 ECC 考虑到您已经知道缺少 k 位并且只为您提供一种在 中重建数据流的方法k 个地方？此外，ECC 添加的位应该是独立的（最好）。这样如果数据的ECC部分发生丢包，它仍然可以重建一些原始数据（并不总是有k个错误，大多数会有none。所以重要的是ECC是错误的容忍其自身添加的 ECC 位）。
在我看来，这是一个很大的不同。对于缺少一位很简单，我可以只使用一个 XOR 位。但是我不够聪明，无法将其概括为n位。
所以，我有一个 n 位的流，我知道最多 k 位丢失（我真的确切地知道哪些以及它们丢失了，腐败是不可能的）。现在我需要一个编解码器来重建它们，同时尽可能少地增加数据流的开销。我梦想有 (n+k) 位来纠正 k 随机位错误 n比特流 :)。最重要的是，理想情况下，如果添加到 n 位数据流的任何 k ECC 位被破坏，比如 [=32= k 位的 ]c 位被损坏，那么它应该仍然能够重建 (k-c) 位错误n 比特流。
请注意ofc虽然xD我不知道错误位置。
示例：
我能想到的一种算法是这样的。要防止错误的 n 位数据流。
令 p 为 n 的最小相对素数。然后用 i = (p * j) mod n 迭代数据流，通过递增 j，对通过选择每个偶数 j 的位获得的子流进行异或。此子流有 n/2 个元素。迭代后，我们得到了 n/2 个元素的奇偶校验。我们可以用同样的方法得到另一半的另一个奇偶校验（取奇数j）。
对于 2 位丢失，这会产生 50% 的错误减少。
好的一面是我们现在可以任意变得更好。只需取下一个更高的相对质数并再次执行相同的操作。现在我们有 25% 的错误机会。基本上，每次我们添加两个额外的奇偶校验位时，我们都可以将错误机会减少一半。
如果您要发送无限精度 real/complex 数字，将有一个简单的解决方案，基于这样一个事实，即通过具有不同 x 坐标的任何 d 个点，都有一个唯一的 d-1 次多项式。因此，给定 d 个数据点，您可以找到此多项式（例如使用拉格朗日插值）并在 n 个以上的点上对其进行评估。如果您丢弃 d+n 点中任意 n 处的值，您仍然可以从其他 n 处的值恢复多项式。实际上这通常是不可用的，因为它在数值上不稳定。
在一个大的离散字母表上，您会问一些与密码学中的 secret sharing 相关的问题，您希望能够在 n 中至少有 t 个密钥时解码消息。您的目标略有不同，但一些有效的秘密共享技术可能会奏效。
你需要的是一个error detecting code. 这与纠错码没什么不同。具有最小距离 n 的二进制代码是一组二进制向量，因此任何两个不同的向量至少在 n 个地方不同。此代码将让您检测到 n-1 个错误，并且您可以更正已知位置的 n-1 个错误（或未知位置的 (n-1)/2 个错误）。
如果两个码字只有n个地方不一样，那么丢掉这几个地方，就无法区分码字，也就无法恢复数据。
一些最简单的纠错码将校验和附加到末尾。请参阅 BCH codes 以了解具有任意大最小距离的无限代码族。拥有一个无限的家庭是件好事，因为虽然人们在实践中发送固定的小数据块，但在您的问题中，如果您想要优化可以纠正消息扩展的错误数量，那么您希望拥有一个巨大的数据块。这些概括了添加奇偶校验位的想法：您选择一些多项式 p(x)，然后确保您发送的位是可被 p(x) 整除的多项式的系数，系数算术 mod 2 (或在有限域中）。例如，您可以将 8 个校验位添加到 7 个数据位，然后纠正最多 4 个位置已知的错误。在 BCH 代码中，在出现错误时恢复消息比在许多其他代码中更简单。一种解码方法与我提到的用于实值数据的插值多项式有关。
您需要一个擦除代码（不是错误检测代码）。 link 和传输层负责错误检测。由于您正在尝试减少 UDP 数据包丢失，因此您已经知道丢失了哪些部分——丢失的数据包丢失了。
不存在字节（或位）级别的擦除或错误之类的事情，至少没有任何合理的可能性（至少有两个底层协议，有时是三个，每个协议都有一个校验和，这确保这一点）。您要么 收到完整、完整的数据报，要么您没有。从来没有介于两者之间。
Cauchy Reed Solomon 码是您可能会考虑的一种 class 算法，这些算法将 k 一定长度的数据块转换为 k+m 块，并允许恢复最多 m 次擦除的原始数据。这种算法的一个特例是 parity，编码和解码都是简单的异或运算，m=1。这正是 Raid-5 中使用的算法，在上面的评论中提到过。
一句话，你想要longhair。
作为替代方案，如果你有很多数据要传输给多方，并且你想要花哨，你可以考虑喷泉代码。这些更复杂（因此更慢）并且比特效率更低，但它们允许您创建任意数量的数据包，其中 any k 将重建 k-lenght 原始消息.如果您能够向许多都需要一大组数据但不一定同时开始下载的客户端进行多播，这可以让您节省大量带宽。
Reed-Solomon 代码 RS(255,223,32) 纠正了影响 255 个字节中的 16 个（或更少）字节的所有错误模式 - 无论它们如何损坏。如果您事先知道哪些字节已损坏，则功能会更高。这种类型的错误称为擦除。
RS(255, 255-k) 解码器纠正所有字节 error/erasure 模式，其边界为：
(2*errorCount + erasureCount) <= k
表示编码器取(255-k)字节的信息块，计算出k字节的校验信息，作为255字节的块与信息块一起发送。
好东西是你不需要在编码数据的时候决定errorCount/erasureCount分布，只要告诉接收端的解码器需要担心哪些字节位置，它就会处理这些错误以及未知位置中的任何剩余错误（只要满足上述条件）。
在一些传输方案中，多个 Reed-Solomon 块被编码，然后在多个数据包中传输。这样，单个数据包丢失造成的丢失字节分布在多个 Reed-Solomon 代码字中。这通常称为交织。
你可以看看我的 Reed-Solomon Encoder/Decoder C 实现。它处理错误和擦除，并包含一个很好的测试台。