Block basis reduction for linear codes in non-Hamming metrics
In the authors' words
In this paper, we generalize the code basis reduction to non-Hamming metrics. We propose a block basis reduction (BKZ) algorithm for codes that works for all coordinate-additive metrics. Our algorithm is a generalization of the algorithm of Ghentiyala and Stephens-Davidowitz, which in turn is an adaptation of the famous BKZ algorithm for lattices to linear codes and the Hamming metric. For block size~ (LLL), we propose a polynomial-time algorithm with complexity~ operations in~, where~ is the length of the code and~ is the alphabet size. For the Lee metric we provide an implementation of our algorithms and present experimental results on finding low Lee weight codewords.
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.