里德-所罗门纠错

里德-所罗门纠错是一种前向纠错码。它通过对数据构建的多项式进行超采样来工作。多项式在几个点上被评估,这些值被发送或记录。对多项式的采样次数超过了必要的范围,使得多项式被过度确定。只要它能正确接收 "许多 "点,即使存在 "少数 "坏点,接收器也能恢复原始多项式。

里德-所罗门编码被用于许多不同类型的商业应用,例如CDDVD和蓝光光盘,数据传输技术,如DSL和WiMAX,以及广播系统,如DVB和ATSC。

概述

里德-所罗门码是块状码。这意味着,一个固定的输入数据块被处理成一个固定的输出数据块。在最常用的R-S码(255,223)的情况下--223个里德-所罗门输入符号(每个8比特长)被编码成255个输出符号。

  • 大多数R-S ECC方案是系统性的。这意味着,输出密码的某些部分包含了原始形式的输入数据。
  • 选择8位的Reed-Solomon符号大小是因为更大的符号大小的解码器在目前的技术下很难实现。这一设计选择迫使最长的码字长度为255个符号。
  • 标准的(255, 223)里德-所罗门码能够纠正每个码字中多达16个里德-所罗门符号错误。由于每个符号实际上是八个比特,这意味着该码可以纠正由于内部卷积解码器而产生的多达16个短时的错误。

里德-所罗门码,像卷积码一样,是一种透明码。这意味着,如果信道符号在某处被颠倒了,解码器仍会工作。其结果将是原始数据的补充。然而,如果使用虚拟补零,里德-所罗门码就会失去其透明度。由于这个原因,在进行里德-所罗门解码之前,必须解决数据的意义(即,真或补)。

Voyager计划的情况下,R-S码在与(7, 1/2)卷积(Viterbi)内码串联时达到了接近最佳性能。由于每个要纠正的错误需要两个校验符号,这导致每个码字总共需要32个校验符号和223个信息符号。

此外,在卷积编码之前,里德-所罗门编码可以在符号的基础上交错进行。由于这样可以将码字中的符号分开,维泰尔比解码器的突发干扰任何一个码字中的一个以上的里德-所罗门符号的可能性就会降低。

基本思路

里德-所罗门码的关键思想是,编码的数据首先被可视化为多项式。该代码依赖于代数中的一个定理,该定理指出,任何k个不同的点都能唯一地确定一个最多为k-1度的多项式。

发送方确定一个度数为k - 1 {displaystyle k-1}的{\displaystyle k-1} 多项式,在一个有限域上,它代表k {displaystyle k}k 数据点。然后,该多项式通过其在不同点的评估被 "编码",而这些值就是实际发送的内容。在传输过程中,这些值中的一些可能会被破坏。因此,实际发送的点超过k个。只要有足够多的值被正确接收,接收者就可以推断出原始多项式是什么,并对原始数据进行解码。

就像人们可以通过插值的方式修正一条曲线一样,里德-所罗门码可以弥补数据块中的一系列错误,以恢复绘制原始曲线的多项式的系数。

历史

该代码是由欧文-S-里德和古斯塔夫-所罗门在1960年发明的,他们当时是麻省理工学院林肯实验室的成员。他们的开创性文章题为 "某些有限域的多项式编码"。写这篇文章时,数字技术还不够先进,无法实现这一概念。1982年,RS码在大规模生产的产品中的首次应用是光盘,其中使用了两个交错的RS码。1969年,Elwyn Berlekamp和James Massey开发了一种大距离RS码的高效解码算法。今天,RS码被用于硬盘驱动器DVD、电信和数字广播协议中。


AlegsaOnline.com - 2020 / 2023 - License CC3