# Referring to elements of a polynomial ring as integers.

Suppose I create a polynomial ring:

F.<a> = GF(2^4)
R.<x> = PolynomialRing(F)


The syntax above is slightly incorrect, I couldn't figure out how to preserve the brackets around the 'a' and 'x'.

For the work I'm doing the references typically refer to elements of the ring in 4 different manners (within the same reference). An example of this is the BBC white paper, "Reed-Solomon Error Correction" by C. K. P. Clarke.

They use index form:

a^11


They use polynomial form:

a^3 + a^2 + a


They use binary form:

1110


They use decimal form:

14


I would like to map what they call decimal form to the polynomial form, because it's very convenient. For instance in the previously mentioned paper they encode a message: x^10 + 2x^9 + 3x^9 + ... 10*x + 11.

In sagemath this would be:

x^10 + a*x^9 + a^4*x^8 + ... a^9*x + a^7


The decimal form is very helpful for me. My eventual goal is to use sagemath to implement a Reed-Solomon encoder/decoder, and write code that parses that implementation and creates System Verilog code that gets implemented in an ASIC (application specific integrated circuit)

edit retag close merge delete

Sort by » oldest newest most voted

First, you can transform a decimal number into a string representing its binary expansion as follows:

sage: n = 14
sage: b = n.bits()
sage: b
[0, 1, 1, 1]


Then you can get the indices of the letters by enumerating this iterator:

sage: list(enumerate(b))
[(0, 0), (1, 1), (2, 1), (3, 1)]


Putting everything together, you can construct your element of F:

sage: sum(a^i for i,j in enumerate(n.bits()) if j)
a^3 + a^2 + a


Note that you can go the other way easily:

sage: c = a^3 + a^2 + a
sage: c.integer_representation()
14


Regarding the index, since F^* is multiplicatively cyclic with a as a generator, you can define and use the following dictionary:

sage: index = {a^i:i for i in range(15)}
sage: index[a^3 + a^2 + a]
11


Now, regarding polynomials, you can first construct the integer polynomial to represent them:

sage: D.<X> = PolynomialRing(ZZ)


Then, you can construct your example polynomial as follows:

sage: P = sum((11-i)*X^i for i in range(11))
sage: P
X^10 + 2*X^9 + 3*X^8 + 4*X^7 + 5*X^6 + 6*X^5 + 7*X^4 + 8*X^3 + 9*X^2 + 10*X + 11


A nice way to access coefficients of a polynomial is by using a dictionary that maps powers to coefficients, so that at the end, you get:

sage: sum([sum(a^i for i,j in enumerate(ZZ(coeff).bits()) if j) * x^power for power,coeff in P.dict().items()])
x^10 + a*x^9 + (a + 1)*x^8 + a^2*x^7 + (a^2 + 1)*x^6 + (a^2 + a)*x^5 + (a^2 + a + 1)*x^4 + a^3*x^3 + (a^3 + 1)*x^2 + (a^3 + a)*x + a^3 + a + 1


If you want the index-ed form, as an integer polynomial:

sage: sum(index[sum(a^i for i,j in enumerate(ZZ(coeff).bits()) if j)] * X^power for power,coeff in P.dict().items())
X^9 + 4*X^8 + 2*X^7 + 8*X^6 + 5*X^5 + 10*X^4 + 3*X^3 + 14*X^2 + 9*X + 7


All that said, note that Reed-Solomon codes ar already implemented in Sage https://doc.sagemath.org/html/en/refe...

more

Instead of n.binary() you can use n.bits() which gives the bits as a list, already in the correct order (so no need to reverse) and as integers (so no need to compare strings).

( 2021-03-21 14:26:42 +0200 )edit

This is indeed simpler, i updated my answer, thanks !

( 2021-03-21 17:23:33 +0200 )edit

Thank you! I do know that there are already built in Reed-Solomon codes, but I'm actually using the package to build codes for use on an integrated circuit. To make things fast on the chip (low latency) I'm going to be translating some of the intermediate results into either lookup tables or boolean logic in the form of System Verilog code.

The GF(2^4) is just a nice example that I often use with co-workers to explain the characteristics of Reed-Solomon codes.

( 2021-03-22 00:11:46 +0200 )edit