java - Reed-Solomon 的第一个 ECC 是否总是与 xor 相同？

Question

我目前正在与 reed-solomon 合作。据我所知，第一个纠错码总是与对数据字进行异或运算相同，因为范德蒙矩阵的第一行始终为 1 并且伽罗华域中的元素相加等同于异或运算。

现在我尝试使用 ReedSolomonEncoder 的 Zxing 3.3.0 实现来获取一些代码字。请参阅以下 Java list :

ReedSolomonEncoder rs = new ReedSolomonEncoder(GenericGF.QR_CODE_FIELD_256);

int[] codeword = {72,87,0,0};

rs.encode(codeword, 2);
System.out.println("Ecc for " + codeword[0] + " and " + codeword[1]);
System.out.println("XOR: " + (72^87));
System.out.println("RS #1: " + codeword[2]); // Shouldn't this be 31 too?
System.out.println("RS #2: " + codeword[3]);

给出以下输出:

Ecc for 72 and 87
XOR: 31
RS #1: 28
RS #2: 3

有两种可能:

1. 我对 Reed-Solomon 有误解
2. 我以错误的方式使用了实现(因为 javadoc 写得不好)

或者这是一个错误，我不相信。

Answer 1

它是编码消息的异或的第一个综合症，并且仅当生成多项式的形式为 (x+1) (x+α) (x+α^2) ... 时。在这种情况下，“第一连续根”为1。对于其他实现，“第一连续根”为α，生成多项式为(x+α) (x+α^2) (x+α^3) ……生成多项式的选择还有其他变体，例如 GF(256) 中的 (x+a^127)(x+a^128) 对于自倒数多项式，1x^2 + ??x + 1。

GF(256) 在这种情况下基于 9 位多项式 x^8+x^4+x^3+x^2+1 或十六进制 11d 。 α 是原语，在这种情况下 α = x+0 == hex 02。

生成多项式为(1x + 1) (1x + 2) = 1x^2 + 3x + 2。编码过程可以形象化为长除法，如下图十六进制所示。消息乘以 x^2(用两个零填充)为两个奇偶校验字节留出空间:

               48 8f
        ------------
1  3  2 |48 57 00 00
         48 d8 90
         --------
            8f 90 00
            8f 8c 03
            --------
               1c 03   remainder

余数是从填充的消息中减去的，但是加减都是互斥的或者对于GF(256)，所以编码后的消息变成了

48 57 1c 03

与您得到的结果相匹配(十六进制 1c = 十进制 28)。

解码时，在这种情况下，syndrome[0] 是消息中所有字节的异或。证候也可以形象化为长除法(证候计算不使用padding):

        syndrome 0:                 syndrome 1:

          48 09 03                    48 c7 8f
      ------------                ------------
 1  1 |48 57 1c 03           1  2 |48 57 1c 03
       48 48                       48 90
       -----                       -----
          1f 1c                       c7 1c
          1f 1f                       c7 93
          -----                       -----
             03 03                       8f 03
             03 03                       8f 03
             -----                       -----
                00                          00

通过将 57 更改为 56 创建错误值 01:

          48 1e 02                    48 c6 8d
      ------------                ------------
 1  1 |48 56 1c 03           1  2 |48 56 1c 03
       48 48                       48 90
       -----                       -----
          1e 1c                       c6 1c
          1e 1e                       c6 91
          -----                       -----
             02 03                       8d 03
             02 02                       8d 07
             -----                       -----
                01                          04