CS Paper Radar

Orthogonal SC-LDPC Codes for the IDS Channel

Frederik Walter, Jessica Bariffi, Antonia Wachter-Zeh

cs.IT ·submitted 2026-10-09 20:35 UTC · v1

Abstract

We propose a coding scheme for the insertion, deletion and substitution (IDS) channel tailored to the short strands of DNA-based data storage. Instead of an inner synchronisation code, a spatially coupled LDPC (SC-LDPC) code is placed across the strands, with its coupling axis aligned to the position along the strands. Every decoded position thus becomes an anchor to synchronise the neighbouring strands. The decoding waves of the SC-LDPC code carry these anchors from both ends of the strands towards the middle. We bound the achievable rate from above by the information rate of a single strand and from below by that of a separated receiver. For strands of 100 nucleotides (the relevant regime for DNA-based data storage), our scheme outperforms a rate-matched concatenated construction.

Closest papers

Nearest neighbours by meaning across the whole index.

Marker-Delimited Codes for Short-Blocklength, High-Rate Coding over Multi-Read Edit Channels

cs.IT ·2026-08-31 ·Sinan Ates Yercan, Marc Antonini, Serge Kas Hanna
published similarity 0.70
Abstract · 7 pages, 2 figures, This paper has been accepted in IEEE ITW'26

The read process of DNA-based data storage systems generates multiple noisy copies of the stored DNA sequences, affected by edit errors consisting of substitutions, deletions, and insertions. Motivated by the challenge of ensuring reliable data retrieval in the presence of edit errors, we present a concatenated coding scheme that accounts for practical design constraints in DNA storage. We introduce and apply the marker-delimited code (MDC) as the inner code, which enables fast and reliable computation of symbolwise a posteriori probabilities (APPs). We combine MDC with an outer LDPC code. The LDPC is decoded via belief propagation using the soft information generated by MDC. Our results show that, in comparison with prior work, this construction provides more efficient error correction over multi-read edit channels in the short-blocklength and high-rate regime.

0.27

Representing Information on DNA using Patterns Induced by Enzymatic Labeling

cs.IT ·2026-10-16 ·Daniella Bar-Lev, Eitan Yaakobi, Zohar Yakhini, Tuvi Etzion
published similarity 0.62
Abstract

Enzymatic DNA labeling is a powerful tool with applications in biochemistry, molecular biology, biotechnology, medical science, and genomic research. This paper contributes to the evolving field of DNA-based data storage by presenting a formal framework for modeling DNA labeling in strings, specifically tailored for data storage purposes. Our approach involves a known DNA molecule as a template for labeling, employing patterns induced by a set of designed labels to represent information. One hypothetical implementation can use CRISPR-Cas9 and gRNA reagents for labeling. Various aspects of the general labeling channel, including fixed-length labels, are explored, and upper bounds on the maximum size of the corresponding codes are given. The study includes the development of an efficient encoder-decoder pair that is proven to be optimal in terms of maximum code size under specific conditions. The codewords for this framework are codesets, i.e., each codeword is a collection of a few labels. Of special interest are codes whose codesets contain fixed-length labels. Their construction and analysis are tied to de Bruijn sequences and constrained coding.

0.54

MacKay-Neal Codes for DNA Channels under Block-MAP Decoding

cs.IT ·2026-10-28 ·Kenta Kasai
theory similarity 0.62
Abstract · 14 pages

We prove achievability below the symmetric information rate (SIR) under block maximum a posteriori (MAP) decoding for a fixed-degree MacKay-Neal (MN) socket ensemble on the quaternary insertion-deletion-substitution channel used to model DNA reads. For every integer $\ell\ge4$, the $(\ell,3,3)$ socket ensemble, with one transmitted bit fixed and an independent uniform known offset, has limiting rate $r_\star=6/\ell$ bits per stored nucleotide. If the joint SIR $J_t$ of a fixed number $t$ of reads under independent, uniformly distributed input nucleotides exceeds $r_\star$, the ensemble-average full extended-word block error is $O(1/n)$, and deterministic graph-offset sequences attain the same limiting rate and message-average error bound. This result concerns the discrete rate family $6/\ell$, not arbitrary rates approaching a given SIR. The channel permits arbitrarily many insertions and unbounded drift, with no alignment supplied to the receiver. The proof combines established MN parity and distance estimates with a strict arbitrary-candidate-list bound and a list construction that accounts for hidden output boundaries.

0.26

The Unified Evaluation App for DNA Data Storage Codecs

cs.ET cs.SE ·2026-08-10 ·Aleksandar Anžel, Chisom Anyabolu, Leon Wimbes, Luca Staus, Ihsan Tri Heldian +10 more
code/data similarity 0.61
Abstract · 38 pages, 12 figures

Background: Deoxyribonucleic acid (DNA) data storage is a paradigm with great potential for ultra-dense and durable information preservation. However, the rapid proliferation of coding schemes, or codecs, each with their own design constraints and reporting practices, has led to a fragmented landscape that lacks a standardized comparative assessment. Methods: We developed an open-source, modular benchmarking platform that systematically integrates and evaluates state-of-the-art DNA storage encoding and decoding methods (codecs). Our approach uses a curated, diverse set of baseline data and applies multidimensional assessment criteria that are aligned with the consensus standard of the DNA Data Storage Alliance. These criteria include encoding/decoding throughput, computational efficiency, error correction performance across substitutions, insertions, and deletions, and cost efficiency. Results: The developed platform integrates standardized wrapper functions for encoding and decoding, allows for the integration of new methods, and automates reproducible evaluations with comprehensive visual and tabular reporting. Benchmarking both contemporary and classical codecs using their default parameters and multiple metrics demonstrates that no single algorithm is optimal across all evaluated dimensions. The trade-offs between information density, success rate, runtime, and cost are quantified and shown to be critical factors in the design of future-proof formats. Conclusions: Our work establishes a rigorously standardized, open-source evaluation framework that enables reproducible benchmarking, supports evidence-based codec selection, and provides the necessary foundation for translating DNA data storage from experimental research into deployable archival systems.

