里德-所罗门码

✍ dations ◷ 2025-08-27 19:17:10 #错误检测与校正

里德-所罗门码(Reed-solomon codes,简称里所码或 RS codes)是一种前向错误更正的信道编码,对由校正过采样数据所产生的有效多项式。编码过程首先在多个点上对这些多项式求冗余,然后将其传输或者存储。对多项式的这种超出必要值的采样使得多项式超定(过限定)。当接收器正确地收到足够的点后,它就可以恢复原来的多项式,即使接收到的多项式上有很多点被噪声干扰有损。

里德-所罗门码被广泛地应用于各种商业用途,最显著的是在 CD、DVD 和蓝光光盘上的使用;在数据传输中,它也被用于 DSL 和 WiMAX;广播系统中 DVB 和 ATSC 也闪现着它的身影;在计算机科学里,它是 RAID 6 标准的重要成员。

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

里德-所罗门码,如同卷积码一样,是一种透明码。这代表如果信道符号在队列的某些地方被反转,解码器一样可以工作。解码结果将是原始数据的补充。但是,里所码在缩短后会失去透明性。在缩短了的码中,“丢失”的比特需要被0或者1替代,这由数据是否需要补足而决定。(如果符号这时候反转,替代的0需要变成1)。于是乎,需要在里所解码前对数据进行强制性的侦测决定(“是”或者“补足”)。

在里德-所罗门数据编码背后的核心可以形象化的表示为多项式。这种码依靠一个代数理论,这个代数理论说明任何长度为k的码可唯一表示成一个阶数(degree)至少为k-1的多项式。

发送者表明一个在有限域中的k-1阶的多项式,它表示k个数据点。这个多项式就根据它在各点的赋值被“编码”,实际传送的是这些值。 在信息传输中,一些值会被破坏。所以,实际发送的点不止k个。只要正确地接收了足量的数值,接收方就可以推算出原始多项式,进而译出原始数据。

同样的,我们可以通过插值来修正曲线。RS码可以将一组有错误序列的信息码转换到找回画出原始曲线的多项式的系数。

给定一个有限域F和多项式环F,令n和k满足 1 k n | F | {\displaystyle 1\leq k\leq n\leq |F|} .选择F中的n个确定元素,记作 { x 1 , x 2 , , x n } {\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}} .码本C是通过计算F中每个 x i {\displaystyle x_{i}} 的阶数小于k的多项式得到的值,即

C是 {\displaystyle } 码;换句话说,是F中长为n,维度为k,最小汉明距离为n-k+1的线性码。

一个RS码满足以上的形式,并遵循:集合 { x 1 , x 2 , , x n } {\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}} F {\displaystyle F} 域中所有非零元素组成的集合(因而, n = | F | 1 {\displaystyle n=|F|-1} )。

RS码在实际应用中,常常使用一个有 2 m {\displaystyle 2^{m}} 个元素的有限域F。这样,每个符号就可以表示为一个m比特的数值。发送方以编码块的形式发送数据点,编码块的符号数量为 n = 2 m 1 {\displaystyle n=2^{m}-1} 个。这样,一个用于8比特符号的RS码每块有 n = 2 8 1 = 255 {\displaystyle n=2^{8}-1=255} 个符号。 (在字节型计算机系统普及的今天,这个数字很实用。)编码块中的数据符号k是一个设计参数, k < n {\displaystyle k<n} 。在一个n = 255的符号块中,常用 k = 223 {\displaystyle k=223} 的8比特数据符加上32个8比特校验符来编码,用 ( n , k ) = ( 255 , 223 ) {\displaystyle (n,k)=(255,223)} 表示,每块最多可以校正16个符号错误。

由有限域中的非零元素构成的集合 { x 1 , . . . , x n } {\displaystyle \{x_{1},...,x_{n}\}} 可以写作 { 1 , α , α 2 , . . . , α n 1 } {\displaystyle \{1,\alpha ,\alpha ^{2},...,\alpha ^{n-1}\}} α {\displaystyle \alpha } 是一个"单位的n次本原根"。习惯上按照这种顺序对RS码进行编码。由于 α n = 1 {\displaystyle \alpha ^{n}=1} ,并且对于每个多项式 p ( x ) {\displaystyle p(x)} ,函数 p ( α x ) {\displaystyle p(\alpha x)} 是与它同次的多项式,因而RS码是循环的。

1968年,Berlekamp发现了一种BCH码解码算法。由于RS码可以看作是BCH码的特例,该算法也可用于解码RS码。

