里德–所罗门码是一种纠错码,通过向数字信息中添加具有数学结构的冗余,使受损或缺失的数据能够恢复。它的符号取自有限域,通常是含有256个元素的域,因此每个符号可以表示一个字节。与直接按单个比特规定纠错能力的编码不同,里德–所罗门码以完整符号为单位纠错:无论一个符号中只有一个比特发生变化,还是所有比特都发生变化,该符号的损坏都只计为一个错误。
里德–所罗门码由欧文·S. 里德和古斯塔夫·所罗门于1960年提出,后来成为数字通信与存储领域的基础技术。它们用于保护光盘、二维条码、通信链路和分布式存储系统中的信息。其核心数学性质是:一条消息可以表示为一个多项式,只要获得足够多个正确的求值结果,就能重建该消息。这使里德–所罗门码在给定码长和符号集大小的条件下,实现冗余量与最小距离之间的最优权衡。
同一种底层构造支持多种不同的工程用途。接收端可以定位并纠正位置未知的错误,也可以重建缺失位置已知的数据,或同时执行这两种操作。实际系统通过系统编码、缩短、交织、与其他编码级联以及专用译码算法,使这种编码适应具体需求。
起源与发展
里德和所罗门在1960年的论文《某些有限域上的多项式码》中提出了这一构造。他们的方法不同于早期编码理论大多采用的二进制视角:它不再仅仅将一个码块看作由单个二进制位组成的序列,而是将符号视为一个更大的代数系统中的元素。这一构造以多项式求值作为差错防护的基础。一个低次多项式与另一个不同的同次多项式,不可能在过多的点上取值相同,因此,多项式的取值为区分有效消息提供了一种可控的方式,即使消息遭到破坏也依然如此。
最初的数学描述并未立即带来后来商业设备所需的低成本、高速译码方法。一种码即使具有可证明的纠错能力,仍可能难以高效译码。因此,代数译码的早期发展与码的构造本身同样重要。围绕博斯–乔杜里–霍昆格姆码开展的研究,包括彼得森方法和戈伦斯坦–齐尔勒方法,提供了根据代数校验确定错误位置的手段。在这一更广泛的框架中,里德–所罗门码可被视为具有特别优异的距离性质的非二元码。
埃尔温·伯利坎普提出了一种高效求解译码方程的方法,并在其1968年出版的《代数编码理论》一书中加以阐述。詹姆斯·梅西在1969年对这一方法作出解释,将其与能够生成给定序列的最短线性反馈移位寄存器的综合问题联系起来。由此形成的伯利坎普–梅西算法成为里德–所罗门译码器的标准组成部分。1975年,杉山康夫及其同事提出了另一种基于扩展欧几里得算法的译码方案。这些方法以适合电子实现的规整计算,取代了实用性较差的代数运算过程。
随着数字硬件使有限域运算的成本降低,里德–所罗门码的应用迅速普及。1982年投入商业应用的激光唱片,让广大公众间接接触到了里德–所罗门编码:其差错控制系统使数字音频能够容忍局部表面缺陷和读出错误。卫星与深空通信系统将这种码与其他差错控制技术结合使用,而后来的存储系统则利用其擦除恢复特性,在多个设备之间保护数据。
研究也逐渐超越了传统的唯一译码。马杜·苏丹1997年的研究以及1999年的古鲁斯瓦米–苏丹算法,展示了如何利用多项式插值,在超出传统半距离界限的情况下恢复出候选消息列表。这些进展将里德–所罗门码与复杂性理论及理论计算机科学联系起来;与此同时,实际工程仍侧重于可预测的时延、可控的硬件成本,以及与既有格式的兼容性。
有限域与求值构造
里德–所罗门码定义在一个有限域上,通常记为 ,其中 是素数的幂。域支持加、减、乘以及除以任意非零元素的运算,并满足通常的代数恒等式。这一点很重要,因为插值和译码都需要精确的除法运算。对任意合数取模的算术运算并不具备同样的结构:在这种情况下,某些非零元素没有乘法逆元。
选取 个互不相同的域元素 ,其中 ,再选取一个正整数 。一条消息由 个域符号组成,将它们视为一个多项式的系数:
其编码所得的码字为
可能的消息共有 条,因此码字也有 个。这种码是线性码,因为将两个消息多项式相加,或将一个消息多项式乘以某个域元素,都会使其求值向量发生相应的运算。其码率为 ,表示传输符号中用于承载信息的比例。
例如,在 上运算,所有运算结果都对 7 取模。设消息多项式为 ,在 处对它求值。得到的五符号码字为
只要有任意两个不同求值点处的正确值,就能确定这个次数至多为一的多项式。额外的求值结果使我们能够恢复缺失的符号,并将正确的直线与受损观测值所指示的直线区分开来。这个例子的规模虽小,但同样的构造也适用于大得多的域和次数更高的多项式。
工程中经常选用 ,其 256 个元素可以用一个字节的 256 种可能取值表示。这些元素并不是按模 256 进行乘法运算的整数。相反,每个元素都表示为一个次数小于八的二元多项式,乘法结果则对一个选定的八次不可约多项式取模。加法就是按位异或。采用不同的不可约多项式和不同的域基,可以表示彼此同构的域,但对应的数学元素可能具有不同的字节表示。
在求值描述中,全部 个域元素都可以作为求值点。传统的循环码实现通常使用 个非零元素,因此在 上便有了常见的 255 个符号的最大码长。对于扩展和广义构造,需要注意其具体约定。特别是,广义里德–所罗门码可以将每个求值结果乘以一个指定的非零坐标乘子,而不改变有关码距的基本论证。
距离、错误与擦除
分组码的保护能力由其最小汉明距离决定,即任意两个不同码字之间取值不同的坐标数的最小值。对于长度为 、维数为 的里德–所罗门码,这个距离为
证明依据的是域上多项式的一个基本事实。如果两个不同的消息多项式 和 的次数都小于 ,那么 就是一个次数至多为 的非零多项式,最多有 个根。因此,它们的求值向量至多在 个位置上相同,必然至少在 个位置上不同。
辛格尔顿界指出,对于长度为 、含有 个码字且字母表大小为 的码,其最小距离不可能大于 。里德–所罗门码达到了这一界限,因此属于最大距离可分码,通常简称为 MDS 码。这里的最优性是指在长度、维数和字母表大小固定时,最小距离达到最大;这并不意味着其译码时间、功耗、修复流量或其他各项系统成本也都最低。
错误是指某个符号的值发生了变化,而其位置事先未知。擦除则是指某个符号的位置已知,但其值无法获得,或已被明确标记为不可信。如果有 个错误和 个擦除,那么只要满足
就能保证唯一恢复。
一个位置未知的错误所消耗的距离裕量是一次擦除的两倍,因为译码器既要确定错误发生的位置,又要确定该位置应有的值。在只有擦除的情况下,任意 个保留下来的坐标都足以重建原始消息。
对于 码,冗余符号数为 32,最小距离为 33。该码可以纠正任意 16 个符号错误、任意 32 个擦除,也可以纠正二者的混合,例如 10 个错误加上 12 个擦除。其码率约为 。如果每个符号为一个字节,那么即使一个字节中的八个比特全部翻转,也仍然只算一个符号错误。反之,若 17 个不同字节各有一个比特受损,就超出了该码所能保证的纠错半径。
最小距离也提供了检错保证:任何影响位置数少于 的非零错误模式,都会使合法码字变成不属于该码的向量。不过,在实际运行中仍须区分检错与纠错。超出保证的纠错半径后,译码器可能报告失败、返回一个候选列表,或误纠正为另一个码字,具体取决于所用算法及接口。一个看似合法的译码后数据块,本身既不能证明其真实性,也不能保证未曾发生超出纠错能力的损坏。
编码、系统形式与码的变体
求值定义直接给出了一种编码方法:在选定的点上计算消息多项式的值。采用朴素方法直接求值大约需要 次域运算,不过,对于适当的规模和表示方式,也可以采用更快的多点求值技术。所得各坐标通常混合了原始系数,因此输入消息不一定会原封不动地出现在码字中。这是一种非系统编码方式,而不是码本身的局限。
系统编码器显式保留 个信息符号,并在其后附加或在其中插入 个校验符号。在求值模型中,可以将消息解释为 个选定求值点上的给定值,以此实现系统编码。多项式插值可确定唯一一个经过这些点、次数小于 的多项式;在其余点上对该多项式求值,就能生成冗余符号。如果改变的只是消息与码字之间的映射,码字集合就保持不变。
另一种广泛使用的方法是循环码描述。设 为域中的一个本原元,并考虑长度为 的全长码。令 ,则生成多项式可写为
其中, 指定第一个根。码字多项式均可被 整除。要进行系统编码,先将消息多项式 乘以 ,再除以 ,然后减去余式:
在特征为二的域上,减法与加法相同。带有有限域反馈的移位寄存器可以高效实现这一计算。
循环码与求值这两种视角描述的是密切相关的码族,但两者的坐标约定和消息映射不能随意互换。规范必须明确域的表示方式、坐标顺序、生成多项式的根,以及信息符号和校验符号的位置。如果这些细节不同,即使两个实现都声称采用 ,也仍可能生成互不兼容的校验字节。
缩短操作可使码适用于更小的数据块。从一个 码出发,编码器在概念上将 个信息符号固定为零,并省略它们对应的系统坐标,从而得到一个冗余量和最小距离均保持不变的 码。删余则是在不固定消息值的情况下移除坐标;它对维数和距离的影响必须另行分析。交织又是另一种不同的操作:它重新排列来自多个码字的符号,使局部物理扰动分散到这些码字中。这些操作都不会改变符号错误的含义,但每种操作都会改变物理故障映射为代数译码问题的方式。
未知错误的代数译码
只要有足够多的正确位置,就可以通过插值恢复擦除的数据。未知错误的译码则更困难,因为接收端必须识别出哪些观测值应当舍弃。传统的代数译码器利用校验约束,将接收码块压缩为伴随式。对于循环码的码字多项式 ,生成多项式的根满足 。若接收多项式为 ,则有
因此,伴随式仅取决于错误模式,而与所发送的消息无关。
译码器需要求出一个错误定位多项式,其根用于确定出错位置。按照一种常见约定,若错误位置对应于非零域元素 ,则采用
伴随式序列满足由 确定的线性递推关系。伯勒坎普–梅西算法会找出与现有伴随式相符的最短递推关系。另一种方法是使用扩展欧几里得算法,求解将伴随式多项式、错误定位多项式和错误求值多项式联系起来的关键方程。这两种方法都能在保证的纠错半径内实现有界距离译码。
确定错误定位多项式后,钱氏搜索会在与各个可能位置对应的域元素处计算其值。该多项式的根即可确定错误位置。随后,译码器确定错误值,通常采用福尼公式,将错误求值多项式与错误定位多项式的形式导数结合起来计算。公式的具体形式取决于若干约定,例如生成多项式的第一个根如何选取,以及位置是直接表示还是用其倒数表示。减去算出的错误值后,便得到候选的纠正码字。
能够处理擦除的译码器会将已知的缺失位置纳入擦除定位多项式。这减少了需要确定的未知位置,并支持错误与擦除混合情况下的界限 。系统可以利用里德–所罗门码本身之外的信息,将某些位置标记为擦除,从而帮助恢复:内层译码器译码失败、光盘区域无法读取,或数据包完整性校验失败,都可能表明整个符号或码块不可靠。正确标记擦除有助于恢复,而误将受损符号当作有效符号接受,则会造成纠正代价更高的未知错误。
实际的译码器还会进行一致性检查。找到的根数应当与求得的定位多项式次数一致,恢复错误值时所需的分母必须有效,纠正后的码块也应满足校验约束。这些检查能够识别许多无法纠正的情况,但无法杜绝超出保证纠错半径时所有可能的误纠正。需要更强保障的系统通常会在纠错编码之外,辅以校验和、密码散列函数,或根据相应故障模型选择的认证机制。
插值译码与超越半最小距离的恢复
另一种唯一译码方法直接从求值表示入手。假设接收值 分别对应互不相同的点 ,且其中至多有 个值出错。引入次数不超过 的错误定位多项式 ,以及次数不超过 的多项式 ,使其在每个接收位置上都满足
当 在所有错误位置上取值为零时,正确的消息多项式满足 。可以通过求解线性方程组确定未知系数,随后进行多项式除法并验证结果。这就是 Berlekamp–Welch 译码的核心思想。
这一表述揭示了为什么需要冗余。与消息有关的多项式和错误定位多项式都含有待求系数,因此,纠正位置未知的错误比恢复擦除需要更多的观测值。经过适当的归一化,标准的唯一译码条件为 。直接使用线性代数并不总是最快的实现方式,但这种方法在受损的求值结果与精确的多项式重构之间建立了直接联系。在某些理论研究中,用求值来描述编码比用循环码的生成多项式更自然,此时这种方法也很有用。
传统唯一译码的纠错能力局限于约半个最小距离,因为超出这一范围后,不同码字周围的译码区域就会重叠。但这并不意味着超出该半径就完全无法恢复。列表译码改变了对输出的要求:它不再坚持只给出一个答案,而是返回指定距离内的所有码字。于是,问题就变成了如何高效地找出一个较短的候选列表,以及能否利用其他信息从中辨别出实际发送的消息。
Sudan 算法及其扩展 Guruswami–Sudan 算法采用二元插值。它们构造一个多项式,使其在接收到的求值点与数值所组成的点对上取值为零,其中后一种方法还施加了重数条件。如果某个候选消息多项式与足够多的观测值一致,那么将它代入这个二元多项式后,就会得到一个代数恒等式。随后,通过因式分解即可找出候选消息多项式。对于码长为 、维数为 的标准里德–所罗门码,所得译码半径可以接近 ,具体还取决于阈值和整数取值方面的细节。渐近而言,可纠正的错误比例趋近于 ,而不再是唯一译码所能达到的、接近 的比例。
软判决方法并不局限于对每个符号作出单一的硬判决。解调器可以为各个可能的有限域符号赋予不同的似然值,而代数软判决译码可以将这些可靠性信息转换为插值重数。在合适的信道条件下,这类方法的性能可以优于硬判决译码,但需要额外的计算和更复杂的控制。候选列表也需要进一步判别:应用本身的结构或独立的完整性信息可能有助于选出答案,但仅凭列表译码本身,无法确定哪个候选才是最初发送的消息。
算术运算、实现与性能
大多数实用的里德–所罗门编码器和译码器都将大量计算资源用于有限域乘法。在 的多项式基表示中,加法就是按位异或,而乘法则需要先将二元多项式相乘,再对定义该域的不可约多项式取模。除法可以通过乘以逆元来实现。这些运算都是精确的,不存在类似浮点计算的舍入误差。
一种常见的软件实现方法是使用相对于某个本原元的对数表和反对数表。对于非零的 和 ,有
零需要特殊处理,因为它的离散对数没有定义。对于符号大小为一个字节的有限域,这些表足够小,在许多处理器上都具有实用性。其他实现方式包括乘法表、向量化查表操作、无进位乘法指令,以及位切片表示。哪种方案最快,取决于码块大小、处理器指令、内存访问量,以及系数是否在许多码块之间保持不变。
硬件编码器通常采用由生成多项式导出的规则反馈结构。译码器则更为复杂,因为它们必须计算伴随式、求解关键方程、搜索根并确定错误幅值。流水线和并行计算可以通过同时处理多个符号、码字或有限域运算来提高吞吐量。专用集成电路可以为这些阶段分别配置专用电路,而可编程实现则必须在算术运算与内存访问及指令开销之间进行权衡。
基本的伴随式计算和钱氏搜索所需的运算量,通常与码块长度和冗余量或纠错能力的乘积成正比。传统关键方程求解算法所需的有限域运算次数,通常与冗余量的平方成正比。对于较大的参数,更快的多项式算法可以降低渐近时间复杂度,但对于短码块,渐近性能更优并不一定意味着实际运行更快。固定开销、数据搬移、向量宽度以及实现的简洁程度,往往决定了实际性能。
有限域的大小带来了另一项权衡。更大的符号集允许普通里德–所罗门码采用更长的码块,但每个符号需要更多比特,算术运算的开销也更高。从八位符号扩展到十六位符号,并不只是将表的大小翻倍:完整查找表的规模随有限域元素个数增长,某些乘法表方案的规模增长得更快。在码距计算中,即使只有一个比特受损,其所在的整个符号也被视为出错。
相应地,兼容性测试也十分严格。不同实现必须在不可约多项式、本原元、生成多项式的根序列、符号顺序以及缩短约定上保持一致。测试用例应涵盖无错误码块、所有允许的擦除数量、处于纠错能力边界的错误与擦除混合情况,以及超出该边界的模式。独立实现或形式验证有助于评估算术运算和控制逻辑,但验证必须针对实际格式建模,而不能只针对抽象的里德–所罗门构造。
光盘与视觉码
CD光盘是编码方案针对物理损伤而设计的典型实例。它采用交叉交织里德–所罗门码(CIRC),将两个以八位符号为单位的里德–所罗门编码级组合起来,其分量码通常记为 和 。这些分量码的冗余配合延迟与交织,将物理读出过程中成簇出现的错误分散到不同的逻辑码字中。因此,一道损坏许多相邻信道符号的划痕,可能只会在每个受影响的码字中造成较少的错误。
交织对这种保护至关重要。里德–所罗门码本身并不知道损伤来自划痕、灰尘、电子噪声还是元件故障;它看到的只是出错的符号位置。重新排列记录序列,会改变这些物理事件在解码器中呈现的方式。两级CIRC结构还可以在各解码级之间传递可靠性信息。对于音频播放,仍然无法纠正的错误可以通过信号插值或静音来掩蔽,但掩蔽并不等于精确纠错。承载数据的格式需要额外保护,因为看似合理的替代字节并不等同于原始数据。
DVD采用里德–所罗门乘积码结构。常规DVD纠错块使用参数为 和 的分量码,沿矩形阵列的两个方向添加冗余。行与列之间的关系提供了互补的约束,解码时可以利用阵列结构,处理超出单个独立分量码纠错能力的错误模式。乘积编码展示了如何将一种常见的代数基本构件组合成更大的保护方案,使其具有不同的整体特性。
二维码对从其模块图案中提取出的字节应用里德–所罗门编码。它的四个标准纠错级别L、M、Q和H,通常分别对应约7%、15%、25%和30%的码字恢复比例。这些数字并不意味着可以任意移除可见方形区域中相同比例的部分,并保证仍能读取。成功读取还取决于能否定位码图、估计其几何形状、读取格式信息,以及获取足够多的可靠模块。
较大的二维码会将数据划分为多个里德–所罗门块,并对这些块的码字进行交织。因此,损伤的位置与损伤的总面积同样重要。集中在结构性重要图案上的损伤,可能在纠错开始之前就导致识别失败,而分散在数据区域中的损伤则可能得到纠正。类似原理也适用于其他二维条码:光学检测、几何处理、符号提取和代数纠错是不同的阶段,各自都有导致失败的条件。里德–所罗门编码保护的是恢复出来的数字符号流,而不能取代获取该符号流所需的图像处理步骤。
通信信道与级联系统
当噪声或中间处理环节会产生符号错误和突发错误时,通信系统会采用里德–所罗门码。这种码的实用性不仅取决于原始物理信道,还取决于送入译码器的数据表示形式。无线电信道中的信号最初可能表现为波动的电压和相位估计值,经过解调和内码纠错后,最终形成字节流。里德–所罗门编码通常用于这个面向字节的外层,而不是最前端的物理信号检测阶段。
一种传统配置由里德–所罗门外码、交织器和卷积码内码组成。内码译码器处理影响传输比特的大部分噪声。内码译码后残留的错误可能成簇出现,因此需要通过解交织,将这些错误分散到不同的外码码字中。随后,里德–所罗门译码器再消除剩余的符号错误。这种分工称为级联编码:各级编码并非只是重复提供保护,而是针对不同的数据表示形式和错误模式发挥作用。
空间遥测标准已采用定义在 上的里德–所罗门码,其中较为典型的是 和 两种形式,其标称纠错能力分别为16个和8个符号。在深空链路中,接收信号功率受到严格限制,而重传的代价可能很高,或不适合实际运行需求。即使噪声已使未编码的符号判决无法满足要求,编码仍能让接收机恢复信息。其收益应通过系统层面的指标来衡量,例如达到指定分组错误率所需的每信息比特能量,而不能仅靠计算校验符号的数量来判断。
里德–所罗门码也已用于地面广播、有线传输系统和数字用户线系统。例如,DVB-S卫星广播标准采用由 码缩短得到的 里德–所罗门外码。它为每个188字节的传输包添加16个校验字节,每个码字最多可纠正8个错误字节。交织和内码编码也是传输链路的组成部分;仅凭外码本身的参数,并不能描述整个系统的性能。
后来的通信系统设计通常采用低密度奇偶校验码或Turbo码,以在长码块条件下获得优异的软判决性能。这并不否定里德–所罗门码的距离特性,而是反映了设计目标的差异:逼近信道容量、迭代译码性能、时延、硬件并行性,或与现有帧格式的兼容性。当错误自然表现为符号擦除,或者代数界限和行为可预测的译码器尤其重要时,短码块的里德–所罗门码仍然很有用。交织器可以提高对突发错误的容忍能力,但也会引入缓冲时延,因此交织深度是一项需要权衡的工程参数,而不是越大越好。
分布式存储、数据恢复及相关构造
在存储系统中,里德–所罗门编码经常被用作纠删码。一个数据条带包含 个信息分片和 个冗余分片,共计 个分片。如果将这些分片分布到不同设备或故障域中,那么任意 个仍然可用的分片都能重建该条带。例如,采用十个数据分片、四个校验分片的配置时,每十个单位的原始数据需要存储十四个单位的分片,并且能够容忍一个条带内任意四个分片丢失。
一个分片通常远大于一个有限域符号。编码时,对各分片中相同位置的符号反复应用同一个小型生成矩阵。系统形式的生成矩阵包含与原始数据对应的单位矩阵部分,以及用于生成校验数据的额外行。解码时,系统选出与可用分片对应的行,对由此形成的 矩阵求逆,再将逆矩阵依次应用于各个符号位置。最大距离可分(MDS)性质要求,每一种允许的 行选取方式所构成的矩阵都可逆。仅仅在单位矩阵后附加一个看似任意的校验矩阵,并不能保证这一性质。
与完整复制相比,存储效率是这种编码最主要的吸引力。保存三份完整副本需要占用原始数据三倍的容量,而采用 个分片的里德–所罗门布局时,不计元数据和运行开销,所需容量为原始数据的 倍。代价则是计算和访问成本。在基本设计中,即使只需生成一个替代分片,重建丢失分片也可能需要从 个仍然可用的分片中读取数据。小规模更新也可能需要读取旧数据或校验数据,并重写多个分片。这些问题推动了局部可修复码和专门的再生方案等替代方法的发展。
必须区分设备丢失与静默数据损坏。磁盘丢失或对象不可用时,擦除位置是已知的;但如果设备返回了错误字节,而又没有其他完整性保护层将其识别出来,就可能产生位置未知的错误。校验和、哈希值以及经过验证的元数据,有助于将检测到的数据损坏转化为擦除。分片在机架、供电域或地理区域之间的放置方式也很重要:即使代数上保证能够容忍四个分片丢失,也无法阻止一次关联故障导致五个分片同时丢失。因此,里德–所罗门冗余并不等同于数据备份、版本保留或灾难恢复策略。
这种多项式构造还与密码学有着重要联系。在沙米尔秘密共享中,秘密被放入多项式的常数项,其余系数则随机选取;在不同点求得的多项式值构成各份秘密份额。足够数量的份额可以重建多项式,而在该构造的假设条件下,少于门限数量的份额不会泄露有关秘密的任何信息。普通的里德–所罗门编码并不提供这种保密性,因为其消息系数并未以相同方式随机化。同样,仅靠冗余也无法认证数据是否遭到蓄意篡改。即使同一个存储或通信系统同时使用编码、加密、完整性验证和访问控制,这些机制所保障的仍是不同的性质。