🔢 mathematics

Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates

This paper investigates weakly constrained codes by proposing a capacity-achieving construction based on Eulerian cycles, deriving codes with linear minimum distance and positive rate through expurgation, and presenting a practical concatenated code scheme that enables polynomial-time encoding and decoding.

Original authors: Prachi Mishra, Sidharth Jaggi, Navin Kashyap, Michael Langberg

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Prachi Mishra, Sidharth Jaggi, Navin Kashyap, Michael Langberg

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message using a string of beads. In the old days of "constrained coding," the rules were very strict: "You are absolutely forbidden from putting two red beads next to each other." If you broke this rule, the message would be rejected. While this prevents errors, it also throws away a lot of potential messages, making your communication slower and less efficient.

This paper introduces a smarter, more flexible approach called Weakly Constrained Codes. Instead of banning specific patterns entirely, the rules simply say: "Red beads can appear, but they shouldn't appear too often, and they should appear about as often as blue beads." It's like a diet plan that doesn't ban pizza but asks you to eat it in moderation.

Here is how the authors solved the problem of making these flexible codes work, using three main steps:

1. The "Eulerian Cycle" Map (Building the Codebook)

To create these flexible codes, the authors used a mathematical map called a directed graph. Think of this graph as a city with intersections (vertices) and one-way streets (edges). Each street has a label (like a bead color).

To ensure the "moderation" rules are followed perfectly, they used a concept called an Eulerian Cycle. Imagine a delivery driver who must drive down every single street in the city exactly once before returning to the start.

The Magic: If the city is designed correctly, the sequence of streets the driver takes automatically guarantees that every type of street (bead pattern) appears exactly the right number of times.
The Result: They built a massive library of these "perfectly balanced" routes. This library is huge and achieves the maximum possible speed (capacity) for sending data under these flexible rules.

2. The "Bad Neighbor" Problem (Adding Error Correction)

The problem with the first step is that while the routes are balanced, they might be too similar to each other. If you send Route A and the receiver gets Route B (because of a glitch), they might not realize an error happened because the two routes look almost identical.

To fix this, the authors used a process called Expurgation (which is a fancy word for "weeding out").

The Analogy: Imagine a crowded party where everyone is wearing a similar outfit. If you want to find a group of people who are all distinct enough that you can tell them apart even if they swap a shirt, you have to kick out the people who look too much like their neighbors.
The Math: They mathematically proved that if you remove the "bad pairs" (routes that are too similar), you are left with a smaller, but still very large, group of routes. Crucially, this remaining group is so distinct that even if some beads get swapped or lost during transmission, the receiver can still figure out the original message. They proved this works for finite lengths of messages, not just in theory.

3. The "Russian Doll" Solution (Making it Practical)

There was one catch: The "weeding out" process in Step 2 is a theoretical magic trick. It proves such a code exists, but it doesn't tell you how to find the specific routes quickly. It would take a computer longer than the age of the universe to find the right route for a long message.

To solve this, they built a Concatenated Code (a code inside a code), like a set of Russian nesting dolls:

The Inner Code (The Small Doll): This is the "weeded-out" code from Step 2. It handles the tricky part of keeping the bead patterns balanced and ensuring the messages are distinct. Because it's small, the computer can look up the answers in a pre-made table very quickly.
The Outer Code (The Big Doll): This is a standard, well-known error-correcting code (Reed-Solomon) that wraps around the inner code. It handles the heavy lifting of fixing transmission errors.
The Result: By combining them, they created a system that is both fast (polynomial-time encoding/decoding) and robust. The outer code fixes the errors, while the inner code ensures the "bead diet" rules are never broken.

Summary of Achievements

The paper claims to have:

Built a library of messages that perfectly follow "frequency rules" (weak constraints) using Eulerian cycles.
Proven that you can pick a subset of these messages that are far enough apart to correct errors, without losing too much speed.
Created a practical system that combines these ideas so a computer can actually send and receive these messages quickly and reliably.

The authors specifically mention that this is useful for DNA data storage (where certain patterns of DNA letters cause errors) and other storage technologies, but they focus strictly on the mathematical construction and the ability to encode/decode these messages efficiently.

Technical Summary: Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates

Problem Statement
Constrained coding is essential for applications ranging from magnetic/optical storage to DNA-based data storage, where specific substrings (e.g., homopolymer runs in DNA) induce transmission errors or biochemical noise. Traditional constrained coding strictly forbids these patterns, often resulting in significant rate loss. "Weakly constrained codes" offer a relaxation where specific patterns are not forbidden but are instead required to occur with prescribed frequencies. While prior work established the existence of such codes and improved asymptotic rate bounds (e.g., via the Gilbert-Varshamov bound), these results were largely non-constructive. They proved the existence of codes with specific empirical statistics but lacked algorithmic mechanisms for codeword generation. Furthermore, existing constructions often lacked efficient encoding/decoding procedures or did not simultaneously guarantee error-correction capabilities (linear minimum distance) and positive rates for finite blocklengths.