通过RS码的另一种定义方法,可以很容易的看出RS码是BCH码的一种特例。令有限域 F {\displaystyle F} 大小为 q {\displaystyle q} , α {\displaystyle \alpha } F {\displaystyle F} 的],亦即 α n = 1 {\displaystyle \alpha ^{n}=1} ,且对所有小于 n {\displaystyle n} 的正整数 i {\displaystyle i} ,均有 α i 1 {\displaystyle \alpha ^{i}\neq 1} 。给定 1 k n {\displaystyle 1\leq k\leq n} , ( f 0 , f 1 , . . . , f n 1 ) {\displaystyle (f_{0},f_{1},...,f_{n-1})} 是RS码的码字当且仅当 α , α 2 , . . . , α n k {\displaystyle \alpha ,\alpha ^{2},...,\alpha ^{n-k}} 是多项式 p ( x ) = f 0 + f 1 x + . . . + f n 1 x n 1 {\displaystyle p(x)=f_{0}+f_{1}x+...+f_{n-1}x^{n-1}} 的根。这样,很容易可以看出RS码是一种多项式码,也就是BCH码。生成多项式 g ( x ) {\displaystyle g(x)} α , α 2 , . . . , α n k {\displaystyle \alpha ,\alpha ^{2},...,\alpha ^{n-k}} 的最小多项式,而码字为能够整除多项式 g ( x ) {\displaystyle g(x)} 的多项式。

RS码的两种定义方式有着非常大的区别,而它们的等价关系并不是显而易见的。在第一种定义中,码字是多项式的值,而在第二种定义中,码字是多项式的系数。另外,第一种定义要求多项式具有特定的比较小的幂次,而在第二种定义中,多项式需要有特定的根。

这两种定义的等价性可以通过有限域上的离散傅立叶变换来证明。离散傅立叶变换创建起了多项式的系数与值之间的对偶关系。这种对偶关系可以不严格的概述如下:令 p ( x ) {\displaystyle p(x)} q ( x ) {\displaystyle q(x)} 为两个次数小于 n {\displaystyle n} 的多项式。如果多项式 p ( x ) {\displaystyle p(x)} 的在 x = α i {\displaystyle x=\alpha ^{i}} i = 0 , , n 1 {\displaystyle i=0,\dots ,n-1} , α {\displaystyle \alpha } 是1的n次原单位根)处的值是 q ( x ) {\displaystyle q(x)} 的系数,那么 q ( x ) {\displaystyle q(x)} 在这些点上的取值在经过乘以一个特定的系数和重新排列以后就成为了 p ( x ) {\displaystyle p(x)} 的系数。

严格的说,令

同时假定 p ( x ) {\displaystyle p(x)} q ( x ) {\displaystyle q(x)} 为离散傅立叶变换对,那么 p ( x ) {\displaystyle p(x)} q ( x ) {\displaystyle q(x)} 的系数和取值有如下关系:对所有的 i = 0 , , n 1 {\displaystyle i=0,\dots ,n-1} f i = p ( α i ) {\displaystyle f_{i}=p(\alpha ^{i})} 并且 v i = 1 n q ( α n i ) {\displaystyle \textstyle v_{i}={\frac {1}{n}}q(\alpha ^{n-i})} .

这样,我们可以得出 ( f 0 , , f n 1 ) {\displaystyle (f_{0},\ldots ,f_{n_{1}})} 是满足RS码第一种定义方式的码字

这样,两种定义方式的等价性便得到了证明。

RS码是一个 {\displaystyle } 码,是一种定义在有限域 F {\displaystyle F} 上的长度为 n {\displaystyle n} ,信息长度为 k {\displaystyle k} ,最短汉明距离为 n k + 1 {\displaystyle n-k+1} 的线性分组码。由于这种编码满足Singleton界,因此它是一种最大距离可分码。由于码长为 n {\displaystyle n} 信息长度为 k {\displaystyle k} 的码的最大汉明距离为 n k + 1 {\displaystyle n-k+1} ,所以在这种意义下RS码是一种最优的编码方法。

RS码的纠错能力由最短汉明距离决定,为 n k + 1 {\displaystyle n-k+1} 。如果预先并不知道错误的位置,RS码最多可以纠正 ( n k ) / 2 {\displaystyle (n-k)/2} 个错误。而在某些情况下,我们可以预知错误的位置(比如BEC信道),此时RS码最多可以纠正 n k {\displaystyle n-k} 个错误。如果我们可以预先知道 S {\displaystyle S} 个错误位置,而此外还有 E {\displaystyle E} 个未知的错误位置,那么在满足 2 E + S < n k {\displaystyle 2E+S<n-k} 的情况下,我们可以完全纠正这些错误。

