🔢 mathematics

Constructions of locally repairable codes via concatenated codes

This paper proposes a systematic construction of optimal binary locally repairable codes using concatenated codes with linear outer codes over $\mathbb{F}_4$ , determining their weight distributions and achieving new bounds for locality $r=2$ while producing classes of codes that meet the Griesmer-like bound and are perfect.

Original authors: Hengfeng Jin, Fang-Wei Fu

Published 2026-05-07

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Hengfeng Jin, Fang-Wei Fu

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 have a massive library of digital files stored across thousands of different hard drives (nodes) in a data center. The goal is to keep this data safe even if some drives break.

The Problem: The "Repair" Bottleneck
Traditionally, if one drive fails, the system might have to look at many other drives to reconstruct the missing piece. This is slow and uses up a lot of network bandwidth.

The Solution: Locally Repairable Codes (LRCs)
This paper introduces a smarter way to store data called Locally Repairable Codes (LRCs). Think of it like organizing your library into small, self-contained "neighborhoods."

If a book (a piece of data) goes missing from one shelf, you don't need to search the whole library. You only need to look at a tiny, specific group of neighboring shelves (called a "repair group") to fix it.
In this paper, the authors focus on binary LRCs, which are special because they use only "0s" and "1s." This makes the repair process incredibly fast and simple, like using a basic calculator instead of a supercomputer.

The Magic Trick: Concatenated Codes (The "Russian Doll" Method)
The authors' main innovation is a construction method they call concatenated codes. Imagine building a complex machine by nesting two simpler machines inside each other:

The Inner Code (The Local Repair Group): This is a small, simple code that handles the immediate repair. In this paper, it's a tiny group of 3 drives where any 2 can fix the 3rd.
The Outer Code (The Master Plan): This is a larger, more complex code that oversees the whole system. The authors chose to build this "Master Plan" using a special mathematical language called F4 (which uses four symbols instead of just two).

How They Did It
The paper claims that by taking a perfect "Master Plan" (the Outer Code) written in the F4 language and wrapping it around the simple "Local Repair Groups" (the Inner Code), they can create a binary LRC that is mathematically optimal.

They didn't just guess; they provided a systematic recipe:

Step 1: Pick a specific type of high-quality code from the F4 world (like a "Perfect Code" or a "Griesmer Code").
Step 2: Use the "Russian Doll" method to wrap it in the binary inner code.
Step 3: The result is a binary LRC that hits the theoretical "gold standard" limits for efficiency and error correction.

Key Achievements
The authors successfully built several types of these "Gold Standard" codes:

Perfect LRCs: These are like a puzzle where every single piece fits perfectly with no wasted space. If a drive fails, the system recovers with 100% efficiency.
Nearly Perfect LRCs: These are almost as good as the perfect ones, hitting the best possible limits known in mathematics for their size.
Weight Distributions: The paper also explains exactly how "heavy" the errors are in these codes. Think of this as knowing exactly how many books are missing in different scenarios, which helps the system predict how hard it will be to fix them.

A Specific Improvement
For a specific scenario where the repair group size is exactly 2 (meaning you need 2 neighbors to fix a broken drive), the authors found a flaw in a previous mathematical rule (the "Johnson-like bound"). They tightened this rule, making it more accurate, and then built codes that actually reach this new, stricter limit.

In Summary
This paper is a blueprint. It says: "If you want to build the most efficient, fast-repairing binary storage system possible, take a specific type of advanced code from the 'F4' mathematical world, wrap it in our simple '3-drive' repair structure, and you will get a system that cannot be mathematically improved upon." They provide the exact list of which "F4" codes to use to get these perfect results.

Technical Summary: Constructions of Locally Repairable Codes via Concatenated Codes

Problem Statement
Locally repairable codes (LRCs) are essential for distributed storage systems, offering low storage costs and efficient data recovery by allowing failed symbols to be repaired using a small number of other symbols (locality $r$ ). While significant research has focused on LRCs over large finite fields, binary LRCs are particularly desirable for practical implementation due to the elimination of multiplication operations during encoding, decoding, and repair. However, the construction of optimal binary LRCs remains challenging. Existing bounds, such as the Singleton-like bound, often fail to account for field size constraints, leading to loose bounds for binary codes. Furthermore, while previous works have established field-size-dependent bounds (e.g., C-M bound, Griesmer-like bound, Johnson-like bound), explicit constructions of binary LRCs that meet these bounds, particularly for locality $r=2$ , have been limited. Additionally, the weight distributions of constructed LRCs are often difficult to characterize, which is critical for analyzing decoding error probabilities.

