Opened 7 years ago
Closed 6 years ago
#19653 closed enhancement (fixed)
New decoders for Generalized Reed-Solomon codes
Reported by: | dlucas | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.1 |
Component: | coding theory | Keywords: | |
Cc: | jsrn | Merged in: | |
Authors: | David Lucas | Reviewers: | Julien Lavauzelle |
Report Upstream: | N/A | Work issues: | |
Branch: | f3b4b11 (Commits, GitHub, GitLab) | Commit: | f3b4b11582fd4c2e976d2e0450d0e8699be0272e |
Dependencies: | #18928, #19897 | Stopgaps: |
Description
This ticket introduces four new different decoders for GRS codes, namely:
GRSBerlekampWelchDecoder
,GRSGaoDecoder
,GRSKeyEquationSyndromeDecoder
andGRSErrorErasureDecoder
.
It requires the new structure for GRS codes introduced in ticket #18928
Change History (54)
comment:1 Changed 7 years ago by
- Branch set to u/dlucas/grs_decoders
comment:2 Changed 7 years ago by
- Commit set to 74cc281ef65d2aed2fca11dd41d6ac268ad52880
- Status changed from new to needs_review
comment:3 Changed 7 years ago by
- Commit changed from 74cc281ef65d2aed2fca11dd41d6ac268ad52880 to b03d7b5ae8f6e725a148b4fe7bcce99043e240db
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
8733405 | Some improved doc-strings and doc-tests
|
229b5cf | Some code beautification
|
fe7e9de | Sanity-checks on input for GRSEvaluationPolynomialEncoder
|
6e7013b | Small doc-string improvements in linear_code and encoder
|
0e82848 | More small docstring improvements
|
91e2e3b | Doc-string typesetting fix
|
eabe7e0 | Reworked coercion of evaluation pts and col mults and refined tests.
|
71070de | Merged with 18928 and fixed conflicts
|
9f4fb84 | Improved docstrings and doctests
|
b03d7b5 | Extra cleaning in documentation
|
comment:4 Changed 7 years ago by
I merged in #18928 latest version and did some fixes and improvements to the documentation.
comment:5 Changed 7 years ago by
- Commit changed from b03d7b5ae8f6e725a148b4fe7bcce99043e240db to 4e1a1845fdacdd3f9fe9e9adacb7c92dcc81b6cd
Branch pushed to git repo; I updated commit sha1. New commits:
4e1a184 | Merge branch 'develop' into grs_decoders
|
comment:6 Changed 7 years ago by
Updated to latest beta, still open for review.
comment:7 Changed 7 years ago by
- Commit changed from 4e1a1845fdacdd3f9fe9e9adacb7c92dcc81b6cd to ffed9486f0d2e5bf3d1a86dff8dfa9a9e33ec9dc
Branch pushed to git repo; I updated commit sha1. New commits:
ffed948 | Merge branch 'u/dlucas/grs_decoders' of git://trac.sagemath.org/sage into grs_decoders
|
comment:8 Changed 7 years ago by
Updated to latest beta, still open for review.
comment:9 Changed 7 years ago by
- Commit changed from ffed9486f0d2e5bf3d1a86dff8dfa9a9e33ec9dc to 37bb7ac8775f51d774cc9edaeeb0ba457c7f2546
Branch pushed to git repo; I updated commit sha1. New commits:
616219c | Update to latest beta
|
baa9f20 | First version of the tutorial
|
cb65314 | Update to latest beta
|
2057fee | Small fixes and improvements
|
77f0629 | Merged #19897
|
37bb7ac | Updated introductory thematic tutorial with a paragraph on decoders and message spaces
|
comment:10 Changed 7 years ago by
- Dependencies changed from #18928 to #18928, #19897
I merged #19897 in, and updated the tutorial.
It's still open for review.
comment:11 Changed 7 years ago by
- Commit changed from 37bb7ac8775f51d774cc9edaeeb0ba457c7f2546 to 4340598e5ae5e932abb87389764ccb6e06561c12
comment:12 Changed 7 years ago by
I updated this ticket to latest beta and removed a deprecated import
statement, so broken doctests won't be broken anymore.
This is still open for review.
comment:13 Changed 6 years ago by
- Commit changed from 4340598e5ae5e932abb87389764ccb6e06561c12 to b8406820e1300efdd3ef95d8e5f326c28878a568
Branch pushed to git repo; I updated commit sha1. New commits:
b840682 | Updated to 7.1beta3 and fixed conflict
|
comment:14 Changed 6 years ago by
- Milestone changed from sage-6.10 to sage-7.1
comment:15 Changed 6 years ago by
- Commit changed from b8406820e1300efdd3ef95d8e5f326c28878a568 to d70d6aa219a0472d1e254a23b6e0427f5cc7e1b2
Branch pushed to git repo; I updated commit sha1. New commits:
d70d6aa | Removed __ne__ methods
|
comment:16 Changed 6 years ago by
I removed __ne__
method in every decoder as a generic one was implemented in another ticket, so these ones are useless.
Now, for the broken doctests, I'm experiencing a weird problem: while trying to build a [10, 5, 6]-GRS code (lines 1549, 1591, 1631 and 1669) the doctesting framework (sage -t grs.py
) actually builds a [9, 5, 5]-GRS code.
Which is quite weird, because if I copy these lines in my Sage terminal, everything works perfectly...
Everything else is still on the clear, so I consider this suitable for review. I'm of course working on the above.
David
comment:17 follow-up: ↓ 18 Changed 6 years ago by
Hi,
Well, I don't know key equation decoding that much, so I didn't review all the ticket yet. But I can post my first comments so that you start modifying the code while I go further on key equation.
coding_theory.srt
- l.125: created --> create
- l.146: to build the [12, 6] GRS code --> to build a ...
- in the example which follows, you give a [6, 3] GRS code (instead of [12, 6]). As your example is quite big, I think you should put the [6, 3] everywhere.
- l.253: it seems that your decoder decodes 2 errors, whereas the [6,3] GRS minimum distance is 4. It means the standard decoder you use is not a half minimum distance one, which is quite inefficient for such a structured code. Two possibilities: either you keep this standard decoder, or you change it to Gao decoder. If you choose to change, do not forget to modify the tutorial.
- l.337: put quotes around
EvaluationVector
andC
- l.352: match --> matches
- l.375: "The default encoder for a code is always one with vector behaviour, so when we call..." To me, this sentence is strange. Maybe "always uses vectors" or "always has a standard vector space as message space".
- l.380: whose length are --> is
- l.390: remove the "then"
- l.364, 442, 446, 550: why did you write "#random" ?
- l.547: "over which has 1" sounds weird.
- l.567: "For instance, we did not mention how Sage manages bounds on codes." Does it manage them ?
- l.585: "to create you own codes" --> your
decoders_catalog.py
- l.16: broken link with
grs.GRSKeyEquationSyndromeDecoder <sage.coding.grs.GRSKeyEquationDecoder>
grs.py
- l. 1083: I dislike the function naming:
precompute
is too general. I also think your documentation is not precise enough : there are many monic polynomials vanishing on the evaluation points; your function returns the only one whose zeroes are exactly the evaluation points. - l. 1107:
G = 1
-->G = PolRing.one()
- l. 1113: Your documentation is not very clear:
- "Returns the greatest common divisor of a and b." --> your function doesn't do that
- "where d is the dimension of self.code() and k its dimension." --> I think you meant the code length for d.
- OUTPUT: a tuple of polynomials (r, s) where r is to the xgcd of a and b and s is the Bezout coefficient of a. ---> as it is written, it is not an *extended* gcd algorithm, as you don't perform the "backward step". It doesn't either return a gcd, but one of its multiples. And I think you should mention the Euclidean algorithm somewhere. Maybe something like: "the algorithm performs the classical Euclidean algorithm until a remainder has degree less than (n+k)/2, and return (r,s) such that in the last step, we have r = a*s + b*t".
- l. 1280: Don't you need to check the
input_space
also (as in GRSGaoDecoder and GRSBerlekampWelchDecoder)? - l. 1383: if
e
is the number of erasures andd
the minimum distance, then the decoding_radius is(d-1-e)//2
. - l. 1372 and after: you can remove backslashes when you wrap a line
- l.1470:
(code.base_field())(0)
-->code.base_field().zero()
. Besides, your comment:ValueError("Impossible to decode a GRS code which contains 0 amongst its evaluation points")
is a bit wrong. I would prefer: "This decoder can't be initialized with a GRS code whose evaluation points contains 0" - l. 1525 (partial xgcd): same comments as in the partial_xgcd of Gao decoder.
Julien
comment:18 in reply to: ↑ 17 Changed 6 years ago by
Awesome remarks Julien.
Just a small clarification
- l. 1083: I dislike the function naming:
precompute
is too general. I also think your documentation is not precise enough : there are many monic polynomials vanishing on the evaluation points; your function returns the only one whose zeroes are exactly the evaluation points.
To be clear: it returns the *minimal-degree* polynomial that vanishes at all the evaluation points (in the algebraic closure, that's equivalent to what you say, but perhaps not everyone would think like that).
comment:19 Changed 6 years ago by
Hello,
Thanks a lot for this thorough review work!
A general remark: at the time I wrote my thematic tutorial, there was no decoder in Sage but syndrome
and nearest_neighbor
, which both are quite slow - hence the small codes.
Now that we have fast decoders, I prefer to default to bigger codes than [6,3]-GRS in examples, just to illustrate that we are fast over not-so-small codes.
grs.py
- I changed default decoder, which is now
Gao
. - I rewrote the documentation of
precompute
, which is now called_polynomial_vanishing_at_alphas
. Maybe not the best name ever (alphas
?) but it's better thanprecompute
. By the way, it's now a private method, which I think is quite better. - I rewrote both
partial_xgcd
as you advised. I also made these private methods, which was actually written in the doc but not done in practice... - No need to check the
input_space
in__eq__
as it comes directly fromcode
. If you check the input of all my decoders, you'll see the user only providescode
, and the input space is extracted fromcode
. As the user has no direct way to influence this, it's not necessary to test it in equality checks. - Fixed my mistake in error-erasure decoder's
decoding_radius
. - I removed the hideous, useless backslashes which were lurking all over the place.
- I rewrote the error message related to the construction of a key equation syndrome decoder over a GRS code including a 0 in its evaluation points. I also introduced a test to illustrate this check.
By the way, Roth's book explains well the key equation decoding (that's where I learnt it). Chp 6, pp 183-196, especially 6.3.1 and 6.3.2 related to key equations, 6.4 for the Euclidean algorithm, 6.5 for Forney's formulæ, 6.6 for a summary of the algorithm.
coding_theory.rst
- I fixed all the typos you notice.
- I "upgraded" all my [6,3] codes to [12, 6] codes. Twice better!
- With these new codes, d/2 now equals to 3, I updated the number of errors accordingly.
- I rewrote the weird sentences you noticed.
To answer your questions:
l.567: "For instance, we did not mention how Sage manages bounds on codes." Does it manage them ?
In a way. There's no central mechanism to take care of bounds, register the best upper- and lower-bound computed so far while working on a code.
However, some bounds are implemented, and I hid them behind codes.bounds
.
So, Sage can somehow compute a few bounds on minimum distance, best parameters for codes and so on.
l.364, 442, 446, 550: why did you write "#random" ?
Because I don't control the output. E.g., l507 a random element of C
is picked, and l550 (example flagged #random
) I use my channel to create *randomly* some errors/erasures in it.
Now, there's a way to control this randomness:
1) Use "hardcoded" vectors.
2) Write set_random_seed(42)
before any random method. In that way, we guarantee the error pattern will always be the same, and thus can write the output of our method. See channel_construction.py
, ll 210-215 for an example.
I chose to *not* use this, as it's an introductory tutorial, designed for beginners. I wanted to illustrate the ability of channels to add random errors in words, and of decoders to correct these random errors. Plus, for beginners, finding a statement such as set_random_seed
might be confusing imho.
So I more or less sacrificed doctest purity on the altar of understandability. Which is not a big deal as these methods are properly doctested in their respective files.
David
comment:20 Changed 6 years ago by
- Commit changed from d70d6aa219a0472d1e254a23b6e0427f5cc7e1b2 to 7cbcca2969f5a72776eaff64951318a6c3c89a84
Branch pushed to git repo; I updated commit sha1. New commits:
5f22eed | Default decoder for GRS codes is now Gao decoder
|
8b654ac | Renamed method precompute and changed its doc
|
b60ca15 | Rewrote documentation of partial_xgcd and made it a private method
|
5ed4ac3 | Fixed error in error-erasure's decoding radius
|
03c15f3 | Removed useless backslashes
|
cc3cb4d | Rewrote error message in KeyEquationSyndromeDecoder
|
a7f3ee1 | Fixed typos
|
c8bc406 | Rewrote some examples
|
7cbcca2 | Rewrote some sentences
|
comment:21 Changed 6 years ago by
* Key equation decoder *
That's fine. I'm convinced we can do more efficient (e.g. "cache" alpha[j]**l
, doing matrix-vector computation, or maybe using some kind of parity-check matrix) to compute the syndrome polynomial, but that's clearly not the point of the ticket.
* Runs * Well, I don't know if that's important to fix them, but I found some non-caught (or badly caught) running errors:
- when running [
Gao
/Key
/Berlekamp
] decoder with a GRS code of dimension k = n (a "full code" with distance 1, ok that's a weird code...): the decoder is built, but when trying todecode_to_message
a wordy
, it begins by checking ify
is a codeword by compute its syndrome, which is done by using the parity check matrix, which doesn't exist due to dimension issues. Thus the following error is raised:ValueError: The dimension must be a positive integer at most the length of the code.
I suggest two solutions (but the second one seems to be the best one, see remark below):- we prevent the construction of a decoder for such a code (in a way, it has no sense to decode that code)
- the decoder returns the input word
- when running [
Gao
/Key
/Berlekamp
] decoder with a GRS code of dimension k=n-1 (distance 2) on a noisy word with 1 error, some weird things happen (for the moment, I don't have any solution for these issues):- for
KeyEquationDecoder
, it tries to decode and fails almost every time (I would say with proba (q-1)/q, as if it was random). - for
GaoDecoder
,decode_to_code
raisesValueError: The polynomial to encode must have degree at most k-1 when trying to re-encode the message
. It meansdecode_to_message
outputs a polynomial with too high degree (k). - for
BerlekampDecoder
, that's a random mix of the two previous behaviour (sooo weird...).
- for
In fact, the previous issues are more important that I thought. For example, see the following script:
C = codes.GeneralizedReedSolomonCode(GF(16,'a').list()[1:], 12) D = C.decoder('ErrorErasure') Chan = channels.ErrorErasureChannel(C.ambient_space(), 0, 3) c = C.random_element() y,era = Chan(c) mp = D.decode_to_message(tuple([y, era]))
The [15,12,4]-GRS code is clearly not a trivial code, but I still get the strange error from the "full code", because in the ErasureError
decoding algorithm, we puncture the code on erasures, and call the error decoding algorithm on the punctured code (which is the full code).
* Another remark *
If you set Gao decoder as the default decoder for GRS, you should also set EvaluationPolynomial
as the default encoder, otherwise we do not have decode_to_message(encode(x)) = x
.
comment:22 Changed 6 years ago by
Yum, border cases! I'll investigate this.
Regarding your
*Another remark*
your example actually works. See as follows:
sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12) sage: c = C.random_element() sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), C.decoder().decoding_radius()) sage: y = Chan(c) sage: c == C.encode(C.decode_to_message(y)) True
What might be bothering you is:
sage: C.decoder().connected_encoder() == C.encoder() False
But actually, AbstractLinearCode.decode_to_message
has been written such that it *always* returns the element of the message space as a vector, because it seems the more natural way of seeing messages. This generic decode_to_message
is more designed for beginners/people who don't want to bother with all the underlying structure, thus we defaulted the the most intuitive representation.
And that's one of the reasons for which we ask default_encoder
to be always set to an encoder whose message_space
is a vector space.
David
comment:23 Changed 6 years ago by
- Commit changed from 7cbcca2969f5a72776eaff64951318a6c3c89a84 to 4aebb5a23a3c571f945bb7da558e03ff4b4c1ace
Branch pushed to git repo; I updated commit sha1. New commits:
4aebb5a | Fixed bug related to full codes, plus some minor tweaks
|
comment:24 Changed 6 years ago by
Hello,
So I fixed the bug related to full codes.
I added a specific test in every decoder's decoding method to check if C.length() == C.dimension()
.
If that's the case, the input word is returned as is/unencoded as is (depending if it's decode_to_code
or decode_to_message
).
I also added a note in these methods to document this behaviour.
As C.decode_to_message()
was also failing in the full code case, I overrode it.
Finally, I renamed shorten_word
to punctured_word
in GRSErrorErasureDecoder
, and store C.length()
and C.dimension()
in variables when they were called multiple times (as it was the case in Berlekamp-Welch.
David
comment:25 Changed 6 years ago by
Hi David,
I found a weird thing in your functions _partial_xgcd()
:
- in Key equation decoder, you define a
stop
variable, but never use it; your halting condition is related to the polynomialt
, contrary to what you say in your documentation. - in Gao decoder, you use a variable
stop
which (I think, though Gao paper is not so clear about it) isn't well-defined. You write:stop = floor(self.code().dimension() + self.code().length()) / 2
; I think that'sstop = (self.code().dimension() + self.code().length()) // 2
instead (note the integer division).
Apparently, it could solve the previous "too-high degree re-encoding" issue.
You also told me to point out when you used numbers instead of field elements. Here is a small list (I don't know if all of them belong to your code):
- l. 197:
0 in ...
-->F.zero()
- l. 317: maybe the 1/...
- l. 1702:
e.append(0)
-->e.append(C.base_ring().zero())
. Maybe also the previous 1 and 0 in lines 1698 and 1699.
Otherwise, the code is pretty good. I've nothing to add.
Julien
comment:26 follow-up: ↓ 28 Changed 6 years ago by
Hello,
I changed what you asked, except the integer division in Gao decoder. I re-read Gao's paper and it's indeed unclear.
So I tried the empirical method, and ran some tests.
In the case /
this snippet:
sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 39) sage: D = C.decoder("Gao") sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), 1) sage: for i in range(100): ....: c = C.random_element() ....: y = Chan(c) ....: assert c == D.decode_to_code(y)
indeed returns the "too-high degree" weird error...
But in the case //
, the same snippet returns an AssertionError
!
I'm really stuck here. If anyone has an idea, I'll be glad to hear it.
David
comment:27 Changed 6 years ago by
- Commit changed from 4aebb5a23a3c571f945bb7da558e03ff4b4c1ace to 29b8892169f34a763c6e1be45a9d7cbba89dd811
comment:28 in reply to: ↑ 26 Changed 6 years ago by
But in the case
//
, the same snippet returns anAssertionError
! I'm really stuck here. If anyone has an idea, I'll be glad to hear it.
The code has minimum distance 2, so it's OK that it can't decode 1 error. Or?
The correct is floor( (n+k)/2 )
. Note that in the current code, the floor function is around n+k
, and not around the division by two. You can do //
as Julien suggests, or move the floor function around the division.
Gao's paper is very complicated to read, though the algorithm is so simple. It's rather silly really -- it would have been much clearer to formulate the stopping criterion as deg s + k > deg r
. That's how you would phrase it when using lattice basis reduction. It implies deg r < floor( (n+k)/2 )
under the assumption that deg s < floor( (n-k)/2 )
.
comment:29 Changed 6 years ago by
Hello,
Hmmm sorry David, I wasn't so clear about what was bothering me. It wasn't the fact that the decoder raised an error (as Johan said, the decoder can't correct 1 error), but I just didn't like the kind of error it raised.
Hope it's clear now.
Julien
comment:30 Changed 6 years ago by
as Johan said, the decoder can't correct 1 error
Oh yes, of course... Sorry for being so dumb here.
I'll change /
to //
ASAP. I'm on something else for now.
comment:31 Changed 6 years ago by
- Commit changed from 29b8892169f34a763c6e1be45a9d7cbba89dd811 to 6e4b0746b3daffbd18c0c874612f957f0ef2a919
Branch pushed to git repo; I updated commit sha1. New commits:
6e4b074 | Replaced standard division by integer division in Gao decoder's stopping criterion
|
comment:32 Changed 6 years ago by
I'll change
/
to//
ASAP.
Done.
comment:33 Changed 6 years ago by
I was actually checking something completely different, but then I noticed that the key equation syndrome decoder has absolutely no sanity checks! If too many errors occurred, or you just gave it a random input, then it will always return something, and often not a codeword!
In the same vain, are you sure that the output of the other decoders will always be codewords? I don't think the divisibility test is sufficient.
comment:34 Changed 6 years ago by
- Commit changed from 6e4b0746b3daffbd18c0c874612f957f0ef2a919 to 6ad583f27736146eb019ba99ecfb54e67c31f5ea
Branch pushed to git repo; I updated commit sha1. New commits:
2246e18 | Better doctests for BW decoder, added sanity check on decode_to_messaage's input
|
7309523 | Better doctests for Gao decoder, added sanity check on decode_to_messaage's input
|
c4ca177 | Better doctests for Error-Erasure decoder, added sanity check on decode_to_messaage's input
|
a074cb8 | Changed my helper methods into private methods
|
6ad583f | Fixed bug in KeyEquation decoder's decode_to_code, added sanity checks, enhanced doctests
|
comment:35 Changed 6 years ago by
Ok, I added sanity checks on the input on every decode_to_*
method.
It does not utterly fail anymore if one tries to decode something which is not a vector (or a vector which is not in the ambient space of the code).
I also upgraded doctests to document this behaviour. New doctests now generate a random codeword c
, create a channel which adds as many errors as decoder's capacity, transmit c
to get y
and compare c
and y
decoded. It's much better than a single hardcoded example.
Furthermore, I added an explicative message to every call to DecodingError
.
comment:36 Changed 6 years ago by
- Commit changed from 6ad583f27736146eb019ba99ecfb54e67c31f5ea to fca099ed40912d26eff991fc612ee793681000c5
Branch pushed to git repo; I updated commit sha1. New commits:
fca099e | Added new sanity check on the output of BW and Gao decoder
|
comment:37 Changed 6 years ago by
And, (sorry, I forgot to add it...) I also made a new sanity check on the output polynomial for BerlekmapWelch
and Gao
: if the output polynomial is not in F[x]
, where F
is the base ring of the code, it raises a DecodingError
.
David
comment:38 Changed 6 years ago by
Your new checks seem good. But they were actually not what I was talking about - I wasn't very clear. Specifically for the BW decoder, let's say that more errors than (d-1)/2 occurs. In that case, all (almost) bets are off! So the division you do could for instance go fine, but you just end up with a polynomial h
which is (when you encode it) nowhere near the received word you got. There are currently no checks for this.
It's similar, I'm pretty sure, with the other decoders.
I added exactly such a check on the Guruswami-Sudan decoder yesterday.
comment:39 Changed 6 years ago by
Two completely different things I just noticed:
- I think the line
R(S.list_from_positions(xrange(0, l0+1)))
can, and should, be writtenR(S[:l0+1])
.
- In Berlekamp-Welch, and in Gao, you do a divisibility test followed by the actual division, i.e. you divide twice. You should instead use the
quo_rem
function to do the division once, and do the divisibility test by seeing if the remainder is zero.
comment:40 Changed 6 years ago by
Ok, I found something very annoying while working on writing an actual check on the output of decoding algortihms:
sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[1:40+1], 12) sage: c1 = C.random_element() sage: c2 = C[1] sage: c1.parent() == c2.parent() False
So if the input of decode_to_code
, say r
is generated through random_elements
, all code like t his:
(r - decoded_word).hamming_weight() > self.decoding_radius(): raise DecodingError("Decoding failed because the number of errors exceeded the decoding radius")
systematically fails because one cannot properly subtract two vectors whose parents are diffrent.
So I'll fix random_element
method...
comment:41 Changed 6 years ago by
Damn. It's related to this sick semantics that the parent of a vector is the subspace. That's also causing trouble in the channels. We should try to fix that at the root, i.e. experiment with the scaffolding code at linear code construction time. Didn't Vincent write something about how to do this in the old sage-devel thread where we discussed the bug?
comment:42 Changed 6 years ago by
- Commit changed from fca099ed40912d26eff991fc612ee793681000c5 to 8673ac587f4e8bece38fc7027c96eef9771c7eec
comment:43 follow-up: ↓ 44 Changed 6 years ago by
Damn. It's related to this sick semantics that the parent of a vector is the subspace. That's also causing trouble in the channels. We should try to fix that at the root, i.e. experiment with the scaffolding code at linear code construction time. Didn't Vincent write something about how to do this in the old sage-devel thread where we discussed the bug?
Ah, in the meanwhile I changed this method to something based on encoding a random element from the message space of the default encode of a code. Probably not the best way to do it, I'm aware of that.
I made the other changes, but
I think the line
R(S.list_from_positions(xrange(0, l0+1)))
can, and should, be writtenR(S[:l0+1])
which I tried, but it did not work.
comment:44 in reply to: ↑ 43 ; follow-up: ↓ 45 Changed 6 years ago by
Ah, in the meanwhile I changed this method to something based on encoding a random element from the message space of the default encode of a code. Probably not the best way to do it, I'm aware of that.
That's like pissing your pants to keep warm: it doesn't fix the problem in the gazillion other ways this could explode (such as using a StaticErrorRateChannel
).
I think the line
R(S.list_from_positions(xrange(0, l0+1)))
can, and should, be writtenR(S[:l0+1])
Try harder, seriously... You need to call list
on S[:l0+1]
as well because the R(...)
call is picky about getting a list and not a vector. I just did it, but it turns out it's slower than list_from_positions
, so I guess you should just keep that though it looks horrendous.
comment:45 in reply to: ↑ 44 Changed 6 years ago by
Replying to jsrn:
Ah, in the meanwhile I changed this method to something based on encoding a random element from the message space of the default encode of a code. Probably not the best way to do it, I'm aware of that.
That's like pissing your pants to keep warm: it doesn't fix the problem in the gazillion other ways this could explode (such as using a
StaticErrorRateChannel
).
I totally take that back! I just looked through LinearCode
and it seems there is no other way that we could end up with a codeword whose parent is the subvector-space. So the problem really *was* with random_element
. Which means your fix is a *good* way to solve the problem :-) Sorry about the flame.
Let's discuss another time whether there is a more efficient way to do it, and whether this bizarre passing through of *args
and **kwargs
to random shouldn't be deprecated (can you please note this down somewhere so we don't forget though?).
Best, Johan
comment:46 Changed 6 years ago by
(for instance, that the following works is not so good:
C.random_element(monkey = 2)
But, as I said, that's for another patch.)
comment:47 Changed 6 years ago by
- Commit changed from 8673ac587f4e8bece38fc7027c96eef9771c7eec to e1b6b091ee15d723378847bfb00e58d41b37d5ee
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
d5e5f35 | Documentation to the root finding module
|
4169e8b | Fixed a bug in some code being validated in the wrong place. Improved
|
5f03b11 | More doc-strings and rm a single assert
|
8f2ce97 | Reflow doc-string
|
0c7b80d | More robust testing: use sets instead of lists. Semantic tests on output. Corner case on zero input
|
2b09750 | Make the example one where the decoding results in a list
|
8133531 | Fixed typo in decode_to_message
|
b4bc257 | Removed #random flag from _flatten_once doctest
|
29448ce | Changed title of rootfinding.py
|
e1b6b09 | Merged now postive reviewed #19666 and fixed conflicts
|
comment:48 Changed 6 years ago by
comment:49 Changed 6 years ago by
- Commit changed from e1b6b091ee15d723378847bfb00e58d41b37d5ee to f3b4b11582fd4c2e976d2e0450d0e8699be0272e
comment:50 Changed 6 years ago by
As this one is not yet reviewed, I take the opportunity to fix a typo in Guruswami-Sudan documentation.
Still open for review.
comment:51 Changed 6 years ago by
- Reviewers set to Julien Lavauzelle
Hi David,
All my previous tests now pass. I won't add anything, so if Johan agrees (and if the patchbot "question mark" isn't a problem), I let you put the ticket in positive review.
Really good job !
Julien
comment:52 Changed 6 years ago by
Hello,
(and if the patchbot "question mark" isn't a problem)
Nah, it's librae which has gone and done it again, see here, it's a completely unrelated test, which fails only on librae, not on the other bots.
I let you put the ticket in positive review
Please do, I don't want to take that from you (plural) ;)
David
comment:53 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:54 Changed 6 years ago by
- Branch changed from u/dlucas/grs_decoders to f3b4b11582fd4c2e976d2e0450d0e8699be0272e
- Resolution set to fixed
- Status changed from positive_review to closed
I pushed the changes, it's now open for review. Please note that I branched #18928 to work on this ticket.
New commits:
New Generalized Reed Solomon code object in Sage, coming with two encoders
Updated to 6.9beta6 and fixed conflict
Overwrote some methods from linear_code
Updated to 6.10beta0 and resolved conflicts
Update to latest beta
Merged with latest beta version and fixed conflicts
Four new decoders for GRS codes