Block basis reduction for linear codes in non-Hamming metrics
En palabras de los autores
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.
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.