Random Access Expectation in DNA Data Storage: Asymptotic Analysis Through Fountain Codes
Christoph Hofmeister, Rawad Bitar, Eitan Yaakobi
原文摘要
The expected number of coded symbols drawn from a linear code until a desired information symbol can be decoded is studied. This quantity is of interest in DNA data storage, where it is called the random access expectation. If the generator matrix of the code is binary and fully symmetric, the process of sampling symbols from the code is equivalent to the encoder of an LT code. Based on this observation, the random access expectation of binary fully symmetric codes under a peeling decoder is analyzed in the large blocklength limit. Asymptotically, a random access expectation, normalized by the number of information symbols, of $0.7869$ is achievable, while for a binary fully symmetric code under a peeling decoder it cannot be below $π/4\approx 0.7854$. The analysis is extended to the case where a set of information symbols needs to be decoded.
cs.IT