Universal Framework for Parametric Constrained Coding
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.
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}
}
EUVIMED