🔢 mathematics

Function-Correcting Codes for Insertion-Deletion Channel

This paper proposes a new framework of function-correcting codes for insertion-deletion channels, establishes the equivalence of its various formulations, derives fundamental bounds on optimal redundancy and code length, and analyzes specific performance limits for several classes of functions.

Original authors: Anamika Singh, Abhay Kumar Singh

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anamika Singh, Abhay Kumar Singh

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 sending a secret message across a noisy, chaotic river. In the world of traditional coding, the river might swap a few letters (like turning an "A" into a "B"). But in this paper, the authors tackle a much messier river: one that randomly drops letters out of your message or adds extra, random letters into it. This is called an "insertion-deletion" channel.

If you lose a letter, the whole message shifts. The word "HELLO" might become "HLLLO" or "HELO." In this chaos, trying to reconstruct the entire original message is like trying to rebuild a shattered vase just by looking at the pieces; it requires a lot of extra "glue" (redundancy) to make sure nothing is lost.

The Big Idea: Do You Need the Whole Vase?

The authors ask a simple question: Do you really need the whole message?

Often, you just need to know a specific fact about the message.

Scenario A: You send a long document. You don't need the decoder to read every word. You just need to know: "Is this document version 1 or version 2?"
Scenario B: You are storing DNA data. You don't need the whole genetic sequence; you just need to know: "How many times does this specific pattern repeat?"

This is where Function-Correcting Codes (FCCs) come in. Instead of trying to save the whole message, these codes are designed to save just the answer to a specific question (the function). This usually requires much less "glue" (redundancy) than saving the whole message.

The Problem: The "Slippery" River

The paper points out a tricky problem. When you add extra "glue" to a message to protect it, and then the river drops or adds letters, the glue and the message can get mixed up in a weird way.

Think of it like two people walking side-by-side holding hands.

Old Way (Substitution Errors): If one person changes their shirt color, it's easy to spot.
New Way (Insertion/Deletion): If one person drops a step or takes a double-step, the other person might accidentally grab the wrong hand of the person next to them. The "alignment" breaks.

The authors discovered that if your "glue" (redundancy) is shorter than your "message," this mixing gets so bad that the system fails. To fix this, they proved that the glue must be at least as long as the message to work properly in this chaotic river.

The New Toolkit: "Distance Matrices"

To solve this, the authors invented a new way to measure how "far apart" two messages are in this chaotic river. They call these Insdel-Distance Matrices.

Imagine you are trying to park two cars in a crowded lot where people keep randomly adding or removing obstacles.

Old Math: "How many spots are different?" (Hamming distance).
New Math: "How many steps do I have to take to move Car A into Car B's spot, accounting for people jumping in and out of the way?"

They created two types of maps (matrices) to calculate this:

Type 1: A basic map.
Type 2: A "super-map" that accounts for the extra chaos when the glue is long. They found that for the system to work, you must use the super-map.

The Results: Saving Money on DNA and Files

The paper tests this new system on four specific types of "questions" (functions) that are common in real life:

The VT-Syndrome: A specific math check used to fix single errors.
Number-of-Runs: Counting how many times the pattern switches (e.g., in DNA, how many times the sequence switches from "A" to "T").
Maximum Run-Length: Finding the longest stretch of identical letters (e.g., the longest string of "AAAAA").
Locally Bounded Functions: Questions where the answer doesn't change wildly even if the message gets slightly messy.

The Findings:

They calculated the minimum amount of extra data needed to guarantee the answer is correct for each of these questions.
They found that for questions like "How many runs are there?", you can save a massive amount of data compared to trying to save the whole message.
They provided mathematical "floor" and "ceiling" limits (bounds) to tell engineers exactly how efficient these codes can possibly be.

Why This Matters (According to the Paper)

The authors specifically highlight two areas where this is crucial:

DNA Data Storage: Storing data in synthetic DNA is expensive. Insertions and deletions are the main errors in DNA. If you only need to check a "synchronization marker" or a "run-length" property rather than the whole DNA strand, you can synthesize much less DNA, saving huge amounts of money.
File Synchronization: When syncing documents, you often just need to verify a "checksum" or a "version ID" to know if files match, rather than re-downloading the whole file.

Summary

The paper builds a new mathematical bridge for sending messages through a river that drops and adds letters. Instead of trying to save the whole message, they show you how to build a tiny, efficient lifeboat that only saves the specific fact you need. They proved that to do this safely, your lifeboat (redundancy) needs to be big enough to handle the river's chaos, and they gave the exact blueprints for how to build these lifeboats for the most common types of questions asked in DNA storage and file syncing.

Technical Summary: Function-Correcting Codes for Insertion-Deletion Channels

Problem Statement
Traditional error-correcting codes (ECCs) are designed to recover the exact transmitted message. However, in many applications such as distributed computing, archival storage, and DNA data storage, the decoder often requires only a specific function of the message (e.g., a checksum, a synchronization marker, or a constraint-related property) rather than the full message reconstruction. While "function-correcting codes" (FCCs) have been developed for substitution-based metrics (Hamming, symbol-pair, Lee), they rely on the property that distance is additive across systematic splits. This property does not hold for insertion-deletion (insdel) channels, where errors disrupt the alignment between transmitted and received sequences. In insdel channels, cross-block alignment between concatenated words can reduce the distance of a concatenation, rendering standard FCC frameworks inapplicable. The paper addresses the challenge of optimizing redundancy for FCCs specifically tailored to insertion-deletion channels.

