内容提示：表整数为素数平方和和一个素数的k次方的华林问题的例外集

文档格式：PDF| 浏览次数：4| 上传日期： 19:17:51| 文档星级：?????

译注：最近看到了RS码，发现还挺有意思的，找了一些资料学习了下，发现对于程序员来说，从这篇看起会比较容易。看完以后想着翻译一下试试，看看自己到底看懂了多少，于是就有了这篇。本文有部分错误，以及一些排版不对的地方，有兴趣的还是看原文更好:)

Reed-Solomon纠错码（以下简称RS码）广泛用于数据存储（如CD）和传输应用中。然而，在这些应用中，码字是藏在了电子设备里，所以无法一窥它们的模样以及它们是如何生效的。有些复杂的条形码设计也采用了RS码，能够暴露出所有的细节，对于想要获得这种技术如何生效的第一手技术的爱好者，这是一种很有趣的方式。
在这篇文章里，我是试图从程序员的视角（而不是数学家的视角）来介绍RS码的基本原理。我会用以当下流行的QR码作为例子来介绍。我选择了Python（主要是因为写出来的代码看起来整洁美观），但是我也会介绍一些不那么显而易见的Python特性，以便那些不熟悉Python的人也能看懂。里头涉及到的数学知识对读者有一定要求，并且一般是大学才教授的，但是应当能让对高中代数掌握较好的人看懂。

这一节详细介绍QR码的结构。本节的信息不完整，这是有意为之，只介绍了一个小的21x21的QR码（也被称为version 1）的常见特征。有关二维码的更多信息，请参考。
这是一个用于当例子的QR码。它由深色和浅色的方格组成，在条形码领域被称为“模块”（module）。在角落的3个方形定位器模式是QR码的典型可见特征。

之所以需要掩码处理，是为了避免数据区域中出现诸如类似定位器模式的形状，或者是大片的空白区域等，可能会使扫描器混淆、错乱。掩码处理逆转某些模块（白色变成黑色，黑色变成白色），保留其他模块不变。
参考下面的图示，红色区域使用一个固定的掩码模式编码，保存了数据区域（黑白部分）的掩码格式信息。当QR码被创建的时候，编码器通过尝试，选择使得不期望出现特征出现最少的那个掩码模式。被选择的掩码模式信息会被保存在格式信息（红色区域）中，使得解码器知道该用哪个。浅灰色的区域是不包含任何信息的固定模式。此外，在定位器模式中，还包含由交错的黑白模块组成的标尺（ ）。

使用异或运算（XOR，eXclusive-or，通常在变成语言中用 ^ 来表示），掩码过程可以很容易地被加载/移除。对格式信息的反掩码操作如下所示。逆时针读取左上角的定位器模式，我们能够得到下面的比特序列，白色表示0，黑色表示1。

格式信息有另一份可辨别的副本，因此即使其中一份被毁坏，也仍然有机会被识别。副本被分成两个部分，分别放在另外两个定位器的边上，同样也是逆时针方向阅读（沿着左下角定位器往上，然后是右上角定位器边缘从左往右）。
格式信息的前2 bits 给出了用于数据的纠错级别。这个尺寸的QR码包含26字节(bytes,1 byte = 8 bits )信息，其中一些用于保存原数据，一些用于保存校验码，如下表所示。左边第一列只是给纠错级别起了个简单的名字。

格式信息中的接下来3 bits用于指定对数据区域使用的掩码模式。模式使用6x6放歌的方式定义，根据需要不断重复以覆盖整个区域。模式如下所示，包含了对应的数学公式指明（掩码中的）每个模块是否是黑色（i和j分别是行列从0开始的编号，从左上角开始算起）

是用于对格式信息本身的错误校验，会在后续章节中解释。

下图展示了经过反掩码操作后的放大了的图样。不同的区域被标记出来了，包括数据区域的边缘。

数据比特从右下角开始，沿着最右边的两列向上走“之”字形。前三个字节分别是 01（译注：可参见图中右下角的小箭头）。接下来两列从上向下读取，因此接下来的字节是 。当读取到底部后，再反过来从下往上读取接下来两列……按照这种方式一直读到最左边的列（如果有必要，跳过timing pattern）。下面是完整的十六进制表示的数据：

