Towards Efficient Decoding Algorithm of q-Ary Codes from Lattice

Linear code, a foundational construct extensively employed in communication, data transmission, and error correction, has been the subject of rigorous study for decades. Despite significant academic successes and widespread adoption, recent studies show that decoding methods for general linear codes, such as syndrome decoding, require the storage and search of large decoding tables, leading to inefficiencies. To mitigate this, Debris-Alazard et al. first proposed adapting Babai's algorithm and the LLL algorithm from lattice theory to binary codes, achieving considerable performance gains. Inspired by this, in this paper, we aim to explore the design of more general linear codes to overcome the limitations of baseline binary codes and enhance their applicability in more advanced applications such as DNA storage and 5G communication systems. To address this gap, we extend the foundational domain and decoding algorithms from lattices to q-ary codes. Specifically, we define a new fundamental domain and propose a polynomial-time decoding algorithm, RedtoFun. To validate our findings, we conduct a series of experiments to evaluate its real-world performance. The results demonstrate that our optimized RedtoFun algorithm surpasses the syndrome decoding scheme in terms of memory overhead and runtime while maintaining performance on par with the SizeRed decoding scheme.