在实际应用中,RS码经常使用大小为 2 m {\displaystyle 2^{m}} 的有限域。在这种情况下,每个符号都包含有 m {\displaystyle m} 比特的信息。发送者将编码后的分组发送给接受者,每个分组通常含有 2 m 1 {\displaystyle 2^{m}-1} 个符号。例如,定义在 G F ( 2 8 ) {\displaystyle GF(2^{8})} 上的RS码每个分组包含有 255 = 2 8 1 {\displaystyle 255=2^{8}-1} 个符号。由于计算机通常以字节为单位来处理数据,因此定义在 G F ( 2 8 ) {\displaystyle GF(2^{8})} 的RS码非常流行。设计参数 k {\displaystyle k} 需要满足 k < n {\displaystyle k<n} ,对于定义在 G F ( 2 8 ) {\displaystyle GF(2^{8})} 上的RS码,通常选择 k = 223 {\displaystyle k=223} 。这个RS码包含有223个数据符号和32个校验符号,表示为 ( 255 , 223 ) {\displaystyle (255,223)} RS码,它最多可以纠正16个符号错误。

RS码的这种性质使得它非常适合纠正传输系统中的突发错误。这是由于不论一个符号中有多少个比特发生错误,都只发生了一个符号错误。而对于不发生突发错误的传输系统,RS码的性能通常不如普通的二元码,

相关

  • 钙离子4s22, 8, 8, 2蒸气压第一:589.8 kJ·mol−1 第二:1145.4 kJ·mol−1 第三:4912.4 kJ·mol−1 (主条目:钙的同位素钙(Calcium)是一种化学元素。其化学符号是Ca,原子序数是20。钙
  • 吡喃酮吡喃酮(Pyrone)是吡喃的酮类衍生物,是一类六元的含氧杂环化合物。与吡喃一样,根据环中双键和羰基的位置不同,吡喃酮可以有两个异构体:α-吡喃酮和γ-吡喃酮。吡喃酮的结构广泛存在
  • 睦邻政策睦邻政策是小罗斯福作为美国总统时期对拉丁美洲的外交政策,它有两个主要目标:保证拉美国家加入二战盟军,不与轴心国或共产主义有任何联系;将拉美转变为美国原材料的供应地与商品
  • 辛夷散辛夷散属于中医方剂的泻火剂,出自严用和的《严氏济生方》,由9味中药组成,是用以治疗鼻瘜肉的方剂,症状为鼻生瘜肉,气息不通,不闻香臭。现代可用治过敏性鼻炎。《医方集解》将本方
  • 力为廉力为廉(William Henry Lacy; 1858年1月8日-1925年9月3日)是美国美以美会差会派往中国的传教士。1858年1月8日,力为廉出生在美国威斯康星州密尔沃基。他毕业于西北大学和加略特圣
  • 凸函数凸函数是具有如下特性的一个定义在某个向量空间的凸子集 C {\displaystyle C} 内的凸函数在内连续,且在除可数个点之外的所有点可微。如果
  • 营团7000系电力动车组营团7000系电力动车组(日语:営団7000系電車/えいだん7000けいでんしゃ  */?)是于1974年(昭和49年)登场的帝都高速度交通营团(营团)的通勤形电车(日语:通勤形車両 (鉄道))。2004年(平成
  • 印蒂雅·艾瑞印蒂雅·艾瑞(英语:India.Arie)原名印蒂雅·艾瑞·辛普森,出生于1975年10月3日,是美国著名的灵魂乐歌手,节奏蓝调音乐歌手创作人,同时也擅长吉他与长笛等乐器。印蒂雅·艾瑞出生于
  • 王纶 (成化甲辰进士)王纶(?年-1510年),字汝言,号节斋,浙江慈谿县(今浙江省慈溪市)人。明朝政治人物,成化甲辰进士,正德间官至湖广巡抚。成化二十年(1484年)甲辰科进士出身。授工部都水司主事,因母丧去职。守丧
  • 薛捍勤薛捍勤(1955年9月15日-),山东人,出生于上海,中国外交官、国际法学者,现任国际法院法官。她曾先后在北京外国语学院、北京大学、美国哥伦比亚大学学习。1980年起,在外交部条约法律司