data-storage

Reed-Solomon码：从入门到放弃 Part 3

其实，对于一般应用场景来说，GF(2^8)已经足够了，因为GF大小为256，刚好能支持1个字节的0~255，而且不需要对输入数据和输出数据进行额外的处理。但是，难免会遇上各种各样奇怪的需求嘛，所以干脆一般情况也随便整整。

目录#

GF(2^p)#

本原多项式#

若要创建GF(2^p)，首先需要的是本原多项式（primitive polynomial）的取值。它在第p+1个bit的取值为1（从右数起，相当于将1左移p个bit），如之前在GF(2^8)所使用的0x11d，它的取值必须大于256（即0x100）。

当然，本原多项式的搜索是构建GF(2^p)的关键，然而它和实数域上的素数并没有太大的关系，毕竟人家是属于GF的嘛。因此，素数不一定可以当本原多项式，本原多项式也不一定是素数。最简单的，就是穷举2^p到2^(p+1)间的奇数，若能够构造乘法表，没有数值冲突，就可以了。

当然，出于效率考虑，个人用c++重写了一遍，检查一个数是否为本原多项式的代码如下（p就是GF括号里面的那个上标啦）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool check_prim_poly(int p, int prim_poly) {
    int n_size = (1 << p) - 1;
    if (prim_poly <= n_size + 1)
        return false;
    char* seen = new char[n_size + 1];
    memset(seen, 0, n_size + 1);
    bool conflict = false;
    int x = 1;
    for (int j = 0; j < n_size; j++) {
        x <<= 1;
        if (x & (n_size + 1)) x ^= prim_poly;
        if (x > n_size || seen[x]) {
            conflict = true;
            break;
        }
        seen[x] = 1;
    }
    delete[] seen;
    return !conflict;
}

数据的取值范围#

在系数p改变的时候，直观影响最大的就是数据的取值范围。在GF(2^8)中，数据范围是0~255，而GF(2^7)中，则为0~127，相反，GF(2^9)则为0~511。前文中，数据统一用List[int]表示也是这个原因，因为在GF(2^9)这种情况下，每个输入数据的有效范围是9 bit（即输入数据的取值范围为0x0~0x1ff），超过了8 bit的表示范围。相反，GF(2^7)无法处理数据大于127的情况，即无法编码0x80~0xff间数据。

值得注意的一点是，尽管在使用GF(2^9)时，你可以直接用8 bit的数据作为输入，但是生成的纠错码就不会遵守这个约束：放飞自我的纠错码依旧会生成在0x100~0x1ff范围内的值。至于怎么把它再转成byte数组，那就是自己思考的事情了。当然，RS码可不管这个，它只要能够正确编码、解码，就足够了。

其次不太重要的就是可编码的数据段长度，GF(2^8)要求数据+校验码的长度不超过255，GF(2^9)则是要求长度不超过511。当然，由于GF(2^9)中每个输入都是9 bit，因此理论最大支持floor(511*9/8)=574字节的数据。为了不混淆，在这里用block记为GF(2^p)的最大可编码长度2^p-1。若校验码长度为k，则实际的有效数据长度为2^p-1-k。

乘法表#

GF(2^p)跟GF(2^8)类似，在建表时规则不变，一样可以通过位移+与本原多项式异或得到，只不过表的大小从GF(2^8)的256项变为GF(2^p)的2^p项，表的唯一对应关系在$\alpha^{2^p-1}=1$时中断而已。

根据查表执行的GF运算法则，则跟GF(2^8)的情况是一致的。

数据padding#

在使用RS码做数据冗余的使用情景下，输入和输出都是8 bit的字节流。但在GF(2^p)的RS码中，输入数据，或者说，作为生成纠错码的多项式的系数，都是p bit大小的，因此，必须对其进行必要的合并和拆分操作。

如在p=9的情况下，对4B长度的数据de ad be ef，可以进行如下拆分，以最大化利用RS码的数据范围：

11011110 10101101 10111110 11101111 ...拆为：
110111101 010110110 111110111 01111...

（即：1bd 0b6 1f7 ...）

带padding的buffer操作#

在GF(2^8)中，最简单的操作分为以下几步：

  1. 从数据中读取一个分段到buffer（byte数组）中
  2. 直接对buffer计算RS码，附加到buffer的最后
  3. 直接将buffer写入到其他byte数据流中

而对非2^8的情况，则是：

  1. 从数据中读取数据到buffer_in（byte数组）中
  2. 对buffer_in（byte数组）进行拆分，拆分后的系数存到coef_in中（int数组）
  3. 对coef_in中的数据计算RS码，将数据及其校验码写入到coef_out中
  4. 对coef_out中的数据，重新组合回byte数组，写入到buffer_out（byte数组）中
  5. 对buffer_out中的数据，写入到数据流中

