Reed-Solomon的第一个ECC总是等同于异或吗？

Question

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

现在我尝试使用Zxing 3.3.0实现的ReedSolomonEncoder获取一些代码字。请参见以下Java列表：

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写得很差）

或者这是一个bug，但我不太相信。

- Obererpel

---

我在想28 + 3 = 31是否纯属巧合？ - Adrian Petrescu

@AdrianPetrescu 我已经检查过了。看起来，XOR = RS#1 (xor) RS#2 总是适用的。 - Obererpel

好的，很酷！那么我接下来要检查的是RS＃1是否始终包含总和的高位字节的一半，而RS＃2始终包含总和的低位字节的一半，就像在这个例子中一样。如果是这样，我认为这就是你的答案-你是正确的，只是ZXing将每个字节单独存储在输出数组中。 - Adrian Petrescu

但我想要有两个更正词。第一个应该是31，第二个应该是2*87 + 72（使用GF（256）的运算符）= 164 + 72 = 236（如果我算对了的话）。 - Obererpel

@Obererpel - 我更新了我的答案，包括通过长除法生成综合症的示例。链接到维基百科文章，解释了Sj的通过求和生成综合症，除了这种情况下，j从0到n-k-1，因此两个综合症是S0和S1，其中S0是解码消息中元素的异或。 - rcgldr

Answer 1

这是一个关于it技术的翻译内容。第一个综合症是编码信息的排他或，只有生成多项式为（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==十六进制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]是消息中所有字节的异或。这些综合指数也可以视为长除法（对于综合指数计算不使用任何填充）：

        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

- rcgldr