Decoder for punctured codes

[David Lucas]

For now, punctured codes do not have any decoder available.

It's possible to implement one (several?) based on the following strategies, which all start the same:

if y is the word to decode (belongs to the punctured code), expand it to y_exp using the list punctured_points. Then...

1/ Fill the new positions with zeroes, and try to decode it using the original_code decoder. 2/ Consider the new positions as erasures, and decode it using an error-erasure decoder. Of course, this can only be done if the original code has an error-erasure decoder. 3/ With codes over GF(q), and t punctured positions, call q^t times the decoder of the original code, flipping bits at each call until we get a sensible result.

[Daniel Augot]

1/ is not very different form 3/ It is simply the first run of the loop when going through all q^t possibilities. A 1'/ could be a randomized 1/ : with a random choice instead of 0.

I would vote for 2/ since most codes we know have an error-and-erasure decoder.

Yet 3/ could be useful if the shortened code is used as the inner code in a concatenated code.

[David Lucas]

I implemented a decoder for punctured codes, for now it works as follows:

• at construction time, user can specify the name of the decoder to use on the original code. If none is selected, it default to original code's default decoder.

• for the decoding I only implemented solution 1/

I was considering the following: as the program can access the list of all available decoders for any code family, it could be interesting to do something with auto-detection. For instance, at construction time, if no decoder is specified by the user, constructor checks if an error-erasure decoder is available, and if it's the case, it picks such a decoder. Downside: it forces to build decoders alphabetically while iterating through the list of available decoders. Another idea: as a code with several points punctured reduces the decoding radius (every punctured point counts as an error/erasure), what about automatically switch to 3/ under certain conditions? Of course, add a parameter to allow the user to disable this costly feature...

[David Lucas]

Update on the chosen behaviour:

There will be one decoder, which takes two optional parameters.

• Something I called strategy (all names are opened to discussion, of course) which indicates the technique used to decode, amongst the following:

  • error-erasure - if the original code has an error-erasure decoder, it uses it (and thus considers punctured positions as erasures), else it returns an exception.
  • zeroes - fills the punctured positions with zeroes and decodes over the original code using its default decoder if original_decoder is set to None, else it uses the decoder passed in original_decoder.
  • try-all - fills the punctured positions with every possible combination of symbols until decoding succeeds (or until every combination have been tried).
  • None - uses error-erasure if an error-erasure decoder is available, else it switches to zeroes behaviour.

• Something I called original_decoder which allows the user to pass a decoder object.

For now, strategy takes precedence over original_decoder: if one chose error-erasure as a strategy, and an original_decoder which is not an error-erasure one, it will fail. Should original_decoder take precedence instead?

[David Lucas]

original_decoder should take precedence, it makes definitely more sense like this. I'm changing this.

Also, for zeroes strategy, I'll fill punctured positions by random values of the base field of the code instead of zeroes, as it might give a slightly higher chance to hit the mark.

[David Lucas]

Implemented, advanced tests available in experiments/test_punctured.sheet