最后的步骤是将信息解码成可读格式。前4 bits 指明了信息是如何编码的。QR码使用几种不同的编码方案，使得不同类型的信息可以更高效地被存储，可参见下表的总结。在方案指示器之后是“长度”字段，告诉解码器保存了多少个字符。字符的长度取决于指定的编码方案。

长度字节数只对小的QR码有效

我们的样例数据开头是 0100 ，表明接下来是每个字符8 bits 。接下来8 bits 是长度字段，（10进制的13），表明有13个字符。之后才是数据字符。前两个是和（对于ASCII字符 ' 和 T）。有兴趣的读者可以自行解码后续的字符。（译注：用微信二维码扫扫就行了。。。）
在数据 bit 之后是另外一个4 bit 模式指示器，可以跟前一个不同，从而允许在一个QR码中混合多个编码方案。如果没有其他数据了，用 0000 来标记结尾（注意，标准允许忽略这个标记，如果存储空间不够的话）。

格式信息是用BCH码编码的，能够纠正一定数量的 bit 错误。BCH码是RS码的普遍形式（所有的RS码都是BCH码）。在QR二维码中，BCH码只用于格式信息，比数据信息中用到的RS码要简单得多，因此我们可以先从这里开始。

用于检测编码信息的过程类似整数除法，但是使用异或来代替减法。格式串应该能够被称为“生成子”（generator）的码“整除”。QR码使用 这个生成子。下面使用前述格式串 001 演示了这个过程：

下面这个Python函数实现了这个过程

译注：这个函数的返回值是参数 fmt 除以生成子的余数

这个函数也可以被用于编码 5-bit 的格式信息：

译注：由于format左移了10个bit，因此这里用 ^ 和用 + 是等价的。实际上因为这里的 + 是按位加（其实也就是异或了），所以它也等同于 - ，这一点对于理解它很重要。如果记格式信息为F，生成子为G，(F<<10)/G的商为Q、余数为R (即F<<10 == QG + R)，则最终的编码信息 C = (F << 10) ^

读者也许会对修改此函数让它能除以不同数字感兴趣。例如，更大些的QR码包含6 bits 的版本信息和12个错误校验码，并使用生成子 1 。
使用数学的规范格式，这些二进制数字可以用一个系数为""（译注:参考链接第三段内容理解）的多项式来描述。数字中的每一个 bit 是多项式中对应一项的系数（译注：该项的幂等于该bit在数字中的位置）。例如：

如果qr_check_format(fmt)得到的余数不是0，那么这个码被损坏或者是读取错误了（译注：即使是0也不能100%保证就对了）。下一步是要找出哪一个格式码最可能是原数据。虽然对于BCH码有许多复杂的解码算法，但是在这里杀鸡用不上牛刀。因为总共只有32个格式串（译注：15 bits 中前5个是原信息，后10个是根据原信息生成的），因此遍历找出所有码字中与fmt不同位数最小的那个会更简单（这个被称为汉明距离, hamming distance）

如果发现fmt不能被唯一地解码，则函数qr_decode_format返回-1。这种情况是由于有多个码字与fmt具有相同的距离。

在讲解用于编码数据的RS码之前，还需要介绍一点数学。类似于乘法和除法，我们定义两个对应的操作，应用于 8-bit 字节（译注：这里应该指的是整数，下同），且其结果也是 8-bit 字节。许多类似的算术规则对于新的定义也仍然有效，例如，任意元素乘以1（幺元）结果不变，任意元素乘以0（零元）得0，不允许除以0。其他有用的数学属性（例如分布率）也仍然有效。（基于这些操作的元素集合）被称为一个有限域()，或者叫伽罗华域(Galois field)。

译注：由于最后的加法是异或（模2加），因此系数为偶数的项都消去了。

相同的结果也可以通过竖式计算的一个修改版得到，只要把其中的加改成异或即可：

 
 
 0

下面这个Python函数实现了这个多项式乘法。

当然，由于结果不能用8-bit来表示了（在这个例子里结果是13 bits ），所以我们在得到最终结果之前还需要一个步骤：模，使用前面提到的除法过程。在本例中，最终的结果是 。
上述的乘法运算也可以直接用进行异或运算:

 0
 0 
 
 

