Improved methods for generating quasi-Gray codes
From MaRDI portal
Publication:3569893
DOI10.1007/978-3-642-13731-0_22zbMATH Open1285.94125arXiv1010.0905OpenAlexW2128902682MaRDI QIDQ3569893FDOQ3569893
Authors: Prosenjit Bose, Paz Carmi, Dana Jansens, Anil Maheshwari, Pat Morin, Michiel Smid 
Publication date: 22 June 2010
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1010.0905
Recommendations
Cited In (8)
- Space-optimal quasi-Gray codes with logarithmic read complexity
- Integer representations towards efficient counting in the bit probe model
- A Survey of Data Structures in the Bitprobe Model
- Gray code compression
- Efficient coroutine generation of constrained Gray sequences
- A fast algorithm to generate Beckett-Gray codes
- Regular numeral systems for data structures
- Integer representations towards efficient counting in the bit probe model
This page was built for publication: Improved methods for generating quasi-Gray codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569893)
