LinearBlockCode top class

[David Lucas]

We propose the following pattern :

LinearBlockCode class

• length()
• dimension()
• is_code_word(x)
• minimum_distance() // Warning : can be long, computes exact minimum distance
• approx_minimal_distance() //provides an upper bound

[Daniel Augot]

I suggest to add

• ambient_space
• message_space
• approx_minimum_distance : there should be two functions, one for a lower bound, another for an upper bound.
• distance : a code should tell its distance(x,y) function of the ambient space, which can be Hamming, Rank, weighted Hamming (for CRT), etc.

[Johan Rosenkilde]

• random_codeword()
• __iter__() to iterate through code
• list()
• Probably lots of functions from Joyner

The following might rely on our design of Encoder/Decoder:

• generator_matrix() ?

  Using default Encoder

• parity_check_matrix()

  as kernel of default generator_matrix or as the "designed" parity_check_matrix?

• syndrome(): Ambient -> Syndrome space

  Should probably use the the default parity_check_matrix.

• generator_matrix_systematic

  This is canonical for the code. Alternatively provide as generator_matrix(systematic=True).

Lots of stuff from Joyner probably inspects and manipulates the generator matrix and parity check matrix to determine properties inherent to the code (i.e. invariant of choice of generator/parity check). These should just be given the default or something.

Remember that all methods which compute something and have no input should be decorated with @cached_method.

[Daniel Augot]

Be careful about the syndrome space. Depending on the code and on the decoding algorithm, the syndromes may belong to an extension field (consider BCH and Goppa codes), while the so-called syndrome decoding, or standard array decoding has syndromes in the same field as the field of codewords.

So, it should be a default_syndrome() function, depending on parity_check_matrix(), while each decoder in the Decoder Class of a given code may provide its own, alternative syndrome() function. For instance, for Goppa codes, you have two decoding algorithms, which do not use the same set of syndromes.

[Johan Rosenkilde]

Hmm, yes, you are raising a tricy question.

You are arguing that syndromes belong to Decoders, since e.g. Goppa codes have a natural syndrome definition both from its Goppa description and its Alternant code description.

But as you mention, syndromes are also used simply as the product of a given parity check matrix and its codeword. We might want the syndrome connected to the "systematic" parity check matrix of our Goppa code.

Contraversely (?), there are decoders for which no natural concept of syndrome arise (e.g. Sudan).

I don't immediately agree that it is the decoders that give rise to a Goppa code's two natural syndrome definitions. Rather it is the nature of the Goppa code and the Alternant code. Thus, a Goppa code could overwrite its syndrome() method, or has a new syndrome_polynomial or something, and likewise could an Alternant code. If you want the Alternant code syndrome for a Goppa code's received word, you first cast/coerce the Goppa code into an Alternant code.

[David Lucas]

And a new one :

• Assuming some people may not like the idea of the encoder process (which could be seen as tedious if you do not care about the encoder choice), which consists in knowing the lists of possible encoders for the code, creating one of them, calling its encoding function on the code, we could add a call_preferred_encoder(self, information) method, which calls the preferred_encoder of self on information and returns a codeword.

[Johan Rosenkilde]

And I propose to simply call this function encode. And add a similar unencode and decode convenience function.

[Daniel Augot]

The following functions could be put as "default" in LinearBlockCode: encode(), unencode(), syndrome() relying on a "default" generating matrix G, and on a "default" parity check matrix H. Would not it make sense also to passe G and H as optional argument, since python tolerates this ?

And also, these three functions can be also defined when non default behavior are needed for special needs in Encode and Decode classes.

[David Lucas]

If you want to pass G and H to encode & co to spare some computation time, it's not necessary because the methods generator_matrix and parity_check_matrix will be cached.

[Johan Rosenkilde]

And if you wanted to pass G and H as a way to allow the user to specify "custom" G and H, then the two convenience functions are probably not the ideal place: rather, if this is wanted functionality, we could have a generic EncoderFromGeneratorMatrix class which takes G at construction time.

David and I talked about having something like an encoder(name, params) function for each code family which takes a string name and returns the corresponding encoder. This is for exploration and usability so that the user can easily get an overview of the in-built encoders that he could employ. The doc-string for encoder should specify which values of name was allowed. E.g. for RS code, we could have something like: name is one of "evaluation", "cyclic", "generator_matrix_standard", "generator_matrix"

followed possibly by a more precise description of what these mean.

With Clément we realised that the Message Space depends on the Encoder and not the code. For instance, in the above, it would be logical that for both "evaluation" and "cyclic" encoder, the message space is univariate polynomials of bounded degree, while for "generator_matrix*", the message space is vectors of length k. Nothe that presuming that an RS code's preferred generator matrix is the Vandermonde, then evaluation and generator_matrix_standard encoders will be more or less the same, but differ in their message spaces.

[David Lucas]

Old discussion about design. No longer useful.