EUVIMEDEUVIMED entdecken
Crossref

Universal Framework for Parametric Constrained Coding

Adir Kobovich, Orian Leitersdorf, Daniella Bar-Lev, Eitan Yaakobi

IEEE Transactions on Information Theory · 2026-06 · 72 (6) · 3678-3692

DOI: 10.1109/tit.2026.3672710 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-06. Verfasst von Adir Kobovich und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: NSF, European Union [European Research Council (ERC), DNAStorage], Schmidt Sciences.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Constrained coding is a subfield of coding theory that tackles efficient communication under constraints. While fixed constraints (e.g., a fixed set of substrings may not appear in transmitted messages) have a general optimal solution, there is increasing demand for supporting parametric constraints that are dependent on the message length and portray some property (e.g., no $\log (n)$ consecutive zeros). Several works have tackled such parametric constraints through iterative algorithms, yet they require complex constructions specific to each constraint to guarantee convergence through monotonic progression. In this paper, we propose a universal framework for tackling any parametric constraint problem through a new simple iterative algorithm. By reducing an execution of this iterative algorithm to an acyclic graph traversal, we prove a surprising result that guarantees convergence with low average time complexity even without requiring any monotonic progression. We demonstrate the effectiveness of this universal framework, with much of our focus on the special case of single-symbol redundancy, while also considering a variety of both local and global constraints. We begin by exploring the local constraints involving illegal substrings of variable length, where the construction essentially iteratively replaces forbidden windows. This local algorithm is applied to various fundamental constraints, achieving state-of-the-art results through simple adaptations of the universal algorithm. We then continue by exploring global constraints, and demonstrate the effectiveness of the proposed construction on repeat-free encoding, reverse-complement encoding and DNA data storage. Overall, the proposed framework generates state-of-the-art constructions with significant ease while also enabling the simultaneous integration of multiple constraints for the first time.

Förderung

  • NSF
  • European Union [European Research Council (ERC), DNAStorage]
  • Schmidt Sciences

Zitieren

APA

Kobovich, A., Leitersdorf, O., Bar-Lev, D., & Yaakobi, E. (2026). Universal Framework for Parametric Constrained Coding. IEEE Transactions on Information Theory, 72(6), 3678-3692. https://doi.org/10.1109/tit.2026.3672710

Vancouver

Kobovich A, Leitersdorf O, Bar-Lev D, Yaakobi E. Universal Framework for Parametric Constrained Coding. IEEE Transactions on Information Theory. 2026;72(6):3678-3692. doi:10.1109/tit.2026.3672710

BibTeX
@article{Kobovich2026,
  author = {Kobovich, Adir and Leitersdorf, Orian and Bar-Lev, Daniella and Yaakobi, Eitan},
  title = {Universal Framework for Parametric Constrained Coding},
  journal = {IEEE Transactions on Information Theory},
  year = {2026},
  volume = {72},
  number = {6},
  pages = {3678--3692},
  doi = {10.1109/tit.2026.3672710}
}
Kostenlos starten →