Behaviour for a vectorial encoder for cyclic codes?

[David Lucas]

I'm currently working on the cyclic codes.

I already wrote an encoder whose message space is a polynomial ring. In that case, encoding a message p is just a multiplication p * g (where g is the generator polynomial of the code) and unencoding a codeword c can be done with a division c // g, assuming c is under polynomial form.

I'd like to implement another decoder whose message space is a vectorial space, but I'm not sure about its behaviour.

I have several ideas:

• either do the same as above, using "casts" vector -> polynomial in the encoding case, polynomial -> vector in the unencoding case; or
• explicity compute a generator matrix and use default implementation of encode/unencode; or
• perform matrix/vector-like operations without explicit computation of the generator matrix using shifts on the vectorial representation of the code's generator polynomial.

As the first seems to be the cheaper (storage-wise), I think it's also a hidden polynomial behaviour, which quite redundant with the polynomial encoder. The second one is classical, but as one of the main upsides of Cyclic Codes is the limited amount of memory needed to represent them (as one avoids to explicitly compute the generator matrix), it sounds a bit against cyclic codes "philosophy". So I'd to prefer the third one.

What do you think of it?

[David Lucas]

I had a (slightly better) idea:

the third proposition (see previous message) holds the following downside : if one encodes a lot of words, it's slower than compute the generator matrix, cache it and perform matrix-vector multiplication for the encoding. So I think suggest introducing a way to check if a generator matrix is known.

If it's yes, we use the default implementation, if it's no we use the operation described in the 3rd proposition. In that way, we keep the philosophy behind cyclic codes alive (memory-wise), while using efficient operations if generator matrix has been computed.

[Daniel Augot]

I think the best is to compute using polynomials. You may even get fast algorithms kicking in at some point. And it is better memory-wise.

It is also connected to the notion of ambient space. In the case of cyclic codes, having the ambient space as a space of polynomials avoid conversion between vectors and polynomials.

[David Lucas]

I think the best is to compute using polynomials. You may even get fast algorithms kicking in at some point. And it is better memory-wise.

Okay, I'll change the algorithm.

It is also connected to the notion of ambient space. In the case of cyclic codes, having the ambient space as a space of polynomials avoid conversion between vectors and polynomials.

I agree, but I think the default behaviour should always be the one using vectors, as it seems more natural to consider messages and codewords as elements of vector spaces.