Information set decoding for ring-linear codes

Abstract Information set decoding (ISD) algorithms currently offer the most powerful tool to solve the two archetypal problems of coding theory, namely the codeword finding problem and the syndrome decoding problem. Traditionally, ISD have primarily been studied for linear codes over finite fields, equipped with the Hamming metric. However, recently, other possibilities have also been explored. These algorithms have been adapted to different ambient spaces and metrics, such as the rank metric or the Lee metric over $$\mathbb {Z}_m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Z</mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:math> . In this paper, we propose a general framework for decoding ring-linear codes that exploits the underlying ring structure to improve traditional approaches. The core idea is to project the decoding instance onto a smaller alphabet, which may enable more efficient decoding algorithms. The framework applies to coordinate-additive metric including Hamming and Lee, and extends to the rank metric, though its effectiveness strongly depends on the chosen metric. We illustrate how this framework can be leveraged to design decoding algorithms for the two aforementioned problems in Hamming, rank, and Lee metrics, along with their range of effectiveness. For each case, we provide the average computational complexity of the resulting algorithms.