Hi Ryan
It seems that we are in agreement with most thing so far then :-)
I just realised, however, a new problem with the whole encoder-decoder
solution. Many such algorithms will want to take various options (like
decoding bound, list size and multiplicity in the Guruswami-Sudan
case), which would best be given at construction time. In the current
idea of having "hidden decoder/encoder objects" constructed and cached
inside the decode() / encode() functions of the code class, which is
chosen depending on some optional second argument, this could be
supported by an optional third argument meant for any options the
constructor of the chosen algorithm expects. However, this has the
disadvantage that the code instance need not only cache a decoding
algorithm for each decoder ever used but actually one for each
(decoder, options)-pair ever used. And this should be looked up every
time the decode() function is called. Alternative, the whole caching
should be discarded but this is also inefficient.
Perhaps a more efficient and simpler way is to take the decoder
objects-idea to the limit: have a function get_decoder() taking the
name and options of a decoder (or possibly neither, then falling back
on a default), and returning a Decoder-object. This object's decode()
function is then the one to be used multiple times. This way, the user
needs to deal with the decoder as a separate object, slightly
disagreeing with the general user methodology of Sage, as far as I see
it. However, it is cleaner and more efficient, and also clearer once
the user gets used to the protocol. One could still support a decode()
function on the code class, but this should always only use the
default decoding algorithm. Of course, the same idea applied to the
encoder functions as well.
What do you say?
- Johan
On Aug 3, 8:03 pm, Ryan Hinton <iob...@email.com> wrote:
> Johan,
>
> Replies inline below.
>
> On Aug 3, 3:34 am, "Johan S. R. Nielsen" <j.s.r.niel...@mat.dtu.dk>
> wrote:
>
> > ...
> > I guess that Ensembles as you describe them could be implemented
> > completely on
> > top of the object hierarchy I am suggesting. E.g. a XCodesEnsemble
> > would have
> > a constructor for specifying exactly the ensemble (sort of like a
> > sub-sub-family?) of XCodes; so it would have a function
> > get_random_code which
> > returns a XCode object. This could easily be standardised to such an
> > extend as
> > allowing generic testing for ensembles.
>
> That was exactly my thought. My current LDPCEnsemble class has both a
> random_element() method which returns a parity check matrix, and a
> random_graph() method. Both should be suitable for generic testing.
> I would modify random_element() to return an instance of one of your
> Code subclasses.
>
> > > The class of codes I am working with (LDPC codes) has an efficient
> > > decoding algorithm (belief propagation, O(n)), but encoding is O(n^2)
> > > in general. And computing the generator matrix for encoding is non-
> > > trivial as well. There are also sometimes multiple encoding
> > > algorithms. So in this case, at least, the complexity of encoding and
> > > decoding are reversed.
>
> > I wasn't aware of this at all; come to think of it, I should have
> > added a
> > disclaimer in my first post, that most everything I wrote would
> > violate some of the generalities
> > of the field ;-)
>
> No problem. I thought your summary was quite good. I should have
> confined my corrections to items pertinent to the interface. :-)
>
> > I guess this calls for the encoding part supporting almost the same
> > structure
> > as decoding. I think, then, that the part about having to implement
> > the decoder
> > as a class in some package coding.decoders (and by extension, also the
> > encoders) should be optional. It seems very superfluous to have a
> > ReedSolomonEncoder-class, but maybe not a LDBCEncoder (and several of
> > the
> > latter), but then the other way around for decoders. Same as for
> > decoders, the
> > encode() function of the LDBCCode class could then take an optional
> > argument
> > for which algorithm to use for encoding, in the case more than one was
> > implemented.
>
> I think having both encoder and decoder objects is a good idea. Your
> Code class could store callable 'encoder' and 'decoder' objects as
> attributes. The encode() and decode() functions could simply delegate
> to these objects. Specifying the 'encode_algorithm=X' and/or
> 'decode_algorithm=Y' in the constructor would specify which encoder/
> decoder object to instantiate for the corresponding attributes, with
> appropriate defaults. Since the encoder and decoder are full objects,
> it's easy for them to defer any expensive initialization until first
> use (since they can maintain state), and they can be swapped at
> runtime.
>
> This is a detailed suggestion, but hopefully a good one.
>
> > > The received data are not in the same field for "soft-decision"
> > > decoding. This is very important for my applications.
>
> > You're right - it also reminds me of the case with erasure decoding.
> > My initial
> > idea is to more or less ignore the matter and again utilise run-time
> > types: for
> > soft-decision decoding, you would use a decoder, which expects a
> > "codeword" of floats, right? So simply give that to it. The decoder
> > function could do an initial type check and throw an exception if it
> > was given a discrete codeword. Different testing functions would need
> > to be implemented for soft-decision decoders, but it should still be
> > straightforward. Maybe there is a problem here for soft-decision
> > decoding over finite fields; how does that even work?
>
> I know some people have done this, but I haven't looked into the
> details.
>
>
>
> > For erasures, the decode function could as its argument take a tuple,
> > where the
> > first element is the received word, and the second element is a list
> > of
> > booleans, the i'th element of which indicates whether the i'th element
> > of the
> > received word is significant. By the function still taking only one
> > argument,
> > it can fit into the argument standard of the decoder-functions (whose
> > first
> > argument is the received word and optional second argument is chosen
> > decoder).
> > This could extend to various generalisations of soft-decision decoding
> > as well,
> > I guess. In general, it can always be up to the specific decoder
> > itself how to
> > interpret the input; the end-user just needs to know, so he can give
> > valid
> > input, and so he can choose the appropriate testing function.
>
> Or, similar to the general soft-decoding case, you can use log-
> likelihood ratios over the domain {+Inf, -Inf, 0}. But LLRs don't
> work for symbols over general fields. I can't think of an "obvious",
> consistent decoder interface at the moment. If the decoders can be
> swapped, the type/structure of the channel output should be part of
> your API.
>
> > > Do be careful with the equality operator. Sometimes it is assumed
> > > that "==" means the same Python class as well as the same "data".
> > > Since a code is *defined* by its mapping, I think I would support "=="
> > > meaning code equivalence without respect to Python class, e.g. the
> > > example you gave. Someone can always test for class equality if
> > > desired.
>
> > As I mentioned, I think this thing raises some issues which can be
> > deferred til
> > later (such as whether or not codes containing the same codewords (but
> > not
> > necessarily giving the same mapping) are equivalent). Once the rest is
> > settled,
> > I'll gladly go into that discussion :-)
>
> No problem. Multiple notions of equality can be handled by methods.
> I'm not enough of a purist to argue over the "right" definition of
> equality for the operator. But I can listen and provide feedback. :-)
>
> Good luck!
>
> - Ryan
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
