Simultaneous Rational Number Codes: Decoding Beyond Half the Minimum Distance with Multiplicities and Bad Primes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913876346404864 |
|---|---|
| author | Abbondati, Matteo Guerrini, Eleonora Lebreton, Romain |
| author_facet | Abbondati, Matteo Guerrini, Eleonora Lebreton, Romain |
| contents | In this paper, we extend the work of (Abbondati et al., 2024) on decoding simultaneous rational number codes by addressing two important scenarios: multiplicities and the presence of bad primes (divisors of denominators). First, we generalize previous results to multiplicity rational codes by considering modular reductions with respect to prime power moduli. Then, using hybrid analysis techniques, we extend our approach to vectors of fractions that may present bad primes. Our contributions include: a decoding algorithm for simultaneous rational number reconstruction with multiplicities, a rigorous analysis of the algorithm's failure probability that generalizes several previous results, an extension to a hybrid model handling situations where not all errors can be assumed random, and a unified approach to handle bad primes within multiplicities. The theoretical results provide a comprehensive probabilistic analysis of reconstruction failure in these more complex scenarios, advancing the state of the art in error correction for rational number codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08472 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simultaneous Rational Number Codes: Decoding Beyond Half the Minimum Distance with Multiplicities and Bad Primes Abbondati, Matteo Guerrini, Eleonora Lebreton, Romain Information Theory Symbolic Computation In this paper, we extend the work of (Abbondati et al., 2024) on decoding simultaneous rational number codes by addressing two important scenarios: multiplicities and the presence of bad primes (divisors of denominators). First, we generalize previous results to multiplicity rational codes by considering modular reductions with respect to prime power moduli. Then, using hybrid analysis techniques, we extend our approach to vectors of fractions that may present bad primes. Our contributions include: a decoding algorithm for simultaneous rational number reconstruction with multiplicities, a rigorous analysis of the algorithm's failure probability that generalizes several previous results, an extension to a hybrid model handling situations where not all errors can be assumed random, and a unified approach to handle bad primes within multiplicities. The theoretical results provide a comprehensive probabilistic analysis of reconstruction failure in these more complex scenarios, advancing the state of the art in error correction for rational number codes. |
| title | Simultaneous Rational Number Codes: Decoding Beyond Half the Minimum Distance with Multiplicities and Bad Primes |
| topic | Information Theory Symbolic Computation |
| url | https://arxiv.org/abs/2504.08472 |