Methodology and Framework
The authors propose a new coding framework for function-correcting insertion-deletion codes (FCIDCs). The core methodology involves:

Equivalence of Formulations: The paper defines function-correcting deletion codes, insertion codes, and insdel codes. It proves that these three formulations are equivalent for a given function $f$ and error tolerance $t$ . Specifically, a code can correct up to $t$ deletions (or insertions) if and only if the insdel distance between codewords corresponding to distinct function values is at least $2t + 2$ .
Handling Cross-Block Alignment: A critical technical hurdle identified is that for systematic encodings $\psi(x) = (x, p(x))$ , the insdel distance $d_{ID}(\psi(x), \psi(y))$ can be significantly lower than the sum of the distances of the message and redundancy parts due to cross-block longest common subsequence (LCS) effects. The authors derive the bound:
$d_{ID}(\psi(x), \psi(y)) \geq d_{ID}(x, y) + d_{ID}(p(x), p(y)) - 2\min\{k, r\}$
where $k$ is the message length and $r$ is the redundancy length.
Irregular Insdel-Distance Codes: To manage the non-additive nature of the metric, the authors introduce insdel-distance matrices ( $I^{(1)}_f$ $I_{f}^{(1)}$ and $I^{(2)}_f$ $I_{f}^{(2)}$ ) and irregular insdel-distance codes.
- Type 1 Matrices ( $I^{(1)}_f$ ): Define constraints based on $2t + 2 - d_{ID}(x, y)$ .
- Type 2 Matrices ( $I^{(2)}_f$ ): Include an additional $+2k$ term to compensate for the worst-case cross-block LCS loss.
  The authors demonstrate that non-trivial systematic FCIDCs are only feasible in the regime where redundancy $r \geq k$ . If $r < k$ , the message vectors themselves must already satisfy the constraints of a classical $t$ -insdel code, offering no redundancy savings.
Bounds Derivation: The paper establishes a relationship between the optimal redundancy $r^f_{ID}(k, t)$ $r_{I D}^{f} (k, t)$ and the shortest achievable length of irregular insdel-distance codes, denoted $N^{(1)}_{ID}$ $N_{I D}^{(1)}$ and $N^{(2)}_{ID}$ $N_{I D}^{(2)}$ . Using this relationship, the authors derive:
- Plotkin-like bounds: Adapted from Hamming metric bounds using the relation $d_H \geq \frac{1}{2}d_{ID}$ .
- Gilbert-Varshamov-like bounds: Derived using supersequence arguments and run-based counting, acknowledging that insdel ball sizes are center-dependent (unlike the uniform spheres in Hamming space).

Key Contributions

Unified Framework: Introduction of FCIDCs and proof of the equivalence between deletion, insertion, and combined insdel correction for function recovery.
Theoretical Tools: Definition of irregular insdel-distance codes and distance matrices that account for cross-block alignment losses, establishing that $r \geq k$ is a necessary condition for systematic gains.
General Bounds: Derivation of lower and upper bounds on optimal redundancy for arbitrary functions, including simplified bounds for specific function classes.
Specific Function Analysis: Application of the framework to four specific classes of functions native to the insdel metric:
1. VT-Syndrome Function: Bounds derived for the weighted sum of bit positions.
2. Number-of-Runs Function: Analysis of the count of maximal contiguous blocks of identical symbols.
3. Maximum-Run-Length Function: Analysis of the length of the longest contiguous block.
4. Locally Bounded Functions: Extension of the locally $(\lambda, \rho)$ -function concept to the insdel metric.

Results
The paper provides explicit lower and upper bounds for the optimal redundancy of FCIDCs for the identified function classes:

VT-Syndrome: The redundancy is bounded between $\frac{2tk}{k+1}$ and a logarithmic expression involving $k$ and $t$ .
Number-of-Runs and Maximum-Run-Length: The authors derive cubic lower bounds in terms of $t$ (e.g., $\approx \frac{10t^3}{3(t+2)^2}$ ) and logarithmic upper bounds. Notably, for the number-of-runs function, a dedicated residue-class construction yields a tighter upper bound than the generic locally-bounded approach.
Locally Bounded Functions: For locally $(2, 2t)_{ID}$ functions, the redundancy is bounded between $t$ and $t+1$ . For locally $(3, 2t)_{ID}$ functions, the lower bound is $\lceil 3t/2 \rceil$ and the upper bound is $2t+2$ .

Significance and Claims
The paper claims that this work represents a substantial theoretical milestone by extending function-correcting codes beyond substitution-based metrics to the more challenging insertion-deletion metric. The significance lies in:

Addressing a Fundamental Gap: It resolves the issue of how to optimize redundancy when the underlying distance metric is non-additive across systematic splits, a problem that invalidates previous FCC methodologies.
Practical Relevance: The framework is motivated by applications in DNA data storage and document exchange, where insertions and deletions are dominant error types. In these scenarios, recovering only specific properties (like run-lengths or VT syndromes) rather than the full strand can significantly reduce synthesis costs and redundancy.
Theoretical Rigor: By establishing the necessity of the $r \geq k$ regime and providing Plotkin and Gilbert-Varshamov type bounds for irregular insdel-distance codes, the paper lays the groundwork for future code constructions and tighter performance limits in synchronization-error channels.

The authors conclude that while the framework is established, future work is needed to tighten closed-form upper bounds, characterize lower bounds for general locally bounded functions, and extend the theory to non-binary alphabets.