下面的python代码用来实现上述等效乘法的异或运算:

#通过使用标准的无进位乘法和不可约多项式规约实现 '''二进制无进位整数乘法''' # 计算整数最高有效位（整数二进制格式第一位）. 等效于 int.bit_length() '''二进制无进位整数除法，返回余数''' # 余数>=除数, 通过移位对齐除数与余数的最高有效位 # 检查余数是否可除（为下一次循环铺垫） # 可除，则对齐最高有效位并执行异或运算(无进位减法) # 用不可约多项式规约，保证结果仍然在GF域内

至于为什么要用作为约数进行规约(reduction)，其数学原理较为复杂，简单来说，所代表的GF(2^8)多项式是一个“不可约(irreducible)”多项式，也叫“本原多项式”。x11d)是Reed-Solomon (RS)码中常用的本原多项式。

译注：从概念上讲，和并不等价，但在本文适用的范畴内是可以等价理解的，而且完全可以和整数中的素数做类比来理解，只不过这个是在多项式的范畴内。

上面的乘法代码效率较差，下面是不同算法实现的更高效率的版本：

3.2 基于对数的乘法

上述过程并不是最适合用来计算伽罗华域乘法的方法。对两个数进行乘法的过程需要8次循环，除法的过程也需要8次循环，然而我们实际上可以通过使用查表的方式来避免循环。一个科学的结果是在内存中建立完整的乘法表，但是那需要创建64k大小的表格（译注：256×256）。下面给出的结果要简洁许多。
首先，注意到使用)来进行乘法是相当简单的（通常把它记为α或 generator number ），只需要向左移1位，然后与进行异或操作（如果有必要）。下面是α的前几次幂：

译注： α^7 * α超过了8-bit，需要与异或得到α^8，依此类推。

如果这个表格依次类推，α的i次幂不会重复，直到α^255=。由此，这个域中的每个元素，除了0之外，都是α的某次幂。α被称为伽罗华域的本原元素（primitive element）或者生成子(generator)。
仔细观察，可以发现另一种实现乘法的方法：把α的幂加起来。

问题是，我们怎么计算是α的几次幂呢？这个问题被称为离散对数（discrete logarithm），目前没有已知的高效解法。然而，因为域中只有256个元素，我们可以很容易地建立起一个指数表；而同时，对应的对数表也也有用。

#使用参数prim给的本原多项式计算指数表和对数表备用 # 计算每一个GF(2^8)域内正整数的指数和对数 # 更一般的情况用下面这行，不过速度较慢 # Optimization: 双倍指数表大小可以省去为了不出界而取模255的运算 (因为主要用这个表来计算GF域乘法，仅此而已).

表gf_exp的冗余（实际只需要256，但是重复了一遍）是为了简化乘法。这样我们就不用保证gf_log[x]和gf_log[y]会超出表的范围。

实现对数表的另一个好处是可以使用幂的差来定义除法。在下面的代码里，加上255是为了保证差不是负数。

Python注记：raise语句抛出一个异常从而终止gf_div函数的执行。

3.4 指数运算和逆运算

对数表的方法同时还可以简化并加速指数运算和逆运算：

继续介绍RS码之前，我们需要定义一些伽罗华域多项式（系数属于伽罗华域）的操作。这可能会带来一点混淆，因为伽罗华域的元素本身也是多项式（译注：是系数仅为0、1的多项式）。我的建议是不要想太多。更混乱的是，x也被用来当作占位符（多项式里的未知数）。这个x和前面提到的多项式的x没有任何关系，因此别把它们混起来。
前面给出的伽罗华域元素的二进制表示发在这里用起来会很罗嗦，因此我换成十六进制。

在Python里，多项式可以按x的幂递减的list来表示，list中的元素是对于项的系数，从而上述多项式变成了[0x01, 0x0f, 0x36, 0x78, 0x40]。（实现中也可以用反过来的顺序，各有优劣。）
第一个函数将一个多项式和一个标量相乘：

Python程序员注意：这个函数不是用Pythonic的方式实现的，它可以用列表推导式(list comprehension)更优雅地实现（译注：指的是可以用return [gf_mul(i, x) for i in p] 来实现）。但是我限制使用这些语言特性以便它可以更方便地被转换成其他语言。

