Opened 6 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:

Status badges

Description

This ticket introduces four new different decoders for GRS codes, namely:

  • GRSBerlekampWelchDecoder,
  • GRSGaoDecoder,
  • GRSKeyEquationSyndromeDecoder and
  • GRSErrorErasureDecoder.

It requires the new structure for GRS codes introduced in ticket #18928

Change History (54)

comment:1 Changed 6 years ago by dlucas

  • Branch set to u/dlucas/grs_decoders

comment:2 Changed 6 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to 74cc281ef65d2aed2fca11dd41d6ac268ad52880
  • Status changed from new to needs_review

I pushed the changes, it's now open for review. Please note that I branched #18928 to work on this ticket.


New commits:

d854eb8New Generalized Reed Solomon code object in Sage, coming with two encoders
0645f58Updated to 6.9beta6 and fixed conflict
dc470beOverwrote some methods from linear_code
f8c2d7aUpdated to 6.10beta0 and resolved conflicts
fa4dd71Update to latest beta
1c1f182Merged with latest beta version and fixed conflicts
74cc281Four new decoders for GRS codes
Last edited 6 years ago by dlucas (previous) (diff)

comment:3 Changed 6 years ago by git

  • Commit changed from 74cc281ef65d2aed2fca11dd41d6ac268ad52880 to b03d7b5ae8f6e725a148b4fe7bcce99043e240db

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

8733405Some improved doc-strings and doc-tests
229b5cfSome code beautification
fe7e9deSanity-checks on input for GRSEvaluationPolynomialEncoder
6e7013bSmall doc-string improvements in linear_code and encoder
0e82848More small docstring improvements
91e2e3bDoc-string typesetting fix
eabe7e0Reworked coercion of evaluation pts and col mults and refined tests.
71070deMerged with 18928 and fixed conflicts
9f4fb84Improved docstrings and doctests
b03d7b5Extra cleaning in documentation

comment:4 Changed 6 years ago by dlucas

I merged in #18928 latest version and did some fixes and improvements to the documentation.

comment:5 Changed 6 years ago by git

  • Commit changed from b03d7b5ae8f6e725a148b4fe7bcce99043e240db to 4e1a1845fdacdd3f9fe9e9adacb7c92dcc81b6cd

Branch pushed to git repo; I updated commit sha1. New commits:

4e1a184Merge branch 'develop' into grs_decoders

comment:6 Changed 6 years ago by dlucas

Updated to latest beta, still open for review.

comment:7 Changed 6 years ago by git

  • Commit changed from 4e1a1845fdacdd3f9fe9e9adacb7c92dcc81b6cd to ffed9486f0d2e5bf3d1a86dff8dfa9a9e33ec9dc

Branch pushed to git repo; I updated commit sha1. New commits:

ffed948Merge branch 'u/dlucas/grs_decoders' of git://trac.sagemath.org/sage into grs_decoders

comment:8 Changed 6 years ago by dlucas

Updated to latest beta, still open for review.

comment:9 Changed 6 years ago by git

  • Commit changed from ffed9486f0d2e5bf3d1a86dff8dfa9a9e33ec9dc to 37bb7ac8775f51d774cc9edaeeb0ba457c7f2546

Branch pushed to git repo; I updated commit sha1. New commits:

616219cUpdate to latest beta
baa9f20First version of the tutorial
cb65314Update to latest beta
2057feeSmall fixes and improvements
77f0629Merged #19897
37bb7acUpdated introductory thematic tutorial with a paragraph on decoders and message spaces

comment:10 Changed 6 years ago by dlucas

  • Dependencies changed from #18928 to #18928, #19897

I merged #19897 in, and updated the tutorial.

It's still open for review.

comment:11 Changed 6 years ago by git

  • Commit changed from 37bb7ac8775f51d774cc9edaeeb0ba457c7f2546 to 4340598e5ae5e932abb87389764ccb6e06561c12

