Universal Framework for Parametric Constrained Coding
Adir Kobovich, Orian Leitersdorf, Daniella Bar-Lev, Eitan Yaakobi · 2024
Constrained coding is a fundamental field in coding theory that tackles efficient communication through constrained channels. 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 that the substrings must satisfy (e.g., no log (n) consecutive zeros). Several works have tackled such parametric constraints through iterative algorithms following the sequence-replacement approach, yet this approach requires complex constraint-specific properties to guarantee convergence through monotonic progression. In this paper, we propose a universal framework for tackling any parametric constraint problem with far fewer requirements, through a 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 efficient average time complexity even without requiring any monotonic progression. We demonstrate how to apply this algorithm to the run-length-limited, minimal Hamming weight, local almost-balanced Hamming weight constraints, as well as repeat-free and secondary-structure constraints. Overall, this framework enables state-of-the-art results with minimal effort.