Decoding Simultaneous Rational Evaluation Codes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2024

Decoding Simultaneous Rational Evaluation Codes

Matteo Abbondati
  • Fonction : Auteur
  • PersonId : 1238085
Eleonora Guerrini
Romain Lebreton

Résumé

In this paper, we deal with the problem of simultaneous reconstruction of a vector of rational numbers, given modular reductions containing errors (SRNRwE). Our methods apply as well to the simultaneous reconstruction of rational functions given evaluations containing errors (SRFRwE), improving known results [7 , 9]. In the latter case, one can take advantage of techniques from coding theory [4, 10] and provide an algorithm that extends classical Reed-Solomon decoding. In recent works [7 , 9], interleaved Reed-Solomon codes [3 , 19 ] are used to correct beyond the unique decoding capability in the case of random errors at the price of positive but small failure probability. Our first contribution is to extend these works to the simultaneous reconstruction with errors of rational numbers instead of functions. Thus considering rational number codes [ 16 ], we provide an algorithm decoding beyond the unique decoding capability and, as a central result of this paper, we analyze in detail its failure probability. Our analysis generalizes for the first time the best known analysis for interleaved Reed-Solomon codes [19] to SRFRwE, improving on the existing bound [8], to interleaved Chinese remainder codes, also improving the known bound [1], and finally for the first time to SRNRwE.
Fichier principal
Vignette du fichier
issac24.pdf (699.39 Ko) Télécharger le fichier

Dates et versions

lirmm-04628184 , version 1 (28-06-2024)

Identifiants

Citer

Matteo Abbondati, Eleonora Guerrini, Romain Lebreton. Decoding Simultaneous Rational Evaluation Codes. ISSAC 2024 - 49th International Symposium on Symbolic and Algebraic Computation, Jonathan Hauenstein, Jul 2024, Raleigh (North Carolina), United States. ⟨10.1145/3666000.3669686⟩. ⟨lirmm-04628184⟩
21 Consultations
23 Téléchargements

Altmetric

Partager

More