A matrix based list decoding algorithm for linear codes over integer residue rings
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/113405
Título: | A matrix based list decoding algorithm for linear codes over integer residue rings |
---|---|
Autor/es: | Napp, Diego | Pinto, Raquel | Saçıkara, Elif | Toste, Marisa |
Grupo/s de investigación o GITE: | Grupo de Álgebra y Geometría (GAG) |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Matemáticas |
Palabras clave: | Finite rings | Linear codes over finite rings | Erasure channel | Decoding algorithms | Matrix representations | Parity-check matrix |
Área/s de conocimiento: | Álgebra |
Fecha de publicación: | 1-abr-2021 |
Editor: | Elsevier |
Cita bibliográfica: | Linear Algebra and its Applications. 2021, 614: 376-393. https://doi.org/10.1016/j.laa.2020.09.031 |
Resumen: | In this paper we address the problem of list decoding of linear codes over an integer residue ring Zq, where qis a power of a prime p. The proposed procedure exploits a particular matrix representation of the linear code over Zpr, called the standard form, and the p-adic expansion of the to-be-decoded vector. In particular, we focus on the erasure channel in which the location of the errors is known. This problem then boils down to solving a system of linear equations with coefficients in Zpr. From the parity-check matrix representations of the code we recursively select certain equations that a codeword must satisfy and have coefficients only in the field pr−1Zpr. This yields a step by step procedure obtaining a list of the closest codewords to a given received vector with some of its coordinates erased. We show that such an algorithm actually computes all possible erased coordinates, that is, the provided list is minimal. |
Patrocinador/es: | This work of the second and forth authors is supported by the Center for Research and Development in Mathematics and Applications (CIDMA) through the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia), references UIDB/04106/2020 and UIDP/04106/2020. The first author partially supported by Ministerio de Ciencia e Innovación via the grant with ref. PID2019-108668GB-I00. The third author is supported by the Swiss Confederation through the Swiss Government Excellence Scholarship no: 2019.0413 and by the Swiss National Science Foundation grant n. 188430. |
URI: | http://hdl.handle.net/10045/113405 |
ISSN: | 0024-3795 (Print) | 1873-1856 (Online) |
DOI: | 10.1016/j.laa.2020.09.031 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © 2020 Published by Elsevier Inc. |
Revisión científica: | si |
Versión del editor: | https://doi.org/10.1016/j.laa.2020.09.031 |
Aparece en las colecciones: | INV - GAG - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
Napp_etal_2021_LinearAlgebraApplicat_final.pdf | Versión final (acceso restringido) | 347,39 kB | Adobe PDF | Abrir Solicitar una copia |
Napp_etal_2021_LinearAlgebraApplicat_preprint.pdf | Preprint (acceso abierto) | 252,53 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.