🔢 mathematics

Linear Code Conversion in the Merge Regime: General Bounds and Reed--Muller Constructions

This paper establishes universal lower bounds on read and write costs for scalar linear code conversion in the merge regime using generalized Hamming weights, and demonstrates that explicit Reed-Muller constructions via Plotkin decomposition can achieve these bounds in specific parameter regimes.

Original authors: Anina Gruica, Benjamin Jany, Stanislav Kruglik

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anina Gruica, Benjamin Jany, Stanislav Kruglik

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 books stored across thousands of servers. To keep these books safe if a server crashes, the library doesn't just make simple copies (which wastes space); instead, it uses a clever math trick called erasure coding. This splits each book into pieces and scatters them, so you can rebuild the whole book even if some pieces are missing.

However, the "rules" for how to split and scatter these pieces (the code parameters) aren't always perfect forever. Sometimes, the library needs to change its strategy—maybe to save space or handle more traffic. When they do this, they usually have to re-encode everything. This is like taking every single book out of the shelves, reading every page, and rewriting the whole thing from scratch. It's slow, expensive, and uses up a lot of energy.

This paper introduces a smarter way to do this: Code Conversion. Instead of rewriting everything, you want to "merge" your old storage rules into new ones by only touching the parts that must change.

Here is the breakdown of the paper's ideas using simple analogies:

1. The Problem: The "Merge"

Imagine you have several small teams of workers (initial codes), each with their own way of organizing files. Suddenly, you need to merge all these teams into one big, efficient team (the final code).

The Old Way: Fire everyone, hire a new team, and have them re-read every single file to organize it under the new system. (High cost).
The New Way (Code Conversion): Keep the files that are already in the right place. Only read the files you need to calculate the new pieces, and write down only the new pieces. The goal is to touch as few files as possible.

2. The Two Costs: Reading vs. Writing

The paper measures efficiency in two ways:

Read Cost: How many files do you have to open and look at to figure out the new organization?
Write Cost: How many new files do you have to create and save?

The authors want to find the absolute minimum number of files you must read or write, no matter how clever your math is.

3. The New Tool: "Generalized Hamming Weights"

Previous research mostly looked at simple codes (like MDS codes) and used basic math to find these minimums. This paper says, "Wait, there's a deeper layer of math we haven't fully used yet."

They use a concept called Generalized Hamming Weights.

The Analogy: Imagine the code is a building.
- Minimum Distance (the old tool) is like checking if the building can stand if you remove one brick. It tells you about the weakest single point.
- Generalized Hamming Weights (the new tool) are like checking if the building stands if you remove one brick, then two bricks, then three bricks, and so on. It maps out how the building's support grows as you remove more parts.

The authors show that by looking at this "growth map" of the building's support, they can prove that for certain types of storage systems, you cannot get away with reading as few files as the old, simpler math suggested. Their new math gives a stricter, more accurate "floor" for the costs.

4. The Solution: Reed-Muller Codes

The authors didn't just make up theory; they built a specific example using Reed-Muller codes (a type of math structure often used in space communications and modern storage).

How they did it: They used a special recipe called the Plotkin decomposition. Think of this as a way to take two smaller, simpler storage blocks and snap them together to form a larger, more complex block without losing the original pieces.
The Result:
- Writing: Their new method is perfect. It writes exactly the minimum number of new files required by the laws of math. It's as efficient as physically possible.
- Reading: For one part of the system, their method is also perfect. For the other part, they found a gap. Their new math says, "You must read at least X files," but their current construction reads a bit more than X. They haven't found the perfect way to read yet, but they know exactly how far off they are.

Summary of the Takeaway

This paper provides a universal rulebook for anyone trying to upgrade their data storage system without re-reading everything.

They proved that for any linear code, there are hard limits on how much data you must read or write.
They showed that using a deeper mathematical tool (Generalized Hamming Weights) gives you a sharper, more accurate picture of these limits than before.
They built a specific, working example using Reed-Muller codes that hits the "perfect" mark for writing data, proving that these efficient conversions are possible.

In short: They figured out the theoretical speed limit for upgrading storage systems and built a car that hits that limit for one of the two main tasks (writing), while showing exactly how much faster the other task (reading) could potentially be.

