Mutually Uncorrelated Codes for DNA Storage
- 1 October 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (6) , 3671-3691
Abstract
Mutually uncorrelated (MU) codes are a class of codes in which no proper prefix of one codeword is a suffix of another codeword. These codes were originally studied for synchronization purposes and recently, Yazdi et al. showed their applicability to enable random access in DNA storage. In this paper,we follow the research of Yazdi et al. and study MU codes along with their extensions to correct errors and balanced codes. We first review a well-known construction of MU codes and study the asymptotic behavior of its cardinality. This task is accomplished by studying a special class of run-length limited codes that impose the longest run of zeros to be at most some function of the codewords length. We also present an efficient algorithm for this class of constrained codes and show how to use this analysis for MU codes. Next, we extend the results on the run-length limited codes in order to study (d h , d m )-MU codes that impose a minimum Hamming distance of dh between different codewords and d m between prefixes and suffixes. In particular, we show an efficient construction of these codes with nearly optimal redundancy. We also provide similar results for the edit distance and balanced MU codes. Last, we draw connections to the problems of comma-free and prefix synchronized codes.Keywords
Funding Information
- Israel Science Foundation (1624/14)
This publication has 26 references indexed in Scilit:
- Prefix partitioned gray codes for particular cross-bifix-free setsCryptography and Communications, 2014
- Next-Generation Digital Information Storage in DNAScience, 2012
- Combinatorial problems motivated by comma‐free codesJournal of Combinatorial Designs, 2004
- Systematic encoding of the Varshamov-Tenengol'ts codes and the Constantin-Rao codesIEEE Transactions on Information Theory, 1998
- Efficient balanced codesIEEE Transactions on Information Theory, 1986
- Nonbinary codes, correcting single deletion or insertion (Corresp.)IEEE Transactions on Information Theory, 1984
- On the construction of comma-free codesIEEE Transactions on Information Theory, 1965
- Fibonacci codes for synchronization controlIEEE Transactions on Information Theory, 1965
- Synchronization of binary messagesIEEE Transactions on Information Theory, 1960
- Comma-Free CodesCanadian Journal of Mathematics, 1958