Methodology
The authors propose a systematic construction of binary LRCs using concatenated codes. The framework utilizes a specific inner code and a carefully selected outer code:

Inner Code: A fixed $[3, 2, 2]$ linear code over $\mathbb{F}_2$ with parity-check matrix $H_{in} = (1, 1, 1)$ . This inner code ensures the resulting concatenated code has locality $r=2$ with disjoint local repair groups.
Outer Code: A linear code $C$ over $\mathbb{F}_4$ with parameters $[n_1, k_1, d_1]$ .
Concatenation: The authors define a one-to-one mapping from $\mathbb{F}_4$ to the inner code. The resulting concatenated code $C'$ is a binary $[n=3n_1, k=2k_1, d=2d_1; r=2]$ LRC.
Weight Distribution Analysis: A key methodological contribution is the derivation of the relationship between the weight distributions of the outer code $C$ and the concatenated code $C'$ . The authors prove that the weight distribution of $C'$ is directly determined by that of $C$ , specifically with $A_{2j}(C') = A_j(C)$ and $A_{2j-1}(C') = 0$ .

Key Contributions and Results

Systematic Construction Framework: The paper establishes a systematic approach to select outer codes over $\mathbb{F}_4$ to generate optimal binary LRCs. This contrasts with previous existence proofs by providing explicit construction criteria.
Optimal Binary LRCs via Griesmer-like Bound:
- The authors demonstrate that outer codes over $\mathbb{F}_4$ achieving the classical Griesmer bound yield binary LRCs that attain the Griesmer-like bound for LRCs.
- Specific classes of optimal codes are constructed, including those derived from non-trivial MDS codes over $\mathbb{F}_4$ , generalized MacDonald codes, and Solomon-Stiffler codes.
- Examples include binary LRCs with parameters such as $[27, 4, 14; 2]$ and $[48, 8, 22; 2]$ .
Perfect and Nearly Perfect Binary LRCs:
- Perfect LRCs: By selecting outer codes over $\mathbb{F}_4$ that are perfect (meeting the sphere-packing bound), the authors construct binary perfect LRCs. The weight distributions of these codes are explicitly derived. For instance, using Hamming codes over $\mathbb{F}_4$ yields perfect binary LRCs with parameters like $[15, 6, 6; 2]$ .
- Nearly Perfect LRCs: The paper constructs nearly perfect binary LRCs by utilizing outer codes that meet the Johnson bound (e.g., the hexacode over $\mathbb{F}_4$ ).
Improved Johnson-like Bound for $r=2$ :
- For the specific case of locality $r=2$ with disjoint local repair groups, the authors improve upon the Johnson-like bound previously established by Ma and Ge.
- They derive a tighter bound on the dimension $k$ of binary LRCs by refining the counting argument for constant weight codes within the dual space.
- Explicit constructions are provided that attain this new, improved bound, such as a binary LRC with parameters $[51, 26, 8; 2]$ derived from a maximal cap in $PG(3, 4)$.

Significance
The paper claims that its primary significance lies in providing a unified and systematic method for constructing optimal binary LRCs. By leveraging the rich theory of linear codes over $\mathbb{F}_4$ , the authors successfully bridge the gap between theoretical bounds and explicit binary constructions. The ability to determine the exact weight distributions of the resulting LRCs based on the outer codes is a notable advancement, as this information is crucial for performance analysis in erasure channels. Furthermore, the improvement of the Johnson-like bound for $r=2$ and the subsequent construction of codes meeting this bound demonstrate a deeper understanding of the structural limits of binary LRCs. The authors conclude that well-designed linear codes over $\mathbb{F}_4$ serve as effective building blocks for high-performance binary LRCs in practical distributed storage applications. Future work is identified as extending these systematic selection rules to the general case where $r > 2$ .

More like this