Technical Summary: Linear Code Conversion in the Merge Regime

Problem Statement
In large-scale distributed storage systems, erasure codes are essential for reliability, but optimal code parameters often change over time due to varying node failure rates and workload patterns. Adapting these parameters typically requires re-encoding data, which incurs high access costs (reading and writing numerous symbols). While "convertible codes" were introduced to minimize this cost by converting data from an initial code to a final code without full re-encoding, existing literature has largely focused on specific code families, such as Maximum Distance Separable (MDS) codes or Locally Repairable Codes (LRCs). There is a lack of a general framework providing universal bounds on access costs for arbitrary linear codes, particularly in the "merge regime" where multiple initial codewords are combined into fewer final codewords.

Methodology
The authors develop a universal framework for scalar linear code conversion in the merge regime. The core methodology relies on linear-algebraic constraints and the properties of subcodes rather than specific code constructions.

Generalized Hamming Weights (GHW): The paper utilizes GHWs to analyze the support growth of subcodes. Unlike minimum-distance arguments, which only capture one-dimensional subcodes, GHWs capture the support properties of higher-dimensional subcodes.
Support Constraints: The framework establishes that unchanged symbols and read symbols impose specific support constraints on subcodes of the final code.
Wei Duality: The authors employ Wei duality to relate the generalized Hamming weights of a code to those of its dual, allowing for refined bounds based on standard code parameters (length, dimension, and dual distance).
Reed–Muller Construction: To demonstrate the framework's applicability, the authors construct explicit convertible Reed–Muller codes using the Plotkin decomposition. This construction exploits the recursive structure of Reed–Muller codes to define a conversion map.

Key Contributions

Universal Lower Bounds: The paper derives universal lower bounds on the write cost (number of new symbols) and read cost (number of symbols read) for converting between arbitrary linear codes in the merge regime.
Refinement via GHW: The bounds are refined using generalized Hamming weights. The authors show that these refined bounds are at least as strong as those derived from minimum distance alone and can be strictly stronger when the final code exhibits nontrivial jumps in its generalized Hamming weight hierarchy.
Recovery of Known Results: The framework successfully recovers known bounds for MDS codes and LRCs in special cases, validating its generality.
Explicit Construction: An explicit Reed–Muller convertible code is constructed for the merge regime ( $\lambda=2$ ). This construction uses the Plotkin sum decomposition to map initial codes $RM(r, m-1)$ and $RM(r-1, m-1)$ to a final code $RM(r, m)$.

Results

Write Cost: For the Reed–Muller construction in the parameter regime $m = r + 2$ , the construction attains the derived write-cost lower bound. Specifically, the number of unchanged symbols matches the upper bounds provided by both the minimum-distance analysis and the GHW analysis (where the latter sharpens the bound for the second initial block).
Read Cost: The analysis of read costs yields mixed results regarding optimality:
- For one initial block ( $R_2$ ), the GHW-based lower bound is sharp for $m \geq 5$ , matching the construction's performance.
- For the other initial block ( $R_1$ ), the GHW analysis improves the lower bound significantly (from a constant value to $m-1$ ), but a gap remains between this lower bound and the actual read cost of the construction.
Comparison with Existing Bounds: The paper demonstrates that for codes with nontrivial GHW hierarchies, the proposed bounds are strictly stronger than those relying solely on minimum distance. In the case of optimal LRCs, the bounds coincide with existing results, but the framework extends to arbitrary linear codes and conversions between different code families.

Significance
The paper claims to provide the first general framework for bounding access costs in linear code conversion that is not restricted to specific code families like MDS or LRCs. By separating the conversion cost forced by linear-algebraic constraints from costs dependent on specific code structures, the work offers a baseline for evaluating future constructions. The application to Reed–Muller codes is significant because, while these codes are increasingly relevant for distributed storage with heterogeneous request patterns, they had not previously been studied from the perspective of code conversion. The results suggest that Reed–Muller codes can support efficient conversion with optimal write costs, though the read cost for certain configurations remains an open optimization problem. The authors note that the journal version refines the conference presentation by formally proving that the GHW-based bounds recover known results and can be strictly stronger, while providing more detailed proofs and motivation.