Methodology
The authors propose a structural framework that models codewords as Eulerian cycles on a multigraph derived from a labeled directed graph representing the constrained system. The methodology proceeds in three stages:

Capacity-Achieving Construction via Eulerian Cycles:
The authors define a weakly constrained system where the empirical frequencies of edge traversals in a graph $G$ must match a target stationary Markov chain $\hat{P}$ exactly (zero tolerance). They construct a multigraph $G_n$ by replicating each edge $e$ exactly $nP(e)$ times. Since $\hat{P}$ is stationary, $G_n$ is balanced and Eulerian. A valid codeword corresponds to an Eulerian cycle in $G_n$ . To analyze the codebook size, they define a subset $C_{pool}$ consisting of sequences formed by a "typical" prefix of length $n' = \lfloor \alpha n \rfloor$ followed by a deterministic structural completion (the lexicographically first Eulerian path) that satisfies the global edge-count constraints.
Expurgation for Error Correction:
To introduce error-correction capability, the authors apply an expurgation argument to $C_{pool}$ . They define a "bad pair" of codewords as those whose relative Hamming distance falls below a target threshold $\delta$ . By modeling the generation of codewords as random walks on the graph (and product graphs for pairs), they utilize concentration inequalities (Bernstein's inequality) and the Large Deviation Principle (LDP) to bound the probability of forming bad pairs. They prove that a sufficiently large independent set (subcode $C_{ec}$ ) exists within $C_{pool}$ that maintains a linear minimum distance and a positive rate.
Concatenated Construction for Efficiency:
Recognizing that the expurgation-based approach is non-constructive and computationally inefficient, the authors propose a practical concatenated code. The expurgated code $C_{ec}$ serves as the inner code ( $C_{in}$ ), and a Reed-Solomon (RS) code serves as the outer code ( $C_{out}$ ). The inner code maps symbols to Eulerian cycles rooted at a fixed vertex, ensuring that concatenation preserves the Eulerian property (and thus the weak constraints). The outer code operates over an alphabet size $q$ (the largest prime power $\le |C_{ec}|$ ).

Key Contributions and Results

Capacity-Achieving Construction: The paper presents a construction of weakly constrained codebooks based on Eulerian cycles that asymptotically achieves the capacity of the constrained system. The rate of the constructed codebook approaches the entropy rate of the maxentropic Markov chain satisfying the constraints.
Existence of Error-Correcting Codes: Through expurgation, the authors establish the existence of weakly constrained codes with linear minimum distance and strictly positive rates for finite blocklengths.
Achievable Rate Analysis:
- Finite Blocklength: Using Bernstein's inequalities, the authors derive bounds on the failure probability (probability of a bad pair) and the resulting size of the expurgated code.
- Asymptotic Regime: Using the LDP, they derive achievable rates. In the limit, the rate converges to $\min(R_1, R_2)$ , where $R_1$ relates to an improved Gilbert-Varshamov bound ( $2H(P) - \sup H(Q)$ ) and $R_2$ relates to the entropy of the underlying chain. This matches the improved GV bound established by Marcus and Roth for constrained systems.
Polynomial-Time Implementation: The proposed concatenated scheme enables polynomial-time encoding and decoding. By scaling the inner blocklength $n$ logarithmically with the total blocklength ( $n = c_0 \log N_{con}$ ), the size of the inner codebook remains polynomial. The inner code is decoded via table lookup (minimum distance), and the outer code uses standard RS decoding. This construction preserves the weak constraints and amplifies the distance guarantees of the inner code.

Significance and Claims
The paper claims to bridge the gap between non-constructive existence proofs and practical code design for weakly constrained systems. Specifically, it provides:

A structural framework (Eulerian cycles on multigraphs) that explicitly models codewords with prescribed empirical statistics.
A constructive proof of the existence of error-correcting weakly constrained codes with linear minimum distance and positive rates, moving beyond non-constructive bounds.
A practical implementation strategy via concatenation that achieves polynomial-time encoding and decoding while maintaining the weak constraints and error-correction properties.

The authors note that their work addresses the need for codes that are not only capacity-achieving but also robust to errors and computationally feasible, which is critical for emerging applications like DNA storage. They conclude that their results provide a comprehensive framework jointly addressing capacity, error correction, and computational efficiency. Future work is noted to focus on improving finite-length rates through better concentration bounds and optimized codebook selection.

1. The "Eulerian Cycle" Map (Building the Codebook)

2. The "Bad Neighbor" Problem (Adding Error Correction)

3. The "Russian Doll" Solution (Making it Practical)

Summary of Achievements

More like this