Branch pushed to git repo; I updated commit sha1. New commits:

1220403Merge branch 'develop' into grs_decoders
4340598Removed deprecated import

comment:12 Changed 6 years ago by dlucas

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 git

  • Commit changed from 4340598e5ae5e932abb87389764ccb6e06561c12 to b8406820e1300efdd3ef95d8e5f326c28878a568

Branch pushed to git repo; I updated commit sha1. New commits:

b840682Updated to 7.1beta3 and fixed conflict

comment:14 Changed 6 years ago by dlucas

  • Milestone changed from sage-6.10 to sage-7.1

comment:15 Changed 6 years ago by git

  • Commit changed from b8406820e1300efdd3ef95d8e5f326c28878a568 to d70d6aa219a0472d1e254a23b6e0427f5cc7e1b2

Branch pushed to git repo; I updated commit sha1. New commits:

d70d6aaRemoved __ne__ methods

comment:16 Changed 6 years ago by dlucas

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: Changed 6 years ago by jlavauzelle

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 and C
  • 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 and d 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 jsrn

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 dlucas

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 than precompute. 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 from code. If you check the input of all my decoders, you'll see the user only provides code, and the input space is extracted from code. 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 git

  • Commit changed from d70d6aa219a0472d1e254a23b6e0427f5cc7e1b2 to 7cbcca2969f5a72776eaff64951318a6c3c89a84

Branch pushed to git repo; I updated commit sha1. New commits:

5f22eedDefault decoder for GRS codes is now Gao decoder
8b654acRenamed method precompute and changed its doc
b60ca15Rewrote documentation of partial_xgcd and made it a private method
5ed4ac3Fixed error in error-erasure's decoding radius
03c15f3Removed useless backslashes
cc3cb4dRewrote error message in KeyEquationSyndromeDecoder
a7f3ee1Fixed typos
c8bc406Rewrote some examples
7cbcca2Rewrote some sentences

comment:21 Changed 6 years ago by jlavauzelle

* 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 to decode_to_message a word y, it begins by checking if y 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 raises ValueError: The polynomial to encode must have degree at most k-1 when trying to re-encode the message. It means decode_to_message outputs a polynomial with too high degree (k).
    • for BerlekampDecoder, that's a random mix of the two previous behaviour (sooo weird...).

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.

Last edited 6 years ago by jlavauzelle (previous) (diff)

comment:22 Changed 6 years ago by dlucas

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 git

  • Commit changed from 7cbcca2969f5a72776eaff64951318a6c3c89a84 to 4aebb5a23a3c571f945bb7da558e03ff4b4c1ace

Branch pushed to git repo; I updated commit sha1. New commits:

4aebb5aFixed bug related to full codes, plus some minor tweaks

comment:24 Changed 6 years ago by dlucas

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 jlavauzelle

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 polynomial t, 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's stop = (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: Changed 6 years ago by dlucas

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 git

  • Commit changed from 4aebb5a23a3c571f945bb7da558e03ff4b4c1ace to 29b8892169f34a763c6e1be45a9d7cbba89dd811

Branch pushed to git repo; I updated commit sha1. New commits:

4479b4dUpdate to 7.1beta4
b2673aaReplaced 0s and 1s by F.zero() and F.one()
29b8892Removed useless stop variable

comment:28 in reply to: ↑ 26 Changed 6 years ago by jsrn

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.

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 jlavauzelle

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 dlucas

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 git

  • Commit changed from 29b8892169f34a763c6e1be45a9d7cbba89dd811 to 6e4b0746b3daffbd18c0c874612f957f0ef2a919

Branch pushed to git repo; I updated commit sha1. New commits:

6e4b074Replaced standard division by integer division in Gao decoder's stopping criterion

comment:32 Changed 6 years ago by dlucas

I'll change / to // ASAP.

Done.

