里德-所罗门码(又称里所码,Reed-solomon codes,简称RS codes)是一种
前向错误更正的
信道编码,对由校正
过采样数据所产生的有效
多项式。编码过程首先在多个点上对这些多项式求冗余,然后将其传输或者存储。对多项式的这种超出必要值得采样使得多项式超定(过限定)。当
接收器正确的收到足够的点后,它就可以恢复原来的多项式,即使接收到的多项式上有很多点被噪声干扰有损。
里德-所罗门码(又称里所码,Reed-solomon codes,简称RS codes)是一种
前向错误更正的
信道编码,对由校正
过采样数据所产生的有效
多项式。编码过程首先在多个点上对这些多项式求冗余,然后将其传输或者存储。对多项式的这种超出必要值得采样使得多项式超定(过限定)。当接收器正确的收到足够的点后,它就可以恢复原来的多项式,即使接收到的多项式上有很多点被噪声干扰有损。
里德-所罗门码被广泛的应用于各种商业用途,最显著的是在
CD、
DVD和
蓝光光盘上的使用;在数据传输中,它也被用于
DSL和
WiMAX;广播系统中
DVB和
ATSC也闪现着它的身影;在计算机科学里,它是
RAID 6标准的重要成员。
里德-所罗门码是
定长码。这意味着一个固定长度输入的数据将被处理成一个固定长度的输出数据。在最常用的(255,223)里所码中,223个里德-所罗门输入符号(每个符号有8个
比特)被编码成255个输出符号。
里德-所罗门码,如同
卷积码一样,是一种透明码。这代表如果信道符号在队列的某些地方被反转,解码器一样可以工作。解码结果将是原始数据的补充。但是,里所码在缩短后会失去透明性。在缩短了的码中,“丢失”的比特需要被0或者1替代,这由数据是否需要补足而决定。(如果符号这时候反转,替代的0需要变成1)。于是乎,需要在里所解码前对数据进行强制性的侦测决定(“是”或者“补足”)。
在里德-所罗门数据编码背后的核心可以形象化的表示为
多项式。这种码依靠一个
代数理论,这个代数理论说明任何k个唯一的确定点表示一个阶数至少为k-1的多项式。
发送者表明一个在有限域中的k-1阶的多项式,它表示k个数据点。这个多项式就根据它在各点的赋值被“编码”,实际传送的是这些值。在传输中,一些值会被破坏。所以,实际发送的点不止k个。只要正确地接收了足量的数值,接收方就可以推算出原始多项式,进而译出原始数据。
RS码是一个[n,k,n-k+1]码,是一种定义在有限域F上的长度为n,信息长度为k,最短汉明距离为n-k+1的
线性分组码。由于这种编码满足Singleton界,因此它是一种最大距离可分码。由于码长为n信息长度为k的码的最大汉明距离为n-k+1,所以在这种意义下RS码是一种最优的编码方法。
RS码的纠错能力由最短汉明距离决定,为n-k+1。如果预先并不知道错误的位置,RS码最多可以纠正(n-k)/2个错误。而在某些情况下,我们可以预知错误的位置(比如BEC信道),此时RS码最多可以纠正n-k个错误。如果我们可以预先知道S个错误位置,而此外还有E个未知的错误位置,那么在满足2E+S
在实际应用中,RS码经常使用大小为2m的有限域。在这种情况下,每个符号都包含有m比特的信息。发送者将编码后的分组发送给接受者,每个分组通常含有2m-1个符号。
RS码的这种性质使得它非常适合纠正传输系统中的突发错误。这是由于不论一个符号中有多少个比特发生错误,都只发生了一个符号错误。而对于不发生突发错误的传输系统,RS码的性能通常不如普通的二元码。