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:
- 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}$.
- 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.
- 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.
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.
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