Galois Reed Solomon

Question

I work on a project about cryptosystem using Reed Solomon codes and it is using implementation of Galois package on Python. As I know, Reed Solomon codes based and work on polynomial representation but using the galois package, it can build the generator matrix on integer representation and it complete the standard form of generator matrix because it complete G=[I|A] which is I is a identity matrix. I wanna ask how the number on row and column matrix became a integer value instead of polynomial Reed Solomon? Thank you

I want to know the basic of integer representation on generator matrix Reed Solomon codes. How is the theory about it? why it doesn’t on polynomial?

Answer 1

There are two types of Reed Solomon code, which Wikipedia refers to as "original view" and "BCH view", and within each view, there are two encoding methods, "simple" encoding and "systematic" encoding.

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

G = [I|A] corresponds to original view, systematic encoding, however G=[I|B] would look similar, but would correspond to BCH view, systematic encoding.

Looking at the example from:

https://galois.readthedocs.io/en/v0.3.5/api/galois.ReedSolomon

update - link has changed:

https://galois.readthedocs.io/en/v0.3.6/api/galois.ReedSolomon

It is using BCH view, systematic encoding. Parameters and example encode that matches the linked example (shown in hex). Generator polynomial is g(x). Note for GF(2^n), both + and - are XOR.

GF(2^4):         x^4 + x + 1
g(x):            (x-2)(x-4)(x-8)(x-3)(x-6)(x-c) =
                 x^6 + 7 x^5 + 9 x^4 + 3 x^3 + c x^2 + a x + c
msg:             e 0 1 9 9 f 1 c 7 = 
                 e x^8 + 0 x^7 + 1 x^6 + 9 x^5 + 9 x^4 + f x^3 + 1 x^2 + c x + 7
encoded msg:     e 0 1 9 9 f 1 c 7 7 a 6 7 7 b

update - data changed in example

encoded msg:     f 0 4 c 9 9 6 d 1 e 3 a 6 b d

In this case, the parity values = (msg * x^6) mod g(x), and are appended to the message. Since this is a linear mapping, the encode operation

(msg * x^6) + ((msg * x^6) % g(x))

can be converted into a matrix multiply by G, where G = [I|B]. In hex:

    |1 0 0 0 0 0 0 0 0 a 3 5 d 1 8|
    |0 1 0 0 0 0 0 0 0 f 1 d 7 5 d|
    |0 0 1 0 0 0 0 0 0 b b d 3 a 7|
    |0 0 0 1 0 0 0 0 0 3 2 3 8 4 7|
G = |0 0 0 0 1 0 0 0 0 3 a a 6 f 9|
    |0 0 0 0 0 1 0 0 0 5 b 1 5 f b|
    |0 0 0 0 0 0 1 0 0 2 b a 7 e 8|
    |0 0 0 0 0 0 0 1 0 f 9 5 8 f 2|
    |0 0 0 0 0 0 0 0 1 7 9 3 c a c|  (last row is the same as g(x))

This matches G as shown here:

https://galois.readthedocs.io/en/v0.3.5/api/galois.ReedSolomon.G

update - link has changed:

https://galois.readthedocs.io/en/v0.3.6/api/galois.ReedSolomon.G/#examples