3

I have to decode some reed solomon codes. I tried to use open source libraries for this but I'm not sure how to apply them to my specific problem.

For example this lib: https://github.com/zxing/zxing/blob/master/core/src/main/java/com/google/zxing/common/reedsolomon/GenericGF.java

Seems to support a lot of codes with a generator function like this:

x^12 + x^6 + x^5 + x^3 + 1
x^10 + x^3 + 1

But I need to support a function with coefficients like this:

2x^10 + 4x^3 + 8

Is my assumption correct that this is not supported by the library? Does anyone know a library that supports this?

Bomgar
  • 553
  • 1
  • 3
  • 13

2 Answers2

2

Reed-Solomon is formally defined using symbols over any finite field. A popular choice is GF(2^b) for some bit-length b; for example, if the symbols are bytes, you would use GF(2^8). GF(2^8) is implemented using polynomials with coefficients over GF(2), modulo a generator. zxing's GenericGF only works for GF(2^b) fields, in which the polynomial coefficients are all either 0 or 1. Your coefficients are not binary, which suggests that you might be operating over GF(p^b) for some other prime p; in this case, zxing will probably not work for you.

You could try a more generic implementation from a computer algebra system; for example, SageMath provides generalized Reed-Solomon codes: https://doc.sagemath.org/html/en/reference/coding/sage/coding/grs_code.html

Side-note: confusingly, there's another definition of "generator polynomial" in Reed-Solomon: in the BCH scheme, the generator is a polynomial whose coefficients are field elements (e.g. GF(p^b)) and whose value is typically g(x) = (x - a)(x - a^2)(x - a^3)... for some primitive element a of the field. I presume this is not the generator you're referring to, as the provided polynomial is not of the right form.

nneonneo
  • 171,345
  • 36
  • 312
  • 383
  • For Reed Solomon's original scheme, the generator polynomial is based on the message to be encoded. "Simple" encoding treats the message as coefficients to a generator polynomial. "Systematic" encoding treats the message as the result of a generator polynomial evaluated over a set of data points. Lagrange interpolation is used to create the generator polynomial. In both cases, only the set of data points is known to encoder and decoder. The decoder has to determine the generator polynomial. This is explained in the Wiki article. – rcgldr Aug 17 '23 at 15:55
2

It appears you are trying to use the "original view" version of Reed Solomon, while the github code is based on the more commonly used "BCH view" of Reed Solomon, which are two different encoding schemes both called Reed Solomon as explained in the Wiki article.

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

As explained in the Wiki article, with the original view, the message itself is treated as either coefficients of a generator polynomial or as evaluated data points. In the second case, Lagrange interpolation is used to create a generator polynomial based on the evaluated data points for systematic encoding (the message itself is the first part of an encoded message).

You will need an original view library. I have some example original view code, but in C, not Java.

rcgldr
  • 27,407
  • 3
  • 36
  • 61