Constrained coding is a fundamental field in coding theory that tackles efficient communication through constrained channels. While channels with fixed constraints have a general optimal solution, there is increasing demand for parametric constraints that are dependent on the message length. 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 constrained-channel problem through a novel 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 the effectiveness of this universal framework by applying it to a variety of both local and global channel constraints. We begin by exploring the local constraints involving illegal substrings of variable length, where the universal construction essentially iteratively replaces forbidden windows. We apply this local algorithm to the minimal periodicity, minimal Hamming weight, local almost-balanced Hamming weight and the previously-unsolved minimal palindrome constraints. We then continue by exploring global constraints, and demonstrate the effectiveness of the proposed construction on the repeat-free encoding, reverse-complement encoding, and the open problem of global almost-balanced encoding. For reverse-complement, we also tackle a previously-unsolved version of the constraint that addresses overlapping windows. 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.
翻译:约束编码是编码理论中处理通过受限信道高效通信的基本领域。虽然具有固定约束的信道有通用的最优解,但越来越多的需要参数约束,这些约束取决于消息长度。一些作品通过迭代算法解决了这些参数约束,但它们需要特定于每个约束的复杂构造,以保证通过单调进展的收敛。在本文中,我们提出了一个通用的框架,通过一种新颖的简单迭代算法处理任何参数约束通道问题。通过将此迭代算法的执行减少到一个无环图遍历,我们证明了一个令人惊讶的结论,即在不需要任何单调进展的情况下保证收敛,并具有高效的平均时间复杂度。我们通过将其应用于各种本地和全局通道约束,展示了这个通用框架的有效性。我们首先探索了涉及各种长度非法子串的本地约束,其中通用构造基本上是迭代性地替换禁止窗口。我们将这种本地算法应用到了最小周期性、最小汉明重量、局部几乎平衡汉明重量和以前未解决的最小回文约束。然后,我们继续探索全局约束,并展示了该提出的构造在无重复编码、反向互补编码以及全局几乎平衡编码这些问题上的有效性。对于反向互补编码,我们还处理了一个以前未解决的重叠窗口版本的约束。总之,所提出的框架具有显著的易用性和同时集成多约束的能力,从而生成最先进的构造。