Ask Your Question
2

Referring to elements of a polynomial ring as integers.

asked 2021-03-21 10:16:30 +0100

jderyck gravatar image

updated 2021-03-21 12:22:06 +0100

tmonteil gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2021-03-21 12:08:07 +0100

tmonteil gravatar image

updated 2021-03-21 17:23:06 +0100

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...

edit flag offensive delete link more

Comments

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).

slelievre gravatar imageslelievre ( 2021-03-21 14:26:42 +0100 )edit

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

tmonteil gravatar imagetmonteil ( 2021-03-21 17:23:33 +0100 )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.

jderyck gravatar imagejderyck ( 2021-03-22 00:11:46 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-03-21 10:16:30 +0100

Seen: 285 times

Last updated: Mar 21 '21