TU2.R3.1

Universal Framework for Parametric Constrained Coding

Adir Kobovich, Orian Leitersdorf, Daniella Bar-Lev, Eitan Yaakobi, Technion - Israel Institute of Technology, Israel

Session:
Codes for Storage 2

Track:
2: Modern Coding Theory

Location:
Ypsilon IV-V-VI

Presentation Time:
Tue, 9 Jul, 11:30 - 11:50

Session Chair:
Rawad Bitar,
Abstract
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 \emph{parametric} constraints that are dependent on the message length and portray some property that the substrings must satisfy (e.g., no $\boldsymbol{\log(n)}$~consecutive zeros). Several works have tackled such parametric constraints through \emph{iterative} algorithms following the sequence-replacement approach, yet this approach requires complex constraint-specific properties to guarantee convergence through \emph{monotonic progression}. In this paper, we propose a universal framework for tackling \emph{any} parametric constraint problem with far fewer requirements, through a \emph{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 \emph{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.
Resources