Is the first ECC of Reed-Solomon always the same as xor?

Question

I am working with reed-solomon at the moment. As far, as I understand, the first error correction code is always the same as xor'ing the data words, because the first row of the vandermonde matrix is always 1 and the addition of elements in a galois field is equivalent to xor.

Now I tried to get some code words using the Zxing 3.3.0 implementation of ReedSolomonEncoder. See the following listing in 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]);

Which gives the following output:

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

There are two possibilities:

1. I have a misconception of Reed-Solomon
2. I am using the implementation in a wrong way (as the javadoc is poorly written)

Or this is a bug, which I somehow do not believe.

Answer 1

It's the first syndrome that is the exclusive or of the encoded message, and only if the generator polynomial is of the form (x+1) (x+α) (x+α^2) ... . In this case, the "first consecutive root" is 1. For other implementations, the "first consecutive root" is α, and the generator polynomial is (x+α) (x+α^2) (x+α^3) ... . There are other variations for generator polynomial choice, such as (x+a^127)(x+a^128) in GF(256) for a self reciprocal polynomial, 1x^2 + ??x + 1.

GF(256) in this case is based on the 9 bit polynomial x^8+x^4+x^3+x^2+1 or hex 11d . α is the primitive, and in this case α = x+0 == hex 02.

The generator polynomial is (1x + 1) (1x + 2) = 1x^2 + 3x + 2. The encode process can be visualized as long division, as shown below in hex. The message is multiplied by x^2 (padded with two zeroes) to leave room for the two parity bytes:

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

The remainder is subtracted from the padded message, but both add and subtract are exclusive or for GF(256), so the encoded messages becomes

48 57 1c 03

which matches the result you're getting (hex 1c = decimal 28).

When decoding, in this case, syndrome[0] is the xor of all the bytes in the message. The syndromes can also be visualized as long division (no padding is used for syndrome calculation):

        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

Create a error value of 01 by changing 57 to 56:

          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