Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates
It addresses the problem of designing codes with prescribed pattern frequencies, offering theoretical and practical constructions for weakly constrained coding.
The paper proposes a capacity-achieving construction of weakly constrained codes using Eulerian cycles and obtains codes with linear minimum distance and positive rate via expurgation, along with a practical concatenated code with polynomial-time encoding and decoding.
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.