PreprintCC BY 4.0arXiv
Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates
Abstract
We investigate weakly constrained codes, in which specific patterns occur with prescribed frequencies rather than being strictly forbidden as in conventional constrained coding. We propose a capacity-achieving construction of a weakly constrained codebook based on Eulerian cycles. We then obtain, via expurgation, weakly constrained codes with linear minimum distance and positive rate, and analyze the rates achievable. Finally, we propose a practical concatenated code construction that supports polynomial-time encoding and decoding.
Related
- Plotkin-Like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels
- The Transmitter Trojan Channel: Achievable Rates and Error Exponents
- Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality
- Generalized Function-Correcting Partition Codes: Bounds and constructions
- Four New Single-Error-Correcting Binary Codes
BibTeX
@misc{mishra2026errorcorrecting,
title = {{Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates}},
author = {Prachi Mishra and Sidharth Jaggi and Navin Kashyap and Michael Langberg},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2605.09113},
eprint = {2605.09113},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.09113},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates
AU - Prachi Mishra
AU - Sidharth Jaggi
AU - Navin Kashyap
AU - Michael Langberg
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2605.09113
UR - https://arxiv.org/abs/2605.09113
AB - We investigate weakly constrained codes, in which specific patterns occur with prescribed frequencies rather than being strictly forbidden as in conventional constrained coding. We propose a capacity-achieving construction of a weakly constrained codebook based on Eulerian cycles. We then obtain, via expurgation, weakly constrained codes with linear minimum distance and positive rate, and analyze the rates achievable. Finally, we propose a practical concatenated code construction that supports polynomial-time encoding and decoding.
ER -