comment:33 Changed 6 years ago by jsrn

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 git

  • Commit changed from 6e4b0746b3daffbd18c0c874612f957f0ef2a919 to 6ad583f27736146eb019ba99ecfb54e67c31f5ea

Branch pushed to git repo; I updated commit sha1. New commits:

2246e18Better doctests for BW decoder, added sanity check on decode_to_messaage's input
7309523Better doctests for Gao decoder, added sanity check on decode_to_messaage's input
c4ca177Better doctests for Error-Erasure decoder, added sanity check on decode_to_messaage's input
a074cb8Changed my helper methods into private methods
6ad583fFixed bug in KeyEquation decoder's decode_to_code, added sanity checks, enhanced doctests

comment:35 Changed 6 years ago by dlucas

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 git

  • Commit changed from 6ad583f27736146eb019ba99ecfb54e67c31f5ea to fca099ed40912d26eff991fc612ee793681000c5

Branch pushed to git repo; I updated commit sha1. New commits:

fca099eAdded new sanity check on the output of BW and Gao decoder

comment:37 Changed 6 years ago by dlucas

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 jsrn

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.

Last edited 6 years ago by jsrn (previous) (diff)

comment:39 Changed 6 years ago by jsrn

Two completely different things I just noticed:

  • I think the line R(S.list_from_positions(xrange(0, l0+1))) can, and should, be written R(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 dlucas

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

Last edited 6 years ago by dlucas (previous) (diff)

comment:41 Changed 6 years ago by jsrn

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 git

  • Commit changed from fca099ed40912d26eff991fc612ee793681000c5 to 8673ac587f4e8bece38fc7027c96eef9771c7eec

Branch pushed to git repo; I updated commit sha1. New commits:

57dbfbfRewrote random_element method
7953d60Proper sanity checks for output of decode_to_* methods
8673ac5Optimized a bit polynomial division in Gao and BW

comment:43 follow-up: Changed 6 years ago by dlucas

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 written R(S[:l0+1])

which I tried, but it did not work.

comment:44 in reply to: ↑ 43 ; follow-up: Changed 6 years ago by 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 think the line R(S.list_from_positions(xrange(0, l0+1))) can, and should, be written R(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 jsrn

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 jsrn

(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 git

  • Commit changed from 8673ac587f4e8bece38fc7027c96eef9771c7eec to e1b6b091ee15d723378847bfb00e58d41b37d5ee

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

d5e5f35Documentation to the root finding module
4169e8bFixed a bug in some code being validated in the wrong place. Improved
5f03b11More doc-strings and rm a single assert
8f2ce97Reflow doc-string
0c7b80dMore robust testing: use sets instead of lists. Semantic tests on output. Corner case on zero input
2b09750Make the example one where the decoding results in a list
8133531Fixed typo in decode_to_message
b4bc257Removed #random flag from _flatten_once doctest
29448ceChanged title of rootfinding.py
e1b6b09Merged now postive reviewed #19666 and fixed conflicts

comment:48 Changed 6 years ago by dlucas

I merged #19666 in this branch, and fixed conflicts. This will prevent merge conflicts in this branch and #19666 ship in the same Sage beta.

comment:49 Changed 6 years ago by git

  • Commit changed from e1b6b091ee15d723378847bfb00e58d41b37d5ee to f3b4b11582fd4c2e976d2e0450d0e8699be0272e

Branch pushed to git repo; I updated commit sha1. New commits:

5093dceUpdate to 7.1beta5
f3b4b11Fixed typo in Guruswami-Sudan doc

comment:50 Changed 6 years ago by dlucas

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 jlavauzelle

  • 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 dlucas

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

Last edited 6 years ago by dlucas (previous) (diff)

comment:53 Changed 6 years ago by jsrn

  • Status changed from needs_review to positive_review

comment:54 Changed 6 years ago by vbraun

  • Branch changed from u/dlucas/grs_decoders to f3b4b11582fd4c2e976d2e0450d0e8699be0272e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.