自从大约60年前编码理论诞生以来，研究人员一直在追求构建“最佳编码”这个难以捉摸的目标，它的编码为他们可以纠正的噪声水平引入了尽可能小的冗余。在这篇文章中，我们综述了最近的进展<我>列表译码这导致了<我>非常高效。的纠错方案<我>最优冗余量，甚至对抗<我>最糟糕的错误由潜在的恶意通道引起。为了纠正一定比例(比如20%)的最坏情况错误，这些代码只需要接近一定比例的冗余符号。理论上，冗余不可能是更低的信息。与目前在各种日常应用中使用的传统算法相比，这种新方法有望纠正两倍以上的错误。
处理损坏的数据是我们现代生活中必不可少的一部分;即使大多数时候我们都幸福地没有意识到这一点。当我们看电视时，电视必须处理在传输过程中失真的信号。当我们用手机通话时，手机必须处理在大气中传输时损坏的音频信号，尽管当连接不好时我们肯定会意识到这一点。当我们上网时，TCP/IP协议必须对在路由过程中丢失或混淆的数据包负责。当我们在dvd上看电影时，播放器必须克服由于刮擦而导致的数据丢失。即使当我们购买食品杂货时，扫描仪也必须处理包装上扭曲的条形码。
在这些和许多其他应用程序中处理错误的关键因素是<我>纠错编码或者只是<我>代码简洁。代码背后的思想在概念上很简单:为信息添加冗余，这样即使结果数据被损坏，例如数据包在路由过程中损坏或DVD被划伤，原始信息仍然可以恢复。
理想情况下，我们希望添加少量冗余，同时能够纠正许多错误。正如人们所预料的那样，这些目标是相互冲突的，而取得正确的平衡是事情变得有趣的地方。例如，考虑每个信息位都重复100次的代码(这称为重复代码)。直观地说，这段代码应该运行良好。特别地，下面是一个自然错误恢复过程<我>解码算法：对于连续100位的数据，识别大多数位是0还是1，并输出相应的位。除非我们很不幸，这个解码算法可以从相当多的错误中恢复。缺点是每100位数据只包含<我>一个想象一下，一张DVD需要多大才能存储如此冗余的电影。另一个极端是奇偶校验码，它将信息位的奇偶校验附加在消息的末尾。这段代码使用了尽可能少的冗余，但错误恢复能力很差。事实上，即使只有两个比特被翻转，它也可以不被发现。例如，0001在奇偶校验码下被编码为00011。如果前两个比特损坏，我们收到11011，我们就会将原始消息误解为1101。想象一下克拉克·盖博在你的奇偶校验编码DVD的最后说<我>乱世佳人“坦白说，亲爱的，我一点也不在乎!”
为了捕捉代码冗余和容错之间的内在张力，让我们正式地定义代码和一些关键参数。一个代码<我>C由<我>编码表格的地图<我>C：<年代up>kn(整数<我>K < n的编码序列<我>k符号从一个更大的序列<我>n符号。给定一个<我>消息米<我米g src="https://dl.acm.org/cms/attachment/cfecc4db-14db-4cb1-8725-3e32cec85f4c/isin.gif" border="0" hspace="2" alt="isin.gif">k，<我>C（<我>米）被称为对应的<我>码字。的参数<我>k，n，被称为<我>尺寸、块长，<我>字母的<我>C，分别。我们经常会用到比率<我>R＝k/n，称为<我>率的<我>C．请注意,<我>R准确地捕获码字的每位所包含的信息量。<我>汉明距离在两个字符串之间<年代up>n是它们不同的坐标的个数。的<我>最小距离的定义为两个不同码字之间的最小汉明距离。
因此，我们感兴趣的问题现在可以重新表述如下:给定一个代码<我>C的速度<我>R，所能容忍的最大误差百分比(我们今后将称之为)是多少<我>C？就像每个码字一样<我>k信息的符号，直觉告诉我们至少在最坏的情况下<我>k码字的符号应该没有损坏，才有希望恢复原始信息。换句话说，我们只能有(<我>N-k）/<我>n= 1 -<我>R，无论解码器的计算能力如何。
本文主要关注以下问题:
我们能编个密码吗<我>C的速度<我>R可以有效地从1 -附近解码<我>R误差的百分比?
令人惊讶的是，我们将证明答案是肯定的。因此，上述简单的信息论极限实际上是可以接近的。特别是，对于小速率，我们可以从几乎所有数据都可能损坏的情况中恢复。例如，即使克拉克·盖博(Clark Gable)吐出“哎呀，咦meap xH don’z hive b hayn!”事实上，上述问题有两个部分。首先，代码应该是这样的:基于其编码的噪声版本，消息的标识应该是惟一的(或接近惟一的)确定的。第二，我们需要一个<我>非常高效。过程根据损坏的码字恢复消息，运行时以块长度中的一个小多项式为界<我>n．蛮力方法，例如搜索所有的码字，需要大量的时间<我>n，并且在计算上令人望而却步。本文的主要信息是，广泛部署的Reed-Solomon代码的变体实际上可以被纠正错误<我>有效地，即使误差的百分比接近绝对1 -<我>R极限。
我们在上面的问题中强调，噪声模型是一个<我>最坏的一种方法是，将信道建模为对手/干扰器，可以以任意方式破坏码字，只受错误总数的限制。对于误差是如何分布的，没有做任何假设。最坏情况模型是在汉明那篇有影响力的论文中提出的。<年代up>12香农在他的开创性著作中开创了另一种方法，<年代up>16就是将噪声信道建模为一个随机过程，其行为受一个精确已知的概率定律支配。一个简单的例子是二进制对称信道(BSC)<我><年代ub>)，其中传输的每个比特都以一个独立于所有其他比特的概率被翻转。对于每一个这样的通道，香农准确地描述了可靠通信可能的最大速率。
我们注意到<我>算法在最坏情况噪声模型中，结果比较困难。事实上，传统上人们认为为最坏情况噪声设计的代码面临(1 -)的极限<我>R) / 2的误差分数，它与a (1 -<我>R）的误差分数。在试图纠正<我>e>（<我>n-<我>k) / 2错误时，我们面临一个问题:在汉明距离内可能有多个码字<我>e从收到的字。在任何代码映射中<我>k符号来<我>n符号，必须有两个码字在距离(<我>n-<我>k+1）或更少。如果传输了其中一个码字，并且由于错误而失真到两个码字之间的中间位置，则不可能明确地恢复原始消息。这表明，超出分数(1 -<我>R) / 2的最坏情况错误，原始消息是不可恢复的。直到20世纪90年代，这的确是编码理论的传统智慧。
在出现多个相邻码字的情况下，一种自然的策略是允许解码器输出一个码字列表。这个模型叫做<我>列表译码．它是20世纪50年代末由Elias提出的<年代up>2Wozencraft,<年代up>19戈尔德里奇和莱文在一个加密应用程序中重新关注算法。<年代up>4此外，事实证明上面的坏情况是相当病态的——对于典型的<我>e错误,<我>e比(大得多)<我>n-<我>k) / 2，原始码字将是距离内唯一的码字<我>e．因此，列表解码除了处理“惟一”解码的错误模式外，还允许我们惟一地恢复传输的码字<我>大多数错误模式。
有趣的是，尽管列表解码问题在编码理论世界中有着悠久的历史，<年代up>一个列表解码算法的大部分进展都发生在理论计算机科学界。这种令人愉快的巧合的原因之一是，列表解码在密码学和计算复杂性理论中有许多应用(例如，参见第5节中关于随机提取器的讨论)。
特别是在过去的十年中，列表解码的主题见证了大量的活动，最终出现了纠正接近信息理论上最优1 -的算法<我>R误差随速率的百分比<我>R．本文的目的是讨论这组最新的结果，它提供了针对最坏情况错误的代码的全部承诺。在第2节中，我们首先描述一个流行的代码家族及其一些解码算法。
1960年，欧文·里德(Irving Reed)和古斯塔夫·所罗门(Gustave Solomon)根据有限域上的多项式，描述了一种纠错码的结构，被称为里德-所罗门码(Reed-Solomon codes)。<年代up>b里德-所罗门码(RS码)在发明近50年后的今天仍然无处不在，应用范围从磁记录到UPS条形码再到卫星通信。为了描述RS编码背后简单而优雅的思想，假设Alice希望通信一对数字(<我>一个，<我>b）给鲍勃。我们可以想到(<我>一个，<我>b）作为指定平面上的一条直线(用<我>X，<我>Y轴)带方程<我>Y＝<我>斧头+<我>b．显然，要指定直线，只需通信直线上的两个点就足够了。为了防止错误，Alice可以对这条线进行过采样，并向Bob发送更多的点，这样即使有几个点被错误扭曲，点的集合也比其他任何线更接近原始的线(<一个href="#F1">图1）．因此，Bob可以希望恢复正确的行，特别是(<我>一个，<我>b）．
编码由…组成的较长的信息<我>k符号通过RS码，人们认为这些是多项式的系数<我>f（<我>X）程度<我>k-1，并将消息编码为<我>n><我>k曲线上的点<我>Y-<我>f（<我>X) =0。同样，编码由多项式的值组成<我>f(X)在<我>n不同的点。形式上，如果F是一个有限域，至少<我>n元素,<我>年代= (<年代ub>1，<年代ub>2．...<年代ub>n)是的序列<我>n截然不同元素，RS编码RS<年代ub>F S n k（<我>米）的讯息<我>米= (<我>米<年代ub>0，<我>米<年代ub>1、……<我>米<年代ub>k-1)由
在哪里<我>f(X) =米<年代ub>0+<我>米<年代ub>1X+……+<我>米<年代ub>k1,<我>X<年代up>k1。我们在这里强调选择<我>年代是由代码设计者决定的，我们将在第3.2节中利用这个特性。
下面的基本代数事实将是至关重要的:
非零多项式<我>p(X)的程度<我>D越过田野<我>F最多只能有<我>D不同的根，即最多<我>D元素<我米g src="https://dl.acm.org/cms/attachment/cfecc4db-14db-4cb1-8725-3e32cec85f4c/isin.gif" border="0" hspace="2" alt="isin.gif">F可以满足<我>p（）＝0。
这一事实意味着两种不同消息的编码<我>米和m比RS<年代ub>F、S、n, k必须在多于<我>N-k的位置。<年代up>c因此RS码的最小距离是最小的<我>N-k+1．它实际上等于<我>N-k+1：例如，考虑与零多项式和多项式对应的消息的编码<我米g src="https://dl.acm.org/cms/attachment/6d4493b9-394e-458b-9056-3c0ba0b2e770/cacm5203_b.gif" border="0" hspace="2" alt="cacm5203_b.gif">．最小距离为<我>(n - k +1）对于维度编码来说是最好的<我>k，使RS编码在这方面是最佳的。
<我米g src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊">2.1.纠正RS码字中的错误
为什么上面的大距离有用?如果最多<我>(n - k)/2误差破坏多项式的计算<我>f（<我>X），然后编码<我>f(X)与其他多项式编码相比，该编码在一致性方面保持了对损坏数据的最佳拟合<我>g (X)程度小于的<我>k．因此，人们有希望恢复健康<我>f(X)和正确的信息即使在<我>(n - k)/2的错误。然而，如何隔离错误并进行恢复并不是直接的<我>f(X)<我>高效。我们不知道错误的位置，尝试所有可能性将需要指数级的时间。
早在1960年，甚至在多项式运行时间被正式定义为高效算法的基础概念之前，Peterson<年代up>15描述了一种多项式时间算法来解决上述问题。我们现在描述的是另一种算法背后的高级想法，这是韦尔奇和伯勒坎普的成果，<年代up>18按照格默尔和苏丹的优雅描述。<年代up>3.
假设编码<我>（f（<年代ub>1),…<我>f（<年代ub>n))的多项式<我>f(X)已传送，我们收到已损坏的版本(<我>y<年代ub>1，<我>y<年代ub>2,……<我>y<年代ub>n)<我>E= {<我>我：<我>y<年代ub>我f（<年代ub>我)}的错误位置的大小最多<我>(n - k)/2。假设我们奇迹般地<我>知道一组<我>E．然后我们可以简单地丢弃<我>y<年代ub>我对应于这些位置，并插值<我>f(X)通过其他正确的数据点。我们至少会有<我>(n + k)/2<我>k位置，所以插值将唯一识别<我>f(X)．
二元插值误差定位:因此，钥匙是一种巧妙的定位方法<我>E快速定位错误。为了证明这一点，让我们把这个问题在几何上当作一个等价物<我>噪声曲线拟合问题。我们得到<我>n点(<年代ub>我y<年代ub>我）<我>我= 1,2，…,<我>n在“飞机”上F×F．目标是找到唯一的带方程的曲线<我>Yf (X)＝0表示度(<我>f) <<我>k它穿过了所有的地方<我>e<我>(n k)/2位置<我>我，即<我>在E。如果没有噪音，在所有地方拟合一条曲线<我>n点很容易，它只是多项式插值。我们知道<我>Yf (X)通过<我>ne点，我们可以得到一条经过所有点的曲线通过拟合通过误差点和曲线的垂直线<我>Yf (X)＝0;看到<一个href="#F2">图2．从代数上讲，如果我们定义
然后是曲线<我>P (xy) =0通过所有的点，即，<我>P (<年代ub>我，<我>y<年代ub>我) = 0<我>我。表达式(1)中的第二个因子称为误差定位多项式，它以误差位置为根。
鉴于<我>P (X, Y)，可以找到它的因子(这可以有效地完成)，从而读取消息多项式<我>f(X)从<我>Yf (X)的因素。但是我们如何找到<我>P (X, Y) ?发现<我>P (X, Y)在它的因式中(1)回避了这个问题，但注意我们也可以写<我>P (X, Y)在表格中<我>P (xy) =d<年代ub>1（<我>X）y-n<年代ub>1（<我>X）学位(<我>D<年代ub>1）<我>e<我>(n k)/2、学位(<我>N<年代ub>1) <<我>e+<我>k<我>(n + k)/2.
知道了这样一个多项式的存在，我们可以尝试找到一个非零二元多项式<我>问（xy) =d<年代ub>2（<我>X）YN<年代ub>2（<我>X）令人满意的
这可以通过建立一个线性方程组来实现F的系数是未知数<我>D<年代ub>2(X)而且<我>N<年代ub>2(X)，<我>n线性约束条件<我>问（<年代ub>我，<年代ub>我) = 0。我们称之为多项式<我>问（XY）因为我们不能假设解等于<我>P (X, Y)（上述系统可能存在多个非零解)。求解这个线性系统当然可以在多项式时间内完成，也可以采用快速、实用的方法。
我们可以用初等代数证明，当错误的数量<我>e<我>(n k)/2，<我>任何内插<我>问（XY）满足上述两个条件<我>必须有<我>P (X, Y)作为一个因素，而应是形式<我>P (xy）一个（x）对于某个非零(可能是常数)多项式<我>(X)。直观的原因是，与曲线相比，数据中的误差很少<我>Yf (X)＝0，<我>曲线P (X, Y)＝0是拟合所有数据点的最经济的方法。形式证明通过考虑多项式进行<我>R(X)<年代up>def＝<我>问(X, f (X))它一定等于零，因为(i)它至少是<我>(n + k)/2根(即所有<年代ub>我的原因<我>f（<我><年代ub>我) =<我>y<年代ub>我)和(ii)度小于<我>(n + k)/2（通过设计<我>问(X, Y))．因此,<我>问（XY）也有<我>Yf (X)作为一个因素，我们可以恢复<我>f(X)通过分解<我>问（XY）．(这里的实际任务比一般的二元多项式因式分解要简单，并且允许使用近线性时间算法。)
<我米g src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊">2.2.列出解码里德所罗门码
我们现在转到里德所罗门码的列表解码。设置和前面一样:给定<我>n点(<我><年代ub>我，<我>y<年代ub>我）<我米g src="https://dl.acm.org/cms/attachment/cfecc4db-14db-4cb1-8725-3e32cec85f4c/isin.gif" border="0" hspace="2" alt="isin.gif">F<年代up>2，求多项式<我>f（<我>X程度小于<我>k这样<我>f（<我><年代ub>我）<我>y<年代ub>我最多<我>e位置<我>我。不同的是现在<我>e>><我>(n k)/2，所以这样的多项式可能不止一个<我>f（<我>X），解码器需要输出。
在深入研究算法之前，我们先停下来考虑一下错误的数量有多大<我>e我们可以通过目标来纠正。显然，我们需要保证只有少数(最多多项式多)在<我>n）解多项式<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)否则解码器就不可能在多项式时间内输出所有信息。利用任意两个多项式的编码差异大于<我>(n k)位置，它可以显示(通过所谓的“约翰逊界”)<我米g src="https://dl.acm.org/cms/attachment/124df924-49da-4207-b259-71ed373dd4cf/cacm5203_c.gif" border="0" hspace="2" alt="cacm5203_c.gif">，解的个数(称为<我>列表的大小)保证多项式小。是否可以证明某个RS码的多项式列表大小的限制甚至更大<我>e仍然是一个悬而未决的关键问题。
我们现在描述苏丹的突破性算法为列表解码RS码的想法。<年代up>17回想一下，我们要解决一个有噪声的曲线拟合问题，并输出所有曲线<我>Y<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X) =0 with deg(<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">) <<我>k它们穿过<我>ne或者更多<我>n点(<我><年代ub>我，<我>y<年代ub>我)．为<我>e<我><我>(n k) /2、Berlekamp-Welch算法插值二元多项式<我>问（XY）一种非常特殊的形式<我>n点。苏丹的想法<我>E> (nk) /2是插值/拟合a<我>一般非零的曲线<我>问（XY）＝0的“度”刚好足够高(这样它的存在是有保证的)<我>所有的<我>n点。的系数可以通过求解线性方程组来有效地拟合这样的曲线<我>问(X, Y)。
对于BerlekampWelch算法，认为<我>Y<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)是一个因素<我>问（XY）的非常特殊的结构<我>问(X, Y)。在列表解码案例中，苏丹利用了形式曲线相交的特殊性质<我>Y-<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)任何插值的二元多项式<我>问（XY）有适当的程度限制。非正式地说，苏丹的想法是考虑到强烈的程度限制<我>问（XY），每一条曲线<我>Y<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X) =0 with deg(<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">) <<我>k这至少是有意义的<我>ne的点必须被插值曲线“使用”，以满足通过所有点的要求<我>n点。举个例子，在<一个href="#F3">图3，目标是找到所有的线(即，我们有<我>k＝2）通过所有的<我>e＝9个<我>n＝14个输入点(有两条这样的线，在图中标出<我>当L<年代ub>1（<我>XY）而且<我>l<年代ub>2(X, Y))。在四度曲线的方程中有足够的自由度，因此可以通过任意14个点来拟合四度曲线。该图说明了一条这样的曲线，它是两条线与一个“椭圆”的乘积。<我>E（XY）。（注意总度<我>问（XY）4）。此外，我们看到这两条相关的行作为因子弹出。这不是巧合，每一个经过14点的4次曲线都必须有这两条线作为因子。原因是:如果一条直线不是因子，那么它最多只能与4次曲线相交4个点。因为每条线都与插值曲线相交至少5个点，所以它一定是一个因子。
更正式地说，是插值多项式的“度”度量<我>问（XY）将是(1，<我>k1）-度，定义为的最大值<我>我+（<我>k1）<我>j超过所有的单项式<我>X<年代up>我Y<年代up>j它的系数是非零的<我>问(X, Y)。让<我>D表示(1，<我>k1）程度<我>问(X, Y)。将上述论证推广到直线，如果是曲线<我>Y<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X) =0 with deg(<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">) <<我>k穿过不止<我>D点,然后<我>Y<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)一定是的因素<我>问(X, Y)。通过计数参数，我们可以证明a (1，<我>k1）度<我>D的<我米g src="https://dl.acm.org/cms/attachment/54ef49e8-ef80-4e11-8409-ba4665518d58/cacm5203_d.gif" border="0" hspace="2" alt="cacm5203_d.gif">足以拟合非零曲线。总之，这就产生了一个可以纠正的算法<我米g src="https://dl.acm.org/cms/attachment/fea947a5-97a5-4622-81fc-47065e0d0d2a/cacm5203_e.gif" border="0" hspace="2" alt="cacm5203_e.gif">误差，或者说是分数<我米g src="https://dl.acm.org/cms/attachment/8c716ca7-f5d8-4710-a5ee-ac11dadabcd6/cacm5203_f.gif" border="0" hspace="2" alt="cacm5203_f.gif">误差作为速率的函数<我>R．
对于低速率，该算法即使在设置中，当噪声淹没了正确的数据，接近100%的符号可能是错误的，也可以恢复。这个特性为密码学和复杂性理论中的一些强大应用奠定了基础。然而，该算法并没有比(1<我>R) / 2的误差分数被传统算法修正为速率>的1/3，也达不到<我米g src="https://dl.acm.org/cms/attachment/516e9622-2d76-40dc-b0e5-4d47c580f907/cacm5203_g.gif" border="0" hspace="2" alt="cacm5203_g.gif">半径由组合边界表示。
现在我们转向改进的算法来修正分数<我米g src="https://dl.acm.org/cms/attachment/516e9622-2d76-40dc-b0e5-4d47c580f907/cacm5203_g.gif" border="0" hspace="2" alt="cacm5203_g.gif">由于古鲁斯瓦米和苏丹的错误。<年代up>10关键的新思想是坚持插值多项式<我>问（XY）有<我>多个每一个都是0<我>n点。为了解释这一点，我们尝试一个高级的几何描述。考虑下面的例子<一个href="#F4">图4与<我>n＝10个点，目标是输出至少通过的所有行<我>Ne =4点。这个例子不能用苏丹的算法求解。实际上，由于有五条解线，如果它们都是某个插值曲线的因子，那么该曲线的次至少为5。然而，不能保证任意度5的曲线通过这些点时，每条线都必须通过其中的4个点作为因子(这条线必须通过6个点才能保证这一点)。让<我>C＊是5次曲线，它是五条解线的乘积。如前所述，如果我们通过10个点插值一条5度曲线，我们通常会<我>不得到<我>C＊作为解。的一个特殊属性<我>C＊它通过每一个点<我>两次;在先验上，没有理由期望一个插值曲线会有这个性质。GuruswamiSudan的想法是<我>坚持插补阶段产生一个5次曲线，在每个点上的多重度至少为2(即，曲线与每个点相交两次)为零。人们可以认为这五条线中的每一条都是曲线的一个因子。事实上，对于7级以上的学生来说也是如此。这是因为每条线与曲线的交点数(计算多重度)至少是4 × 2 = 8，大于曲线的度数。最后，我们总是可以拟合经过任意10个点两次的7度曲线(再次通过计数参数)。通过在插值步骤中坚持多重性，我们可以解决这个例子。
一般来说，GuruswamiSudan列表解码器的插值阶段找到一个多项式<我>问（XY）它的多重度是0<我>w对于某个合适的整数<我>w在每一个<我>（<年代ub>我y<年代ub>我)．<年代up>d当然，这总是可以用(1，<我>k1）-度是一个因素<我>w更大(只需将先前的插值多项式提高到<我>w“th权力)。关键的收获是，只需要一个因子的学位就可以达到所需的多样性<我米g src="https://dl.acm.org/cms/attachment/62f2f281-982d-45b4-8bf5-b06a94ef7767/cacm5203_h.gif" border="0" hspace="2" alt="cacm5203_h.gif">大。第二步是一样的，这里每个正确的数据点都很重要<我>w0。这<我米g src="https://dl.acm.org/cms/attachment/80ea08af-0d5a-4d53-8726-a2fdf09268fc/cacm5203_i.gif" border="0" hspace="2" alt="cacm5203_i.gif">要素的节约转化为生产力的提高<我米g src="https://dl.acm.org/cms/attachment/516e9622-2d76-40dc-b0e5-4d47c580f907/cacm5203_g.gif" border="0" hspace="2" alt="cacm5203_g.gif">来<我米g src="https://dl.acm.org/cms/attachment/8c716ca7-f5d8-4710-a5ee-ac11dadabcd6/cacm5203_f.gif" border="0" hspace="2" alt="cacm5203_f.gif">．看到<一个href="#F5">图5对于误差率和误差分数之间的权衡图，以及(1 -<我>R) / 2传统唯一解码算法的权衡。注意，我们现在得到了改进<我>每一个率。还绘制了信息理论极限1<我>R，以及ParvareshVardy对低利率的改进，我们将很快讨论。
软解码:我们现在评论多重性思想的一个进一步的关键好处，它与列表解码的潜在实际应用有关。多重度可以用来对不同码字位置的相对重要性进行编码，对于我们对其值更有信心的符号使用较高的多重度，而对于可信度估计较低的不太可靠的符号使用较低的多重度。在实践中，这种置信度估计(称为“软输入”)在解码器的输入端(例如，从模拟信号的解调)有大量可用。这导致了一个有前途的<我>不痒的决定在实际应用中具有良好编码增益的RS码解码器，<年代up>13它被采用在月球反弹计划中，以改善无线电操作员之间的通信，他们从月球上反弹无线电信号，进行远程联系。
我们现在讨论RS代码的一种变体，称为<我>折叠里德所罗门代码（因此折叠RS码)，这将使我们接近分数1的最佳纠错半径<我>R的错误。折叠RS码中的码字将与RS码字一一对应。我们从一个非正式的描述开始。考虑与多项式对应的RS码字<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X），在点上计算<我>x<年代ub>0，<我>x<年代ub>1、……<我>x<年代ub>n1从F的码字所描述的<一个href="#F6">图6．折叠RS码中对应的码字<我>折叠参数的<我>米＝4）是通过将RS码字上的四个连续符号并列在一起得到的，如底部所示<一个href="#F6">图6．换句话说，我们认为RS代码是一个更大的字母(四倍于“包大小”)和四倍于小块长度的代码。这种重新打包减少了必须处理的错误模式的数量。例如，如果我们的目标是在新的较大符号的1/4分数内纠正错误，那么我们就不再需要纠正中(粉色)阴影列对应的错误模式<一个href="#F6">图6（而在ReedSolomon案例中，需要考虑原始符号上的相同错误模式)。
我们想在这里强调一个微妙的点:在最坏情况的错误模型中，错误的“原子”单位是一个字母字符。这在上面的例子中非常重要，用来排除小字母可以接受的错误模式。对于可能会担心这构成“欺骗”的读者，例如，如果有人将整个RS码字折叠成一个大符号，我们提供了两个相反的观点。首先，因为我们将只使用<我>常数折叠参数，字母尺寸比RS码增加不大。第二，在第4节中，我们将看到如何将折叠的RS代码转换为字母大小的代码<我>完全不依赖吗在块长度上，同时仍然保持类似的纠错属性。
我们现在正式定义折叠RS代码。让场的非零元素F由<我>，即每个非零元素为<我><年代up>我对于某个0<我>我|F2）这样的<我>对于任何有限域F)总是存在的<我>米1．成为…<我>折叠参数，让<我>n是一个能被整除的整数<我>米而且<我>n||1。带有折叠参数的折叠RS编码<我>米）的消息多项式<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X）有作为其<我>j0的符号<我>j<<我>n/<我>米，<我>米元组(<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我><年代up>j米),<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我><年代up>jm+1),…<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我><我><年代up>jm+<我>米1))。
这些代码的块长度是<我>N＝<我>n/<我>米．代码的速率保持不变<我>k/<我>n，因为折叠操作不会引入任何进一步的冗余。
折叠操作确实限制了人们需要担心的错误模式。但是，与未展开的RS代码相比，如何在解码算法中实际利用这一点并设法纠正更大比例的错误呢?我们接下来讨论这个问题。
<我米g src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊">3.1.多元解码
回想一下两步Guruswami-Sudan (GS)算法。首先，我们插值一个二元多项式<我>问（<我>X，<我>Y）通过点(<我><年代ub>我，<我>y<年代ub>我）<我米g src="https://dl.acm.org/cms/attachment/cfecc4db-14db-4cb1-8725-3e32cec85f4c/isin.gif" border="0" hspace="2" alt="isin.gif">F<年代up>2．然后在第二步中，我们对二元多项式进行因式分解，并保留原有形式的因子<我>Y<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X)，<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X）是一个次小于的多项式<我>k（可能有一些因素不是线性的<我>Y：我们忽略他们)。让我们在一个等价的描述中重新描述第二步，这将在后面有用。特别是考虑<我>单变量多项式<我>R<年代ub>X（<我>Y）相当于<我>问（<我>X，<我>Y），其中系数本身为<我>多项式在不确定的<我>X它们的系数来自F:给定多项式<我>问（<我>X，<我>Y）一个人会计算<我>R<年代ub>X（<我>Y）的所有系数<我>Y一起(例如，如果<我>问（<我>X，<我>Y) = (<我>Y（<我>X1)) (<我>Y<年代up>2+<我>X<年代up>3.),那么<我>R<年代ub>X（<我>Y) =<我>一个<年代ub>3.Y<年代up>3.+<我>一个<年代ub>2·<我>Y<年代up>2+<我>一个<年代ub>1·<我>Y+<我>一个<年代ub>0,在那里<我>一个<年代ub>3.= 1,<我>一个<年代ub>2＝<我>X+1，<我>一个<年代ub>1＝<我>X<年代up>3.而且<我>一个<年代ub>0X<年代up>4+ X<年代up>3.)．现在请注意<我>Y<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)是一个因素<我>问（XY）当且仅当<我>f(X)是一个<我>根单变量多项式的<我>R<年代ub>XY，也就是多项式<我>R<年代ub>Y（<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X))与零多项式(在例子中，<我>Y（X1）分<我>问（XY）而且<我>R<年代ub>X（<我>X1）0）。
现在让我们回到列表解码折叠RS码的问题<我>米＝4．给定接收到的单词whose<我>我符号(表示0<我>我是<我>(y<年代ub>我,01，y<年代ub>我1，y<年代ub>我，y<年代ub>我3)，我们需要输出所有靠近折叠的RS码字。为了激发算法背后的思想，暂时假设传输的码字来自所谓的<我>交叉R年代编码<我>订单4．在这种代码中的任何码字都将具有as its<我>我Th符号(0)<我>我<我><我>N1）4元组(<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我><年代up>4<我>我)，<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">1（<我><年代up>4<我>我)，<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">2（<我><年代up>4<我>我)，<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">3.（<我><年代up>4<我>我)),<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">1 (X),<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">2 (X)而且<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">3.（<我>X）最多是若干次多项式<我>k我。我们注意到折叠RS码是一个子码<年代up>e的交错RS码<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">j（<我>X）<我>＝<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我><年代up>jX) 1个<我>j3.
考虑到上面的设置，首先要探索的是是否可以将GS算法推广到交错RS码的设置。要看到这样的泛化，请注意RS码是1阶RS码的交叉。GS算法插值了一个非零二元多项式<我>问（XY）在这种情况下。因此，对于一个4阶的交错RS码，一个自然的尝试是计算一个非零的5变量多项式<我>问（xy，z, u, w)，其中(一如既往)<我>Y是一个占位符<我>为<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)（这部分是泛化)<我>Z,你，<我>W是占位符<我>为<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">1(X)<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">2(X)<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">3.（<我>X)，分别。下一步是求根，我们计算4变量多项式<我>R<年代ub>X(Y, Z, U, W)等于<我>问（xy，z, u, w)现在我们希望找到所有的元组<我>(y，z, u, w)使<我>R<年代ub>X(Y, Z, U, W)消失，这是所需的元组<我>（<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">1（<我>X）<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">2（<我>X）<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">3.（<我>X）)是其中之一。后一个条件实际上是可以满足的，但问题在于生成的元组的数量<我>R0可以非常大(以指数增长)<我>n）。为了直观地了解哪里出了问题，回想一下在古鲁斯瓦米-苏丹的情况，我们有一个未知的问题<我>Y还有一个限制条件<我>R<年代ub>X(y) = 0。然而，在交错RS设置中，我们有<我>四个未知数<我>Yz u w但<我>只有一个约束<我>R<年代ub>X(y, z, u, w) = 0。这本质上意味着四个未知数中的三个是无约束的，因此几乎可以是任何次小于的多项式<我>k。
上面的泛化(和类似的想法)在一些作品中尝试过，但无法解码超越<我米g src="https://dl.acm.org/cms/attachment/516e9622-2d76-40dc-b0e5-4d47c580f907/cacm5203_g.gif" border="0" hspace="2" alt="cacm5203_g.gif">半径。最后，在GS算法发表7年后，Parvaresh和Vardy<年代up>14有个巧妙的主意:强制多项式<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">1（<我>X），<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">2（<我>X)，<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">3.（<我>X）与…有关<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X）．特别地，他们只看交错RS码的子码在哪里<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">j（<我>X) = (<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">j1 (<我>X）)<我><年代up>d国防部<我>（E(X))1<我>j3.．我们定了<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">0（<我>X）<我>＝<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X))，对于某个正整数参数<我>d一个不可约多项式<我>E(X)。我们使用不可约多项式计算模数的原因是，这些多项式之间的关系转化为它们对应的占位符之间的下列关系:<我>Z = y<年代up>d， u = y<年代up>d<年代up>2,<我>W＝y<年代up>d<年代up>3.．换句话说，我们有所收获<我>三个新四个变量的约束条件<我>Yz u w。加上插值约束<我>R<年代ub>X（<我>Y，<我>Z, u, w) =0，这就恢复了未知数的数量和约束的数量相等。这反过来意味着可能的解的数量是多项式有界的。(得到这个结论涉及到一些步骤，但它们大多都是“底层细节”)进一步，该方法不仅建立了解的数量的界限，而且给出了一个多项式时间算法来寻找这些解。要了解这一点，请注意，给定三个新的约束条件，我们正在寻找的根<我>单变量多项式<我>R<年代ub>X(Y, Y<年代up>dY<年代up>d<年代up>2Y<年代up>d<年代up>3.)，这可以通过众所周知的多项式时间算法来实现。<年代up>1
最后，让我们回到列表解码折叠RS码的问题<我>米＝4。<我>在折叠RS码，我们有这样的性质<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">j(X)是相关的<我>来<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)1<我>j<我>3.事实上，结合Guruswami和Rudra在有限域中的一些著名结果<年代up>9我们证明了这一点<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X）<我>＝（<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X）)<年代up>| F | 1国防部<我>（E(X))，在那里<我>E（x) =x<年代up>| F | 1-是一个不可约多项式。我们注意到不可约多项式<我>E(X)在Parvaresh-Vardy(从今以后，PV)法典中只有一些学位要求。我们对<我>E(X)因此，折叠RS码是PV码的一种特殊情况。然而，我们还没有完成。到目前为止，我们所能声称的只有折叠的RS码率<我>R带折叠参数<我>米＝4可以从与对应PV码相同的误差分数中列表解码，这恰好是<我米g src="https://dl.acm.org/cms/attachment/17b2a5f7-124b-423f-a4b4-fbc90b605478/cacm5203_j.gif" border="0" hspace="2" alt="cacm5203_j.gif">．我们有4个<我>R出现而不是<我>R因为PV码的速率是原始RS码速率的1/4，因为消息的编码<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X）现在由的评价组成<我>四个多项式而不是这些<我>的<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">(X)。接下来，我们将扩展我们的另一个主要思想，即“压缩”PV编码以避免这种速率损失，并使纠正接近分数1 -<我>R的错误。
<我米g src="https://portal.acm.org/images/bullet.gif" vspace="2" alt="＊">3.2.最后一点
对Parvaresh-Vardy的改进来自于对苹果和橘子的比较。特别地，到目前为止我们已经看到，折叠参数为4的折叠RS码是4阶PV码的一个特例。相反，让我们比较折叠的RS码和的PV码<我>小顺序，说2。结果表明，具有4折叠参数的折叠RS码是特定的2阶PV码的压缩形式，我们将利用这一观察结果。特别是，如<一个href="#F7">图7比较折叠RS码字和2阶PV码(其中多项式<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我>X）在点{1，，<我>．．.，<我><年代up>n1} \ {<年代up>3.，<我><年代up>7、……<我><年代up>n－1})。我们在PV编码中发现<我>的<我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">，对于每一个0<我>我<我>n / m1和每个0<我>< j < m1，<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我><年代up>心肌梗死+j)恰好出现两次(一次是<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">（<我><年代up>心肌梗死+j)，另一次是<我><我米g src="https://dl.acm.org/cms/attachment/2b03cf8c-a8e2-4d4c-9d0f-2e0b8abc5d8a/fnof.gif" border="0" hspace="2" alt="fnof.gif">1（<年代up>1米我+j))，而它只在折叠RS编码中出现一次。换句话说，包含在折叠RS码字中的一个符号中的信息<我>四个F中的元素)在PV码字中的三个符号上重复(值为<我>六个这意味着即使折叠的RS码字和PV码字具有完全相同的信息，折叠的RS码字被压缩了3/2倍。这反过来又以同样的因素提高了RS码的折叠率。因此，我们可以列出具有折叠参数4和速率的解码折叠RS码<我>R从一个分数<我米g src="https://dl.acm.org/cms/attachment/bf49a9d0-ce0a-4fe2-bcac-fffd8bf98ec8/cacm5203_k.gif" border="0" hspace="2" alt="cacm5203_k.gif">的错误。
因此，我们提出了具有折叠参数的折叠RS的列表解码算法<我>米可以模块化地定义如下:展开接收到的字的适当的PV码的顺序<我>年代米然后在这个展开的接收字上运行Parvaresh&Vardy列表解码器。结果表明，该列表解码器可以对这种折叠RS码进行校正<我>R从上到下<我米g src="https://dl.acm.org/cms/attachment/c85ea153-d8e5-4748-b49d-0a8e9163a317/cacm5203_l.gif" border="0" hspace="2" alt="cacm5203_l.gif">误差的百分比。通过选择<我>米比…大(稍<我>年代和选择<我>年代足够大(以1/。表示<我米g src="https://dl.acm.org/cms/attachment/cfecc4db-14db-4cb1-8725-3e32cec85f4c/isin.gif" border="0" hspace="2" alt="isin.gif">)，我们可以得到以下结果。
定理1。<我>对于每个>0<我>而且0 <<我>R<1，<我>有一类折叠式RS码，其速率至少为R，并且可以被列表解码到一个分数１ －<我>R-时间误差（<我>N/<年代up>2）<我><年代up>O（<我>1日志(1 / R))其中N是代码的块长度。代码的字母大小是（<我>N/<年代up>2）<我><年代up>O(1 /<年代up>2）．
我们注意到时间复杂性对<我>， 1/<我>指数。改善这一界限仍然是一个具有挑战性的开放问题。
到目前为止，我们已经讨论了大字母上的代码。例如，比率的折叠RS码<我>R可以从1解码list<我>R<我>分数的错误需要字母大小大致<我>n<年代up>O (1 /<年代up>2),<我>n是代码的块长度。这种大的字母大小可能是一个缺点。接下来，我们讨论已知的帮助我们减少字母大小的技术。
我们从可能是最自然的小字母{0,1}开始。对于在此字母表上定义的代码(也称为<我>二进制编码)，结果表明，从错误的分数列表解码的最佳可能率是1<我>H（<我>），在那里<我>H（x) =x日志<年代ub>2x（1<我>x）日志<年代ub>2（1<我>x）为熵函数。有两点需要注意。首先，速率1<我>------ - - - - - H（<我>）比折叠RS码所能达到的速率1小得多。(事实证明，要达到1的速率，字母的大小至少需要是2<年代up>1 /；这一节后面会详细介绍。)第二，正如香农的开创性论文所示，<年代up>16数量1<我>H（<我>）是<我>完全与二进制对称信道平衡计分卡中可以实现的最佳可能速率(又名“容量”)相同。因此，列表解码可以弥合香农随机模型和汉明最坏情况模型之间传统的差距。
我们将折叠RS码的结果“转移”到二进制码的结果，这种结果是通过一种将代码组合在一起的自然方法实现的<我>代码连接由福尼在40多年前提出。由于解码折叠RS码的强大算法，我们可以使用这种方法来实现一种被称为<我>Zyablov绑定误差修正率和百分比之间的关系。<年代up>9在后续的工作中，使用另一种代码连接的泛化，我们改进了交换到<我>Blokh-Zyablov绑定．<年代up>8图8绘制这两种权衡以及可能的最佳权衡(列表解码能力)。二进制码的列表解码能力与有效算法所能达到的最佳边界之间存在很大差距。缩小这一差距仍然是一个核心和极具挑战性的开放问题。
现在，我们简要介绍一下如何解决第3节中提出的大字母问题。当折叠RS码的折叠参数为常数(如定理1)时，表示字母符号所需的比特数不大于折叠RS码块长度的对数。这足够小，可以使用上面提到的代码拼接的思想来减少字母。为了保持被解码的错误率和错误率之间的最佳权衡，我们需要将连接与一种使用的重新分配符号的方法相结合<我>扩张器图．<年代up>6这就产生了利率代码<我>R它可以从一个分数1中解码<我>R<我>2个字母的错误<年代up>1 /<我>4，接近2的下界<年代up>1 /<我>前面提到的。
首先，我们提到一些在我们的结果最初发表之后出现的相关工作。将本文的结果扩展到框架的进一步工作<我>一个lgebraic-geometric代码在古鲁斯瓦米做了什么<年代up>5古鲁斯瓦米和帕特塞克。<年代up>7在Parvaresh-Vardy列表解码器中的一个令人惊讶的应用是构造<我>随机提取器古鲁斯瓦米、乌曼斯和瓦丹的作品。<年代up>11随机提取器将弱随机源的输入转换为几乎完全随机的字符串，在理论计算机科学中已经深入研究了超过15年。这个最新的提取器在所有参数中几乎是最优的，同时具有简单的、自包含的描述和证明。
尽管本文提出的工作在我们对列表解码的理论理解上取得了良好的进展，但将这些思想应用到实践中还需要进一步的创新。最后，我们提出了两个实际挑战。
第一个挑战是使折叠RS码的列表解码算法更加实用。回想一下，该算法涉及一个插值步骤和一个“寻根”步骤。对于后一步，有一些可以在实践中使用的快速启发式方法。然而，由于需要求解的线性系统的大尺寸，插值步骤对于实际目的来说似乎太过低效。对于这一步，拥有更高效的算法将非常有用。我们注意到，GuruswamiSudan算法已经得到了这样的改进。
第二个挑战更为普遍。代码在通信和数据存储等领域有许多实际应用。尽管有希望和最近的进展，列表解码还没有在实际系统中得到广泛应用(尽管如前所述，Moonbounce程序确实使用基于多重度的列表解码器)。一个可能的原因是，先前的列表解码算法在高速率情况下，没有提供比传统的唯一解码算法更大的增益。然而，这不再是一个问题，我们现在有算法可以在这种情况下获得更好的理论边界。此外，折叠RS码与实践中普遍存在的RS码非常相似。在不久的将来，列表解码有望在实际系统中得到更广泛的应用。
这里描述的研究部分得到了美国国家科学基金会CCF-0343672奖和斯隆和帕卡德基金会奖学金的支持。我们感谢罗尼特·鲁宾菲尔德对本文早期草稿提出的宝贵意见。
1.大有限域上的因式多项式。<我>数学。第一版。24（1970)，71373.5。
<一个n一个米e＝"R2">
<一个n一个米e＝"R3">3.多变量多项式的高弹性校正器。<我>信息处理，第43期， 4(1992)， 169174。
<一个n一个米e＝"R4">4.Goldreich, O, Levin, L.所有单向函数的核心谓词。在<我>第21届ACM计算理论研讨会论文集， 1989, 2532。
<一个n一个米e＝"R5">5.V. Artin自同构，回旋函数场和折叠列表可解码码，2008。手稿。
<一个n一个米e＝"R6">6.Guruswami, V.， Indyk, P.具有接近最佳速率的线性时间可编/可解码码。<我>IEEE反式。信息论51， 10(2005)， 33933400。
<一个n一个米e＝"R7">7.相关代数-几何编码:有界字母上改进的列表解码。<我>数学。77年第一版。， 261(2008年1月)，447473。
<一个n一个米e＝"R8">8.Guruswami, V.， Rudra, A.通过多级连接更好的二进制列表可解码码。在<我>第11届随机化与计算国际研讨会论文集， 2007, 554568。
<一个n一个米e＝"R9">9.Guruswami, V.， Rudra, A.实现列表解码能力的显式代码:到单例边界的错误纠正。<我>IEEE反式。信息论54， 1(2008)， 135150。初步版本<我>获得STOC 06年．
<一个n一个米e＝"R10">10.Guruswami, V.， Sudan, M. ReedSolomon和代数几何编码的改进解码。<我>IEEE反式。信息理论，<我>45（1999)，17571767。
<一个n一个米e＝"R11">11.Guruswami, V.， humans, C, Vadhan, S.P. ParvareshVardy代码的不平衡扩展器和随机提取器。在<我>第22届IEEE计算复杂度会议论文集， 2007, 96108。
<一个n一个米e＝"R12">12.错误检测和错误纠正码。<我>贝尔系统技术（1950年4月)，147160
<一个n一个米e＝"R13">13.里德所罗门码的代数软判决译码。<我>IEEE反式。信息论/， 11(2003)， 28092825。
<一个n一个米e＝"R14">14.Parvaresh, F.， Vardy, A.在多项式时间内修正GuruswamiSudan半径以外的误差。在<我>第46届IEEE计算机科学基础研讨会论文集， 2005, 285294。
<一个n一个米e＝"R15">15.BoseChaudhuri码的编码和纠错程序。<我>IEEE反式。信息理论，<我>6（1960)，459470。
<一个n一个米e＝"R16">16.沟通的数学理论。<我>贝尔系统技术（1948）， 379423, 623656。
<一个n一个米e＝"R17">17.苏丹，M.里德所罗门码超出纠错范围的解码。<我>j．复杂性，<我>13， 1(1997)， 180193。
<一个n一个米e＝"R18">18.代数分组码的纠错。<我>美国专利号4,633,4701986年12月。
<一个n一个米e＝"R19">19.沃兹克拉夫特，J.M.列表解码。<我>季度进展报告，电子研究实验室，麻省理工学院， 48(1958)， 9095。
回到顶部
文卡特斯Guruswami（venkat@cs.washington.edu)，计算机科学与工程，华盛顿大学，西雅图，WA 98105，美国。目前正在访问卡耐基梅隆大学计算机科学系，匹兹堡，宾夕法尼亚州。
阿特洛杜罗（一个tri@cse.buffalo.edu)，计算机科学与工程，布法罗大学，纽约州立大学，布法罗。
a.这个问题大约在50年前提出，而列表解码的主要组合限制是在20世纪70年代和80年代确立的。
<一个n一个米e＝"FNB">b.对于本文，不熟悉域的读者可以将有限域理解为{0,1，…，<我>p1）质数<我>p用加法和乘法运算定义模<我>p．
<一个n一个米e＝"FNC">c.如果没有，RS<年代ub>F,<我>年代,n, k(m) RS<年代ub>F,<我>年代,n, k(m)，对应于非零多项式的求值<我米g src="https://dl.acm.org/cms/attachment/38214841-003b-4c55-8675-a19f4b0e38ca/cacm5203_o.gif" border="0" hspace="2" alt="cacm5203_o.gif">（<我>米<年代ub>我米<年代ub>我）<我>X<年代up>我最多的程度<我>k1、至少有<我>k零:一个矛盾。
<一个n一个米e＝"FND">d.在这段描述中，我们跳过了将多个0的概念形式化，但它遵循了标准的思路，我们建议有兴趣的读者参考古鲁斯瓦米和苏丹<年代up>10了解详情。
<一个n一个米e＝"FNE">e.这与查看消息的适当子集是一样的。
这篇论文的原始版本发表在<我>《IEEE信息论汇刊》，2008年。
DOI: http://doi.acm.org/10.1145/1467247.1467269
图1。从直线上采样过采样<我>Y＝<我>斧头+<我>b容忍:容忍发生在…的错误<我>X＝3.和5。
©2009 acm 0001-0782/09/0300 $5.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2009 ACM, Inc.
没有找到条目
