New decoders for Generalized Reed-Solomon codes

[dlucas]

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

[dlucas]

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

---

New commits:

​d854eb8	New Generalized Reed Solomon code object in Sage, coming with two encoders
​0645f58	Updated to 6.9beta6 and fixed conflict
​dc470be	Overwrote some methods from linear_code
​f8c2d7a	Updated to 6.10beta0 and resolved conflicts
​fa4dd71	Update to latest beta
​1c1f182	Merged with latest beta version and fixed conflicts
​74cc281	Four new decoders for GRS codes

[git]

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

[dlucas]

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

[git]

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

​4e1a184

Merge branch 'develop' into grs_decoders

[dlucas]

Updated to latest beta, still open for review.

[git]

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

[dlucas]

Updated to latest beta, still open for review.

[git]

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

[dlucas]

I merged #19897 in, and updated the tutorial.

It's still open for review.

[git]

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

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

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

[git]

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

​b840682

Updated to 7.1beta3 and fixed conflict

[git]

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

​d70d6aa

Removed __ne__ methods

[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

[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

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

[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

[git]

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

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

[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

[git]

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

​4aebb5a

Fixed bug related to full codes, plus some minor tweaks

[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

[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

[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

[git]

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

​4479b4d	Update to 7.1beta4
​b2673aa	Replaced 0s and 1s by F.zero() and F.one()
​29b8892	Removed useless stop variable

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

[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

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

[git]

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

​6e4b074

Replaced standard division by integer division in Gao decoder's stopping criterion

[dlucas]

I'll change / to // ASAP.

Done.

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

[git]

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

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

[git]

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

​fca099e

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

[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

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

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

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

[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?

[git]

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

​57dbfbf	Rewrote random_element method
​7953d60	Proper sanity checks for output of decode_to_* methods
​8673ac5	Optimized a bit polynomial division in Gao and BW

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

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

[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

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

[git]

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

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

[git]

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

​5093dce	Update to 7.1beta5
​f3b4b11	Fixed typo in Guruswami-Sudan doc

[dlucas]

As this one is not yet reviewed, I take the opportunity to fix a typo in Guruswami-Sudan documentation.

Still open for review.

[jlavauzelle]

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

[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