2024/11/12 by Himelfarb, Gabriel Sac, Schwartz, Moshe
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #H.1.1 #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2411.08233
We study skew-tolerant Gray codes, which are Gray codes in which changes in consecutive codewords occur in adjacent positions. We present the first construction of asymptotically non-vanishing skew-tolerant Gray codes, offering an exponential improvement over the known construction. We also provide linear-time encoding and decoding algorithms for our codes. Finally, we extend the definition to non-binary alphabets, and provide constructions of complete m-ary skew-tolerant Gray codes for every base m≥ 3.