这个函数将两个多项式"加"起来（照旧使用异或操作）

下一个函数将两个多项式乘起来：

最后，我们需要对一个多项式求值，给定某个x值，求出其标量结果。我们引入秦九韶算法(Horner Scheme, 霍纳算法，中国人很牛逼有没有!)来避免计算x的n次幂：

还剩一个相对复杂的多项式除法没有讲到，留待下一节与RS码一块讲。

好了，背景知识都介绍完了，我们可以开始看看RS码了。 *译注吐槽：终于进入重点了。

前面费了这么大的篇幅介绍有限域和多项式，是因为它们是纠错编码技术的基础。通过有限域和多项式的算法，我们给数据添加了一种结构。尽管信息不变，但是数据的结构化允许我们通过定义其上的规则操作数据，这种独立于数据的结构让我们可以通过它来恢复损坏的数据。

BCH编码乃至其它大多数的纠错码编码原则是：采用有限的字典(limited dictionary)存储差异最大的信息元，越长的信息元差异往往越大。在上述RS编码方式中，我们通过将RS码后缀在原信息码后面的方式，加长了原码长；而RS码基本是独一无二的，通过巧妙的算法，可以用RS码来推断原信息。
通俗的讲，类比加密的过程，生成多项式(generator polynomial)就是我们编码用的字典，而用它除原信息多项式的运算就是我们加密（RS编码）的过程。

RS码使用类似BCH码的生成多项式，将 (x - α^n) 乘起来。例如：

下面这个函数计算对于给定数量nsym个校验符号的RS码需要的生成多项式：

这个函数不是很高效，因为它在每次循环中陆续分配了更大的数组给g；但是在实际应用中它并不是瓶颈，优化癖读者有兴趣的话可以重写它，让它只给g分配一次。

现成的多项式除法算法中，最简单的是类似整数除法的算法。下面的例子展示了数据 12 34 56 （注记：这是16进制表示的）是如何被编码的：

余数和原数据连起来得到编码后的数据 12 34 56 37 e6 78 d9。这种整数除法由于算法实现中需要用的很多的规约循环导致算法效率低下。是一种更高效的算法。下面的代码是该算法对GF(2^p)多项式的一个扩展实现：

# 余数就是 RS 码! 后缀到原信息之后形成全部编码

简单吧！事实上，RS编码流程中，最后的编码是最简单的步骤，它只是一个多项式除法运算。而解码才是RS码中最难的步骤，因为根据你需要的不同，你能找到很多种不同的算法来实现。（译注：选择恐惧症怕怕！！！）解码的部分我们以后再讲。将之前的多项式综合除法的代码和上面的编码函数内联在一起，得到的下面的代码就是在很多RS编码软件库中你将看到的样子：

#RS码只用到余数, 所以我们用原信息覆盖商得到完整编码.

下面这个例子演示了编码函数如何对第一节的样例QR码中的数据进行编码。它计算出的结果中的第二行（译注：输出的第二行）与样例QR码中解码出来的纠错码相符

RS解码是从可能损毁的经过RS编码处理的信息中还原信息的过程。
尽管RS编码的过程是不变的，但是却有多种解码方法，相应的就有多种解码算法。
RS解码流程大致可以分为5个步骤：

1. 计算伴随式(syndromes polynomial). 这个方法需要我们通过Berlekamp-Massey等算法分析哪些字符是错误的，或者快速判断输入的信息是否完全损坏。
2. 由前两式计算错误判别式(evaluator polynomial). 判断有多少字符被篡改的必要步骤。
3. 由前三式计算错误等级式(magnitude polynomial). 这个式子保存了有哪些值需要从原信息中减去，所以也叫损毁式。换个角度讲，在这一步我们提取错误的信息保存到这个式子中。
4. 修复输入信息. 通过将原输入信息中的错误信息减去来完成修复。
   

（译注：这个要怎么翻译啊。。Syndrome是症状的意思，这里的确也是在计算收到的RS码码字的症状，从而判断是否接受到了错误的码字。）（译注：后来看了各种文档以后，得知一般都翻译为“伴随式”）
RS码的译码操作需要多个步骤。第一个步骤就是计算数据的伴随式。把数据当成一个多项式，使用x = α^0, α^1, α^2, ..., α^n对其求值（译注：得到n个伴随式的值）。因为这些x值使得生成多项式的值为0，因此如果读取到的数据没有损坏，结果应当是0。如果不是，这些伴随式里就包含了完成纠错所必需的信息。计算伴随式的实现很简单：

