Ask Your Question
1

Issues with Reed-Solomon encoder

asked 2021-01-20 15:44:24 +0100

joakim_uhlin gravatar image

I am trying out the Reed-Solomon encoder in Sage and I have found it to exhibit a curious behavior. I first create an encoder for a $(7,3)$-Reed Solomon code as follows

sage: F.<a> = GF(8,name='a',modulus=x^3+x+1)
....: Fx.<x> = F[]
....: C = codes.ReedSolomonCode(F, 7, 3)
....: E = C.encoder("EvaluationPolynomial")

Now I can write

sage: E.encode(x)
(1, a, a^2, a + 1, a^2 + a, a^2 + a + 1, a^2 + 1)

Or

sage: E.encode(a*x^0+a^2*x+x^2)
(a^2 + a + 1, a^2 + 1, a, 0, a^2 + 1, 0, a^2 + a + 1)

But I get when I write the following

sage: E.encode(a)

I get the following error

"AttributeError: 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement' object has no attribute 'degree'"

If I instead write

sage: E.encode(a*x^0)

Everything works as intended. Is this how it is supposed to work? Does one always need an "$x$" to be part of a term, even when one actually has a constant term? Is there a better way to do it?

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
1

answered 2021-01-20 16:08:04 +0100

FrédéricC gravatar image

updated 2021-01-20 16:08:13 +0100

You can use parent(a) to see that a is not a polynomial, hence the error message. You need to tell sage that you want the image of a in the polynomial ring. You can also use Fx(a) for doing that.

edit flag offensive delete link more

Comments

FrédéricC's answer works for what I wanted to do! One can just write E.encode(Fx(a)) instead of what I initially did. I tried to look for a way to avoid needing to use Fx however. The following works

F = GF(8,name='a',modulus=x^3+x+1)
Fx.<x> = F[]
Fa.<a> = Fx

but I still get issues if I write E.encode(1) or E.encode(0). There is a NotImplementedError in this case. If one writes E.encode(Fx(1)) or E.encode(Fx(0)), this is circumvented.

joakim_uhlin gravatar imagejoakim_uhlin ( 2021-01-21 10:31:32 +0100 )edit
1

Note about zero and one:

  • Fx.zero() directly provides the zero element of Fx while Fx(0) uses the integer zero and then turns it into an element of Fx.
  • Likewise, Fx.one() directly provides the one element of Fx while Fx(1) turns the integer one into an element of Fx.

So one can use E.encode(Fx.one()) and E.encode(Fx.zero()).

One could name the polynomials 0, 1 and a for easy access, e.g.

p0 = Fx.zero()
p1 = Fx.one()
pa = Fx(a)

and then use e.g. E.encode(pa) instead of E.encode(Fx(a)).

slelievre gravatar imageslelievre ( 2021-01-21 12:01:59 +0100 )edit

I realized the code I suggested using in the above comment does not work - it seems to set $a=x$, which is not what I intended.

joakim_uhlin gravatar imagejoakim_uhlin ( 2021-01-21 17:03:57 +0100 )edit
0

answered 2021-01-21 18:37:15 +0100

joakim_uhlin gravatar image

Based on the help I got from FrédéricC and slelievre, I managed to create the following encoder-decoder:

F.<a> = GF(8,name='a',modulus=x^3+x+1)
Fx.<x> = F[]
C = codes.ReedSolomonCode(F, 7, 3)
E = C.encoder('EvaluationPolynomial')
M = E.message_space()
D = C.decoder('BerlekampWelch')

pa = Fx(a)
p0 = Fx.zero()
p1 = Fx.one()

m = M.random_element()
n = E.encode(m)
o = D.decode_to_message(n);
print(m)
print(o)
edit flag offensive delete link more

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-01-20 15:44:24 +0100

Seen: 41 times

Last updated: Jan 21