Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Mutually Uncorrelated Codes for DNA Storage
event speaker icon
Maya Levy (M.Sc. Thesis Seminar)
event date icon
Thursday, 13.07.2017, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. E. Yaakobi
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 work 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. Then, we present an efficient algorithm for MU codes with linear encoding and decoding complexity. Next, we extend these results for (d_h; d_m)-MU codes that impose a minimum Hamming distance of d_h between different codewords and d_m between prefixes and suffixes. Particularly we show an efficient construction of these codes with nearly optimal redundancy. Lastly, we provide similar results for the edit distance and balanced MU codes.