'''给定原信息和纠错标记数，计算伴随式 从数学角度看，这个过程就是一个傅里叶变换 (Chien搜索刚好相反).

继续上面的例子，我们可以看到（编码后的）数据的伴随式的确都是0；而引入一个错误以后就会得到非零伴随式。

下面的代码用来自动检查信息是否有误：

收到的数据 r(x) 是由编码后的数据（RS码的码字） c(x) 和错误 e(x) 组合得到的：
记v=nsym由于c(x)在α^0, α^1, α^2, ..., α^(v-1)都是生成多项式的根（去看生成多项式的定义就知道了，注意+实际上也是-），而c(x)能够表示为 q(x) * g(x) （不明白的话可以参看2.1节的译注），所以这里对c(x)求值的结果必然都是0。
如果对r(x)的求值都是0，说明e(x)也都是0，说明要么是没问题，要么就是错到根本发现不出来（正好是另一个码字）。如果r(x)不等于0，那么伴随式S正好就是所有e(x)的值：
如果错误的码字个数不超过v/2，通过S是可以还原信息的。

如果错误的位置是已知的（译注：某些信道可以预知，比如BEC信道，wiki这么说的，我也不知道是啥；不过QR码是另一个例子），纠正它是最简单的。这被称为消除纠正。对于每一个添加的纠错码，都可以纠正一个消除（译注：这里应该是说，添加的n个纠错码能够保证纠正n个消除码字）。如果错误位置未知，那么对于一个错误，需要2个错误校验符号。这在实际应用中非常有用，比如QR码的某些位置被覆盖或被剪掉什么的。扫描器很难知道发生了什么，所以不是所有的QR码扫描器都能纠正消除。
有了伴随式，接下来计算定位式：

最后，Forney算法实现第4步，下面的函数包含了该算法，实现纠正消除：

# 更直白的Forney算法实现： # 纠正误码! (纠错码也会被修正!) # (这里并不是Forney 算法, 只是直接套用了解码结果)

Python注记：这个函数使用[::-1]来反转列表元素的顺序。

译注：这个算法我没去看，有兴趣的读者可以看本文提到的另一篇讲解。

更可能的情况是未知位置的错误，所以第一步是找出它们。Berlekamp-Massey算法（通常简称为BM算法）用来计算错误定位多项式。然后我们只需要计算这个（错误定位）多项式的零点（译注：应该就是指多项式的根），这标志了错误的位置。

old_loc = [1] # BM 是一个迭代算法，需要对比新旧值(Sigma)来判断哪些变量需要更新。 # 而且同时还能优化效率: 我们只计算第K项的多项式乘法. 避免套嵌循环. # 查看结果是否正确, 或者错误太多无法修复

接下来，我们用一种简单直接的试验方法，通过这个定位式来定位多项式中的0，进而定位错误位置。代码如下：

译注：这个算法我也没细看，大体上，它用到了牛顿恒等式（根据4.3.3计算的伴随式）来生成错误定位多项式，然后求值得到错误的位置。更详细一点的信息可参考

这样的方法效率不高，Chien搜索是一种更高效的算法。<div color="white"（译注：英文原作者在此留了个坑，这不是我的风格，以后找到了补上！）</div>
下面是一个纠正了编码后数据中3个错误的例子：

4.3.5 消除和错误纠正

为了能够纠正错误和消除，我们需要让已知的消除不影响查找错误位置。这可以通过计算Forney syndrome来实现，如下所示：

这是实现一个全功能的错误/消除纠正RS解码器所需的最后一个片段。如果想进一步深究，原作者推荐了一本书，《》

下面的例子展示了如何使用上文中的代码进行编码和解码：

译注："Bobmath"将上述代码整合以后提交到了pypi，包名叫reedsolo，可以在找到。稍微要注意的一点是，上述的所有代码实际上是针对GF(256)上面的RS码实现的，且使用了固定的生成多项式，所以并不是完全通用。