使用里德-所罗门码Reed-Solomon奇偶校验提高传输数据的可靠性 - berthub

21-06-15 banq

里德-所罗门码Reed-Solomon 是一种很酷的方式来保护消息免受损坏或部分到达。根据您的选择,您可以将t 个奇偶校验符号添加到消息中。
这些t奇偶校验符号允许您:
  • 从未知位置的t/2 个损坏的符号中恢复
  • 从已知位置的t 个损坏/丢失的符号中恢复
  • 检测消息是否已损坏(除非损坏超过t 个)

一个符号可以是 8 位长并等于一个字节,但情况并非一定如此。

这不仅是非常好的错误恢复能力,而且可以证明没有比这更好的了(至少,不是在每个符号的基础上)。
您可以随意选择t,这意味着您可以选择您想要的保护级别。
但是,您不能随意选择生成的受保护块的长度:这始终是 255 字节(使用字节大小的符号时)。

请注意,对于 7 位符号,块大小将为 127 个符号,或总共 889 位,相当于大约 111 个字节。

您添加的奇偶校验符号越多,您的消息在块中的空间就越小。
 

在实践中使用 Reed-Solomon
如前所述,只要我们使用 8 位符号,总码字将始终为 255 字节长。
根据您的需要,您可能需要更多或更少的保护。但是请注意,计算机硬件很少会损坏单个字节(即一旦它们命中您的编程语言)。更常见的是整个扇区、磁盘或内存库消失在您身上。
但是,您的 RAM 很可能会损坏单个数据位。此外,TCP 和以太网校验和足够弱,以致于可能会在未被发现的情况下漏掉损坏。
然而,这种情况非常罕见,您最好依靠密码学来检测此类数据完整性问题并完全重新传输。RS 在这个领域不值得。
您没有看到大量损坏字节的原因之一是,许多传输和存储技术内部已经使用 RS 或类似 RS 的算法,而不会向您公开这些。
对于程序员来说,一个更常见的问题是数据的彻底消失。这一直发生 - 磁盘经常发生故障,甚至 SSD,甚至可能更是如此。此外,网络总是会丢弃数据包。
 

纠删码
举个例子,假设我们有一个音频流,我们想要针对丢弃的数据包进行强化。假设我们要针对 20% 的数据包丢失添加保护。
为此,我们可以取 4 个原始数据包,为每个数据包添加 25% 的奇偶校验,然后将 4 个原始数据包涂抹在 5 个新数据包上,如下所示:


请注意,我们还必须为每个数据包添加一个序列号。这允许接收器准确检测丢失了哪些数据包。
如果没有丢失任何东西,接收器会等待,直到所有 5 个数据包都进入,并取消涂抹。在这种情况下,运行 Reed-Solomon 解码器将只检测任何(非常罕见的)单个损坏的字节。
但是如果第四个数据包丢失了,事情将是这样的:


原来的 4 个小包中的每一个现在都有 25% 的洞!为了从中恢复,RS 解码器需要准确地知道消息的哪些部分丢失了。幸运的是,我们知道这一点,因为我们知道分发模式并且我们知道哪个数据包丢失了。
因此,RS 能够完美地重建四个原始数据包,并且我们的音频流不会中断。
上面是一个非常简单的示例,说明如何使用 RS 获得对大量数据丢失的恢复能力。但是请注意,在此类计划中花很多心思是值得的。丢包会是什么样子?它可能会爆发吗?什么样的延迟是可以接受的?一个非常有效的设置可能会缓冲 30 秒的数据,例如,这对于实时采访是无用的。
上述方案也适用于冗余文件和数据存储。例如,许多 RAID6 变体或多或少地使用如上所述的 RS。
 

总结

  • 普通 8 位模式下的 Reed-Solomon 对 255 字节块进行操作
  • 您可以选择这样的块中有多少是奇偶校验的
  • 如果您选择t个字节,则您的有效载荷为 255- t个字节
  • 然后解码器可以纠正未知位置的t/2错误
  • 它还可以纠正已知位置的t错误(擦除)
  • RS 还将可靠地检测但不修复多达t 个错误
  • 对于较小的有效载荷,可以“填充”部分甚至大部分 255- t有效载荷字节
  • RS 不能替代加密完整性检查!
  • 使用 Reed-Solomon 时,请注意它的确切配置方式,(255,223) 不能告诉您足够的信息
  • 通常不需要 RS 来保护磁盘上的数据或在 IP 网络传输期间防止单个字节错误
  • 然而,RS 可以非常擅长为丢失的磁盘或数据包添加冗余
  • 虽然处理概率的代码有很多创新,但 LDPC、Turbo 和 Polar 码并不适用于对具体位和字节进行纠错



详细点击标题

1