单个多项式系数的padding#

一步步来解决，首先是第2点的拆分：优先将数据划分为p与8的最小公倍数的bit。在p=9时最小公倍数为72 bit，即9B大小，在p=7时则为7B，其他特殊的情况，如p=4时依然是1B，p=16是2B。在这里，把拆分出来的完整分段，记为segment。segment的长度不长（通常情况是1~10+B），而一个block包含若干个segment。

对于一个100B的数据来说，可以划分为9B*11+1B，即11个完整的分段（Segment）和最后的1B。因此，需要处理两种情况：

  1. 分段是完整的
  2. 分段是不完整的

对前11个分段，只要把9B的数据拆开分别作为8个多项式的系数即可。

对最后一段（可能不完整）的数据，需要将其对齐到p的整数倍，这里我采用的方法是：对首个填充的bit填0，后续的bit填1，一种简单的填充方式，起个奇怪的名字吧，就叫“首0尾1”填充方法。
举个例子，对3 bit的数据填充为xxx0 1111 1。而上面例子中最后的一个单独的byte，则对应xxxx xxxx 0，然后将其作为一个多项式系数，传入到RS码的编码数据中。

1
2
3
          | Segment #0                      | Segment #1 ~ #10 | Segment #11
buffer_in | de ad be ef 00 11 22 33 44      | ......           | cc
coef_in   | 1bd 0b6 1f7 0f0 002 048 119 144 | ......           | 198

由此，得到的完整的多项式系数有8*11+1=89个。假设生成的校验码有2个，直接生成校验码后的系数长度为89+2=91。细心的读者可能会注意到，实际的数据量91 coef*9 bit/coef=819 bit并不能被8整除，不能完整写入到byte数组里面。接下来要解决的就是这个头疼的问题了。

多个多项式系数的padding#

这里我使用的方法是对coef_in继续进行数据填充。如在上面的198后面继续填充5个9个bit都为1（0x1ff）的系数，最后得到的是96 coef*9 bit/coef=864 bit=108 Byte，很好，问题解决。示意图如下（中括号中的01e 005是生成的校验码，而大括号里面的则是纯填充的数据）：

1
2
3
4
           | Segment #0 ~ #10 | Segment #11
coef_in    | ......           | 198 {1ff 1ff 1ff 1ff 1ff}
coef_out   | ......           | 198 {1ff 1ff 1ff 1ff 1ff} [01e 005]
buffer_out | ......           | cc 7f ff ff ff ff fc 3c 05

这里，我们可以对比另外一种填充方法：对buffer_out进行填充，如下所示。0x198 0x01e 0x005 = 1100 1100 0000 0111 1000 0000 101，按照“首0尾1”，对它填充到4字节，后2字节为：1000 0000 101[0 1111]（中括号里面的就是填充的bit）

1
2
3
           | Segment #0 ~ #10 | Segment #11
coef_out   | ......           | 198 [01e 005]
buffer_out | ......           | cc 07 80 af

这种方法很简单，但是缺点也暴露得很明显：最后填充的几个bit，是不受RS码保护的。若在填充的数据中发生错误，要修复起来就比在coef_in填充要难多了。所以这方法在实现之前就被我pass掉了。

而在coef_in填充的时候，实际上还有挺多小细节需要关注到的。比如：

  1. p特别小，而校验码太长的极端情况：由于实际的有效数据长度太小，导致填充到一半就已经凑够一整个编码block了。这种情况下的解决方案：先对完整的block进行编码，再对编码后为对齐8的倍数所需要的填充bit数进行重新计算，重新进行填充。
  2. 跟AES（一种加密算法）的pad类似，在原始数据已经是8的倍数的时候，依然需要按这规则再次填充到8的整数倍，否则规则的不一致会导致在解码过程中移除填充bit的时候发生冲突，带来灾难性后果。
  3. 其实没啥了，填充的长度越短越好。

填充完后，coef_out的数据长度永远是8的倍数，因此可以直接转为byte数组，再写入到下游的数据流中自然也是水到渠成的事情了。可喜可贺可喜可贺。

解码的unpadding#

过程其实非常直观，buffer_in对应编码后的字节数据，重新拆分到coef_in进行解码，解码之后将数据写入到coef_out中。然后对coef_out的数据从后往前移除bit为1的数据，直到遇到首个bit为0的数据并将其移除为止，将剩下的数据重新组合到byte数组写入到buffer_out即可。因为在进行padding操作前的数据一定是8的倍数（来自byte数组），所以还原后的数据依然是8的倍数，这里就不需要掉头发再考虑其他情况了。

后记#

研究生生活真充实，时间真的都是全靠挤出来的（指1小时工作，55分钟划水）。最后Part 4把RS码完整的c++实现代码放一放吧，番外再说说用python调用dll进行编码解码的那点破事。