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:

I have a misconception of Reed-Solomon
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.

@AdrianPetrescu I checked this. It seems, that XOR = RS#1 (xor) RS#2 always applies. — Obererpel
Okay, cool! Then the next thing I would check is if RS#1 always contains the high-order byte half of the sum, and RS#2 always contains the low-order byte half of the sum, the way it is in this example. If so, I think that's your answer - you're correct, it's just that ZXing is storing each byte separately in the output array. — Adrian Petrescu
But I want to have two correction words. The first one should be 31, the second should be 2*87 + 72 (using the operators of GF(256)) = 164 + 72 = 236 (if i did the math right) — Obererpel
@Obererpel - I updated my answer to include examples of syndrome generation via long division like method. Link to wiki article which explains syndrome generation via summation for Sj, except for this case j goes from 0 to n-k-1, so the two syndromes are S0 and S1, where S0 is the xor of the elements in the decoded message. — rcgldr

rcgldr rcgldr · Accepted Answer · 2017-05-30T03:16:03

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

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

1 Answers