2010/10/05 by Dana Jansens, Prosenjit Bose, Jansens, Dana +9
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #DNA and Biological Computing #cs.DM
paper · pdf · doi:10.48550/arxiv.1010.0905
Masters Thesis. A conference version appeared in the proceedings of SWAT 2010
arxiv created 2010/10/05 · arxiv updated 2010/10/06
Consider a sequence of bit strings of length d, such that each string differs from the next in a constant number of bits. We call this sequence a quasi-Gray code. We examine the problem of efficiently generating such codes, by considering the number of bits read and written at each generating step, the average number of bits read while generating the entire code, and the number of strings generated in the code. Our results give a trade-off between these constraints, and present algorithms that do less work on average than previous results, and that increase the number of bit strings generated.