Variable ball collision decoding.

摘要

This paper presents a new decoding algorithm named Variable Ball-Collison Decoding (VBCD) which can be used to decode any linear code. It is based upon the Ball-Collison Decoding (BCD) algorithm by Bernstien, et al. In preparation for the description of the algorithm, we first include sections on both basic Coding Theory and some Public Key Cryptosystem preliminaries. We then analyze VBCD's asymptotic complexity and find that under certain circumstances it is more likely than BCD to finish successfully given the same parameters. In addition, we show that it is possible for VBCD to take the same number of operations as BCD. We were unable to prove that these two events can occur simultaneously. Finally, we include some timing data from implementations of VBCD and BCD run on small codes.