Uncertainty of Reconstruction with List-Decoding from Uniform-Tandem-Duplication Noise
arXiv:2001.07047 · doi:10.1109/TIT.2021.3070466
Abstract
We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with strings (where a previous paper considered ) in asymptotic terms, where code-words are taken from an error-correcting code. Thus, we find the trade-off between the design minimum distance, the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease coding redundancy, or the required number of reads, or both.
arXiv comment13 pages, no figures. Accepted version
References in corpus (4)
- Asymptotically Optimal Codes Correcting Fixed-Length Duplication Errors in DNA Storage Systems
- Capacity of DNA Data Embedding Under Substitution Mutations
- Reconstruction Codes for DNA Sequences with Uniform Tandem-Duplication Errors
- Single-Error Detection and Correction for Duplication and Substitution Channels