4

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

现在我尝试使用 ReedSolomonEncoder 的 Zxing 3.3.0 实现来获取一些代码字。请参阅 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 写得不好）

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

4

1 回答 1

4

这是编码消息的异或的第一个综合症，并且仅当生成多项式的形式为 (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）。

解码时，在这种情况下，综合症 [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
于 2017-05-30T03:16:03.337 回答