Coding for Deletion Channels with Multiple Traces

Mahed Abroshan, Ramji Venkataramanan, Lara Dolecek, Albert Guillén i Fàbregas

Abstract

This paper presents an efficient coding scheme designed for the multiple-trace deletion channel, a model particularly relevant to DNA-based data storage. By partitioning codewords into blocks protected by Varshamov-Tenengolts (VT) codes, the proposed method leverages multiple noisy copies (traces) to resynchronize data and correct deletions. The scheme features linear encoding complexity and low-complexity decoding, achieving near-optimal rates for single-deletion correction per block.

Introduction

In emerging data storage technologies like DNA storage, the primary physical challenge is the occurrence of deletions rather than simple bit-flips. Deletions cause a loss of synchronization, making it difficult for a decoder to determine the original bit positions. DNA storage systems typically provide multiple "traces"—noisy reads of the same sequence. This research focuses on designing codes that specifically exploit these multiple traces to ensure reliable and efficient data reconstruction.

Proposed Coding Scheme

The authors propose a two-phase strategy for coding and decoding:

  1. Code Construction: The codeword is divided into blocks, each being a Varshamov-Tenengolts (VT) code. VT codes are classically known for their ability to correct a single deletion. These blocks are concatenated to form the final sequence, achieving a code rate of $R \approx 1 - \frac{\log n_b}{n_b}$.
  2. Decoding Phase 1 (Synchronization): The decoder identifies starting positions of blocks across all traces by calculating the VT "syndrome" (a mathematical fingerprint). If a block in a trace matches the expected syndrome, it is assumed to be deletion-free and used as an "anchor" to resynchronize other traces.
  3. Decoding Phase 2 (Correction): If all traces for a specific block contain at least one deletion (a "congested" block), the decoder seeks a trace with exactly one deletion. Since VT codes can correct a single deletion, the original block can be recovered from that trace.

The encoding complexity is $O(n)$, while decoding complexity scales as $O(t^2 k^2 n)$, where $n$ is length, $t$ is the number of traces, and $k$ is the number of deletions.

Performance Analysis

Numerical simulations demonstrate that the scheme's reliability improves significantly with the number of traces and the size of the alphabet.

Error probability vs. block length $n_b$ for binary ($q=2$) and quaternary ($q=4$) alphabets. Larger alphabets and longer blocks contribute to lower error rates.

As shown in Figure 1, the error probability decreases as the block length $n_b$ increases. This is because Phase 1 synchronization becomes more robust. Furthermore, the performance is markedly better for non-binary alphabets (e.g., $q=4$ for DNA bases), as the probability of a random sequence accidentally matching a syndrome is lower, making the "syndrome as anchor" strategy more robust.

Empirical error probability vs. number of traces $t$. The error probability decays exponentially as the number of available traces increases.

A key result is the exponential decay of the error probability with respect to the number of traces $t$, as illustrated in Figure 2. For a fixed number of deletions, increasing the number of traces from 2 to 8 can reduce the error probability by several orders of magnitude, validating the effectiveness of the multi-trace approach in overcoming deletion-induced synchronization loss.

Conclusion

The proposed VT-based block coding scheme offers a practical solution for the deletion channel in multi-trace scenarios. By using syndromes as anchors for synchronization, the method avoids the overhead of heavy marker sequences. Future work will focus on extending this model to handle insertions and substitutions, as well as developing codes capable of correcting multiple deletions per block.

Summary updated

BibTeX
@inproceedings{abroshan2019coding,
  author = {Mahed Abroshan and Ramji Venkataramanan and Lara Dolecek and Albert Guillén i Fàbregas},
  title = {{Coding for Deletion Channels with Multiple Traces}},
  booktitle = {ISIT},
  year = {2019},
  doi = {10.1109/isit.2019.8849647},
}
Figure