0.26

One Burst of t-Deletion and One Burst of t-Substitution Error-Correcting Codes

cs.IT ·2026-08-25 ·Yajuan Liu, Han Cai, Tolga M. Duman
published similarity 0.60
Abstract

Synchronization errors, including insertions, deletions, and substitutions, may occur in bursts in communication systems such as DNA data storage, file synchronization, and magnetic recording. In this paper, we study an error model con?sisting of one burst of t-deletions and one burst of t-substitutions. By reformulating the original sequence into a matrix form, we propose an explicit construction of error-correcting codes capable of correcting one burst of t-deletions and one burst of t-substitutions with O(log n) redundancy.

0.57

Data Protection in Function-Correcting Symbol-Pair Codes: Redundancy Bounds and Protection Profiles

cs.IT ·2026-09-10 ·Anamika Singh, Abhay Kumar Singh
similarity 0.58
Abstract

In several storage systems, including DNA storage and flash memory, errors affect neighbouring symbols jointly, and the Hamming metric does not adequately capture such error patterns. The symbol-pair read channel, introduced by Cassuto and Blaum~\cite{cassuto2011codes}, addresses this by reading consecutive pairs of symbols rather than individual symbols. Motivated by this, we introduce function-correcting symbol-pair codes with data protection (FCSPC-DP), which guarantee reliable recovery of a desired function of the message while simultaneously protecting the message itself against symbol-pair errors. We derive bounds on the optimal redundancy of such codes and establish a relationship with joint-pair distance matrices. We also give explicit constructions of FCSPC-DP for locally pair-bounded functions and symbol-pair weight functions. We introduce the pair-separation constant of a function, the minimum symbol-pair distance between messages sharing a function value, and show that when it is sufficiently large, data protection requires no additional redundancy: the optimal redundancy coincides with that of the corresponding code without data protection. Considering the symbol-pair analogue of the $α$-distance graph, we introduce two code invariants, the generation profile and the disconnection threshold, and use them to characterise a code's protection properties. Relating the two metrics through these invariants yields upper and lower bounds on the symbol-pair threshold in terms of its Hamming counterpart, both of which are attained. We further extend the classical Plotkin and sphere-packing bounds to this setting.

0.27

Analysis and Design of Spatially Coupled LDPC Codes for Pulsed-Jamming-Resilient Space Telemetry

cs.IT ·2026-11-16 ·Massimo Battaglioni, Mauro M. M. Costantino, Rebecca Giuliani, Franco Chiaraluce, Marco Baldi
theory similarity 0.57
Abstract

Jamming is a major threat to space telemetry downlinks, which operate under severe power and bandwidth constraints. This paper develops a jamming-aware analysis and design framework for protograph-based spatially coupled low-density parity-check (SC-LDPC) codes. For pulsed jamming with jamming state information (JSI) at the receiver, we derive a two-state protograph-based extrinsic information transfer (PEXIT) recursion that tracks the messages originating from clean and jammed symbols separately and merges them at the check nodes through a mutual-information-matched Gaussian approximation. For non-interleaved pulsed jamming, we map each pulse realization, through the serialization of the lifted codeword, to a profile of jammed fractions over the variable-node types, and we prove that, under random lifting, this profile determines the local channel-state statistics. The resulting position-dependent thresholds are the objective of a constrained differential-evolution search over protographs, coupling memories, and edge spreadings. At different code rates, the designed ensembles are compared with the Consultative Committee for Space Data Systems (CCSDS) accumulate, repeat-by-4, and jagged accumulate (AR4JA) LDPC codes whose block length matches the SC-LDPC constraint length, with longer AR4JA codes whose block length is comparable with the size of the sliding window decoder, and with non-optimized SC-LDPC codes. Under pulsed jamming with random pulse positions and with JSI, the ensembles designed over random pulse realizations, decoded through sliding window decoding, reach a bit error rate of $10^{-4}$ at lower signal-to-noise ratios than all the benchmarks.

0.37

Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes

cs.IT ·2026-10-05 ·Roee Gross, Yitzchak Grunbaum, Matteo Bertuzzo, Eitan Yaakobi, Alberto Ravagnani
benchmarkhot direction similarity 0.56
Abstract

DNA storage systems retrieve information by randomly sampling synthesized DNA strands, making the number of reads required for successful recovery a fundamental performance measure. This motivates the coverage depth problem: for given code parameters, determine a linear code that minimizes the expected number of randomly sampled columns required to span the entire information space. While MDS codes are known to be optimal whenever they exist, identifying optimal codes in parameter regimes where MDS codes do not exist remains largely open. In this work, we derive a general formula for the expectation in the coverage depth setting, and apply this result to establish the optimality of the $q$-ary simplex code for the parameters that allow its existence. Moreover, we show the optimality of the $q$-ary Hamming code by relating coverage depth to independent sets in the dual code and exploiting log-concavity properties of matroid basis-generating polynomials. We further analyze random linear codes, derive an exact expression for their expected coverage depth, and show that, in the constant-rate regime, their additive gap from the MDS benchmark remains bounded independently of the code length.

0.44