Metraipolis › archive › dc_fd7f5e697c30

A General Plotkin-type Bound on Function-Correcting Codes with Wyner-Graham Distance — arXiv:2608.29573

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.29573
License (as archived): CC0-1.0
Archived: 2026-10-17T09:38:51.285Z
SHA-256 of the archived text: 306a0fba63ca451e4d389fd0bad85d346726c433372ef4d139d03e8e32df4792
Stable URL of this page: https://metraipolis.com/documento/dc_fd7f5e697c30

How to cite

A General Plotkin-type Bound on Function-Correcting Codes with Wyner-Graham Distance — arXiv:2608.29573 — arXiv (en), https://arxiv.org/abs/2608.29573 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fd7f5e697c30 (Metraipolis archive dc_fd7f5e697c30, sha256 306a0fba63ca451e4d389fd0bad85d346726c433372ef4d139d03e8e32df4792)

BibTeX

@misc{dcfd7f5e697c30,
  title = {A General Plotkin-type Bound on Function-Correcting Codes with Wyner-Graham Distance — arXiv:2608.29573},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.29573},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fd7f5e697c30; sha256 306a0fba63ca451e4d389fd0bad85d346726c433372ef4d139d03e8e32df4792},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.29573. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Function correcting codes (FCCs) are designed to protect a specified function evaluation of messages at a higher level than the level of protection for messages, against errors while reducing the redundancy required for reliable communication. FCCs have thus far been studied for channels matched to various distances, including the Hamming and Lee distances. Every function partitions the message space into preimage sets corresponding to its distinct function values. Existing Plotkin-type bounds on the optimal redundancy of FCCs under the studied distances, applicable to arbitrary functions on the message space, depend on the pairwise distances among all the message vectors. This makes these bounds difficult to compute. We derive a general Plotkin-type bound on the optimal redundancy of FCCs under Wyner Graham distances, which include the Hamming and Lee distances as special cases. Our bound depends only on the cardinalities of the preimage sets and the sum of pairwise distances only among vectors within each preimage set. This approach significantly reduces the computations required to evaluate the existing Plotkin-type bounds and yields simplified bounds that are easier to compute for specific functions. We obtain simplified Plotkin-type bound for linear functions under the Wyner-Graham distance. Furthermore, the existing simplified bounds for linear functions under the Hamming and Lee distances are recovered as special cases of the proposed bound. We also obtain simplified bounds for several important classes of functions, including the Hamming weight function, the Hamming weight distribution function, the monomial functions under the Hamming distance, and the modular sum function, the Lee weight function, and the Lee weight distribution function under the Lee distance.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in math.IT).
Categorie arXiv: Information Theory (cs.IT) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2608.29573 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T09:10:18.067Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).