里德-所罗门码

✍ dations ◷ 2025-06-30 20:37:52 #错误检测与校正

里德-所罗门码(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码的性能通常不如普通的二元码,

相关

  • 化学符号化学符号以拉丁字母缩写的形式表达化学元素或官能基。化学元素的符号通常为一个或两个字母,而一些人造元素的IUPAC临时符号则使用三个字母。元素的化学符号在元素周期表中使
  • 四氢孕酮孕烷醇酮(英语:Pregnanolone)也被称为四氢孕酮(英语:tetrahydroprogesterone,THP)可指:
  • 凯泽在物理学里,波数是波动的一种性质,定义为每 2π 长度的波长数量(即每单位长度的波长数量乘以 2π)。更明确地说,波数是每 2π 长度内,波动重复的次数(一个波动取同样相位的次
  • 伊兹密尔伊兹密尔(土耳其语:İzmir;希腊语:Σμύρνη),旧称士麦那(Smyrna),位于爱琴海伊兹密尔湾东南角,为土耳其第三大城市、第二大港口。伊兹密尔为伊兹密尔省首府,全市共分9区。据2018年
  • 行为规范障碍品行障碍(英语:Conduct disorder)也称为行为规范障碍,是指在青少年阶段的患者出现反复、持续的攻击性、反社会性、对立违抗性的行为障碍。这些行为违反了与年龄相适应的社会行为
  • 蓝瑞斯猪长白猪(Landrace pigs)也称蓝德瑞斯猪或蓝瑞斯猪,是家猪中著名的瘦肉型品种。长白猪因高产和高饲料利用率而著称,常用作杜长大(杜洛克×(长白×大白))杂交体系的母系猪。另外,也有农
  • 费利克斯·萨伐尔费利克斯·萨伐尔(法语:Félix Savart ,1791年6月30日-1841年3月16日)是法国一位物理学家和医生。他与让-巴蒂斯特·毕奥共同创建了毕奥-萨伐尔定律。这是静磁学的一个基本定律,精
  • 翁闹翁闹(1910年2月21日-1940年11月21日),号杜夫,台湾日治时期作家,彰化社头人。1910年(明治43年),翁闹出生于台中厅武西堡关帝庙社二百六十四番地,本是陈纣、陈刘春家四男,五岁时被彰化社
  • 云南科技出版社云南科技出版社、又称云南科学技术出版社,是一家中华人民共和国的出版社,位于云南省昆明市书林街100号。云南科技出版社的前身为云南人民出版社科技读物编辑室。1985年6月27日
  • 爱丽丝·芭布斯爱丽丝·芭布斯(英语:Alice Babs, 1924年1月26日-2014年2月11日),原名希尔杜·爱丽丝·尼尔森(斯瓦希里语:Hildur Alice Nilsson),是一名瑞典韦斯特维克市出生的歌手和演员,她也参与到