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.


翻译:约束编码是编码理论中处理通过受限信道高效通信的基本领域。虽然具有固定约束的信道有通用的最优解,但越来越多的需要参数约束,这些约束取决于消息长度。一些作品通过迭代算法解决了这些参数约束,但它们需要特定于每个约束的复杂构造,以保证通过单调进展的收敛。在本文中,我们提出了一个通用的框架,通过一种新颖的简单迭代算法处理任何参数约束通道问题。通过将此迭代算法的执行减少到一个无环图遍历,我们证明了一个令人惊讶的结论,即在不需要任何单调进展的情况下保证收敛,并具有高效的平均时间复杂度。我们通过将其应用于各种本地和全局通道约束,展示了这个通用框架的有效性。我们首先探索了涉及各种长度非法子串的本地约束,其中通用构造基本上是迭代性地替换禁止窗口。我们将这种本地算法应用到了最小周期性、最小汉明重量、局部几乎平衡汉明重量和以前未解决的最小回文约束。然后,我们继续探索全局约束,并展示了该提出的构造在无重复编码、反向互补编码以及全局几乎平衡编码这些问题上的有效性。对于反向互补编码,我们还处理了一个以前未解决的重叠窗口版本的约束。总之,所提出的框架具有显著的易用性和同时集成多约束的能力,从而生成最先进的构造。

0
下载
关闭预览

相关内容

Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月23日
Arxiv
0+阅读 · 2023年5月18日
VIP会员
相关VIP内容
相关资讯
Multi-Task Learning的几篇综述文章
深度学习自然语言处理
15+阅读 · 2020年6月15日
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员